|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)|
|Re: Parsing wars firstname.lastname@example.org (1992-09-10)|
|Re: Parsing wars email@example.com (1992-09-13)|
|From:||firstname.lastname@example.org (Bruce J Bell)|
|Organization:||California Institute of Technology, Pasadena|
|Date:||Wed, 9 Sep 1992 00:46:52 GMT|
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
Return to the
Search the comp.compilers archives again.