NetNews Usenet Archive 1992 #20/NN_1992_20.iso/spool/comp/compiler/1524

Internet Message Format | 1992-09-08 | 2.8 KB

Path: sparky!uunet!gatech!rutgers!faatcrl!iecc!compilers-sender
From: [e-mail] (Jim Roskind x5570)
Newsgroups: comp.compilers
Subject: Re: Parsing wars
Keywords: parse, LR(1)
Message-ID: <[e-mail]>
Date: 5 Sep 92 16:54:36 GMT
References: <[e-mail]>
Sender: [e-mail]
Reply-To: [e-mail] (Jim Roskind x5570)
Organization: Compilers Central
Lines: 44
Approved: [e-mail]

[e-mail] writes:
> 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.

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.

Mind you, I have no real idea as to how to specify such parsers, or how to
build the transition tables that I indicate can be built.  For a given
grammar, the big loss is that there is no longer a cannonical parsing
order, such as is specified with LR parsers.  If you restrict the
transition table so that you must have a "shift" after every "strange
reduce,", then you have exactly an LR parsing engine.

Oh well, it is interesting, but I'm not sure what the use is.  It would be
more interesting if a clear class of parsers could be specified, and these
parsers required the "strange reduce" to be implemented.

Jim Roskind-   Author of a YACCable C++ grammar
Independent Consultant
[phone] or [phone] x5570
[e-mail] or ...!uunet!leafusa!jar
--
Send compilers articles to [e-mail] or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.