<p>I have done some more research, and I think I've found a solution for the 1st and 2nd questions, as for the 3rd one, I found an existing solution on StackOverflow for it, the proof attempts are written below:</p>

<p>We start by writing the three rules of the definition of an LL(1) grammar:</p>

<p>For every production <code>A -&gt; α | β</code> with <code>α ≠ β</code>:</p>

<ol>
<li><code>FIRST(α) ∩ FIRST(β) = Ø</code>.</li>
<li>If <code>β =&gt;* ε</code> then <code>FIRST(α) ∩ FOLLOW(A) = Ø</code> (also, if <code>α =&gt;* ε</code> then <code>FIRST(β) ∩ FOLLOW(A) = Ø</code>).</li>
<li>Including <code>ε</code> in rule (1) implies that at most one of <code>α</code> and <code>β</code> can derive <code>ε</code>.</li>
</ol>

<p><strong>Proposition 1:</strong> <em>A non-factored grammar is not LL(1).</em></p>

<p><strong>Proof:</strong></p>

<p>If a grammar G is non-factored then there exists a production in G of the form:</p>

<pre><code>A -&gt; ωα1 | ωα2 | ... | ωαn
</code></pre>

<p>(where <code>αi</code> is the <code>i-th α</code>, not the symbols <code>α</code> and <code>i</code>), with <code>α1 ≠ α2 ≠ ... ≠ αn</code>. We can then easily show that:</p>

<pre><code>∩(i=1,..,n) FIRST(ωαi) ≠ Ø
</code></pre>

<p>which contradicts rule (1) of the definition, thus, a non-factored grammar is not LL(1). ∎</p>

<p><strong>Proposition 2:</strong> <em>A left-recursive grammar is not LL(1).</em></p>

<p><strong>Proof:</strong></p>

<p>If a grammar is left-recursive then there exists a production in G of the form:</p>

<pre><code>S -&gt; Sα | β
</code></pre>

<p>Three cases arise here:</p>

<ol>
<li><p>If <code>FIRST(β) ≠ {ε}</code> then:</p>

<p><code>    FIRST(β) ⊆ FIRST(S)</code></p>

<p><code>=&gt;  FIRST(β) ∩ FIRST(Sα) ≠ Ø</code></p>

<p>which contradicts rule (1) of the definition.</p></li>
<li><p>If <code>FIRST(β) = {ε}</code> then:</p>

<p>2.1. If <code>ε ∈ FIRST(α)</code> then:</p>

<p><code>ε ∈ FIRST(Sα)</code></p>

<p>which contradicts rule (3) of the definition.</p>

<p>2.2. If <code>ε ∉ FIRST(α)</code> then:</p>

<p><code>    FIRST(α) ⊆ FIRST(S)</code> (because <code>β =&gt;* ε</code>)</p>

<p><code>=&gt;  FIRST(α) ⊆ FIRST(Sα) ........ (I)</code></p>

<p>we also know that:</p>

<p><code>FIRST(α) ⊆ FOLLOW(S) ........ (II)</code></p>

<p>by <code>(I)</code> and <code>(II)</code>, we have:</p>

<p><code>FIRST(Sα) ∩ FOLLOW(S) ≠ Ø</code></p>

<p>and since <code>β =&gt;* ε</code>, this contradicts rule (2) of the definition.</p></li>
</ol>

<p>In every case we arrive at a contradiction, hence, a left-recursive grammar is not LL(1). ∎</p>

<p><strong>Proposition 3:</strong> <em>An ambiguous grammar is not LL(1).</em></p>

<p><strong>Proof:</strong></p>

<p>While the above proofs are mine, this one is not, it's by <a href="https://stackoverflow.com/users/588948/kevin-a-naud%C3%A9">Kevin A. Naudé</a> which I got from his answer that is linked below:</p>

<p><a href="https://stackoverflow.com/a/18969767/6275103">https://stackoverflow.com/a/18969767/6275103</a></p>

CC BY-SA 4.0
2019-01-06T19:21:29.127Z
2019-01-06T19:55:26.623Z
2019-01-06T19:55:26.623Z
Djaouad
<p>I've learned from several sources that an LL(1) grammar is:</p>

<ol>
<li>unambiguous,</li>
<li>not left-recursive,</li>
<li>and, deterministic (left-factorized).</li>
</ol>

<p>What I can't fully understand is why the above is true for any LL(1) grammar. I know the LL(1) parsing table will have multiple entries at some cells, but what I really want to get is a formal and general (not with an example) proof to the following proposition(s):</p>

<p>A left-recursive (1), non-deterministic (2), or ambiguous (3) grammar is not LL(1).</p>

CC BY-SA 4.0
2019-01-05T18:21:14.457Z
I don't know what `left-factored' means, but Corollary 5.41 of Sippu & Soisalon-Soininen's _Parsing Theory_ answers (1) and Theorem 5.37 of the same answers (3) for any SLL(k) grammar, while Lemma 8.39 shows that any LL(1) grammar is SLL(1).
Sylvain
CC BY-SA 4.0
2019-01-05T19:08:07.437Z
@Sylvain Thanks for the references, and by 'left-factored' I mean 'deterministic grammar', e.g., `S->aB|aC` is not left-factored, `S->aS'` ;; `S' -> B|C` is left-factored).
Djaouad
<fl.formal-languages><grammars>
Why can't a left-recursive, non-deterministic, or ambiguous grammar be LL(1)?
Djaouad
# Why can't a left-recursive, non-deterministic, or ambiguous grammar be LL(1)?

(Asked by: username_0 on 2019-01-05)

I've learned from several sources that an LL(1) grammar is:

1. unambiguous,
2. not left-recursive,
3. and, deterministic (left-factorized).

What I can't fully understand is why the above is true for any LL(1) grammar. I know the LL(1) parsing table will have multiple entries at some cells, but what I really want to get is a formal and general (not with an example) proof to the following proposition(s):

A left-recursive (1), non-deterministic (2), or ambiguous (3) grammar is not LL(1).

**Tags:** fl.formal-languages, grammars

> **Comments:**
> **username_1**: I don't know what `left-factored' means, but Corollary 5.41 of Sippu & Soisalon-Soininen's _Parsing Theory_ answers (1) and Theorem 5.37 of the same answers (3) for any SLL(k) grammar, while Lemma 8.39 shows that any LL(1) grammar is SLL(1).  
> **username_0**: @username_1 Thanks for the references, and by 'left-factored' I mean 'deterministic grammar', e.g., `S->aB|aC` is not left-factored, `S->aS'` ;; `S' -> B|C` is left-factored).  

---

## 1 answers

### Answer by username_0 on 2019-01-06. Score: 1 | Accepted answer

I have done some more research, and I think I've found a solution for the 1st and 2nd questions, as for the 3rd one, I found an existing solution on StackOverflow for it, the proof attempts are written below:
We start by writing the three rules of the definition of an LL(1) grammar:
For every production A -> α | β with α ≠ β:

FIRST(α) ∩ FIRST(β) = Ø.
If β =>* ε then FIRST(α) ∩ FOLLOW(A) = Ø (also, if α =>* ε then FIRST(β) ∩ FOLLOW(A) = Ø).
Including ε in rule (1) implies that at most one of α and β can derive ε.

Proposition 1: A non-factored grammar is not LL(1).
Proof:
If a grammar G is non-factored then there exists a production in G of the form:
A -> ωα1 | ωα2 | ... | ωαn

(where αi is the i-th α, not the symbols α and i), with α1 ≠ α2 ≠ ... ≠ αn. We can then easily show that:
∩(i=1,..,n) FIRST(ωαi) ≠ Ø

which contradicts rule (1) of the definition, thus, a non-factored grammar is not LL(1). ∎
Proposition 2: A left-recursive grammar is not LL(1).
Proof:
If a grammar is left-recursive then there exists a production in G of the form:
S -> Sα | β

Three cases arise here:

If FIRST(β) ≠ {ε} then:
    FIRST(β) ⊆ FIRST(S)
=>  FIRST(β) ∩ FIRST(Sα) ≠ Ø
which contradicts rule (1) of the definition.
If FIRST(β) = {ε} then:
2.1. If ε ∈ FIRST(α) then:
ε ∈ FIRST(Sα)
which contradicts rule (3) of the definition.
2.2. If ε ∉ FIRST(α) then:
    FIRST(α) ⊆ FIRST(S) (because β =>* ε)
=>  FIRST(α) ⊆ FIRST(Sα) ........ (I)
we also know that:
FIRST(α) ⊆ FOLLOW(S) ........ (II)
by (I) and (II), we have:
FIRST(Sα) ∩ FOLLOW(S) ≠ Ø
and since β =>* ε, this contradicts rule (2) of the definition.

In every case we arrive at a contradiction, hence, a left-recursive grammar is not LL(1). ∎
Proposition 3: An ambiguous grammar is not LL(1).
Proof:
While the above proofs are mine, this one is not, it's by Kevin A. Naudé which I got from his answer that is linked below:
https://stackoverflow.com/a/18969767/6275103


---

