Parsing formulas

Conditions: no ${\beta }_i$ starts with $A$, and no ${\alpha }_i$ is $\epsilon$. $A^{\prime }$ is a new nonterminal. The new grammar has $n+m+1$ alternatives in total: $n$ for $A$ and $m+1$ for $A^{\prime }$.

Applies when two or more alternatives of $A$ share a nonempty prefix $\alpha$ (take the longest one); $A^{\prime }$ is a new nonterminal, and an empty ${\beta }_i$ becomes $\epsilon$. Repeat until no two alternatives of any nonterminal share a prefix.

Also at most one alternative of $A$ may derive $\epsilon$. The condition holds for every nonterminal exactly when no cell of the LL(1) table has two entries.

Applies to LL(1) and LR parsers on an accepted string $w$ of $|w|$ tokens whose parse tree has $p$ internal nodes, not counting the augmented start $S^{\prime }$. In LL, $|w|$ counts the matches and $p$ the expansions; in LR, $|w|$ counts the shifts and $p$ the reductions. A node for an $\epsilon$-production counts in $p$. Accept, and the final match of $, are not counted unless the question says so.

If $\beta$ is empty or nullable, $a$ itself is among the new lookaheads. The initial item is $S^{\prime }\to \cdot S$ with lookahead $. Goto works exactly as in LR(0), carrying the lookaheads along unchanged. Reduce by $A\to \alpha$ only on the item's own lookahead.

Each inclusion is proper. A grammar class here means the set of grammars the method parses without conflict. LL(1) is not contained in LALR(1), SLR(1) or LR(0), and none of those is contained in LL(1): LL(1) is incomparable with each of them. More generally every LL(k) grammar is LR(k).