# Why is the following grammar not LL(1)

Consider the following grammar:

S → bAb
| bBa
A → aS
| CB
B → b
| Bc
C → c
| cC


I have to provide the reasons as to why this grammar is not LL(1). So far all I can think of is that the grammar is not left factored given the productions:

S → bAb
| bBa


But I am also wondering if the grammar is left recursive due to the productions:

B → b
| Bc


Options provided are:

• This grammar has left recursion. (Unsure)
• This grammar has right recursion. (Would not make grammar not LL(1))
• This grammar is ambiguous. (Unsure)
• This grammar is not left factored. (Correct)
• This grammar can produce infinitely many distinct strings. (This shouldn't affect a grammar right?)

As far as I can tell, the grammar is not ambiguous, I have tried 3 different inputs and all have resulted in a single parse tree. So is this grammar not LL(1) just because of the lack of left factoring? or also because the grammar is left recursive?

• What is the definition of left-recursive?
– rici
Jul 5 '20 at 18:11

LL(1) grammars must be unambiguous, have no left recursion, and no conflicts.

The grammar you provide is unambiguous in terms of the syntax tree, however there are conflicts when parsing (which stops it from being an LL(1) grammar). The conflicts reside in the first set of S and C. That is to say, FIRST(S) = { b }, but its ambiguous in which production rule to apply: S -> bAb or S -> bBa. This can be eliminated by factoring out the b as such:

S  -> b S'
S' -> A b | B a


Similarly for C:

C  -> c C'
C' -> c C' | eps


The grammar also has left recursion in the rule B -> Bc; this is the definition of left recursion. This can be removed as such:

B   -> b B'
B'  -> c B' | B''
B'' -> c


• Correct. Those are direct left and right recursive rules. You also have to watch for indirect recursion, e.g. A -> B x and B -> A y (this is an instance of indirect left recursion). Jul 6 '20 at 17:48