Re: Parsing wars

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 comp.compilers page.
Search the comp.compilers archives again.