1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What is the definition of left-recursive? $\endgroup$ – rici Jul 5 at 18:11
0
$\begingroup$

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:

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks! that makes sense, and the CFG checker is quite helpful too :) I'm wondering about the productions for B and C, it seems like B is left recursive but C is right recursive, is that a correct observation? $\endgroup$ – odra Jul 6 at 16:25
  • $\begingroup$ 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). $\endgroup$ – Tyler Jul 6 at 17:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.