Lesson 2.6 — More lookahead: LL(k), LL() and ALL()¶

Techniques: strong LL(k), full (canonical) LL(k), LL(*) lookahead DFAs, ALL(*) adaptive prediction · Pebble implements: none (pebblec is LL(1) with two hand-coded LL(2) spots); theory + oracles in tools/course/lib/grammar.py · Lab: — (drill lookahead) · Prerequisites: Lesson 2.3, Lesson 2.5 · Time: 4–5 hours

A conflict in an LL(1) table says one token is not enough. Sometimes two are: a labeled statement L: and an expression L = 1 both start with an identifier, and Clang looks at the next token to decide. Sometimes no fixed number is enough: $S \to X\, c \mid X\, d$ with $X \to a\, X \mid b$ must scan past any number of as. This lesson climbs the lookahead ladder, from $k$ tokens with global context (strong LL(k)), to $k$ tokens with local context (LL(k)), to regular lookahead (LL(*)), to ANTLR 4's adaptive prediction, which simulates the grammar on the actual input and falls back to full parser context only when it must.

1. Problem and motivation¶

Input: a grammar that is not LL(1) (but, for all of these methods, not left-recursive) and a decision point: a nonterminal $A$ with several alternatives, at some position in the input. Output: which alternative to take, using as little lookahead as possible. The question matters for every grammar written for humans rather than for LL(1): C++ declarations vs expressions, Java generics, and every grammar in ANTLR's grammar repository.

Strong LL(k)¶

Lewis and Stearns defined LL(k) in general [LS68]; the "strong" variant uses one table per nonterminal indexed by $k$-token strings, with $\mathrm{FOLLOW}_k(A)$ summarizing all contexts of $A$ [RS70; AU72 §5.1]. It is the direct generalization of the LL(1) table and what most "LL(k)" generators actually build, sometimes approximated further (ANTLR 2's linear approximate lookahead [Par93]).

Full (canonical) LL(k)¶

Rosenkrantz and Stearns showed that strong LL(k) is strictly weaker than LL(k) for $k \ge 2$ and that every LL(k) grammar can be parsed with a finite set of tables $T_{A,L}$, one per nonterminal and local follow set $L$ [RS70; AU72 §5.1]. More lookahead gives strictly more languages: LL(k) ⊊ LL(k+1) [Kur69]. Full LL(k) is rarely implemented because the number of tables explodes.

LL(*)¶

Parr and Fisher's LL(*) [PF11], the algorithm of ANTLR 3, drops the fixed $k$: at each decision it builds a lookahead DFA by subset construction over the grammar's transition network (ATN), so a decision can scan arbitrarily far as long as the lookahead language is regular. When static analysis fails (recursion in the lookahead), ANTLR 3 falls back to syntactic predicates and backtracking.

ALL(*)¶

Adaptive LL(*) [PHF14], the algorithm of ANTLR 4, moves the analysis to parse time: at each decision it simulates all alternatives on the actual remaining input, first cheaply without the parser's call-stack context (SLL), and only if that simulation cannot separate the alternatives, again with the full context (LL). The DFAs it builds are cached, so repeated decisions become table lookups. ALL(*) handles every non-left-recursive grammar (ANTLR rewrites direct left recursion itself, Lesson 2.4) and resolves true ambiguities by picking the lowest alternative.

2. Definitions and algorithms¶

Definition 2.6.1 (k-strings and k-concatenation)

A $k$-string is a string over $T \cup \{\$\}$ of length at most $k$ in which $\$$ can only be the last symbol, and then the string may be shorter than $k$. For strings $x, y$, the $k$-prefix $x{:}k$ is the first $\min(k, \lvert x \rvert)$ symbols of $x$, and $k$-concatenation is $x \oplus_k y \triangleq (x y){:}k$ (a string ending in $\$$ does not grow). For sets, $L_1 \oplus_k L_2 \triangleq \{\, x \oplus_k y \mid x \in L_1,\ y \in L_2 \,\}$. The set of $k$-strings is finite; $\oplus_k$ is associative and monotone in both arguments with unit $\{\varepsilon\}$.

Definition 2.6.2 (FIRST$_k$ and FOLLOW$_k$)

\[ \begin{aligned} \mathrm{FIRST}_k(\alpha) &\triangleq \{\, w{:}k \mid w \in T^{*},\ \alpha \Rightarrow^{*} w \,\},\\ \mathrm{FOLLOW}_k(A) &\triangleq \{\, x \mid S\,\$ \Rightarrow^{*} \beta A \gamma,\ x \in \mathrm{FIRST}_k(\gamma) \,\} \qquad (\gamma \text{ ends in } \$). \end{aligned} \]

For $k = 1$ these are Definition 2.2.1's sets, with $\varepsilon \in \mathrm{FIRST}_1(\alpha)$ iff $\alpha$ is nullable.

Definition 2.6.3 (LL(k) and strong LL(k))

$G$ is LL(k) if for all leftmost derivations $S\,\$ \Rightarrow_{\mathrm{lm}}^{*} w A \gamma \Rightarrow_{\mathrm{lm}} w \alpha \gamma \Rightarrow^{*} w x$ and $S\,\$ \Rightarrow_{\mathrm{lm}}^{*} w A \gamma \Rightarrow_{\mathrm{lm}} w \beta \gamma \Rightarrow^{*} w y$, $x{:}k = y{:}k$ implies $\alpha = \beta$ (Definition 2.3.2 with $k$ tokens). $G$ is strong LL(k) if for every pair of distinct alternatives $A \to \alpha \mid \beta$:

\[ \big(\mathrm{FIRST}_k(\alpha) \oplus_k \mathrm{FOLLOW}_k(A)\big) \cap \big(\mathrm{FIRST}_k(\beta) \oplus_k \mathrm{FOLLOW}_k(A)\big) = \emptyset . \]

The set $\mathrm{LA}_k(A \to \alpha) \triangleq \mathrm{FIRST}_k(\alpha) \oplus_k \mathrm{FOLLOW}_k(A)$ is the alternative's strong lookahead set.

k-concatenation on the running example

With $k = 2$: $\{b\} \oplus_2 \{aa, ba\} = \{ba, bb\}$ and $\{\varepsilon\} \oplus_2 \{aa, ba\} = \{aa, ba\}$; the two sets share $ba$, which is exactly why strong-vs-full is not strong LL(2) (§3). With $k = 3$ the follow strings end in $\$$: $\{b\} \oplus_3 \{aa\$, ba\$\} = \{baa, bba\}$.

Strong LL(k)¶

Algorithm 2.6.4 (StrongLLk)

Input: $G$, $k \ge 1$.
Output: $\mathrm{LA}_k(p)$ for every production and the conflicting pairs.
Precondition: none (terminates on every grammar).
Postcondition: F $= \mathrm{FIRST}_k$, FO $= \mathrm{FOLLOW}_k$ (Lemma 2.6.10); $G$ is strong LL(k) iff no conflict is reported.
Invariant: every set only grows and stays below its least fixed point.

Oracles: first_k_sets, follow_k_sets, strong_llk_lookahead, min_strong_k.

function FirstK(G, k):                              # least fixed point, like FIRST (Lesson 2.2)
    F(A) ← {} for every A;  F(t) ← {t} for terminals
    repeat
        for each A → X1 … Xm:
            cur ← {ε}
            for each Xi: cur ← cur ⊕k F(Xi)
            F(A) ← F(A) ∪ cur
    until no F(A) changed
    return F

function FollowK(G, k, F):
    FO(A) ← {} for every A;  FO(S) ← {$}
    repeat
        for each A → α B β with B ∈ N:
            FO(B) ← FO(B) ∪ (FirstOfK(β, F) ⊕k FO(A))
    until no FO(B) changed
    return FO

function StrongLLk(G, k):
    F ← FirstK(G, k);  FO ← FollowK(G, k, F)
    for each production p = A → α:  LA(p) ← FirstOfK(α, F) ⊕k FO(A)
    conflicts ← { (p, q) : p ≠ q alternatives of one A, LA(p) ∩ LA(q) ≠ {} }
    return (LA, conflicts)                            # table: M[A, x] = { p : x ∈ LA(p) }

function FirstOfK(X1 … Xm, F):  cur ← {ε};  for each Xi: cur ← cur ⊕k F(Xi);  return cur

Clang decides a label with a second token

Reproduce (clang 23.1.2; any OS):

cat > label.c <<'EOF'
void f(int L) {
  L: L = 1;
  L = 2;
}
EOF
clang -fsyntax-only -Xclang -ast-dump -fno-color-diagnostics label.c \
  | sed -n '/FunctionDecl.* f /,$p' | sed -E 's/ 0x[0-9a-f]+//g'

Output (complete):

`-FunctionDecl <label.c:1:1, line:4:1> line:1:6 f 'void (int)' external-linkage
  |-ParmVarDecl <col:8, col:12> col:12 used L 'int'
  `-CompoundStmt <col:15, line:4:1>
    |-LabelStmt <line:2:3, col:10> 'L'
    | `-BinaryOperator <col:6, col:10> 'int' '='
    |   |-DeclRefExpr <col:6> 'int' lvalue ParmVar 'L' 'int'
    |   `-IntegerLiteral <col:10> 'int' 1
    `-BinaryOperator <line:3:3, col:7> 'int' '='
      |-DeclRefExpr <col:3> 'int' lvalue ParmVar 'L' 'int'
      `-IntegerLiteral <col:7> 'int' 2

What to notice: both statements start with the identifier L, so $\mathrm{LA}_1$ of labeled-statement and expression-statement overlap; their $\mathrm{LA}_2$ sets do not ($\{\mathtt{id}\ {:}\}$ versus $\{\mathtt{id}\ {=}, \dots\}$). Parser::ParseStatementOrDeclarationAfterAttributes peeks with Token Next = NextToken(); if (Next.is(tok::colon)) and produces a LabelStmt or an expression [CLANG-ParseStmt]: a hand-coded strong LL(2) decision, with no table.

Full (canonical) LL(k)¶

Definition 2.6.5 (Local follow sets)

A context is a pair $(A, L)$ of a nonterminal and a set $L$ of $k$-strings. $(S, \{\$\})$ is reachable; if $(B, L')$ is reachable and $B \to \beta A \gamma \in P$, then $(A, \mathrm{FIRST}_k(\gamma) \oplus_k L')$ is reachable. $L$ is a local follow set of $A$. The LL(k) table of a context is $T_{A,L}[x] \triangleq \{\, A \to \alpha \mid x \in \mathrm{FIRST}_k(\alpha) \oplus_k L \,\}$. Every local follow set of $A$ is a subset of $\mathrm{FOLLOW}_k(A)$.

Algorithm 2.6.6 (LLkTables)

Input: $G$, $k$.
Output: the reachable contexts and their tables, or a conflict.
Precondition: none.
Postcondition: contexts is exactly the set of reachable contexts; $G$ is LL(k) iff no $T_{A,L}[x]$ has two productions (Theorem 2.6.13, for reduced $G$).
Invariant: every context in contexts is reachable (Definition 2.6.5); every reachable context popped from work has had all its successors added.

Oracles: llk_contexts, full_llk_conflicts, min_full_k. Parsing pushes $(A, L)$ pairs instead of bare nonterminals.

function LLkTables(G, k):
    F ← FirstK(G, k)
    contexts ← {(S, {$})};  work ← [(S, {$})]
    while work is not empty:
        (A, L) ← pop work
        for each alternative p = A → X1 … Xm:
            T_{A,L}[x] ← T_{A,L}[x] ∪ {p}  for every x ∈ FirstOfK(X1 … Xm, F) ⊕k L
            for each i with Xi ∈ N:
                L′ ← FirstOfK(Xi+1 … Xm, F) ⊕k L                # local follow of this occurrence
                if (Xi, L′) ∉ contexts: add it to contexts and work
    G is LL(k) iff no T_{A,L}[x] has two productions

ANTLR 4 uses the caller's context only when it must

Reproduce (ANTLR 4.13.2 complete jar, OpenJDK 21.0.10):

cat > SllLl.g4 <<'EOF'
grammar SllLl;
s  : 'x' b 'c' 'd' | 'y' b 'd' ;
b  : 'c' | ;
WS : [ \t\r\n]+ -> skip ;
EOF
java -jar antlr-4.13.2-complete.jar SllLl.g4
javac -cp antlr-4.13.2-complete.jar SllLl*.java
for input in 'x c d' 'y c d' 'x c c d'; do
  echo "== $input"
  echo "$input" | java -cp antlr-4.13.2-complete.jar:. org.antlr.v4.gui.TestRig SllLl s -tree -diagnostics
done

Output (complete):

== x c d
line 1:4 reportAttemptingFullContext d=1 (b), input='cd'
line 1:4 reportContextSensitivity d=1 (b), input='cd'
(s x b c d)
== y c d
line 1:4 reportAttemptingFullContext d=1 (b), input='cd'
line 1:2 reportContextSensitivity d=1 (b), input='c'
(s y (b c) d)
== x c c d
(s x (b c) c d)

What to notice: this is sll-vs-ll from §3. It is LL(2) but not strong LL(k) for any $k$: $\mathrm{FOLLOW}_k(B)$ merges the two occurrences of $b$, and the remaining input c d is compatible with both alternatives in the merged view. reportAttemptingFullContext is ANTLR noticing that context-free lookahead cannot decide decision d=1 (rule b) on cd; reportContextSensitivity reports that the local follow set did decide it, after 2 tokens after x and after 1 token after y [ANTLR4-PATN]. That is Algorithm 2.6.6's $T_{B,\{cd\}}$ and $T_{B,\{d\$\}}$, computed lazily for the one context that occurs. On x c c d the context-free lookahead suffices.

LL(*)¶

Definition 2.6.7 (Configurations, closure, SLL and LL contexts)

A configuration is a pair $(i, \sigma)$ of an alternative number $i$ of the decision nonterminal $A$ and a stack $\sigma$: the string of grammar symbols still to be matched, possibly ending in a return marker $\uparrow X$ ("continue after some occurrence of $X$"). Closure expands a leading nonterminal into each of its alternatives and replaces a leading $\uparrow X$ by $\gamma\, \uparrow Y$ for every occurrence $Y \to \beta X \gamma$ (and by $\$$ if $X = S$). In SLL mode the decision starts from $(i, \alpha_i\, \uparrow A)$, so returning from $A$ continues into every caller; in LL mode it starts from $(i, \alpha_i\, \gamma)$ with $\gamma$ the parser's actual stack. A configuration set has a conflict when every stack in it is shared by two or more alternatives: then no further input can separate them.

Algorithm 2.6.8 (LLStarDFA)

Input: a decision nonterminal $A$, a stack bound max_stack.
Output: a DFA whose accept states name alternatives, or failure ("not LL-regular").
Precondition: $G$ has no left recursion (otherwise Closure does not terminate).
Postcondition: on success, running the DFA on the input from the decision point predicts the alternative an LL parser must take whenever it reaches an accept state (Theorem 2.6.16).
Invariant: a DFA state reached by input $u$ is the set of configurations $(i, \sigma)$ such that alternative $i$ can match $u$ followed by something matching $\sigma$ (Lemma 2.6.15).

Oracle: llstar_dfa. Closure is shared with ALL(*) below.

function LLStarDFA(G, A, max_stack):
    D0 ← Closure({ (i, αi ↑A) : A → αi is the i-th alternative })
    states ← [D0];  work ← [D0]
    while work is not empty:
        D ← pop work
        if all configurations of D have one alternative i: mark D "predict i";  continue
        if every stack in D is shared by ≥ 2 alternatives: mark D "conflict";  continue
        if some stack in D is longer than max_stack: fail "not LL-regular"    # fall back
        for each terminal t that begins some stack of D:
            E ← Closure({ (i, rest) : (i, t rest) ∈ D })
            if E ∉ states: append E to states and work
            add the edge D --t--> E
    return the DFA

function Closure(configs):                          # SLL context: ↑X returns to every caller of X
    result ← {};  work ← configs;  seen ← {}
    while work is not empty:
        (i, st) ← pop work;  if (i, st) ∈ seen: continue;  seen ← seen ∪ {(i, st)}
        if st starts with a nonterminal B: push (i, β · rest(st)) for every B → β
        else if st starts with ↑X:
            if X = S: push (i, $)
            for every occurrence Y → β X γ: push (i, γ · ↑Y)
        else: result ← result ∪ {(i, st)}                # starts with a terminal, $ or is empty
    return result

ANTLR 3: an LL(*) lookahead DFA, and a decision it refuses

Reproduce (ANTLR 3.5.2 complete jar, from the ANTLR 3 website's download page; OpenJDK 21.0.10):

cat > LLStar.g <<'EOF'
grammar LLStar;
s : x 'c' | x 'd' ;
x : 'a' x | 'b' ;
EOF
cat > LLStarLoop.g <<'EOF'
grammar LLStarLoop;
s : x 'c' | x 'd' ;
x : 'a'* 'b' ;
EOF
java -jar antlr-3.5.2-complete.jar LLStar.g
java -jar antlr-3.5.2-complete.jar -dfa LLStarLoop.g && cat LLStarLoop.dec-1.dot

Output (complete; the first command exits with status 1):

error(211): LLStar.g:2:3: [fatal] rule s has non-LL(*) decision due to recursive rule invocations reachable from alts 1,2.  Resolve by left-factoring or using syntactic predicates or using backtrack=true option.
digraph NFA {
rankdir=LR;
node [fontsize=11, shape = circle, fixedsize=true, width=.4]; "s0"
node [fontsize=11, shape = circle, fixedsize=true, width=.4]; "s1"
node [fontsize=11, shape = circle, fixedsize=true, width=.4]; "s2"
node [fontsize=11, shape = doublecircle, fixedsize=true, width=.6]; "s3=>1"
node [fontsize=11, shape = doublecircle, fixedsize=true, width=.6]; "s4=>2"
"s0" -> "s1" [fontsize=11, fontname="Courier", arrowsize=.7, label = "'a'", arrowhead = normal];
"s1" -> "s2" [fontsize=11, fontname="Courier", arrowsize=.7, label = "'b'", arrowhead = normal];
"s2" -> "s3=>1" [fontsize=11, fontname="Courier", arrowsize=.7, label = "'c'", arrowhead = normal];
"s2" -> "s4=>2" [fontsize=11, fontname="Courier", arrowsize=.7, label = "'d'", arrowhead = normal];
"s1" -> "s1" [fontsize=11, fontname="Courier", arrowsize=.7, label = "'a'", arrowhead = normal];
"s0" -> "s2" [fontsize=11, fontname="Courier", arrowsize=.7, label = "'b'", arrowhead = normal];
}

What to notice: the first grammar is llstar from §3. Algorithm 2.6.8 builds a 4-state DFA for it because its stacks are symbol strings: after a, the configuration $(1, X\, c\, \uparrow S)$ closes back to the start state, since the tail call $X$ at the end of $a\, X$ leaves nothing behind. ANTLR 3's configurations carry return-address stacks instead, so each recursive call of x pushes a new frame, the configuration sets never repeat, and NFAToDFAConverter [ANTLR3-NFAToDFA] stops with error 211 [PF11]. Written as an EBNF loop, the same language gives the cyclic DFA above: s1 -a-> s1 scans any number of as, and the accept states s3=>1 and s4=>2 predict alternative 1 on c and 2 on d, as in §3.

ALL(*)¶

Algorithm 2.6.9 (AdaptivePredict)

Input: decision $A$, the remaining input $t_1 t_2 \cdots$, the parser's stack $\gamma$ below $A$.
Output: an alternative (and, on a true ambiguity, a report).
Precondition: $G$ has no left recursion.
Postcondition: the prediction is an alternative that can derive the remaining input in context $\gamma$ whenever one exists; if two can, the minimum is returned and reported (Theorem 2.6.17).
Invariant: after reading $k$ tokens, $D$ is the set of configurations consistent with $t_1 \cdots t_k$: for every caller in SLL mode, for $\gamma$ in LL mode.

Oracles: adaptive_predict, all_star_predict. ANTLR 4 caches the SLL states as a DFA per decision; the oracle recomputes them.

function AdaptivePredict(A, input, γ):
    r ← Simulate(A, input, context = none)           # stage 1: SLL
    if r is an alternative: return r
    r ← Simulate(A, input, context = γ)              # stage 2: full LL, only after an SLL conflict
    return r's alternative (on a conflict: the minimum alternative, and report an ambiguity)

function Simulate(A, input, context):
    if context = none: D ← Closure({ (i, αi ↑A) })     # SLL: ↑ continues into every caller
    else:              D ← Closure({ (i, αi γ) })      # LL: the real stack (ending in $)
    for k ← 1, 2, …:
        t ← input[k]
        D ← Closure({ (i, rest) : (i, t rest) ∈ D })
        if D is empty: return error
        if all configurations of D have one alternative i: return (i, k)
        if every stack in D is shared by ≥ 2 alternatives: return (conflict, k)

ANTLR 4: SLL alone is not enough

Reproduce (ANTLR 4.13.2, OpenJDK 21.0.10; the SllLl parser compiled in the "Full (canonical) LL(k)" box above):

echo 'x c d' | java -cp antlr-4.13.2-complete.jar:. org.antlr.v4.gui.TestRig SllLl s -tree -SLL
echo 'x c d' | java -cp antlr-4.13.2-complete.jar:. org.antlr.v4.gui.TestRig SllLl s -tree

Output (complete):

line 1:4 missing 'c' at 'd'
(s x (b c) <missing 'c'> d)
(s x b c d)

What to notice: with -SLL the parser runs only stage 1 of Algorithm 2.6.9 (PredictionMode.SLL [ANTLR4-PredictionMode]). The SLL simulation for b on c d ends in a conflict (both alternatives reach the stack $, §3), and SLL resolves it to the minimum alternative b : 'c', which is wrong in this context: the parser then misses the second c and repairs the input (Lesson 2.7). The default mode retries with full context and predicts $B \to \varepsilon$. This is why ANTLR's recommended two-stage strategy reparses with PredictionMode.LL whenever the SLL pass reports a syntax error [PHF14].

3. Worked example¶

Running example. Three small grammars from the corpus, one per rung of the ladder (all in tests/ch02/Inputs):

strong-vs-full:  (1) S → a A a a   (2) S → b A b a   (3) A → b   (4) A → ε
llstar:          (1) S → X c       (2) S → X d       (3) X → a X  (4) X → b
sll-vs-ll:       (1) S → x B c d   (2) S → y B d     (3) B → c    (4) B → ε

Strong LL(k) on the running example¶

strong-vs-full, decision $A$ (oracle strong_llk_lookahead; $k$-strings written without spaces):

k	FIRST_k(A)	FOLLOW_k(A)	LA(3) A → b	LA(4) A → ε	shared
1	{b, ε}	{a, b}	{b}	{a, b}	b
2	{b, ε}	{aa, ba}	{ba, bb}	{aa, ba}	ba
3	{b, ε}	{aa$, ba$}	{baa, bba}	{aa$, ba$}	none

$\mathrm{FOLLOW}_2(A)$ collects aa from (1) (what follows $A$ there, then $ cut off at 2) and ba from (2). The union mixes the two contexts: in context (1), $A \to b$ would be followed by a a, so its lookahead is ba; $A \to \varepsilon$ in context (2) sees b a too. Strong LL(2) cannot tell them apart, so the grammar is strong LL(3) but not strong LL(2).

Full (canonical) LL(k) on the running example¶

The same grammar with $k = 2$ (oracle llk_contexts, full_llk_conflicts):

step	context popped	occurrence	new context
1	(S, {$})	(1) S → a A a a: L′ = FIRST_2(a a) ⊕2	(A, {aa})
2	(S, {$})	(2) S → b A b a: L′ = FIRST_2(b a) ⊕2	(A, {ba})
3	(A, {aa})	no nonterminals on the right	—
4	(A, {ba})	no nonterminals on the right	—

table	A → b	A → ε	conflict?
T_{A,{aa}}	{ba}	{aa}	no
T_{A,{ba}}	{bb}	{ba}	no

Both tables are conflict-free: the grammar is LL(2). Parsing b b a pushes $(A, \{ba\})$ after $S \to b\, A\, b\, a$; the lookahead ba selects $A \to \varepsilon$ in $T_{A,\{ba\}}$, where the strong table saw a conflict. (sll-vs-ll is more extreme: it is LL(2), but $\mathrm{LA}_k(B \to c)$ and $\mathrm{LA}_k(B \to \varepsilon)$ both contain $(c\,d\,\$){:}k$ for every $k$, so it is not strong LL(k) for any $k$; min_strong_k finds none.)

LL(*) on the running example¶

llstar is not LL(k) for any $k$ (min_full_k finds none up to 4: $a^{k} b\, c$ and $a^{k} b\, d$ share every prefix of length $k$). Its lookahead DFA for decision $S$ (oracle llstar_dfa):

state	configurations	edges	accepts
D0	(1, a X c ↑S) (1, b c ↑S) (2, a X d ↑S) (2, b d ↑S)	a → D0, b → D1	—
D1	(1, c ↑S) (2, d ↑S)	c → D2, d → D3	—
D2	(1, $)	—	alternative 1
D3	(2, $)	—	alternative 2

Moving D0 on a gives (1, X c ↑S) and (2, X d ↑S), whose closure is D0 again: the cycle is what lets LL(*) scan any number of as.

flowchart LR
  D0((D0)) -->|a| D0
  D0 -->|b| D1((D1))
  D1 -->|c| D2(["D2: predict 1"])
  D1 -->|d| D3(["D3: predict 2"])

The same construction on tests/ch02/Inputs/ambiguous-ab.grammar ($S \to a\, S \mid a\, S\, b \mid \varepsilon$) never stops adding bs to the stacks: its lookahead is not regular, llstar_dfa gives up ("recursion in the lookahead"), and ANTLR 3 would fall back to backtracking.

ALL(*) on the running example¶

sll-vs-ll, decision $B$ after the parser has consumed x; remaining input c d $; real stack below $B$: c d $.

Stage 1, SLL (oracle adaptive_predict(..., mode="SLL")):

k	token	configurations
0	—	(1, c ↑B) (2, c d ↑S) (2, d ↑S)
1	c	(1, c d ↑S) (1, d ↑S) (2, d ↑S)
2	d	(1, $) (2, $)

At $k = 0$, alternative 2 ($B \to \varepsilon$) is at ↑B, which returns into both occurrences of $B$: before c d (from $S \to x\, B\, c\, d$) and before d (from $S \to y\, B\, d$). At $k = 2$ both alternatives reach the identical configuration stack $: an SLL conflict, although the input is not ambiguous. Stage 2, full LL with the real stack:

k	token	configurations
0	—	(1, c c d $) (2, c d $)
1	c	(1, c d $) (2, d $)
2	d	(2, $)

Only alternative 2 survives: $B \to \varepsilon$, after 2 tokens. With the other caller (after y, stack d $) the same remaining input c d $ is predicted as alternative 1 after one token by LL, while SLL, which ignores the caller, conflicts exactly as before. ANTLR 4 reports exactly these two outcomes (input='cd' and input='c', real-world box in §2). For llstar's decision $S$ on a a b d $, SLL alone predicts alternative 2 after 4 tokens, and ANTLR 4 caches the states it built as a DFA like the one above.

Try it

./course drill lookahead --seed 2 --difficulty hard (SLL vs LL on a fresh instance); --difficulty easy asks for strong LL(k) sets, medium for an ALL(*) prediction at the start symbol.

4. Invariants and correctness¶

Strong LL(k)¶

Lemma 2.6.10 (FIRST$_k$ and FOLLOW$_k$ are least fixed points)

The loops of Algorithm 2.6.4 terminate and compute $\mathrm{FIRST}_k$ and $\mathrm{FOLLOW}_k$ of Definition 2.6.2.

Proof

The sets of $k$-strings over $T \cup \{\$\}$ form a finite lattice under $\subseteq$, and each update is a union with an expression built from $\oplus_k$, which is monotone (Definition 2.6.1). So Theorem 2.2.4 applies: the iteration from the empty sets reaches the least fixed point within the lattice height. That this fixed point is the derivational set is proved exactly like Theorem 2.2.5, replacing "first token" by "first $k$ tokens": a derivation $A \Rightarrow A \to X_1 \cdots X_m \Rightarrow^{*} w$ splits $w = w_1 \cdots w_m$, and $w{:}k = w_1{:}k \oplus_k \cdots \oplus_k w_m{:}k$.

Theorem 2.6.11 (Strong LL(k) grammars are LL(k))

If $G$ is strong LL(k), then it is LL(k), and the predictive parser that chooses, for top $A$ and lookahead $x = t_{i+1} \cdots t_{i+k}{:}k$, the unique alternative $p$ with $x \in \mathrm{LA}_k(p)$, parses exactly $L(G)$.

Proof

Take two derivations as in Definition 2.6.3 with $x{:}k = y{:}k = z$. As in Lemma 2.3.7(a), $z \in \mathrm{FIRST}_k(\alpha\gamma) \subseteq \mathrm{FIRST}_k(\alpha) \oplus_k \mathrm{FIRST}_k(\gamma)$, and $\mathrm{FIRST}_k(\gamma) \subseteq \mathrm{FOLLOW}_k(A)$ because $\gamma$ follows $A$ in a sentential form; so $z \in \mathrm{LA}_k(A \to \alpha)$, and likewise $z \in \mathrm{LA}_k(A \to \beta)$. Disjointness forces $\alpha = \beta$. The parser claim is Theorem 2.5.9 with $k$-token lookahead: the unique alternative whose set contains $z$ is the one the leftmost derivation uses.

Theorem 2.6.12 (Strong LL(1) = LL(1); strong LL(k) ⊊ LL(k) for k ≥ 2 [RS70])

(a) A reduced grammar is strong LL(1) iff it is LL(1). (b) For every $k \ge 2$ the grammar

\[ G_k:\quad S \to a\, A\, a^{k} \mid b\, A\, b\, a^{k-1}, \qquad A \to b \mid \varepsilon \]

is LL(2), hence LL(k), but not strong LL(k).

Proof

(a) For $k = 1$, $\mathrm{FIRST}_1(\alpha) \oplus_1 \mathrm{FOLLOW}_1(A)$ is $\mathrm{FIRST}(\alpha)$ if $\alpha$ is not nullable and $\mathrm{FIRST}(\alpha) \cup \mathrm{FOLLOW}(A)$ if it is: exactly $\mathrm{PREDICT}(A \to \alpha)$ (Definition 2.3.1). So strong LL(1) says the PREDICT sets of each nonterminal's alternatives are pairwise disjoint, i.e. the LL(1) table has no conflict, which is equivalent to LL(1) by Theorem 2.3.8.

(b) Contexts. $A$ occurs twice, with local follow sets $L_1 = \{a^{k}\}{:}2 = \{aa\}$ and $L_2 = \{b\, a^{k-1}\}{:}2 = \{ba\}$ for $k = 2$ (and their $k$-prefixes in general). LL(2): in context 1, $A \to b$ has lookahead $\{ba\}$ and $A \to \varepsilon$ has $\{aa\}$; in context 2, $\{bb\}$ and $\{ba\}$; the decision on $S$ is made by the first token. All tables are conflict-free, so $G_k$ is LL(2) by Theorem 2.6.13, and an LL(2) grammar is LL(k) for $k \ge 2$ (equal $k$-prefixes have equal 2-prefixes). Not strong LL(k): $\mathrm{FOLLOW}_k(A) = \{a^{k}, b\, a^{k-1}\}$, so $\mathrm{LA}_k(A \to b) \ni b \oplus_k a^{k} = b\, a^{k-1}$ and $\mathrm{LA}_k(A \to \varepsilon) \ni b\, a^{k-1}$: the sets intersect. For $k = 2$, $G_2$ is the strong-vs-full grammar of §3.

Full (canonical) LL(k)¶

Theorem 2.6.13 (LL(k) ⟺ conflict-free local tables [RS70])

Let $G$ be reduced. Algorithm 2.6.6 terminates; $G$ is LL(k) iff every table $T_{A,L}$ of a reachable context is conflict-free; and the parser that stacks $(A, L)$ pairs and consults $T_{A,L}$ parses exactly $L(G)$.

Proof sketch (full proof: [RS70]; [AU72, §5.1])

Termination: there are finitely many pairs $(A, L)$, and each is added at most once. Soundness of contexts: by induction, $(A, L)$ is reachable iff some left-sentential form $w A \gamma$ has $\mathrm{FIRST}_k(\gamma\,\$) = L$, because the local follow set of an occurrence is computed from what follows it in its production and the local follow set of the parent. Equivalence: with $L = \mathrm{FIRST}_k(\gamma\,\$)$ known exactly, the argument of Theorem 2.3.8 applies verbatim with $k$-prefixes: two alternatives are both viable for the same lookahead in the same left-sentential form iff their sets $\mathrm{FIRST}_k(\alpha) \oplus_k L$ intersect. The parser keeps the exact $L$ on its stack, so its choice is the one Definition 2.6.3 requires.

Proposition 2.6.14 (More lookahead is strictly more powerful)

For every $k \ge 1$ the grammar $S \to a^{k}\, b \mid a^{k}\, c$ is LL(k+1) but not LL(k); and there are languages that have an LL(k+1) grammar but no LL(k) grammar.

Proof (grammar part below; language part: [Kur69])

Both alternatives have $\mathrm{FIRST}_k = \{a^{k}\}$ and $\mathrm{FOLLOW}_k(S) = \{\$\}$, so the only table conflicts at $a^{k}$; with $k + 1$ tokens the sets $\{a^{k}b\}$ and $\{a^{k}c\}$ are disjoint. (Left factoring makes this language LL(1), which is why the language statement needs a subtler family; Kurki-Suonio constructs one.)

When it breaks: the number of contexts can be exponential in $k$ and $\lvert T \rvert$ (§5), which is why this is theory more than practice.

LL(*)¶

Lemma 2.6.15 (DFA state invariant)

A state $D$ of Algorithm 2.6.8 reached from $D_0$ by input $u$ contains a configuration $(i, \sigma)$, with $\sigma$ starting with a terminal or ending the decision, iff alternative $i$ derives $u \sigma'$ for some $\sigma'$ with the SLL continuation $\sigma$ (every caller allowed at return markers).

Proof

By induction on $\lvert u \rvert$. For $u = \varepsilon$, Closure of the initial configurations enumerates the leftmost expansions of each $\alpha_i\, \uparrow A$ until a terminal or $ is exposed; return markers are expanded into every occurrence, which is the SLL over-approximation of the context. A move on $t$ keeps exactly the configurations whose stack starts with $t$ and removes it; closing again restores the "starts with a terminal" form.

Theorem 2.6.16 (LL(*) prediction)

If Algorithm 2.6.8 succeeds, then for every input on which the DFA reaches an accept state "predict $i$", alternative $i$ is the only alternative that can derive the input read so far in any context, so an LL parser must choose it. The construction terminates iff finitely many distinct configuration sets arise; the stack bound makes it total, at the price of rejecting some decisions.

Proof sketch (full treatment: [PF11])

By Lemma 2.6.15, an accept state for $i$ means no configuration of another alternative is consistent with the input read, even in the over-approximated SLL context; the real context is one of those considered, so predicting $i$ is sound. Subset construction terminates iff the set of reachable configuration sets is finite, which holds when the lookahead language of the decision is regular and the stacks stay bounded; recursion in the lookahead (as in ambiguous-ab) makes the stacks grow without bound, and the bound turns that into a failure instead of non-termination.

When it breaks: recursion in the lookahead, decisions that need the caller's context (SLL's over-approximation reports a conflict), and implementations whose stacks record return addresses: ANTLR 3 rejects llstar although this algorithm accepts it (real-world box in §2).

ALL(*)¶

Theorem 2.6.17 (Correctness of adaptive prediction [PHF14])

For a non-left-recursive $G$, (a) if the SLL stage returns a single alternative, it is the correct prediction; (b) if the LL stage returns a single alternative, it is the correct prediction; (c) if the LL stage ends in a conflict and the remaining input is a valid continuation, it is genuinely ambiguous at this decision (two alternatives derive it in the actual context), and returning the minimum alternative yields a valid parse; if it is not, the syntax error surfaces later with either choice. Hence a parser using AdaptivePredict at every decision recognizes exactly $L(G)$.

Proof sketch (full proof: [PHF14])

(a) The SLL configuration set over-approximates the LL one (Lemma 2.6.15 with every caller allowed), so if only alternative $i$ survives in SLL, only $i$ can survive in LL. (b) In LL mode the configurations are exact: they are the ways each alternative can continue in the parser's real stack, so a single survivor is the only viable alternative. (c) A conflict in LL mode means two alternatives reach an identical stack after consuming the same input; from there every continuation of one is a continuation of the other, so if the remaining input can be derived at all, both alternatives derive it: an ambiguity, for which the minimum alternative is as valid as any. Termination: each step consumes a token, and without left recursion the closure of a finite set is finite.

When it breaks: left recursion (closure loops; ANTLR rewrites direct left recursion, Lesson 2.4) and side-effecting actions inside predicates. SLL alone is sound only when it does not report a conflict (real-world box in §2).

5. Complexity¶

Variables: $k$ lookahead, $\lvert T \rvert$ terminals, $\lvert N \rvert$ nonterminals, $\lvert G \rvert$ grammar size, $n$ input length, $\tau = \lvert T \rvert + 1$.

Technique	Time (worst)	Time (typical)	Space	Variables
Strong LL(k)	sets of up to $\tau^{k}$ strings: $O(\lvert G \rvert \cdot \tau^{2k})$ per pass	$k = 2$ or $3$ is manageable	table $\lvert N \rvert \cdot \tau^{k}$	as above
Full LL(k)	up to $\lvert N \rvert \cdot 2^{2\tau^{k}}$ contexts (Proposition 2.6.18)	rarely built	one table per context	as above
LL(*)	subset construction: exponential in the number of configurations; may not terminate without the bound	small DFAs for most decisions	per-decision DFA	—
ALL(*)	$O(n^{4})$ per parse [PHF14]	linear in practice: DFA cache hits	DFA cache grows with the input seen	$n$

Proposition 2.6.18 (Size of the lookahead objects)

There are at most $\sum_{j=0}^{k} \tau^{j} \le 2\tau^{k}$ distinct $k$-strings, so each $\mathrm{FIRST}_k$/$\mathrm{FOLLOW}_k$ set and each strong table row has $O(\tau^{k})$ entries, and one $\oplus_k$ of two such sets costs $O(\tau^{2k})$; there are at most $\lvert N \rvert \cdot 2^{2\tau^{k}}$ contexts $(A, L)$.

Proof

A $k$-string is a string of length $j \le k$ over at most $\tau$ symbols: $\sum_{j \le k} \tau^{j}$ choices, which is at most $2 \tau^{k}$ for $\tau \ge 2$. $\oplus_k$ of two sets computes one concatenation per pair. A context is a nonterminal and a subset of the $k$-strings.

Pathological input: for llstar, any fixed-$k$ method fails for every $k$, because $a^{k} b\, c$ and $a^{k} b\, d$ agree on their first $k$ symbols; LL(*) handles it with a 4-state DFA, and a single ALL(*) prediction reads the whole $a$-run ($k = n + 2$ tokens for $a^{n} b\, c/d$). For ALL(*), grammars that force full-LL re-simulation at every decision (every decision SLL-conflicts) lose the DFA cache's benefit.

At scale: Parr, Harwell and Fisher report linear time and space behavior on grammars for 12 programming languages, and that ALL(*) is orders of magnitude faster than general (GLL/GLR) parsers on the same grammars [PHF14]. The same paper recommends the two-stage strategy (parse with SLL, and only after a syntax error reparse with full LL), because SLL alone suffices for almost all real inputs [PHF14].

Strong LL(k)¶

Linear approximate lookahead [Par93] (ANTLR 2): store, for each alternative, $k$ sets of tokens (position by position) instead of sets of $k$-strings — trade-off: $O(k \tau)$ instead of $\tau^{k}$, but more conflicts (it forgets which tokens go together).
Local lookahead in hand-written parsers: NextToken() at the few places that need $k = 2$ (real-world box in §2) — trade-off: no generator and no table, but the grammar's LL(2) spots are only documented in code.

Full (canonical) LL(k)¶

LL(k) → strong LL(k) by splitting nonterminals [RS70; AU72 §5.1]: duplicate $A$ per local follow set so that $\mathrm{FOLLOW}_k$ becomes exact — trade-off: the grammar grows with the number of contexts.
LL(k) with syntactic predicates [PQ95]: try a sub-parse to decide — trade-off: arbitrary lookahead, but backtracking cost.

LL(*)¶

Backtracking fallback with memoization (ANTLR 3, [PF11]): when the DFA analysis fails, try alternatives in order with a memoized sub-parse — trade-off: always works, but loses linear-time guarantees.
Semantic predicates in the DFA (ANTLR 3 "hoisting"): predicates participate in prediction — trade-off: context-sensitive decisions, but the analysis must reason about code.

ALL(*)¶

Two-stage parsing (ANTLR 4 PredictionMode.SLL + BailErrorStrategy, then PredictionMode.LL on failure): parse the whole file with SLL, and only if that fails, reparse with LL — trade-off: fastest for valid input; an invalid file is parsed twice (real-world box in §2).
Exact ambiguity detection (PredictionMode.LL_EXACT_AMBIG_DETECTION [ANTLR4-PredictionMode]): keep simulating until the full set of ambiguous alternatives is known — trade-off: precise diagnostics for grammar authors, slower prediction.

7. In real compilers¶

Strong LL(k)¶

Clang (LLVM 23.1.2) uses fixed extra lookahead where the grammar needs $k = 2$: clang/lib/Parse/ParseStmt.cpp — Parser::ParseStatementOrDeclarationAfterAttributes peeks with NextToken() to see whether an identifier is followed by : (a label; real-world box in §2) [CLANG-ParseStmt]; clang/include/clang/Parse/Parser.h — Parser::GetLookAheadToken(unsigned N) peeks N tokens [CLANG-Parser].
rustc compiler/rustc_parse/src/parser/mod.rs — Parser::look_ahead(dist, …) (Rust 1.90.0) is the same $k$-token peek, used throughout the statement and item parsers [RUSTC-Parser].
JavaCC: LOOKAHEAD(k) (global option or per choice point) generates code that compares the next $k$ tokens.

Full (canonical) LL(k)¶

No production tool builds canonical LL(k) tables: the table count explodes and the same power is available more cheaply with predicates, LL(*) or ALL(*). Its role is theoretical: it defines the class that strong LL(k), LL(*) and ALL(*) are measured against. Its closest production relative is ALL(*)'s full-context stage, which consults the one local context that actually occurs instead of tabulating all of them (real-world box in §2; execATNWithFullContext in [ANTLR4-PATN]).

LL(*)¶

ANTLR 3 tool/src/main/java/org/antlr/analysis/NFAToDFAConverter.java — NFAToDFAConverter.convert and reach (ANTLR 3.5.2): the subset construction of §2 over the grammar's NFA, with recursion-depth limits and a fallback to syntactic predicates (real-world box in §2) [ANTLR3-NFAToDFA].
Clang's tentative parsing plays the same role by hand: clang/lib/Parse/ParseTentative.cpp — Parser::isCXXDeclarationStatement scans arbitrarily far ahead and returns a TPResult (True, False, Ambiguous, Error), like a lookahead DFA's accept states [CLANG-ParseTentative].

ALL(*)¶

ANTLR 4 runtime/Java/src/org/antlr/v4/runtime/atn/ParserATNSimulator.java (4.13.2): adaptivePredict (entry and DFA cache), execATN (SLL simulation), execATNWithFullContext (the LL stage, entered after reportAttemptingFullContext), computeReachSet and closure [ANTLR4-PATN]; atn/PredictionMode.java defines SLL, LL and LL_EXACT_AMBIG_DETECTION and the conflict tests (hasSLLConflictTerminatingPrediction, resolvesToJustOneViableAlt) [ANTLR4-PredictionMode]; BailErrorStrategy.java supports two-stage parsing.
ANTLR 4 runtimes for C++, Python, Go, JavaScript, Swift and others port the same simulator; grammars in the antlr/grammars-v4 repository (Java, C#, SQL dialects, …) run on it.

Find where LLVM does it. Open clang/lib/Parse/ParseTentative.cpp (LLVM 23.1.2) and find Parser::isCXXDeclarationStatement. Question: what is the name of the enumeration type that the TryParse… helpers return to say "declaration", "expression", "ambiguous" or "error"? (quiz clang-tentative-result)

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Strong LL(k)	Strong LL(k) grammars; = LL(1) at k = 1, strictly weaker than LL(k) for k ≥ 2	\|T\|^k-size sets · fine for k ≤ 3	Like LL(1): the conflicting k-strings are reported	Medium	JavaCC LOOKAHEAD(k); hand-coded k = 2 peeks (Clang, rustc)
Full (canonical) LL(k)	All LL(k) grammars; LL(k) ⊊ LL(k+1)	Exponentially many tables · impractical	Exact	High	Theory; defines the class others approximate
LL(*)	Decisions with regular lookahead, plus predicate/backtracking fallback	Static analysis may blow up; parsing is linear with the DFAs	Good; analysis warnings for non-LL(*) decisions	High	ANTLR 3
ALL(*)	Every non-left-recursive CFG (ambiguities resolved to the minimum alternative)	O(n⁴) worst · linear in practice with DFA caching	Good; reports real ambiguities at run time	Very high (runtime ATN simulation)	ANTLR 4 in all its target languages

Choose strong LL(k) with small $k$ when only a few decisions need a second token: hand-code the peek (as Clang and rustc do) or set a local LOOKAHEAD(2). Choose full LL(k) never in practice; use it to reason about what a grammar needs. Choose LL(*) when you are on ANTLR 3 or want static guarantees for regular lookahead. Choose ALL(*) when you want to write the grammar naturally and let the tool decide at run time; accept the larger runtime and the fact that ambiguities are only discovered on inputs that exhibit them.

9. Assessment¶

Technique	Quiz ids (`solutions/quizzes/ch02.yaml`)	Drill	Flashcard tag	Exercises
Strong LL(k)	`llk-min-k`, `full-llk-contexts`	`./course drill lookahead --difficulty easy`	`strong-llk`	— (theory + oracle)
Full LL(k)	`llk-min-k`, `full-llk-contexts`	`./course drill lookahead --difficulty easy` (asks `full-k`; half the instances separate it from strong k)	`full-llk`	—
LL(*)	`llstar-dfa`, `sll-vs-ll`	`./course drill lookahead --difficulty medium`	`llstar`	—
ALL(*)	`sll-vs-ll`, `clang-tentative-result`	`./course drill lookahead --difficulty hard`	`all-star`	—

An SLL conflict is not an ambiguity

SLL forgets who called the rule, so two alternatives can merge even when the real context would separate them (the running example); only a conflict under full LL context means the input really has two parses (Theorem 2.6.17). Conversely, trusting SLL's minimum-alternative choice without the LL retry produces wrong parses (real-world box in §2).

References¶

See the chapter references.

Technique	Time (worst)	Time (typical)	Space	Variables
Strong LL(k)	sets of up to \(\tau^{k}\) strings: \(O(\lvert G \rvert \cdot \tau^{2k})\) per pass	\(k = 2\) or \(3\) is manageable	table \(\lvert N \rvert \cdot \tau^{k}\)	as above
Full LL(k)	up to \(\lvert N \rvert \cdot 2^{2\tau^{k}}\) contexts (Proposition 2.6.18)	rarely built	one table per context	as above
LL(*)	subset construction: exponential in the number of configurations; may not terminate without the bound	small DFAs for most decisions	per-decision DFA	—
ALL(*)	\(O(n^{4})\) per parse [PHF14]	linear in practice: DFA cache hits	DFA cache grows with the input seen	\(n\)

Lesson 2.6 — More lookahead: LL(k), LL(*) and ALL(*)¶

1. Problem and motivation¶

Strong LL(k)¶

Full (canonical) LL(k)¶

LL(*)¶

ALL(*)¶

2. Definitions and algorithms¶

Strong LL(k)¶

Full (canonical) LL(k)¶

LL(*)¶

ALL(*)¶

3. Worked example¶

Strong LL(k) on the running example¶

Full (canonical) LL(k) on the running example¶

LL(*) on the running example¶

ALL(*) on the running example¶

4. Invariants and correctness¶

Strong LL(k)¶

Full (canonical) LL(k)¶

LL(*)¶

ALL(*)¶

5. Complexity¶

6. Variants and refinements¶

Strong LL(k)¶

Full (canonical) LL(k)¶

LL(*)¶

ALL(*)¶

7. In real compilers¶

Strong LL(k)¶

Full (canonical) LL(k)¶

LL(*)¶

ALL(*)¶

8. Comparison¶

9. Assessment¶

References¶

Lesson 2.6 — More lookahead: LL(k), LL() and ALL()¶