Re: Parsing wars

bruce@harry.ugcs.caltech.edu (Bruce J Bell)
Wed, 9 Sep 1992 00:46:52 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)
Re: Parsing wars bruce@harry.ugcs.caltech.edu (1992-09-09)
Re: Parsing wars mickunas@m.cs.uiuc.edu (1992-09-10)
Re: Parsing wars bburshte@pyramid.com (1992-09-13)
| List of all articles for this month |

Newsgroups: comp.compilers
From: bruce@harry.ugcs.caltech.edu (Bruce J Bell)
Organization: California Institute of Technology, Pasadena
Date: Wed, 9 Sep 1992 00:46:52 GMT
References: 92-09-006 92-09-043
Keywords: parse, LR(1)

jar@cheops.HQ.Ileaf.COM (Jim Roskind x5570) writes:


( about a stack-based parser that puts reduced nonterminals back on the input,
    instead of on the stack )


>The conseqeunces of this extension are quite significant, and the
>resulting parser engine provides a much larger class of parsers than LR
>parsers. Clearly all LR parsers are a subset of the above parsers, as
>doing the above "strange reduce" followed by a "shift" is identical to
>doing a classical LR engine "reduce."


>To see the weirdness of this extension, it can be noted that you can build
>an N pass parser using the above mechanisms. Certainly parsing is not
>restricted to Left to right, Right most derivation. ...


If you allow "single-reductions", this parser sounds an awful lot like a
Turing machine, but if you require that all reductions convert more than
one symbol to a nonterminal, you have a parser that is less powerful than
a Turing machine, but still more powerful than an LR parser. Either way,
I have heard this kind of parser referred to as a "two-stack parser",
since the "strange reduce" treats the input as a stack which is
initialized with the program text on it.


Also, if there are no single-reductions, you are guaranteed that the parse
takes time proportional to the length of the input string, while a 2-stack
parser with single-reductions could conceivably take a great deal of time,
or just enter an infinite loop...


I have looked into this class of parser as possibly being powerful enough
to integrate lexing into the parser. I doubt it would improve efficiency
much, but the idea of putting the entire front end into a single
conceptual framework has its appeal.


Bruce J. Bell
--


Post a followup to this message

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