Lesson 2.3 — LL(1) parsing tables and their conflicts¶

Techniques: LL(1) table construction with conflict classification, conflict resolution by priority · Pebble implements: the table (lab exercise E4) · Lab: labs/ch02-ll1-toolkit (SPEC, contract buildLL1Table; ll1 table) · Prerequisites: Lesson 2.2 (nullable, FIRST, FOLLOW) · Time: 3 hours

With the running example's sets from Lesson 2.2 you can already decide by hand which production to use: on lookahead +, $E'$ must use $E' \to +\, T\, E'$; on ), $E'$ must vanish. Writing all these decisions into a matrix $M[\text{nonterminal}, \text{lookahead}]$ gives the LL(1) parsing table. A cell that receives two productions is a conflict: the grammar is not LL(1) (Theorem 2.3.8), and this lesson shows how to tell why (FIRST/FIRST or FIRST/FOLLOW) and when you may resolve a conflict by preferring one production.

1. Problem and motivation¶

A top-down parser for $G$ must, at every step, choose among $A$'s alternatives by looking at the next token. Lewis and Stearns defined the grammars for which $k$ tokens always suffice (LL(k), [LS68]); Knuth's Top-down syntax analysis characterized LL(1) grammars by FIRST and FOLLOW [Knu71], and Rosenkrantz and Stearns proved the general properties of the class [RS70]. The table is both the parser (the driver of Lesson 2.5 is 30 lines around it) and the test: a conflict-free table proves the grammar LL(1), hence unambiguous (Corollary 2.3.9).

LL(1) table construction and conflict classification¶

The construction fills $M$ from FIRST and FOLLOW; the classification says which of two very different problems a conflict is. A FIRST/FIRST conflict (two alternatives can start with the same token) is usually fixed by left factoring or left-recursion removal (Lesson 2.4). A FIRST/FOLLOW conflict (an $\varepsilon$-alternative competes with a real one, because the token can also follow the nonterminal) often means the grammar is ambiguous, as in the dangling else, and no rewrite of the same language fixes it without changing the tree. pebblec's grammar is checked this way: tests/ch02/Inputs/statements.grammar, a Pebble-like statement subset, has a conflict-free table.

Conflict resolution by priority¶

When a conflict is the dangling else, every practical parser does the same thing: in the conflicting cell, keep the production that consumes the else and drop the $\varepsilon$-alternative. The ALGOL 60 report avoided the problem syntactically [Nau60]; C and its descendants kept the ambiguous syntax and a disambiguating rule ("an else is associated with the lexically nearest preceding if", C23 §6.8.4.2). Parser generators turn such rules into a priority policy: ANTLR resolves every remaining ambiguity in favor of the lowest-numbered alternative [PHF14], and yacc prefers shift over reduce [Joh75] (Ch 3).

2. Definitions and algorithms¶

$\mathrm{Nullable}$, $\mathrm{FIRST}$ and $\mathrm{FOLLOW}$ are as in Lesson 2.2, Definition 2.2.1. A grammar is reduced if every nonterminal is reachable ($S \Rightarrow^{*} \alpha A \beta$ for some $\alpha, \beta$) and productive ($L(A) \neq \emptyset$).

Definition 2.3.1 (PREDICT sets and the LL(1) table)

For a production $p = A \to \alpha$,

\[ \mathrm{PREDICT}(p) \triangleq \mathrm{FIRST}(\alpha) \cup \begin{cases} \mathrm{FOLLOW}(A) & \text{if } \alpha \text{ is nullable,} \\ \emptyset & \text{otherwise.} \end{cases} \]

The LL(1) table is $M : N \times (T \cup \{\$\}) \to \mathcal{P}(P)$, $M[A, t] \triangleq \{\, p = A \to \alpha \mid t \in \mathrm{PREDICT}(p) \,\}$. A cell is empty (an error entry), single, or conflicting ($\lvert M[A, t] \rvert \ge 2$).

Definition 2.3.2 (LL(1) grammar [LS68, Knu71])

Write $\mathrm{first}_1(x)$ for the first symbol of $x\,\$$. $G$ is LL(1) if for all leftmost derivations

\[ S \Rightarrow_{\mathrm{lm}}^{*} w A \gamma \Rightarrow_{\mathrm{lm}} w \alpha \gamma \Rightarrow^{*} w x \quad\text{and}\quad S \Rightarrow_{\mathrm{lm}}^{*} w A \gamma \Rightarrow_{\mathrm{lm}} w \beta \gamma \Rightarrow^{*} w y \]

with $w, x, y \in T^{*}$, $\mathrm{first}_1(x) = \mathrm{first}_1(y)$ implies $\alpha = \beta$: one token of lookahead after the matched prefix $w$ always determines the production.

A non-LL(1) grammar in two lines

For $S \to A\, a$, $A \to a \mid \varepsilon$: the left-sentential form $A\, a$ continues as $a\, a$ (with $A \to a$) or as $a$ (with $A \to \varepsilon$); both continuations start with a, so $G$ is not LL(1). In the table, $\mathrm{PREDICT}(A \to a) = \{a\}$ and $\mathrm{PREDICT}(A \to \varepsilon) = \mathrm{FOLLOW}(A) = \{a\}$ collide in $M[A, a]$.

Definition 2.3.3 (Conflict kinds)

A conflicting cell $M[A, t]$ is a FIRST/FIRST conflict if at least two of its productions $A \to \alpha$ have $t \in \mathrm{FIRST}(\alpha)$, and a FIRST/FOLLOW conflict otherwise: then at most one production is there because $t \in \mathrm{FIRST}(\alpha)$, and every other one because $\alpha$ is nullable and $t \in \mathrm{FOLLOW}(A)$. (Two nullable alternatives conflict on all of $\mathrm{FOLLOW}(A)$; that is also FIRST/FOLLOW.)

Definition 2.3.4 (Priority policy)

A priority policy is a total order $\prec$ on $P$ (here: the numbering). Resolving a table under $\prec$ replaces every conflicting cell by the singleton of its $\prec$-least production. The resolved language $L_{\prec}(G)$ is the set of inputs accepted by the predictive parser (Lesson 2.5) driven by the resolved table.

LL(1) table construction and conflict classification¶

Algorithm 2.3.5 (BuildTable)

Input: $G$ and its $\mathrm{Nullable}$, $\mathrm{FIRST}$, $\mathrm{FOLLOW}$ (Lesson 2.2).
Output: $M$ and the list of conflicting cells with their kind.
Precondition: the three sets are the least fixed points (Theorem 2.2.5); FirstOf is Algorithm 2.2.6's helper.
Postcondition: $M[A, t] = \{\, p \mid t \in \mathrm{PREDICT}(p) \,\}$ for every cell (Lemma 2.3.7), and every conflicting cell is reported once with its kind per Definition 2.3.3.
Invariant: after processing productions $p_1, \dots, p_j$, $M[A, t] = \{\, p_i \mid i \le j,\ t \in \mathrm{PREDICT}(p_i) \,\}$.

Reference solution: solutions/labs/ch02-ll1-toolkit/src/Table.cpp; contract ll1::buildLL1Table.

function BuildTable(G, nullable, FIRST, FOLLOW):
    M[A, t] ← {} for every A ∈ N, t ∈ T ∪ {$}
    for each production p = A → α:
        (f, α_nullable) ← FirstOf(α, nullable, FIRST)
        for each t ∈ f:            M[A, t] ← M[A, t] ∪ {p}      # t can begin α
        if α_nullable:
            for each t ∈ FOLLOW(A): M[A, t] ← M[A, t] ∪ {p}      # α vanishes, t follows A
    conflicts ← []
    for each cell (A, t) with |M[A, t]| ≥ 2:
        via_first ← |{ p = A → α ∈ M[A, t] : t ∈ FirstOf(α, nullable, FIRST).f }|
        kind ← FIRST/FIRST if via_first ≥ 2 else FIRST/FOLLOW
        append (A, t, sorted M[A, t], kind) to conflicts
    return (M, conflicts)                    # G is LL(1) iff conflicts is empty (Theorem 2.3.8)

CPython 3.8's LL(1) generator rejects a FIRST/FIRST conflict

Reproduce (CPython source at tag v3.8.0, run with Python 3.11.15; needs network for the clone):

git -c advice.detachedHead=false clone -q --depth 1 --filter=blob:none --sparse -b v3.8.0 https://github.com/python/cpython
cd cpython && git sparse-checkout set Parser/pgen Grammar
cat > stmt.gram <<'EOF'
file_input: stmt ENDMARKER
stmt: expr_stmt | assign_stmt
expr_stmt: NAME '+' NAME
assign_stmt: NAME '=' NAME
EOF
python3 -m Parser.pgen stmt.gram Grammar/Tokens /dev/null /dev/null 2>&1 | tail -1
cat > fixed.gram <<'EOF'
file_input: stmt ENDMARKER
stmt: NAME ('+' | '=') NAME
EOF
python3 -m Parser.pgen -v fixed.gram Grammar/Tokens /dev/null /dev/null | sed -n '/^First set for/,$p'

Output (complete; tail -1 keeps the last line of the traceback):

ValueError: rule stmt is ambiguous; NAME is in the first sets of expr_stmt as well as assign_stmt
First set for file_input
    - NAME
First set for stmt
    - NAME

Grammar summary
===============
- 7 labels
- 2 dfas
- 4 tokens
- 0 keywords
- Start symbol: file_input

What to notice: ParserGenerator.calcfirst in Parser/pgen/pgen.py [CPY38-pgen] builds the FIRST set of each alternative and raises exactly when two alternatives of one rule overlap: a FIRST/FIRST conflict of Definition 2.3.3 at $M[\mathit{stmt}, \mathtt{NAME}]$. The error says "ambiguous", but the grammar is not ambiguous (each sentence has one tree); it is only not LL(1), which is Theorem 2.3.8's distinction. The fixed grammar is the left-factored version (Lesson 2.4). This check is why Python's grammar needed hacks until 3.9 switched to PEG [PEP617].

Conflict resolution by priority¶

Algorithm 2.3.6 (Resolve)

Input: a table $M$ with conflicts and a priority policy $\prec$.
Output: a conflict-free table $M'$ and a report of the dropped productions.
Precondition: none.
Postcondition: $M'[A, t] \subseteq M[A, t]$, $\lvert M'[A, t] \rvert \le 1$, and $M'$ equals $M$ on single cells; $L_{\prec}(G) \subseteq L(G)$ (Lemma 2.3.11).
Invariant: every processed cell holds exactly its $\prec$-least production.

function Resolve(M, priority):
    report ← []
    for each cell (A, t) with |M[A, t]| ≥ 2:
        keep ← the production of M[A, t] that comes first in priority
        append (A, t, M[A, t] − {keep}) to report     # generators print this as a warning
        M[A, t] ← {keep}
    return (M, report)

Clang and GCC take the else greedily, and warn

Reproduce (run with clang 23.1.2 from the course toolchain and the system gcc 13.3.0; the GCC source pointer below is pinned at GCC 15.1.0, where c_parser_if_statement and -Wdangling-else are unchanged in substance; any OS):

cat > dangle.c <<'EOF'
void g(int);
void f(int a, int b) {
  if (a)
    if (b) g(1);
    else g(2);
}
EOF
clang -fsyntax-only dangle.c
clang -fsyntax-only -Xclang -ast-dump -fno-color-diagnostics dangle.c 2>/dev/null \
  | sed -n '/FunctionDecl.* f /,$p' | sed -E 's/ 0x[0-9a-f]+//g'
gcc -fsyntax-only -Wdangling-else dangle.c

Output (complete):

dangle.c:5:5: warning: add explicit braces to avoid dangling else [-Wdangling-else]
    5 |     else g(2);
      |     ^
1 warning generated.
`-FunctionDecl <line:2:1, line:6:1> line:2:6 f 'void (int, int)' external-linkage
  |-ParmVarDecl <col:8, col:12> col:12 used a 'int'
  |-ParmVarDecl <col:15, col:19> col:19 used b 'int'
  `-CompoundStmt <col:22, line:6:1>
    `-IfStmt <line:3:3, line:5:13>
      |-ImplicitCastExpr <line:3:7> 'int' <LValueToRValue>
      | `-DeclRefExpr <col:7> 'int' lvalue ParmVar 'a' 'int'
      `-IfStmt <line:4:5, line:5:13> has_else
        |-ImplicitCastExpr <line:4:9> 'int' <LValueToRValue>
        | `-DeclRefExpr <col:9> 'int' lvalue ParmVar 'b' 'int'
        |-CallExpr <col:12, col:15> 'void'
        | |-ImplicitCastExpr <col:12> 'void (*)(int)' <FunctionToPointerDecay>
        | | `-DeclRefExpr <col:12> 'void (int)' Function 'g' 'void (int)'
        | `-IntegerLiteral <col:14> 'int' 1
        `-CallExpr <line:5:10, col:13> 'void'
          |-ImplicitCastExpr <col:10> 'void (*)(int)' <FunctionToPointerDecay>
          | `-DeclRefExpr <col:10> 'void (int)' Function 'g' 'void (int)'
          `-IntegerLiteral <col:12> 'int' 2
dangle.c: In function 'f':
dangle.c:3:6: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
    3 |   if (a)
      |      ^

What to notice: the inner IfStmt is the one marked has_else: both compilers resolved $M[S', \mathtt{else}]$ in favor of $S' \to \mathtt{else}\ S$, the priority choice of §3, and the resulting tree is the one C23 §6.8.4.2 prescribes (Proposition 2.3.12). Clang's warning comes from Parser::ParseIfStatement (diag::warn_dangling_else) [CLANG-ParseStmt], GCC's from c_parser_if_statement [GCC-CParser]: the "report" of Algorithm 2.3.6, surfaced to the programmer.

Bison: the same conflict, resolved by shift and silenced by %expect

Reproduce (bison 3.8.2; any OS):

cat > dangle.y <<'EOF'
%token IF THEN ELSE ID
%%
s: IF ID THEN s | IF ID THEN s ELSE s | ID ;
EOF
cat > dangle-expect.y <<'EOF'
%token IF THEN ELSE ID
%expect 1
%%
s: IF ID THEN s | IF ID THEN s ELSE s | ID ;
EOF
bison -Wcounterexamples -o /dev/null dangle.y
bison -Wall -o /dev/null dangle-expect.y && echo "dangle-expect.y: accepted silently"

Output (complete):

dangle.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
dangle.y: warning: shift/reduce conflict on token ELSE [-Wcounterexamples]
  Example: IF ID THEN IF ID THEN s . ELSE s
  Shift derivation
    s
    `-> 1: IF ID THEN s
                      `-> 2: IF ID THEN s . ELSE s
  Reduce derivation
    s
    `-> 2: IF ID THEN s                     ELSE s
                      `-> 1: IF ID THEN s .
dangle-expect.y: accepted silently

What to notice: an LR generator meets the same ambiguity as a shift/reduce conflict and resolves it by the fixed priority "shift wins" [Joh75], which attaches the ELSE to the inner IF exactly like $M'[S', e] = \{S' \to e\, S\}$. %expect 1 is the grammar author's statement that exactly this one resolution was reviewed; any additional conflict makes Bison fail [BISON-Manual].

3. Worked example¶

Running example (the same grammar as Lesson 2.2, tests/ch02/Inputs/running.grammar), with the sets computed there:

(1) S  → i E t S S'   (4) S' → ε           (7) E' → ε          nullable = {S', E'}
(2) S  → a            (5) E  → T E'        (8) T  → ( E )      FOLLOW(S) = FOLLOW(S') = {e, $}
(3) S' → e S          (6) E' → + T E'      (9) T  → x          FOLLOW(E) = FOLLOW(E') = {), t}

LL(1) table construction and conflict classification on the running example¶

One row per production, in order (the loop of BuildTable):

production	FirstOf(α)	α nullable?	cells receiving it
(1) S → i E t S S'	{i}	no	M[S, i]
(2) S → a	{a}	no	M[S, a]
(3) S' → e S	{e}	no	M[S', e]
(4) S' → ε	{}	yes	M[S', e], M[S', $] (FOLLOW(S') = {e, $})
(5) E → T E'	{(, x}	no	M[E, (], M[E, x]
(6) E' → + T E'	{+}	no	M[E', +]
(7) E' → ε	{}	yes	M[E', )], M[E', t] (FOLLOW(E') = {), t})
(8) T → ( E )	{(}	no	M[T, (]
(9) T → x	{x}	no	M[T, x]

The resulting table (empty cells are errors; ‼ marks the conflict):

	(	)	+	a	e	i	t	x	$
S				2		1
S'					‼ 3 4				4
E	5							5
E'		7	6				7
T	8							9

Classification of $M[S', e] = \{3, 4\}$: $e \in \mathrm{FirstOf}(e\, S) = \{e\}$, but $e \notin \mathrm{FirstOf}(\varepsilon) = \{\}$; only one production is there through FIRST, so it is a FIRST/FOLLOW conflict. It exists because $e \in \mathrm{FOLLOW}(S')$: $S'$ ends production (1), so $\mathrm{FOLLOW}(S) \subseteq \mathrm{FOLLOW}(S')$, and $e \in \mathrm{FOLLOW}(S)$ because $S$ is followed by $S'$ (whose FIRST contains $e$) in production (1) itself. This is the dangling else: i x t i x t a e a has two trees (the oracle counts 2).

For contrast, tests/ch02/Inputs/expr-left-recursive.grammar ($E \to E + T \mid T$ …) has conflicts $M[E, (]$ and $M[E, \mathtt{id}]$, both FIRST/FIRST: $E + T$ and $T$ both begin with $\mathrm{FIRST}(T)$ (Corollary 2.3.10). For the running example, ll1 table prints:

conflict M[S', e] FIRST/FOLLOW: (3) S' -> e S; (4) S' -> ε;
LL(1): no

Conflict resolution by priority on the running example¶

Priority = production number: $M[S', e]$ keeps (3) $S' \to e\, S$. The resolved parser on i x t i x t a e a (oracle ll1_parse(..., resolve="first"); stack top on the right):

step	stack	input	action
1	$ S	i x t i x t a e a $	output (1) S → i E t S S'
2	$ S' S t E i	i x t i x t a e a $	match i
3	$ S' S t E	x t i x t a e a $	output (5) E → T E'
4	$ S' S t E' T	x t i x t a e a $	output (9) T → x
5	$ S' S t E' x	x t i x t a e a $	match x
6	$ S' S t E'	t i x t a e a $	output (7) E' → ε
7	$ S' S t	t i x t a e a $	match t
8	$ S' S	i x t a e a $	output (1) S → i E t S S' (the inner if)
9	$ S' S' S t E i	i x t a e a $	match i
10	$ S' S' S t E	x t a e a $	output (5) E → T E'
11	$ S' S' S t E' T	x t a e a $	output (9) T → x
12	$ S' S' S t E' x	x t a e a $	match x
13	$ S' S' S t E'	t a e a $	output (7) E' → ε
14	$ S' S' S t	t a e a $	match t
15	$ S' S' S	a e a $	output (2) S → a
16	$ S' S' a	a e a $	match a
17	$ S' S'	e a $	M[S', e] resolved: output (3) S' → e S — the inner if takes the else
18	$ S' S e	e a $	match e
19	$ S' S	a $	output (2) S → a
20	$ S' a	a $	match a
21	$ S'	$	output (4) S' → ε — the outer if has no else
22	$	$	accept

The same policy on tests/ch02/Inputs/first-follow.grammar ($S \to A\, a$; $A \to a \mid \varepsilon$) is wrong: $M[A, a] = \{A \to a, A \to \varepsilon\}$ resolved to $A \to a$ makes the parser reject the sentence a (it consumes the only a inside $A$, then finds $ where a is required).

Try it

./course drill ll1-table --seed 3 --difficulty hard fills a whole table with conflicts and asks for their kinds; --solution shows the per-production rows above.

4. Invariants and correctness¶

LL(1) table construction and conflict classification¶

Lemma 2.3.7 (PREDICT is exact)

(a) If $S\,\$ \Rightarrow_{\mathrm{lm}}^{*} w A \gamma\,\$ \Rightarrow_{\mathrm{lm}} w \alpha \gamma\,\$ \Rightarrow^{*} w\, t\, z$ with $t \in T \cup \{\$\}$, then $t \in \mathrm{PREDICT}(A \to \alpha)$. (b) Conversely, if $G$ is reduced and $t \in \mathrm{PREDICT}(A \to \alpha)$, there are $w$, $\gamma$, $z$ with $S\,\$ \Rightarrow_{\mathrm{lm}}^{*} w A \gamma\,\$$ and $\alpha \gamma\,\$ \Rightarrow^{*} t\, z$. After Algorithm 2.3.5, $M[A, t] = \{\, p \mid t \in \mathrm{PREDICT}(p) \,\}$.

Proof

(a) The token $t$ descends either from $\alpha$, so $\alpha \Rightarrow^{*} t \cdots$ and $t \in \mathrm{FIRST}(\alpha)$; or $\alpha \Rightarrow^{*} \varepsilon$ and $t$ descends from $\gamma\,\$$, so $S\,\$ \Rightarrow^{*} w A t \cdots$ and $t \in \mathrm{FOLLOW}(A)$ with $\alpha$ nullable. Either way $t \in \mathrm{PREDICT}(A \to \alpha)$.

(b) Case $t \in \mathrm{FIRST}(\alpha)$. $A$ is reachable, so some sentential form contains it; take a parse tree of such a form, expand every nonterminal left of $A$ to terminals (they are productive), and read off the leftmost derivation that expands nodes in preorder and stops when $A$ is the leftmost unexpanded node (Lemma 2.1.10): it reaches a form $w A \gamma$. Since $\alpha \Rightarrow^{*} t \cdots$, also $\alpha \gamma\,\$ \Rightarrow^{*} t \cdots$. Case $\alpha$ nullable and $t \in \mathrm{FOLLOW}(A)$. By definition $S\,\$ \Rightarrow^{*} \delta A t \eta$; expand $\delta$ to terminals $w$ and apply the same preorder argument to a tree of $w A t \eta$: at the moment $A$ is the leftmost unexpanded node the form is $w A \gamma\,\$$, and the rest of the derivation turns $\gamma\,\$$ into a string starting with $t$ (the node for $t$ lies to the right of $A$ and nothing between them yields a terminal). With $\alpha \Rightarrow^{*} \varepsilon$, $\alpha \gamma\,\$ \Rightarrow^{*} t \cdots$.

The last claim is the invariant of Algorithm 2.3.5: each production is added exactly to the cells of its PREDICT set, computed with FirstOf = FIRST (Theorem 2.2.5).

Theorem 2.3.8 (Conflict-free table ⟺ LL(1) [Knu71, RS70])

Let $G$ be reduced. Then $M$ has no conflicting cell if and only if $G$ is LL(1) (Definition 2.3.2), if and only if for every pair of distinct alternatives $A \to \alpha \mid \beta$: (i) $\mathrm{FIRST}(\alpha) \cap \mathrm{FIRST}(\beta) = \emptyset$, (ii) not both $\alpha$ and $\beta$ are nullable, and (iii) if $\beta$ is nullable then $\mathrm{FIRST}(\alpha) \cap \mathrm{FOLLOW}(A) = \emptyset$.

Proof

No conflict ⇒ LL(1). Take two derivations as in Definition 2.3.2 with $\mathrm{first}_1(x) = \mathrm{first}_1(y) = t$. By Lemma 2.3.7(a) applied to each, $t \in \mathrm{PREDICT}(A \to \alpha) \cap \mathrm{PREDICT}(A \to \beta)$, so both productions are in $M[A, t]$; as the cell is not conflicting, $\alpha = \beta$.

LL(1) ⇒ no conflict. Suppose $A \to \alpha \ne A \to \beta$ are both in $M[A, t]$, i.e. $t$ is in both PREDICT sets. Apply Lemma 2.3.7(b) to $A \to \alpha$: it gives a left-sentential form $w A \gamma$ from which $\alpha$ leads to a string starting with $t$. The construction in (b) depends on $t$ and $A$, and in the FIRST case on nothing else, so we can choose the same $w A \gamma$ for $\beta$: if $t \in \mathrm{FIRST}(\beta)$, use any left-sentential form containing $A$ (as in the first case); if $\beta$ is nullable and $t \in \mathrm{FOLLOW}(A)$, use the form built from $t \in \mathrm{FOLLOW}(A)$, for which $\gamma\,\$ \Rightarrow^{*} t \cdots$, and then $\alpha \gamma\,\$$ also starts with $t$ whether $t$ comes from $\alpha$ (as $t \in \mathrm{FIRST}(\alpha)$) or from $\gamma$ (as $\alpha$ is nullable). This yields two leftmost derivations violating Definition 2.3.2.

Conditions (i)–(iii). A cell $M[A, t]$ holds two alternatives iff $t$ lies in both PREDICT sets. By Definition 2.3.1 that happens iff $t$ is in both FIRST sets (violating (i)); or both alternatives are nullable and $t \in \mathrm{FOLLOW}(A)$, which is non-empty for a reachable $A$ in a reduced grammar (some symbol, at worst $\$$, follows it), so (ii) is violated; or exactly one, $\beta$, is nullable and $t \in \mathrm{FIRST}(\alpha) \cap \mathrm{FOLLOW}(A)$, violating (iii).

Corollary 2.3.9 (LL(1) grammars are unambiguous)

If $G$ is LL(1), every $w \in L(G)$ has exactly one parse tree.

Proof

Suppose $w$ has two trees. By Lemma 2.1.10 it has two different leftmost derivations. Let $w' A \gamma$ be the last left-sentential form they share; at the next step they apply different productions $A \to \alpha$ and $A \to \beta$, and both continue to $w = w' x$. Then $x = y$, so $\mathrm{first}_1(x) = \mathrm{first}_1(y)$, and Definition 2.3.2 forces $\alpha = \beta$, a contradiction.

Corollary 2.3.10 (Direct left recursion is never LL(1))

If $G$ is reduced and cycle-free and has productions $A \to A \alpha$ and $A \to \beta$, then $M$ has a conflict in row $A$.

Proof

If $\beta$ derives some non-empty terminal string, let $t$ be its first token: $t \in \mathrm{FIRST}(\beta)$, and $A \alpha \Rightarrow \beta \alpha$ gives $t \in \mathrm{FIRST}(A \alpha)$, a FIRST/FIRST conflict at $M[A, t]$. Otherwise $L(\beta) = \{\varepsilon\}$, so $\beta$ and $A$ are nullable; $\alpha$ is not nullable, since otherwise $A \Rightarrow A \alpha \Rightarrow^{*} A$ would be a cycle, and $\alpha$ is productive ($G$ is reduced), so it derives a non-empty string, whose first token we call $t$. Then $t \in \mathrm{FIRST}(A \alpha)$ (as $A$ is nullable) and $t \in \mathrm{FOLLOW}(A)$ (as $\alpha$ follows $A$), while $\beta$ is nullable: a FIRST/FOLLOW conflict at $M[A, t]$.

Classification is well defined: it depends only on the cell's contents and on FIRST, not on the order of insertion. When it breaks: unreachable or unproductive nonterminals can create conflicts in rows that no derivation uses, so Theorem 2.3.8 needs a reduced grammar; and for $k \ge 2$, a FOLLOW$_k$-based table is only sufficient (Lesson 2.6, Theorem 2.6.12).

Conflict resolution by priority¶

Lemma 2.3.11 (Priority resolution is sound)

For every priority policy, the parser driven by the resolved table $M'$ is deterministic, every tree it builds is a parse tree of $G$, and $L_{\prec}(G) \subseteq L(G)$.

Proof

Every cell of $M'$ has at most one production, so each configuration has at most one move. Every move of the $M'$-parser is a move of the $M$-parser, whose expansions are leftmost derivation steps of $G$ (Lemma 2.5.8); so an accepting run spells a leftmost derivation $S \Rightarrow_{\mathrm{lm}}^{*} w$ and its tree is a tree of $G$.

Proposition 2.3.12 (Priority is complete for the dangling else)

For the if-grammar of §3, preferring $S' \to e\, S$ loses no sentence: $L_{\prec}(G) = L(G)$, and the tree built attaches every e to the nearest preceding unmatched i.

Proof (the nearest-if tree exists for every sentence: [ALSU07 §4.3.2])

Every sentence $w \in L(G)$ has a tree $\tau$ in which each e is attached to the nearest preceding unmatched i: this is the tree of the "matched/unmatched statement" grammar of [ALSU07 §4.3.2], which generates the same language. Follow the leftmost derivation of $\tau$. At a step that expands $S'$, the next input token is e exactly when $\tau$ uses $S' \to e\, S$ there: if $\tau$ used $S' \to \varepsilon$ while e comes next, that e would belong to an enclosing i, although the i owning this $S'$ is unmatched and nearer, contradicting the choice of $\tau$. So at every $S'$-step the resolved cell ($M'[S', e] = \{S' \to e\, S\}$, $M'[S', \$] = \{S' \to \varepsilon\}$) prescribes the production $\tau$ uses, and at every other step the cell is single and holds $\tau$'s production by Lemma 2.3.7(a). The resolved parser therefore follows $\tau$'s derivation and accepts $w$, and the tree it builds is $\tau$. With Lemma 2.3.11, $L_{\prec}(G) = L(G)$.

When it breaks: when the dropped production was the only way to derive some sentence. In first-follow.grammar ($S \to A\, a$, $A \to a \mid \varepsilon$), the priority choice $A \to a$ gives $L_{\prec}(G) = \{aa\} \subsetneq L(G) = \{a, aa\}$: the input a is rejected (§3). Generators therefore warn about every resolved conflict (Bison, real-world box in §2), and grammar authors must justify each one.

5. Complexity¶

Variables: $\lvert P \rvert$ productions, $\lvert G \rvert$ total grammar size, $\lvert N \rvert$ nonterminals, $\lvert T \rvert$ terminals, $c$ = number of conflicting cells.

Technique	Time (worst)	Time (typical)	Space	Variables
LL(1) table + classification	$O(\lvert G \rvert \cdot \lvert T \rvert + \lvert P \rvert \cdot (\lvert T \rvert + 1))$ after FIRST/FOLLOW; classification $O(c \cdot \lvert P \rvert \cdot \lvert G \rvert)$	milliseconds	$O(\lvert N \rvert \cdot (\lvert T \rvert + 1))$ dense, or $O(\#\text{entries})$ sparse	as above
Priority resolution	$O(c \cdot \lvert P \rvert)$	free at parse time	none extra	—

Proposition 2.3.13 (Cost of BuildTable)

Algorithm 2.3.5 runs in $O(\lvert G \rvert \cdot \lvert T \rvert + \lvert P \rvert (\lvert T \rvert + 1) + c \cdot \lvert P \rvert \cdot \lvert G \rvert)$ time.

Proof

FirstOf over all right sides costs $O(\lvert G \rvert)$ unions of sets of size $\le \lvert T \rvert$. Each production is inserted into at most $\lvert T \rvert + 1$ cells. The classification loop visits $c$ cells; each holds at most $\lvert P \rvert$ productions, and each test recomputes one FirstOf in $O(\lvert G \rvert)$ (or $O(1)$ with the first loop's results cached).

Pathological input: a nonterminal with many nullable alternatives, e.g. $A \to B_1 \mid \cdots \mid B_k$ with every $B_i \to b_i \mid \varepsilon$: all $k$ alternatives land in every cell of $\mathrm{FOLLOW}(A)$, so the conflicting cells hold $k$ productions each and row $A$ has $\Theta(k \cdot \lvert \mathrm{FOLLOW}(A) \rvert)$ entries.

At scale: LL(1) tables are sparse. Over the corpus, the Pebble-like statements.grammar fills 32 of its 128 cells and json.grammar 24 of 96 (25 %; ll1 table shows them). Tarjan and Yao's row-displacement scheme stores such tables in space close to the number of entries while keeping $O(1)$ lookup [TY79].

LL(1) table construction and conflict classification¶

Table compression [TY79]: overlay the sparse rows in one array with per-row offsets (row displacement) — trade-off: a smaller table and $O(1)$ lookups, but a one-time packing step and a check array to detect "empty".
Default entries: store only the non-error entries and use the most common production as each row's default; errors are then detected later (after some $\varepsilon$-expansions) — trade-off: smaller tables, but the parser loses the immediate-error-detection property that Lesson 2.7's recovery relies on.
Per-rule DFAs (ELL(1)) [CPY38-pgen]: right sides are regular expressions compiled to DFAs, so a FIRST/FIRST overlap inside one rule is merged by subset construction instead of reported — trade-off: fewer spurious conflicts, but only within a rule (real-world box in §2 and Lesson 2.4).

Conflict resolution by priority¶

Semantic or syntactic predicates [PQ95]: annotate an alternative with a condition ({isTypeName()}?) or a lookahead test that decides the conflict at parse time — trade-off: can resolve conflicts that no static priority can, but the grammar no longer describes the language alone.
Rewrite to an unambiguous grammar (matched/unmatched statements [ALSU07 §4.3.2]) or change the language (mandatory braces, as in Pebble, Rust, Swift; or an end if keyword) — trade-off: a clean LL(1)/LR(1) grammar, at the cost of a larger grammar or a different syntax.

7. In real compilers¶

LL(1) table construction and conflict classification¶

CPython 3.8 Parser/pgen/pgen.py — ParserGenerator.calcfirst (v3.8.0) builds the FIRST sets of every rule's DFA and rejects a FIRST/FIRST overlap with "rule … is ambiguous; … is in the first sets of … as well as …" (real-world box in §2) [CPY38-pgen]. Python used this LL(1) parser until 3.9 switched to PEG [PEP617].
ANTLR 4 runtime/Java/src/org/antlr/v4/runtime/atn/LL1Analyzer.java — getDecisionLookahead (4.13.2) computes, for each alternative of a decision, its LL(1) lookahead set; the tool uses it to find the decisions that are LL(1) (disjoint sets) and need no adaptive prediction [ANTLR4-LL1Analyzer].

Conflict resolution by priority¶

Clang (LLVM 23.1.2) clang/lib/Parse/ParseStmt.cpp — Parser::ParseIfStatement consumes an else whenever it sees tok::kw_else after the then-branch (the priority choice (3) above) and, when the inner statement of an if without braces took the else, warns with diag::warn_dangling_else ("add explicit braces to avoid dangling else") [CLANG-ParseStmt] (real-world box in §2).
GCC gcc/c/c-parser.cc — c_parser_if_statement (GCC 15) takes the else greedily as well and implements -Wdangling-else [GCC-CParser].
ANTLR 4 runtime/Java/src/org/antlr/v4/runtime/atn/PredictionMode.java — resolvesToJustOneViableAlt (4.13.2): when prediction ends in a conflict, the minimum alternative wins, i.e. priority = order of alternatives [ANTLR4-PredictionMode].
Bison resolves shift/reduce conflicts by shifting and lets the author acknowledge them with %expect (real-world box in §2) [BISON-Manual].

Find where LLVM does it. Open clang/lib/Parse/ParseStmt.cpp (LLVM 23.1.2) and find Parser::ParseIfStatement. Question: which diagnostic ID does Clang emit when an inner if without braces takes the else? (quiz clang-dangling-else)

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
LL(1) table construction + conflict classification	Exactly the LL(1) grammars (a proper subset of LR(1)); a conflict-free table proves unambiguity	O(\|G\| + \|P\|·\|T\|) · milliseconds; ~25 % of cells filled	Names every conflicting cell and its kind (FIRST/FIRST vs FIRST/FOLLOW)	Low once FIRST/FOLLOW exist	LL generators (CPython ≤ 3.8 pgen, JavaCC, ANTLR's LL(1) decisions), grammar review
Conflict resolution by priority	Deterministic parser for a subset of L(G); equal to L(G) for the dangling else, smaller in general	O(#conflicts) at build time · free at parse time	Silent unless warned; can drop sentences	Trivial	Dangling else (C, C++, Java), ANTLR's "first alternative wins"

Choose the table test when you design or change a grammar for a top-down parser: it is exact (Theorem 2.3.8) and cheap, and the conflict kind tells you whether to left-factor (FIRST/FIRST) or to think about ambiguity (FIRST/FOLLOW). Choose priority resolution when the conflict is a known, documented ambiguity whose intended tree the priority produces (the dangling else, Proposition 2.3.12); otherwise rewrite the grammar or add lookahead (Lesson 2.6).

9. Assessment¶

Technique	Quiz ids (`solutions/quizzes/ch02.yaml`)	Drill	Flashcard tag	Exercises
LL(1) table + classification	`table-cells-running`, `conflict-kinds`	`./course drill ll1-table`	`ll1-table`	E4
Priority resolution	`conflict-kinds` (when is priority safe?), `clang-dangling-else`	`./course drill ll1-table --difficulty hard` (classify, then decide)	`priority`	— (lab: `ll1 parse` on `dangling-else.grammar` reports the conflict)

A FIRST/FOLLOW conflict hides behind ε

In $S \to A\, a$, $A \to a \mid \varepsilon$ nothing looks ambiguous, yet $M[A, a]$ holds both alternatives, and preferring $A \to a$ breaks the sentence a. Always look at FOLLOW before blaming FIRST.

References¶

See the chapter references.

Technique	Time (worst)	Time (typical)	Space	Variables
LL(1) table + classification	\(O(\lvert G \rvert \cdot \lvert T \rvert + \lvert P \rvert \cdot (\lvert T \rvert + 1))\) after FIRST/FOLLOW; classification \(O(c \cdot \lvert P \rvert \cdot \lvert G \rvert)\)	milliseconds	\(O(\lvert N \rvert \cdot (\lvert T \rvert + 1))\) dense, or \(O(\#\text{entries})\) sparse	as above
Priority resolution	\(O(c \cdot \lvert P \rvert)\)	free at parse time	none extra	—

Lesson 2.3 — LL(1) parsing tables and their conflicts¶

1. Problem and motivation¶

LL(1) table construction and conflict classification¶

Conflict resolution by priority¶

2. Definitions and algorithms¶

LL(1) table construction and conflict classification¶

Conflict resolution by priority¶

3. Worked example¶

LL(1) table construction and conflict classification on the running example¶

Conflict resolution by priority on the running example¶

4. Invariants and correctness¶

LL(1) table construction and conflict classification¶

Conflict resolution by priority¶

5. Complexity¶

6. Variants and refinements¶

LL(1) table construction and conflict classification¶

Conflict resolution by priority¶

7. In real compilers¶

LL(1) table construction and conflict classification¶

Conflict resolution by priority¶

8. Comparison¶

9. Assessment¶

References¶