Sat, 28 Jun 2008 11:43:39 -0500

From: | Max Hailperin <max@gustavus.edu> |

Newsgroups: | comp.compilers |

Date: | Sat, 28 Jun 2008 11:43:39 -0500 |

Organization: | Compilers Central |

References: | 08-06-053 08-06-055 08-06-061 08-06-071 |

Keywords: | parse |

Posted-Date: | 28 Jun 2008 14:42:34 EDT |

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.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.