# Whats Wrong with this LL(1) Grammar?

I am trying to build a LL(1) parse table for the following Grammar:

S -> L
L -> L : L
L -> id R
R -> ( L )
R -> ( )
R -> Epsilon

There are two Problems here. First the L rules are a left recursion and the R rules have ( as the same prefix. So I modified the Grammar to this one:

S -> L
L -> id R X
X -> : L X
X -> Epsilon
R -> ( P
R -> Epsilon
P -> L )
P -> )

I then checked the Grammar with the JFLAP Tool and it says that my grammar is not LL(1). But I just don't see the Problem.

Can somebody help me out here?

regards Alex

Your original grammar is ambiguous:

L → L : L
L → id R


Suppose we have id : id : id. (For simplicity, I'm just letting R derive the empty string, but any valid derivation of the Rs would end up with the same ambiguity.) That needs to be derived from S → L → L1 : L2, but from there, either L1 or L2 can derive L : L. In effect, the two cases correspond to : associating to the left or associating to the right, but with longer sequences of :-separated id R clauses, the number of possible parses increases exponentially.

Your rewrite does not eliminate this ambiguity, it just makes it harder to see.

In short, you need to decide how : associates. It probably makes most sense for it to associate to the left, but an LL grammar really only handles right-association. (That's not a huge problem since you can reassociate the AST easily enough, but with an LR parser generator you wouldn't have to do any of this.) If we rewrite L as right-associative, we automatically eliminate the left-recursion problem:

S  → L
L  → L'
L  → L' : L
L' → id R


(Really, L' is not very useful in this case; it would have been almost as simple to write L → id R | id R L. But in either case, you end up needing to factor out the common prefix.)

• Hi rici. Thanks for your answer. I understand you wrote and entered it into Jflap, but it still says that the grammar is not LL(1). is the tool reliable? – AdelPoint Aug 30 '15 at 14:21
• @adelpoint: actually, i did not try it with any tool. So I might have missed another problem. – rici Aug 30 '15 at 14:58
• Thanks anyway. It helped me understand the Problem better :) – AdelPoint Aug 30 '15 at 15:26
• @AdelPoint: Looking at it, I realize that my change introduces another shared prefix which needs to be factored out. I really don't see the point to LL grammar generators, personally; excellent LR generators are available and IMHO you don't need to think nearly as hard about grammars to write an LR-parseable grammar. YMMV. – rici Aug 30 '15 at 21:54