Re: Parsing wars (Jonathan Eifrig)
Tue, 1 Sep 1992 17:07:19 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)
[2 later articles]
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Jonathan Eifrig)
Organization: The Johns Hopkins University CS Department
Date: Tue, 1 Sep 1992 17:07:19 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 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 ( The Johns Hopkins University, C.S. Dept.

Post a followup to this message

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