Proofs: LR(0) parsing

LR0-PARSE accepts exactly the sentences, reports errors at the earliest token, and runs in linear time full

This proof shows: correctness.

Statement. Let $G$ be a grammar, let $G^\dagger$ be $G$ without the productions that use a nonterminal deriving no terminal string, augmented with $S' \to S \, \$$, and suppose BUILD-LR0 finds no conflict for $G^\dagger$. Then for every input $w = a_1 \cdots a_n$, with $a_{n+1} = \$$:

1. LR0-PARSE accepts if and only if $w \in L(G)$, and then it returns a parse tree of $w$ with root $S$;
2. if $L(G) \ne \emptyset$ and it reports an error at token $i$, then $a_1 \cdots a_{i-1}$ is a prefix of a sentence, and $a_1 \cdots a_i$ is not a prefix of any sentence when $i \le n$, while $w \notin L(G)$ when $i = n + 1$;
3. it stops after at most $c \, (n + 2)$ steps, where $c$ depends only on $G$.

$G$ and $G^\dagger$ have the same parse trees of sentences, because a tree of a terminal string uses only nonterminals that derive terminal strings. So it suffices to argue about $G^\dagger$. We write $\gamma$ for the string of symbols on the stack (the labels of the roots of the stack trees, from the bottom), $q_0, \ldots, q_m$ for the stack of states, $\mathrm{GOTO}(I_0, \gamma)$ as on the LR item page, and $u$ for the tokens shifted so far. A run coincides with another run up to a point if both made the same steps until then.

Step 1 (invariant). At all times (a) $q_j = \mathrm{GOTO}(I_0, X_1 \cdots X_j)$ for $\gamma = X_1 \cdots X_m$ and every $j$, and (b) the $j$-th stack tree is a parse tree of $G^\dagger$ with root $X_j$, and the yields of the stack trees, in order, spell $u$. Both hold at the start. A shift of $a$ pushes $\mathrm{GOTO}(q_m, a)$ and the leaf $a$. A reduction by $A \to \beta$ happens when $q_m$ contains the complete item $A \to \beta \cdot$. By Knuth's theorem on the LR item page, $q_m$ is the set of items valid for $\gamma$, so there is a rightmost derivation $S' \Rightarrow_{rm}^* \delta A x \Rightarrow_{rm} \delta \beta x$ with $\gamma = \delta \beta$. So the top $|\beta|$ symbols are $\beta$, the popped trees have the roots $\beta$, and the new node satisfies the definition of a parse tree. Moreover $\delta A$ is a prefix of the right-sentential form $\delta A x$, so it has a valid item, $\mathrm{GOTO}(q_{m - |\beta|}, A)$ is defined, and it equals $\mathrm{GOTO}(I_0, \delta A)$.

Step 2 (soundness). If the parser accepts, the top state contains $S' \to S \$ \cdot$, which is valid for $\gamma$; as $S'$ occurs on no right side, the only rightmost derivation that can make it valid is $S' \Rightarrow S \$$ itself, so $\gamma = S \$$. By Step 1(b) the first stack tree has root $S$ and yield $u$ without its last token $\$$. The parser returns it only if $\$$ was the last token, that is, $u = w \$$, so it returns a parse tree of $w$, and $w \in L(G)$.

Step 3 (shifts stay inside sentences). Suppose the parser shifts $a$ with stack $\gamma$ after shifting $u$. Then $\mathrm{GOTO}(q_m, a)$ is defined, so $\gamma a$ has a valid item and is a prefix of a right-sentential form $\gamma a \zeta$ of $G^\dagger$. Every symbol of $G^\dagger$ derives a terminal string, so $\zeta \Rightarrow^* x$ for some terminal string $x$, and $\gamma \Rightarrow^* u$ by Step 1(b). Hence $S' \Rightarrow^* u a x$. Every terminal string derived from $S'$ is $v \$$ with $v \in L(G)$, so $u a$ is a prefix of $v \$$ for some sentence $v$.

Step 4 (completeness). Let $v \in L(G)$ and let $S' = \theta_0 \Rightarrow_{rm} \theta_1 \Rightarrow_{rm} \cdots \Rightarrow_{rm} \theta_M = v \$$ be a rightmost derivation in $G^\dagger$, with $\theta_1 = S \$$. Write $\theta_j = \alpha_j \beta_j x_j$ for $j \ge 1$, where $\beta_j$ is the handle reduced in the step from $\theta_{j-1}$, by $A_j \to \beta_j$, and $x_j$ is a terminal string. We claim that the run on $v$ passes through configurations with stack $\gamma$ and unread input $z$ such that $\gamma z = \theta_j$ and $\gamma$ is a prefix of $\alpha_j \beta_j$, for $j = M, M-1, \ldots, 1$. At the start, $\gamma = \varepsilon$ and $z = v \$ = \theta_M$. Consider such a configuration.

• If $\gamma = \alpha_j \beta_j$, the item $A_j \to \beta_j \cdot$ is valid for $\gamma$, so the top state has a complete item. Since there is no conflict, it is the only complete item and the state has no shift item, so the parser reduces by $A_j \to \beta_j$, or accepts if $j = 1$. For $j = 1$ the input is used up, so the parser accepts $v$. For $j > 1$ the new stack is $\alpha_j A_j$ with input $x_j$, and $\alpha_j A_j x_j = \theta_{j-1}$. The handle of $\theta_{j-1}$ ends at or after this $A_j$, because $x_j$ consists of terminals and the step from $\theta_{j-2}$ rewrote the rightmost nonterminal; so $\alpha_j A_j$ is a prefix of $\alpha_{j-1} \beta_{j-1}$.
• If $\gamma$ is a proper prefix of $\alpha_j \beta_j$, the next symbol of $\alpha_j \beta_j$ is the first symbol $a$ of $z$, a terminal. Then $\gamma a$ is a prefix of $\alpha_j \beta_j$ and has a valid item, so the top state has an item with the dot before $a$. Since there is no conflict, it has no complete item, its action is shift, and $\mathrm{GOTO}(q_m, a)$ is defined. The parser shifts $a$, and the claim holds for the same $j$ with a longer $\gamma$.

Each step shortens $z$ or decreases $j$, so the run reaches $j = 1$ and accepts. With Step 2 this proves part 1. It also shows that the run on $v$ follows the rightmost derivation of any tree of $v$; since the run is unique, $v$ has only one parse tree in $G^\dagger$.

Step 5 (earliest error). The actions before the $(i+1)$-th shift depend only on $a_1 \cdots a_i$, because the parser looks at a token only when it shifts it. An error at line L5 at token $i$ means $\mathrm{GOTO}(q_m, a_i)$ is undefined after $u = a_1 \cdots a_{i-1}$ has been shifted. If $i > 1$, Step 3 for the last shift shows that $u$ is a prefix of $v \$$ for a sentence $v$, and as the parser has not accepted, $\$$ is not in $u$, so $u$ is a prefix of $v$; if $i = 1$, $u = \varepsilon$ is a prefix of any sentence. If $a_1 \cdots a_i$ were a prefix of $v' \$$ for some sentence $v'$, the run on $v'$ would coincide with the run on $w$ up to this point and then fail, contradicting Step 4. For $i \le n$ this means that $a_1 \cdots a_i$ is no prefix of a sentence; for $i = n + 1$, $a_i = \$$ and it means $w \notin L(G)$. At line L7, an error at token $i$ means that the parser shifted $\$$ as the token $a_i$ with $i \le n$. Then $a_1 \cdots a_{i-1} \in L(G)$ by Step 2's argument, and no sentence contains $\$$. Finally, a state with no action can only be state 0 when $S$ has no production in $G^\dagger$, that is, when $L(G) = \emptyset$. This proves part 2.

Step 6 (linear time). Assume $L(G) \ne \emptyset$; otherwise the parser stops at once. Consider any moment of the run before it stops, with $u$ shifted. By Step 3, or trivially if $u = \varepsilon$, $u$ is a prefix of $v \$$ for a sentence $v$, and the run so far coincides with the run on $v$, which by Step 4 is finite and builds the unique tree $t_v$. Every node built so far lies in a stack tree, and every stack tree is a subtree of $t_v$.

No repeated node. In $t_v$ no node has a proper descendant with the same label and the same yield span: otherwise replacing the subtree of the upper one by the subtree of the lower one gives a second tree of $v$, against uniqueness. Let $p$ be the number of nonterminals of $G^\dagger$ and $r \ge 1$ the length of its longest right side.

Size of a stack tree. Let $T$ be a stack tree with yield of length $\ell$. The nonempty yield spans of the nodes of $T$ form a laminar family of intervals of $\ell$ positions, so there are at most $2\ell - 1$ distinct ones. Nodes with the same nonempty span lie on one path, because disjoint subtrees with nonempty yields have disjoint spans, so by the previous paragraph at most $p + 1$ nodes share a span. A maximal subtree with empty yield has all its nodes at the same empty span, so no label repeats on a path, its height is at most $p$, and its size is at most $c_\varepsilon = r^{p+1}$. Each such subtree is $T$ itself or a child of a node with nonempty yield. So $|T| \le c_1 (\ell + 1)$ with $c_1 = (p + 1)(1 + r \, c_\varepsilon) + c_\varepsilon$.

Number of stack trees. At most $|u|$ stack trees have a nonempty yield. Let $E_c$ and $E_d$, $c < d$, be two stack entries with empty yield and only entries with empty yield between them. Entries higher on the stack were pushed later, and $E_c$ has not been popped since it was pushed. If a token had been shifted between the pushes of $E_c$ and $E_d$, it would lie in an entry above $E_c$ and below $E_d$, which would then have a nonempty yield; so no token was shifted in between. In that interval the parser never looked below $E_c$, so its steps depend only on the state of $E_c$. If $E_c$ and $E_d$ had the same state, then from the push of $E_d$ on the same steps would repeat forever without a shift, but the run on $v$ is finite and ends by shifting $\$$. So the entries of one block of consecutive empty-yield entries have distinct states, and each block has at most $N$ entries, where $N$ is the number of states. There are at most $|u| + 1$ blocks, so there are at most $|u| + N (|u| + 1)$ stack trees.

Total. Each step builds one node, so the number of steps so far is at most the total size of the stack trees, which is at most $c_1 (|u| + |u| + N(|u| + 1)) \le c \, (|u| + 1)$ with $c = c_1 (N + 2)$. Since $|u| \le n + 1$, the run has at most $c \, (n + 2)$ steps before it stops, which proves part 3. $\blacksquare$