|Parsing wars email@example.com (1992-08-31)|
|Re: Parsing wars firstname.lastname@example.org (1992-09-01)|
|Re: Parsing wars email@example.com (1992-09-02)|
|Re: Parsing wars firstname.lastname@example.org.OZ.AU (1992-09-02)|
|Re: Parsing wars email@example.com (1992-09-03)|
|Re: Parsing wars jar@cheops.HQ.Ileaf.COM (1992-09-05)|
|Re: Parsing wars firstname.lastname@example.org (1992-09-08)|
|Re: Parsing wars email@example.com (1992-09-09)|
|[2 later articles]|
|From:||firstname.lastname@example.org (Jonathan Eifrig)|
|Organization:||The Johns Hopkins University CS Department|
|Date:||Tue, 1 Sep 1992 17:07:19 GMT|
>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
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 (email@example.com) The Johns Hopkins University, C.S. Dept.
Return to the
Search the comp.compilers archives again.