Re: LL(1) vs. LR(1)

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

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