<p>I know that, for a grammar <span class="math-container">$G$</span> to belong to <span class="math-container">$LL(1)$</span>, it is <strong>necessary</strong> that</p>

<ol>
<li><span class="math-container">$G$</span> is not ambiguous; that is, every sentence has a unique parse tree in <span class="math-container">$G$</span>.</li>
<li><span class="math-container">$G$</span> has no left recursion; that is, we can't derive a sentential form like <span class="math-container">$A\alpha$</span> from a non-terminal <span class="math-container">$A$</span>.</li>
<li><span class="math-container">$G$</span> has no left factors; that is, there are no two rules of the form <span class="math-container">$A\to a\alpha$</span> and <span class="math-container">$A\to a\beta$</span> in <span class="math-container">$G$</span>, where <span class="math-container">$\alpha,\beta$</span> are strings of terminals and/or non-terminals.</li>
</ol>

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

<p>The textbook <em>Compilers: Principles, Techniques and Tools</em> by <em>Aho, Lam, Sethi</em> and <em>Jeffrey</em> 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.</p>

CC BY-SA 4.0
2019-02-17T17:34:01.473Z
$A\to a A a\mid b A b\mid \varepsilon$ is not LL(1); its language is not a deterministic CFL.
Sylvain
CC BY-SA 4.0
2019-02-18T12:14:18.017Z
@Sylvain consider turning this into an answer
Hermann Gruber
<fl.formal-languages><context-free><compilers>
Is there an unambiguous grammar that has no left recursion or left factors, but is not in $LL(1)$?
Berserker
# Is there an unambiguous grammar that has no left recursion or left factors, but is not in $LL(1)$?

(Asked by: username_0 on 2019-02-17)

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.

**Tags:** fl.formal-languages, context-free, compilers

> **Comments:**
> **username_1**: $A\to a A a\mid b A b\mid \varepsilon$ is not LL(1); its language is not a deterministic CFL.  
> **username_2**: @username_1 consider turning this into an answer  

---

## 0 answers

