Re: Parsing wars (Andrew Bromage)
Wed, 2 Sep 1992 23:37:24 GMT

          From comp.compilers

Related articles
Parsing wars (1992-08-31)
Re: Parsing wars (1992-09-01)
Re: Parsing wars (1992-09-02)
Re: Parsing wars (1992-09-02)
Re: Parsing wars (1992-09-03)
Re: Parsing wars jar@cheops.HQ.Ileaf.COM (1992-09-05)
Re: Parsing wars (1992-09-08)
Re: Parsing wars (1992-09-09)
Re: Parsing wars (1992-09-10)
Re: Parsing wars (1992-09-13)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Andrew Bromage)
Organization: Computer Science, University of Melbourne, Australia
Date: Wed, 2 Sep 1992 23:37:24 GMT
References: 92-09-006
Keywords: parse, LR(1) writes:
>The parsing is called shift-reduce parsing, and I thought I had understood
>that. What happens on a reduction though is, instead of pushing the
>nonterminal of the lhs of the reduced production onto a symbol stack and
>digging through the goto table for the appropriate state to push onto the
>state stack, the nonterminal is *prepended* to the input sequence of
>tokens and parsing resumes as normal. The other actions, shift, accept and
>error are as expected, an action shiftreduce combines the normal shift and
>the strange reduce.

The action "shiftreduce" has been used for years to optimise LR(0) states
in LALR(1) parsers. The idea is to first create default actions, and then
for any state in which the default action is to reduce, change this to a
"shiftreduce". The benefit of this is that the LALR lookahead set is only
really used in the final parser when a shift-reduce conflict would
otherwise arise. It also helps in the removal of unit productions.
(Apparently. I've never seen it used this way - someone told me about
this). However, the size of the tables are reduced considerably - as most
grammars which people write produce parsers which largely consist of LR(0)

Pushing nonterminals onto the token stream, however, is a new one to me.
I suppose that this would optimise the GOTO tables a bit, but there are
better ways of doing this, like creating distinct reduce and lookahead
states (IMHO).

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.