Re: Parsing wars

In article 92-09-006, 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.




In the traditional Aho-Sethi-Ullman-parser (p.219) there is an implicit
shift appended to every reduce. This is some kind of partial evaluation
because it is not always possible to write things back to your input.




> [It sounds to me like a way to combine the shift and goto tables, since
> pushing the nonterminal and then shifting it would be equivalent to a
> goto. -John]




Exactly this is the case. Terminal symbols and nonterminal symbols are
not distinguished. The goto table is merged into the action table such
that "goto[s,A]=i" becomes "action[s,A]=shift i". This can make things
easier.


Now you can have terminal symbols as well as nonterminals in the input,
which is needed for example in program transformation systems.
Consider the rule:
        EVAL(E:expr "+" "0") => EVAL(E)
The the parser's input for the lhs would be:
        expr "+" "0"
This would be impossible to parse with a traditional shift-reduce parser.


I have done this (as well as other things) in my masters thesis in 1988/89
and it works very well but I reinvented the wheel. I once saw an article
on exactly this topic but I forgot the reference.


Horst Hogenkamp
--

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