13 Oct 2001 23:11:17 -0400

Related articles |
---|

LL(1) vs. LR(1) willverine@hotpop.com (Will) (2001-10-12) |

Re: LL(1) vs. LR(1) gzw@home.com (Geoff Wozniak) (2001-10-13) |

Re: LL(1) vs. LR(1) joachim_d@gmx.de (Joachim Durchholz) (2001-10-13) |

Re: LL(1) vs. LR(1) cfc@world.std.com (Chris F Clark) (2001-10-13) |

From: | "Joachim Durchholz" <joachim_d@gmx.de> |

Newsgroups: | comp.compilers |

Date: | 13 Oct 2001 23:11:17 -0400 |

Organization: | Compilers Central |

References: | 01-10-042 |

Keywords: | parse |

Posted-Date: | 13 Oct 2001 23:11:16 EDT |

Will <willverine@hotpop.com> wrote:

*> I was told that LR(1) parsers are much more powerful than the LL(1)*

*> parsers because they recognize more grammars. [...]*

*> Can anyone give me a grammar that is in LR(1) but not in*

*> LL(1)? [...]*

*> Due to backtracking, LL(1) may end up being exhaustive in that*

*> it may backtrack to the point that it reaches the last production*

*> in which it will try to apply.*

I always thought that LL parsing does not backtrack. You just select

the production based on the first input symbol that you see (and the

restrictions that make a grammar LL(1) make sure that only the right

production will match).

Are you considering a backtracking extension to LL(1)? If that is the

case, could you define the extension? (Note that any extension was

probably considered years ago and already has a standard name.)

Here's a (silly) grammar that's LR(1) but not LL(1):

S ::= A B

A ::= x

B ::= x

Since LL does not remember previous states, it will not know that the

first x should reduce to A and the second x should reduce to B. LR uses

the left context to distinguish the two cases.

LL(1) plus backtracking would handle this just fine, of course. A

grammar that's LR(1) but not LL(1)-with-backtracking would need some

infinities, but since the input string is finite the LL backtracker will

(sooner or later) find those productions that were selected by the LR

parser, so my guess is that LL(1)-with-backtracking is at least as

powerful as LR(1). The complexity could easily be exponential though.

The order in which alternatives to productions are tried is important

though, and it may well be that a depth-first search will terminate in

less cases than a breadth-first search (though it's dubious wether LL is

still an appropriate name if the latter technique is used).

*> However, the LR(1) algorithms for*

*> producing the parsing table also seems to be exponential.*

Yes it is.

Essentially, the LR table generation algorithm creates a lot of DFAs,

and since constructing a DFA has exponential worst-case complexity, LR

generation must be exponential.

There is an important difference though: LL(1)-with-backtracking is

slow (possibly exponential) during parsing, while LR table generation

is slow only during table construction. LR parsing is linear with

input length (as is LL(1) parsing without backtracking).

*> P.S. - Where can I find a complete FAQ on basic compiler theory? The*

*> only FAQ I found is this: http://www.faqs.org/faqs/compilers/, and it*

*> does not have any discussion on theory.*

The usual source is the "Dragon Book" (sorry, no reference handy). It

covers the basic techniques (operator precedence, LL(1), LR(1),

SLR(1), LALR(1)) and their comparative advantages and disadvantages

quite extensively. However, understanding the algorithms is more work

than simply implementing them, and it's a bit outdated in its

assumptions (memory efficiency is more strongly stressed than today's

computers would require).

Regards,

Joachim

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.