Parsing wars

dww@inf.fu-berlin.de
Mon, 31 Aug 1992 16:13:40 GMT

          From comp.compilers

Related articles
Parsing wars dww@inf.fu-berlin.de (1992-08-31)
Re: Parsing wars eifrig@beanworld.cs.jhu.edu (1992-09-01)
Re: Parsing wars horst@techfak.uni-bielefeld.de (1992-09-02)
Re: Parsing wars bromage@mullauna.cs.mu.OZ.AU (1992-09-02)
Re: Parsing wars bburshte@pyramid.com (1992-09-03)
Re: Parsing wars jar@cheops.HQ.Ileaf.COM (1992-09-05)
Re: Parsing wars dww@inf.fu-berlin.de (1992-09-08)
[3 later articles]
| List of all articles for this month |

Newsgroups: comp.compilers
From: dww@inf.fu-berlin.de
Organization: Free University of Berlin
Date: Mon, 31 Aug 1992 16:13:40 GMT
Keywords: parse, LR(1), question, comment

I have encountered a parsing method that I do not understand. Perhaps it's
just some sort of fancy technique, maybe I overlooked something. If
someone can either tell me how this works or else state <rtfm,book,topic>
I would be grateful.


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.


My question: how and why does this work? What does it buy me? (Is it
extremely efficient? Use compact tables? Wrong?)


Thanks for any clues!
--
Debora Weber-Wulff dww@inf.fu-berlin.de
Institut fuer Informatik +49 30 89691 124
Nestorstr. 8-9, D-W-1000 Berlin 31
[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]
--


Post a followup to this message

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