Ambiguity, left recursion and left factoring

Why it exists

A parser must be able to decide, for every sentence, which tree it has, and top-down parsers must also be able to decide, from one token, which production to use. Real grammars as people first write them often fail both tests: the natural grammar for expressions is ambiguous, the natural way of writing a list is left-recursive, and two alternatives often begin with the same symbols. This page shows how to rewrite such grammars without changing the language so that parsers can use them.

Prerequisites

You need context-free grammars, derivations and parse trees (context-free grammars). Quick recap: a derivation replaces a nonterminal by the right side of one of its productions at each step; in a leftmost derivation the leftmost nonterminal is replaced each time, in a rightmost one the rightmost. Each parse tree corresponds to exactly one leftmost and exactly one rightmost derivation.

Precise definitions

Ambiguous grammar. A grammar is ambiguous if some string of its language has more than one parse tree. Equivalently: more than one leftmost derivation, or more than one rightmost derivation. (Two different derivations with the same tree, such as a leftmost and a rightmost one, do not make a grammar ambiguous.)

Ambiguity is a property of the grammar, not of the language: many languages have both ambiguous and unambiguous grammars. A language is inherently ambiguous if every grammar for it is ambiguous; for example $\{a^i b^j c^k : i = j \text{ or } j = k\}$. It is undecidable whether an arbitrary context-free grammar is ambiguous, so there is no algorithm that settles it for all grammars; for a given small grammar you look for a string with two trees.

Why it matters: the meaning of a program is attached to its parse tree, so two trees mean two meanings. Every LL(1) and every LR(k) grammar is unambiguous, so an ambiguous grammar is never LL(1) or LR(k); parser generators such as Yacc nevertheless accept some ambiguous grammars and resolve the conflicts with precedence and associativity declarations.

Removing ambiguity from expressions. The grammar $E \to E + E \mid E * E \mid (E) \mid \text{id}$ gives no precedence and no associativity. Fix it by layering, one nonterminal per precedence level, lowest precedence at the top:

$E \to E + T \mid T, \qquad T \to T * F \mid F, \qquad F \to (E) \mid \text{id}.$

A production of the form $E \to E + T$ is left recursive, which makes $+$ left associative: $a + b + c$ is $(a + b) + c$. A right-associative operator (such as exponentiation or assignment) uses right recursion: $P \to F \wedge P \mid F$. Binding tighter means being deeper in the layering: $*$ is generated below $+$, so $a + b * c$ must group as $a + (b * c)$.

Dangling else. In $S \to \text{if } E \text{ then } S \mid \text{if } E \text{ then } S \text{ else } S \mid \text{other}$ the string if E then if E then S else S has two trees (the else belongs to the inner or the outer if). The rule of nearly all languages is: each else matches the nearest unmatched then. The unambiguous grammar separates the two kinds of statement:

$\begin{aligned} S &\to M \mid U\\ M &\to \text{if } E \text{ then } M \text{ else } M \mid \text{other}\\ U &\to \text{if } E \text{ then } S \mid \text{if } E \text{ then } M \text{ else } U \end{aligned}$

(M is a matched statement, U an unmatched one.) The then branch before an else must be matched, so no else can slip past an inner unmatched if.

Left recursion. A grammar is left recursive if some nonterminal $A$ derives $A\alpha$ for some $\alpha$ ($A \Rightarrow^+ A\alpha$). It is immediate if there is a production $A \to A\alpha$ and indirect if the cycle goes through other nonterminals. A top-down parser (recursive descent or LL(1)) loops forever on it: to expand $A$ it expands $A$ again without consuming a token. Bottom-up (LR) parsers have no problem with it; in fact left recursion makes them use less stack.

Immediate. If $A \to A\alpha_1 \mid \dots \mid A\alpha_m \mid \beta_1 \mid \dots \mid \beta_n$ where no $\beta_i$ begins with $A$, replace by

$A \to \beta_1 A' \mid \dots \mid \beta_n A', \qquad A' \to \alpha_1 A' \mid \dots \mid \alpha_m A' \mid \varepsilon.$

The new grammar generates the same strings (a $\beta$ followed by any number of $\alpha$'s) but is right recursive.

Indirect (the general algorithm). Number the nonterminals $A_1, \dots, A_n$. For $i = 1$ to $n$: for $j = 1$ to $i-1$, replace every production $A_i \to A_j\gamma$ by $A_i \to \delta_1\gamma \mid \dots \mid \delta_k\gamma$ where $A_j \to \delta_1 \mid \dots \mid \delta_k$ are the current productions of $A_j$; then eliminate the immediate left recursion of $A_i$. (The algorithm assumes the grammar has no cycles $A \Rightarrow^+ A$ and no $\varepsilon$-productions.)

Left factoring. If two alternatives of $A$ begin with the same string, $A \to \alpha\beta_1 \mid \alpha\beta_2$, a predictive parser cannot choose between them by looking at the next token. Defer the decision:

$A \to \alpha A', \qquad A' \to \beta_1 \mid \beta_2.$

Repeat until no two alternatives share a prefix.

Effects on the tree. Removing left recursion or factoring changes the shape of the parse tree and the grammar but not the language. In particular after removing left recursion from $E \to E + T \mid T$ the tree of $a + b + c$ leans to the right even though $+$ is still meant to be left associative; the semantic actions (see translation schemes) must compensate. Left factoring does not remove ambiguity: the dangling else stays ambiguous after factoring.

How it works

First the ambiguity. The grammar $E \to E + E \mid E * E \mid (E) \mid \text{id}$ is run on the string $\text{id} + \text{id} * \text{id}$ and the leftmost derivations found by exhaustive search are shown as trees growing. There are exactly two. In the first the root production is $E \to E + E$ (so the product is computed first, which is the usual meaning); in the second the root is $E \to E * E$ (the sum is computed first).

The layered grammar $E \to E + T \mid T$, $T \to T * F \mid F$, $F \to (E) \mid \text{id}$ derives the same string in exactly one way (found by the same exhaustive search):

The number of parse trees of the flat grammar for $n$ binary operators in a row is the Catalan number $C_n = \frac{1}{n+1}\binom{2n}{n}$: 1, 2, 5, 14 for $n = 1,2,3,4$ (counted by two independent methods in the checks). So id+id+id+id has 5 trees.

Worked examples

Cheat box

Traps and GATE patterns

Connections

Ambiguity is also studied as a property of grammars in ambiguity in grammars. The transformed expression grammar is the one used to build the FIRST and FOLLOW sets (FIRST and FOLLOW) and the table of the LL(1) parser. Bottom-up parsers (LR parsing) accept the left-recursive layered grammar directly. The tree shape after removing left recursion is repaired by semantic actions, see translation schemes.

PYQs

Consider two grammars G1 and G2 with the
production rules given below:

G1: S → if E then S | if E then S else S | a

       E → b

G2: S → if E then S | M

       M → if E then M else S | c

       E → b

where if, then, else, a, b, c are the terminals.

Which of the following option(s) is/are CORRECT?

Consider the following parse tree for the expression
a#b$c$d#e#f, involving two binary operators $ and #.

Which one of the following is correct for the given
parse tree?

Consider the following expression grammar G:

E → E - T | T

T → T + F | F

F → (E) | id

Which of the following grammars is not left
recursive, but is equivalent to G?

Which one of the following grammars is free from
left recursion?

Consider the grammar defined by the following
production rules, with two operators * and +

S → T * P

T → U | T * U

P → Q + P | Q

Q → Id

U → Id

Which one of the following is TRUE?

Consider two binary operators '↑' and '↓' with the
precedence of operator ↓ being lower than that of the
operator ↑. Operator ↑ is right associative while
operator ↓ is left associative. Which one of the
following represents the parse tree for expression
(7↓3↑4↑3↓2) ?

The grammar A → AA | (A) | ε is not suitable for
predictive-parsing because the grammar is

Consider the context-free grammar

E → E + E
E → (E * E)
E → id

where E is the starting symbol, the set of terminals is
{id, (+,),*}, and the set of non-terminals is {E}.

For the terminal string id + id + id + id, how many
parse trees are possible?

COMPILER DESIGN

Self-check

Revision card

References