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

Chris Clark USG <>
20 Jan 1998 23:51:45 -0500

          From comp.compilers

Related articles
LL(2) always factorable to LL(1)? (Andrew M. Duncan) (1998-01-17)
Re: LL(2) always factorable to LL(1)? (Chris Clark USG) (1998-01-20)
Re: LL(2) always factorable to LL(1)? (1998-01-21)
Re: LL(2) always factorable to LL(1)? (1998-01-23)
Re: LL(2) always factorable to LL(1)? (Chris F Clark) (1998-01-23)
Re: LL(2) always factorable to LL(1)? (Terence Parr) (1998-01-23)
Re: LL(2) always factorable to LL(1)? (Scott Stanchfield) (1998-01-24)
Re: LL(2) always factorable to LL(1)? (Terence Parr) (1998-02-01)
| List of all articles for this month |

From: Chris Clark USG <>
Newsgroups: comp.compilers
Date: 20 Jan 1998 23:51:45 -0500
Organization: Digital Equipment Corporation - Marlboro, MA
References: 98-01-071
Keywords: parse, 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

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:
3 Proctor St.
Hopkinton, MA 01748 phone: (508) 435-5016
USA 24hr fax: (508) 435-4847

Post a followup to this message

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