Re: Parsing wars

dww@inf.fu-berlin.de 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)
states.


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).


bromage@mullauna.cs.mu.oz.au
--

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