I know that, for a grammar $G$ to belong to $LL(1)$, it is necessary that

  1. $G$ is not ambiguous; that is, every sentence has a unique parse tree in $G$.
  2. $G$ has no left recursion; that is, we can't derive a sentential form like $A\alpha$ from a non-terminal $A$.
  3. $G$ has no left factors; that is, there are no two rules of the form $A\to a\alpha$ and $A\to a\beta$ in $G$, where $\alpha,\beta$ are strings of terminals and/or non-terminals.

I am wondering whether these conditions are sufficient for the grammar to be in $LL(1)$. If not, is there a grammar satisfying these conditions and yet is not in $LL(1)$? If the answer is yes, this would imply that we can eliminate left recursion and left factors from any unambiguous grammars to obtain equivalent $LL(1)$ grammars.

The textbook Compilers: Principles, Techniques and Tools by Aho, Lam, Sethi and Jeffrey says that this is not the case. But, the example grammar they give (Example 4.33, pp. 225, Second Edition) is ambiguous, even though it has no left factors or left recursion.

  • 1
    $\begingroup$ $A\to a A a\mid b A b\mid \varepsilon$ is not LL(1); its language is not a deterministic CFL. $\endgroup$ – Sylvain Feb 17 '19 at 17:34
  • $\begingroup$ @Sylvain consider turning this into an answer $\endgroup$ – Hermann Gruber Feb 18 '19 at 12:14

Your Answer

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

Browse other questions tagged or ask your own question.