Re: Parsing wars

jar@cheops.HQ.Ileaf.COM (Jim Roskind x5570) writes [about "strange parsing"]


>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. To see how to make an
>N pass (trivial) parser using the above engine, you simply have to note
>that a series of "strange reduces" (re: which put stuff back into the
>input queue) can be used at any point to "back up" into the current stack.
>To be fair about this, you have to provide trivial reductions that have a
>right hand side of length 1, and provided new non-terminal names for the
>"popped" entries on the stack.


Oh yes, with backing up it seems you could parse a lot more languages
like a^n b^n c^n (rough sketch: shift all the "a"'s over, then all the
"b"'s. When we reach a "c", delete it, shovel the "b"'s - or a non-terminal
representing them - back into the input, when an "a" or a non-terminal
representing it turns up on the input, delete it and the "b" that should now
be the first element of the "input". Now shovel the "b"'s back on the stack
until we find another "c" and repeat. If they all are gone, we've recognized
the word. Only a^n b^n c^n will be accepted, because we manage to delete an
"a", a "b" and a "c" together.). You might need productions like
? -> ? to strange-reduce whatever is on the top of the stack to the input,
or you could even have terminal symbols on the left hand side of a production.
The trick would be how to specify all this and produce an appropriate table.


It might be rather difficult :-) to prove the termination of this parsing
algorithm, but it seems to be an interesting idea. Has anyone ever seen
something like this described? Pointers, please!


--
Debora Weber-Wulff dww@inf.fu-berlin.de
Institut fuer Informatik +49 30 89691 124
Nestorstr. 8-9
D-W-1000 Berlin 31
--

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