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 Moderator adds:


>[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]


It's also a cheesy way of saving the parse tree. Since nothing is
ever popped off of the parsing stack, the result of parsing is just the
input annotated with special non-terminal symbols. This is basically the
parse tree written out by either a pre- or post-order traversal, depending
on whether you look at the stack from either the top or the bottom.


There are better ways of making a parse tree, of course, since
this method gives one that is (1) difficult to traverse and (2) reflects
the _concrete_ rather than the _abstract_ syntax of the language, which is
usually more useful. It is, however, relatively space efficient, the
entire stack being only a (small) constant factor larger than the input.
So it could be useful for some things, like printing error messages
including the offending portion of the input.
--
Jack Eifrig (eifrig@cs.jhu.edu) The Johns Hopkins University, C.S. Dept.
--

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