Proofs: LL(*) parsing

ALL-STAR-PARSE accepts exactly the sentences of a grammar without left recursion, returns their parse trees and reports errors at the first token that no sentence allows full

This proof shows: correctness.

Statement. Let $G = (V, \Sigma, R, S)$ be a grammar in which every nonterminal derives some terminal string and no nonterminal $A$ satisfies $A \Rightarrow^+ A \gamma$ (no left recursion, direct or hidden). For every input $w = a_1 \cdots a_n$, ALL-STAR-PARSE stops, and:

1. it accepts if and only if $w \in L(G)$, and then it returns a parse tree of $w$ with root $S$;
2. if it reports an error at position $e$ (with $e = n + 1$ meaning the end of the input), then $a_1 \cdots a_{e-1}$ is a prefix of a sentence, and $a_1 \cdots a_e$ is not when $e \le n$.

The DFA cache does not change the result, so the statement holds for any contents of the cache built by earlier inputs.

Setup. Write $\Rightarrow$ for one rewriting step and $L(\alpha)$ for the terminal strings that a string of symbols $\alpha$ derives; $L(\alpha) \neq \emptyset$ for every $\alpha$ because every symbol is productive. A head step on a string $\gamma$ either replaces its first symbol $B \in V$ by the right side of a production $B \to \delta$, or removes its first symbol when it is the next input token (a match). This is the nondeterministic top-down parser: $\gamma \Rightarrow^* x$ for a terminal string $x$ if and only if some sequence of head steps turns $\gamma$ into $\varepsilon$ while matching exactly $x$, because a leftmost derivation rewrites the first nonterminal, and every terminal before it can be matched first. Call $\gamma$ settled when it is $\varepsilon$ or starts with a terminal.

Step 1: head expansions terminate. From a fixed string $\gamma$, there is no infinite sequence of head steps without a match. Suppose there were one. Its expansions form a forest of partial derivation trees whose roots are the symbols of $\gamma$, and an infinite sequence would expand infinitely many nodes of the tree of one symbol, so by König's lemma (each node has at most $|G|$ children) that tree has an infinite path $B_0, B_1, B_2, \ldots$. Each $B_{j+1}$ is expanded only after all of its left siblings have been expanded to $\varepsilon$, since there was no match, so $B_j \Rightarrow \eta_j B_{j+1} \cdots$ with $\eta_j \Rightarrow^* \varepsilon$. Some label repeats, $B_j = B_l$ with $j < l$, and then $B_j \Rightarrow^+ B_j \gamma'$, which is left recursion. By König's lemma again, the set of strings reachable from $\gamma$ by head expansions is finite. So every CLOSURE call terminates, and the set it returns is the set of settled strings reachable by head expansions, with the stack entries of the parser read in when the local part becomes empty (line L27).

Step 2: what the configuration sets contain. Consider a call of ADAPTIVE-PREDICT for $A$ at position $i$, with the parser stack $X_1 \cdots X_q$ below $A$ (top first), and write $\alpha_p$ for the right side of the production $p$ of $A$.

• SLL. For $t \ge i$, as long as the loop reaches the step $t$, the set $D$ at that step is the set of pairs $(p, \gamma)$ with $\gamma$ settled such that head steps turn $\alpha_p$ into $\gamma$ while matching exactly $a_i \cdots a_{t-1}$. For $t = i$ this is the definition of the start state. A step from $t$ to $t+1$ happens only when no pair of $D$ has $\gamma = \varepsilon$ (line L15), so every pair is $(p, a_t \beta)$ or does not start with $a_t$; line L18 keeps the pairs that can match $a_t$ and closes them, which by Step 1 gives exactly the settled strings reachable after matching $a_i \cdots a_t$. A cached edge was computed by the same function of $(D, a_t)$, so it is the same set.
• LL. A configuration $(p, \gamma, d)$ stands for the full stack $\gamma X_{q-d+1} \cdots X_q$. By the same induction, the set $C$ at step $t$ represents exactly the settled full stacks reachable from $\alpha_p X_1 \cdots X_q$ by head steps that match $a_i \cdots a_{t-1}$, and each such stack is represented at least once. The representation $(\varepsilon, 0)$ is the only one of the empty stack.

Step 3: the choice of a production is safe. Say that a production $p$ of $A$ fits when $\alpha_p X_1 \cdots X_q \Rightarrow^* a_i \cdots a_n$. Claim: if some production fits, ADAPTIVE-PREDICT returns a production that fits. Fix a fitting $p^*$ and a sequence of head steps from $\alpha_{p^*} X_1 \cdots X_q$ that matches $a_i \cdots a_n$ and ends with the empty stack. Let $u$ be the first position at which its local part, the part that comes from $\alpha_{p^*}$, is empty and settled; $u$ exists, at the latest at the end.

• SLL, before $u$. At every step $t \le u$ the run has a pair $(p^*, \gamma_t)$ in $D$ by Step 2, with $\gamma_t \neq \varepsilon$ for $t < u$, so the loop never reaches line L17 or L19 before $u$. If it stops at line L14 at some $t \le u$, every pair has the alternative $p^*$, which is returned. If it stops at line L16 at some $t$, then the stacks of $p^*$ and of the returned alternative $p$ are the same nonempty strings $\gamma$, and since $\gamma_t$ is one of them, the same head steps that finish the run of $p^*$ from $\gamma_t X_1 \cdots X_q$ finish a run of $p$: so $p$ fits. At step $u$ the pair $(p^*, \varepsilon)$ is in $D$, so the loop stops at line L14 with $p^*$ or calls LL-PREDICT at line L15.
• LL. Now the run of $p^*$ gives, at every step $t \le n + 1$, a configuration of $p^*$ in $C$, and at $t = n + 1$ the configuration $(p^*, \varepsilon, 0)$. So the loop never reports an error. If it stops at line L22, it returns $p^*$. If it stops at line L23, the represented stacks of the returned $p$ include those of $p^*$, and the run of $p^*$ continues from one of them, so $p$ fits. If it reaches line L24, $C$ holds $(p, \varepsilon, 0)$ exactly for the productions $p$ whose head steps match all of $a_i \cdots a_n$ and empty the stack, that is, the fitting ones; the smallest of them is returned.

Step 4: acceptance. Invariant J: at each test of line L2, with $a_1 \cdots a_{i-1}$ matched and the stack $X_1 \cdots X_q$, the tree built so far is the tree of a leftmost derivation $S \Rightarrow^* a_1 \cdots a_{i-1} X_1 \cdots X_q$, with one empty slot for each stack entry; and if $w \in L(G)$, then $X_1 \cdots X_q \Rightarrow^* a_i \cdots a_n$. Initially the stack is $S$. A match keeps both parts. An expansion of $X_1$ by $p$ performs one leftmost derivation step, so the first part holds; for the second, if $X_1 \cdots X_q \Rightarrow^* a_i \cdots a_n$, then some production of $X_1$ fits, and by Step 3 the production chosen fits too (when $X_1$ has a single production, it is the fitting one). So if $w \in L(G)$, line L6 is never reached (the top terminal is $a_i$, by the second part and since a settled string that derives $a_i \cdots a_n$ starts with $a_i$), no prediction reports an error (Step 3), and when the stack is empty the second part says $a_i \cdots a_n = \varepsilon$: the parser accepts. Conversely, when it accepts, the stack is empty and $i = n + 1$, so the first part gives a leftmost derivation $S \Rightarrow^* w$ whose tree has been returned, and $w \in L(G)$.

Step 5: termination. Every prediction loop advances $t$ by one at each round and stops at $t = n + 1$ at the latest, and each CLOSURE call terminates (Step 1). In the main loop, each round matches a token or expands a nonterminal, and between two matches the expansions are head expansions of the stack, finitely many by Step 1. So the parser stops.

Step 6: errors. Say that a step of the parser inspects the tokens it compares, $a_i$ at line L5 and $a_i, \ldots, a_t$ in the prediction loops, and the end of the input when it tests $i = n + 1$ or $t = n + 1$; let $h$ be the largest inspected position so far, with $n + 1$ for the end. Invariant K: at each test of line L2, the stack $X_1 \cdots X_q$ derives a string that starts with $a_i \cdots a_{h-1}$ (empty when $h \le i$), and when the end has been inspected, it derives $a_i \cdots a_n$ itself. A match keeps K. At a prediction that returns $p$ after inspecting up to the step $t$, the set at step $t$ holds a configuration of $p$ (lines L14, L16, L22, L23) or, at line L24, $(p, \varepsilon, 0)$; by Step 2, $\alpha_p X_2 \cdots X_q$ derives, by productivity, a string that starts with $a_i \cdots a_{t-1}$, or $a_i \cdots a_n$ exactly at line L24. If an earlier step had inspected up to $h > t$, then by K a run from the stack before the expansion matches $a_i \cdots a_{h-1}$; it starts with some production of $X_1$, which is still alive at step $t$, so it is $p$ when the loop stops at line L14 or L22, and at line L16 or L23 the same continuation works for $p$, as in Step 3. So K holds after the expansion.

Now let the parser report an error at position $e$. By K, $e \ge h$ before the failing step: if $e < h$, a run that matches past $a_e$ exists, so the top terminal is $a_e$ at line L5, and a prediction keeps a configuration alive past $e$. The failing step inspects $e$, and $a_1 \cdots a_{e-1}$ is a prefix of a sentence: the stack, or a configuration alive at step $e$, derives a string that starts with $a_i \cdots a_{e-1}$, and with the first part of J and productivity this extends to a sentence. Suppose that $e \le n$ and some sentence $w'$ starts with $a_1 \cdots a_e$. Every step of the parser up to the failing one inspects only positions up to $e$, where $w$ and $w'$ agree (the end of the input is never inspected, since $e \le n$ and $e \ge h$), and the DFA cache returns the same sets for the same arguments. So the parser on $w'$ makes the same moves and reports the same error, which contradicts Step 4 for $w' \in L(G)$. Hence $a_1 \cdots a_e$ is not a prefix of a sentence. $\blacksquare$