Grammar Transformations for Parsing

A context-free grammar written to describe a language is often unsuitable for a parser. An ambiguous grammar gives a parser two trees to choose from. A left-recursive grammar sends a top-down parser into an infinite loop. Two alternatives that begin with the same symbols force a top-down parser to guess. This note collects the three standard rewrites that fix these problems while keeping the language the same: eliminating ambiguity, eliminating left recursion, and left factoring.

Each rewrite preserves the set of strings but changes the shape of the parse trees. That matters later, because translations attached to the grammar (for example, evaluating left-associative subtraction) must then be adjusted to the new shape.

Notation used in all Compiler Design notes. Upper-case letters and names such as E, T, stmt are nonterminals; lower-case letters, operator symbols and bold-face names such as id are terminals; Greek letters $\alpha, \beta, \gamma$ are strings of grammar symbols (possibly empty); $\varepsilon$ is the empty string. The first production's head is the start symbol. A vertical bar separates alternatives.

The grammar $E \to E + E \mid E * E \mid ( E ) \mid \textbf{id}$ is ambiguous: id + id * id has two parse trees, one grouping id * id first and one grouping id + id first. With only +, the string id + id + id + id has 5 parse trees, the Catalan number $C_3$, one per way of bracketing three operators.

The fix introduces one nonterminal per precedence level, lowest precedence nearest the start symbol, and chooses left or right recursion per operator to fix associativity:

Now id + id * id has exactly one parse tree, with * below +.

Associativity rule. A left-recursive production $E \to E \text{ op } T$ makes op left-associative (the leftmost operator is deepest in the tree, so it is applied first). A right-recursive production $E \to T \text{ op } E$ makes it right-associative, as used for exponentiation P -> B ^ P | B. Associativity is read from where the recursive nonterminal sits relative to the operator, not from the parser that will be used.

Reading an unusual grammar. In

- is on the lower level $T$, so it binds tighter than *; - is left-associative (left recursion in $T$) and * is right-associative (right recursion in $E$). The string 8 - 2 - 1 * 3 * 2 - 1 has exactly one parse tree. First split at the * signs into the $T$-pieces 8 - 2 - 1, 3 and 2 - 1; each piece groups to the left, and the pieces combine from the right:

With the usual precedences the same string would evaluate to $8 - 2 - 6 - 1 = -1$.

The grammar S -> i E t S | i E t S e S | a, E -> b (with i for if, t for then, e for else) is ambiguous: i b t i b t a e a has two trees, one attaching the else to the inner if and one to the outer. Languages choose "match each else with the closest unmatched then". An unambiguous grammar for that rule separates matched statements (every then has its else) from open ones:

It generates the same strings, and i b t i b t a e a now has exactly one tree, with the else attached to the inner if. Parser generators usually keep the short ambiguous grammar and resolve the conflict in favour of shifting else, which gives the same grouping.

A top-down parser expands the leftmost nonterminal. With $A \to A\alpha$ it would expand $A$ to $A\alpha$, then to $A\alpha\alpha$, without ever consuming input. The cure rewrites the recursion to the right.

Group the $A$-productions as

where no $\beta_j$ begins with $A$. Every string derived from $A$ is some $\beta_j$ followed by any sequence of $\alpha_i$'s. Replace them by

with a new nonterminal $A'$. Applied to the expression grammar:

The two explicitly parenthesised expression grammars, the precedence grammar and this left-recursion-free grammar, generate exactly the same strings (257 token strings of length at most 9 agree). This rewritten grammar is not left-recursive and is LL(1).

Precondition. If every $\alpha_i$ were $\varepsilon$ (a production $A \to A$), the rewrite would be meaningless; such cycles are removed first. $\varepsilon$-productions elsewhere are allowed in the immediate case.

Example: several alternatives on each side. $S \to S a \mid S b \mid c \mid d$ has $\alpha_1 = a$, $\alpha_2 = b$, $\beta_1 = c$, $\beta_2 = d$:

Both grammars generate $(c \mid d)(a \mid b)^{*}$.

Example: one $\beta$ is $\varepsilon$. In $A \to A c \mid A a d \mid b d \mid \varepsilon$, the non-recursive alternatives are $\beta_1 = b d$ and $\beta_2 = \varepsilon$. The $\varepsilon$ alternative does not disappear; it becomes $A \to A'$:

Both generate $(b d \mid \varepsilon)(c \mid a d)^{*}$. Dropping $A \to A'$ would lose every string that does not start with b d, for example c and ad.

The general algorithm orders the nonterminals $A_1, A_2, \ldots, A_n$ and makes every production $A_i \to A_j\gamma$ satisfy $j > i$.

Precondition: the grammar has no cycles ($A \Rightarrow^{+} A$) and no $\varepsilon$-productions; with $\varepsilon$-productions, hidden left recursion can survive the substitution. Time: the substitution step can multiply the number of productions, so the output may be exponentially larger than the input in the worst case.

Worked example. Order $S, A$ in

$S$ has no immediate left recursion. For $A$, substitute the $S$-productions into $A \to S c$: $A \to A a c \mid b c \mid d$. Now remove the immediate left recursion with $\alpha = a c$, $\beta_1 = b c$, $\beta_2 = d$:

The original grammar is left-recursive ($S \Rightarrow A a \Rightarrow S c a$); the result is not, and both generate the same strings (all strings up to length 10 agree).

Hidden left recursion. In S -> A S b | c, A -> a | eps no production starts with S, yet $S \Rightarrow A S b \Rightarrow S b$ because $A$ is nullable. This grammar is left-recursive. Questions that ask "is the grammar left-recursive?" test exactly this.

When two alternatives share a non-empty prefix $\alpha$, a predictive parser cannot choose between them by looking at the next token. Left factoring delays the choice until the prefix has been read:

Take $\alpha$ to be the longest prefix common to two or more alternatives, and repeat until no two alternatives of any nonterminal share a prefix.

Example 1 (dangling else). S -> i E t S | i E t S e S | a has common prefix i E t S:

The language is unchanged, but the grammar is still ambiguous and still not LL(1): with e as the next token, $S'$ may either take e S or derive $\varepsilon$ (because e can follow $S'$). Left factoring removes guessing caused by common prefixes; it cannot remove ambiguity.

Example 2 (repeated factoring). A -> a b c | a b d | a e. The longest prefix shared by two alternatives is a b, but a is shared by all three. Factoring a first and then b:

Common misconceptions.