Re: LL(2) always factorable to LL(1)?

> I'm TA-ing a compilers course, and am looking for some good examples
> of (for example) languages that are intrinsically LL(0,1,2) and same
> for LR. It's clear that some languages can be expressed in an LL(2)
> grammar, but the grammar can be further factored. For example:
>
> S -> id "=" Expr | id "(" Params ")"
>
> is LL(2) but can be factored to
>
> S -> id rest
> rest -> "=" E | "(" Params ")"
>
>Is this always possible?


The theoretical answer is yes. Any LR(k) language is also an LL(1)
language. Of course, we may not have the LL(1) grammar for that
language.


However, as Terrance Parr rightly often points out, the same is not
true once you add semantic actions. The proof of this was shown long
ago in a paper by Ben Brogsol. This is the argument for k>1 parser
generators. The point is that you cannot factor across action code,
at least not distinct action code.


Thus, an LL(2) only grammar is (where {x} represents semantic actions):


S -> id {1} "=" Expr | id {2} "(" Params ")"


I think an LR(1) only grammar is:


S -> X ";" | Y "."
X -> id {1} | X ";" id {1}
Y -> id {2} | Y "." id {2}


In both cases, the problem is that the semantic action depends upon
the lookahead. In the LL(2) case, the lookahead is contained in the
same rule. In the LR(1) case, the lookahead comes from the contextual
rule. That captures the essential difference between LL and LR
parsing. In LR parsing, you don't have to make your parsing decision
on which rule to apply until you have looked at the trailing context
(i.e. the tokens which come from the rule which calls your rule).


Of course, these examples are quite simple and it is easy to see how
to delay the actions until the appropriate tokens have been
recognized. In real-life, the problem is not always quite as simple.
However, generally someone can figure out how to get an LL(1) grammar
for any language. It's just a matter of effort. The only question is
how much more complicated is the LL(1) grammar than its related LL(k)
or LR(k) cousin and which would you rather deal with.


-Chris Clark
************************************************************************
Compiler Resources, Inc. email: compres@world.std.com
3 Proctor St. http://world.std.com/~compres
Hopkinton, MA 01748 phone: (508) 435-5016
USA 24hr fax: (508) 435-4847
--

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