Re: predictive parsing and non-recursive predictive parsing

kamal <kamalpr@hp.com> writes:


> Will RDP shift in case of shift/reduce conflict the way yacc does?


A recursive descent parser doesn't ever shift. A recursive descent
parser is a top-down parser, which I have previously termed a
"confirm/expand" parser by analogy with the conventional description
of bottom-up parsers as "shift/reduce" parsers. See
http://compilers.iecc.com/comparch/article/06-04-136


> So, whats the advantage of opting for a rightmost derivation? I think
> it helps when you have left-recrusive rules like
> E->ET
>
> where E and T are non-terminals.


Yes, one advantage is that LR parsers can handle left recursion.


However, that isn't the only advantage. The fundamental advantage is
that the reduce action in a shift/reduce parser takes place once the
parser has already read in the production's entire yield plus the
lookahead beyond it (one more terminal, most commonly), whereas the
expand action in a confirm/expand parser has to take place much
earlier, when only first little bit of the yield has been seen as the
lookahead (again, typically just one terminal). Consider for example
the following situation:


A -> B c
A -> D e


In an LR parser, there will never be a reduce-reduce conflict here,
because by the time the reduction to A is happening, the input has
been read in all the way through the c or e, and hence depending on
which of them was read, it is clear whether to reduce by the first
production or the second.


In fact, given that there is some lookahead, the LR parser can do even
more. Suppose we complete the grammar with


B -> f f f f f
D -> f f f f f


The LR parser will know whether to reduce the 5 repetitions of the
terminal f to B or to D, because it will have seen not only all 5 of
them, but also a lookahead symbol. If that lookahead symbol is c,
then the 5 fs are reduced to B. (And then after shifting the c, B c
is reduced to A.) If the lookahead symbol is e, then the 5 fs are
reduced instead to D. (And then after shifting the e, D e is reduced
to A.)


Contrast this to the situation of an LL(1) parser (including a
predictive recursive descent parser). Right away when it sees the
first f, it needs to choose between the two productions for A, which
it can't possibly do.


This particular grammar is LR(1) but not LL(1), LL(2), LL(3), LL(4),
or LL(5). It is LL(6), because 6 symbols of lookahead would be enough
to get past the 5 fs and to the c or e. But consider replacing the
definitions of B and D with right-recursive ones that can yield
arbitrarily many fs. Then you've got a grammar that isn't LL(k) for
any k, yet is LR(1). And it still doesn't involve left-recursion.


Conversely, any grammar that is LR(k) is LL(k). So LR parsing is
strictly more powerful, and this is true even if one rules out
left-recursion.

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