Why is the following grammar not LL(1)

Question

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?

Answer 1

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

Check the following for more information:

• LL parser: https://en.wikipedia.org/wiki/LL_parser
• Left recursion: https://en.wikipedia.org/wiki/Left_recursion
• CFG checker (including LL(1)): http://smlweb.cpsc.ucalgary.ca/