Skip to content

Lesson 2.1 — Grammars, derivations and ambiguity

Techniques: derivations and parse trees (with the Chomsky hierarchy and CST vs AST), ambiguity detection, precedence and associativity by layering · Pebble implements: layering (Pebble's expression grammar, docs/language/pebble-spec.md) · Lab: the provided grammar model labs/ch02-ll1-toolkit/include/ll1/Grammar.h · Prerequisites: Ch 1 (tokens, regular languages) · Time: 3–4 hours

The lexer of Ch 1 turns a + b * c into the tokens id + id * id. Which of the two groupings, (id + id) * id or id + (id * id), did the programmer mean? A regular expression cannot even say that parentheses balance, so the parser needs a stronger formalism: a context-free grammar. This lesson defines grammars, derivations and trees; shows how a grammar can be ambiguous (two trees for one sentence) and why no algorithm can detect that in general; and shows how grammar writers encode precedence and associativity so that each sentence has exactly one tree.

1. Problem and motivation

The parser's contract is: given a token sequence, decide whether it belongs to the language, and if so produce the tree that later phases (Ch 5, Ch 6, Ch 11) walk. pebblec parses with hand-written recursive descent (Lesson 2.5); its grammar in docs/language/pebble-spec.md is the specification that code must implement, and the precedence table in that spec is a layered grammar written as a table.

Derivations and parse trees

Context-free grammars were introduced by Chomsky as one level of a hierarchy of generative grammars [Cho56, Cho59] and, independently, as Backus–Naur Form to define ALGOL 60 [Nau60]. A derivation rewrites the start symbol step by step into a sentence; a parse tree records which production produced which part and forgets the order of the steps. Parsers are classified by the derivation they reconstruct: top-down parsers (this chapter) build a leftmost derivation, bottom-up parsers (Ch 3) a rightmost one in reverse. Compilers then shrink the concrete tree into an abstract syntax tree (AST); IDE tools increasingly keep the full concrete syntax tree (CST).

Ambiguity detection

A grammar is ambiguous when some sentence has two parse trees. For a compiler that is a bug: the two trees usually mean different programs ((a + b) * c vs a + b * c). In 1962 Cantor, Floyd, and Chomsky and Schützenberger independently proved that no algorithm decides whether an arbitrary context-free grammar is ambiguous [Can62, Flo62, CS63]. What remains are semi-decision procedures (search for a sentence with two trees) and sufficient conditions (every LL(1) or LR(1) grammar is unambiguous [Knu71, Knu65]).

Precedence and associativity by layering

The standard cure for expression ambiguity gives each precedence level its own nonterminal and uses left or right recursion for associativity. The ALGOL 60 report already wrote arithmetic expressions this way (<term> and <factor> [Nau60, §3.3.1]), and the C and Java standards still do (additive-expression, multiplicative-expression).

2. Definitions and algorithms

Notation follows the chapter's Notation section: \(A, B \in N\), \(a, b, t \in T\), \(\alpha, \beta, \gamma \in (N \cup T)^{*}\), \(w \in T^{*}\), \(\varepsilon\) the empty string.

Definition 2.1.1 (Context-free grammar)

A context-free grammar (CFG) is a quadruple \(G = (N, T, P, S)\) where \(N\) (nonterminals) and \(T\) (terminals, the token kinds) are finite disjoint sets, \(P \subseteq N \times (N \cup T)^{*}\) is a finite set of productions, written \(A \to \alpha\), and \(S \in N\) is the start symbol. Productions are numbered \(1, \dots, \lvert P \rvert\) in the order they are written. The size of \(G\) is \(\lvert G \rvert \triangleq \sum_{A \to \alpha \in P} (1 + \lvert \alpha \rvert)\), and \(r \triangleq \max_{A \to \alpha \in P} \lvert \alpha \rvert\) is the longest right-hand side.

Definition 2.1.2 (Derivation, sentential form, language)

For \(\beta, \gamma \in (N \cup T)^{*}\) and \(A \to \alpha \in P\), the derivation step is \(\beta A \gamma \Rightarrow \beta \alpha \gamma\). It is leftmost, written \(\Rightarrow_{\mathrm{lm}}\), if \(\beta \in T^{*}\), and rightmost, \(\Rightarrow_{\mathrm{rm}}\), if \(\gamma \in T^{*}\). \(\Rightarrow^{*}\) is the reflexive–transitive closure of \(\Rightarrow\) and \(\Rightarrow^{+}\) the transitive closure. A sentential form is any \(\alpha\) with \(S \Rightarrow^{*} \alpha\) (a left-sentential form if \(S \Rightarrow_{\mathrm{lm}}^{*} \alpha\)); a sentence is a sentential form in \(T^{*}\). The language of \(G\) is

\[ L(G) \triangleq \{\, w \in T^{*} \mid S \Rightarrow^{*} w \,\}, \qquad L(X) \triangleq \{\, w \in T^{*} \mid X \Rightarrow^{*} w \,\} \text{ for } X \in N \cup T . \]

Definition 2.1.3 (Parse tree, CST, AST)

A parse tree for \(w\) is an ordered tree whose root is labelled \(S\), whose leaves, read left to right, spell \(w\) (a leaf may be labelled \(\varepsilon\)), and in which every interior node labelled \(A\) with children labelled \(X_1, \dots, X_k\) corresponds to a production \(A \to X_1 \cdots X_k \in P\) (\(k = 0\): one child \(\varepsilon\)). The sequence of leaves is the tree's yield. The tree is a concrete syntax tree (CST) when it is kept in full: every token, including ( and ;, and every unit step such as \(E \to T\). An abstract syntax tree (AST) is a tree over a different alphabet (operators and operands) that keeps only what later phases need: no punctuation, no unit chains such as \(E \Rightarrow T \Rightarrow F\).

Derivation, tree and AST of id + id * id

With the layered grammar of §3, \(E \Rightarrow_{\mathrm{lm}} E + T \Rightarrow_{\mathrm{lm}} T + T \Rightarrow_{\mathrm{lm}} \dots \Rightarrow_{\mathrm{lm}} \mathtt{id} + \mathtt{id} * \mathtt{id}\) takes 8 steps; each step is one interior node of the 13-node CST, and the AST \(+(\mathtt{id}, *(\mathtt{id}, \mathtt{id}))\) has 5 nodes.

Definition 2.1.4 (Chomsky hierarchy)

A grammar with productions \(\alpha \to \beta\), \(\alpha \in (N \cup T)^{*} N (N \cup T)^{*}\), is of type 0 (unrestricted) in general; type 1 (context-sensitive) if \(\lvert \alpha \rvert \le \lvert \beta \rvert\) for every production (with \(S \to \varepsilon\) allowed when \(S\) occurs on no right side); type 2 (context-free) if every \(\alpha\) is a single nonterminal (Definition 2.1.1); type 3 (right-linear, regular) if every production has the form \(A \to t B\), \(A \to t\) or \(A \to \varepsilon\). Each class generates strictly more languages than the next: \(\{a^{n} b^{n} \mid n \ge 0\}\) is context-free but not regular, and \(\{a^{n} b^{n} c^{n} \mid n \ge 0\}\) is context-sensitive but not context-free [Cho59; HU79].

Definition 2.1.5 (Ambiguity)

\(G\) is ambiguous if some \(w \in L(G)\) has two distinct parse trees; a language is inherently ambiguous if every grammar for it is ambiguous. \(\#_{G}(w)\) denotes the number of parse trees of \(w\) (possibly \(\infty\) if \(G\) has a cycle \(A \Rightarrow^{+} A\)).

An ambiguous grammar and an inherently ambiguous language

The flat grammar \(E \to E + E \mid E * E \mid (\,E\,) \mid \mathtt{id}\) of §3 has \(\#(\mathtt{id} + \mathtt{id} * \mathtt{id}) = 2\). The layered grammar generates the same language with \(\# = 1\) for every sentence, so ambiguity belongs to the grammar. By contrast, \(\{a^{i} b^{j} c^{k} \mid i = j \lor j = k\}\) is inherently ambiguous: every grammar gives \(a^{n} b^{n} c^{n}\) two trees for infinitely many \(n\) [HU79].

Derivations and parse trees

Algorithm 2.1.6 (Replay, tree ↔ derivation, CST → AST, shape classifier)

  • Input: \(G\) and a sequence \(p_1, \dots, p_m\) of production numbers with a mode (leftmost or rightmost); or a parse tree; or \(G\) alone for ChomskyType.
  • Output: the sentential forms \(\alpha_0 = S, \alpha_1, \dots, \alpha_m\), or the first invalid step; the leftmost/rightmost derivation of a tree; its AST; the Chomsky type of \(G\)'s production shapes.
  • Precondition: for ToAst, grouping is encoded only by the tree's shape (a layered expression grammar, Algorithm 2.1.9).
  • Postcondition: Replay returns \(\alpha_m\) with \(S = \alpha_0 \Rightarrow_{\mathrm{lm}} \alpha_1 \Rightarrow_{\mathrm{lm}} \cdots \Rightarrow_{\mathrm{lm}} \alpha_m\) (or \(\Rightarrow_{\mathrm{rm}}\)); Leftmost(t) is a leftmost derivation whose tree is \(t\) (Lemma 2.1.10).
  • Invariant: before step \(i\) of Replay, form \(= \alpha_{i-1}\) and \(S \Rightarrow^{i-1} \alpha_{i-1}\) in the chosen mode.
function Replay(G, p1 … pm, mode):                   # mode = leftmost or rightmost
    form ← S
    for step ← 1 to m:
        positions ← indices of nonterminals in form
        if positions is empty: fail "no nonterminal left at step" step
        i ← first(positions) if mode = leftmost else last(positions)
        (A → α) ← production p_step
        if form[i] ≠ A: fail "step expands A, but the form has form[i] there"
        form ← form[1 … i−1] · α · form[i+1 …]
    return form

function Leftmost(tree):                              # preorder = leftmost derivation
    if tree is a leaf: return []
    return [production(tree)] · Leftmost(child1) · … · Leftmost(childk)

function Rightmost(tree):                             # right-to-left preorder
    if tree is a leaf: return []
    return [production(tree)] · Rightmost(childk) · … · Rightmost(child1)

function ToAst(node):                                 # for a layered expression CST
    if node is a token id: return Leaf(id)
    if node has one child: return ToAst(child)        # unit chain E → T → F: skip
    if node's children are ( X ): return ToAst(X)     # parentheses only group
    (L, op, R) ← the three children
    return Binary(op, ToAst(L), ToAst(R))

function ChomskyType(G):                              # by the shapes of the productions
    if every production is A → t B, A → t or A → ε: return 3
    if every left side is a single nonterminal: return 2
    if every production α → β has |α| ≤ |β| (S → ε allowed): return 1
    return 0

Clang builds an AST, not a CST

Reproduce (clang 23.1.2; any OS):

cat > paren.c <<'EOF'
int f(int a, int b, int c) { return (a + b) * c; }
EOF
clang -fsyntax-only -Xclang -ast-dump -fno-color-diagnostics paren.c \
  | sed -n '/FunctionDecl.* f /,$p' | sed -E 's/ 0x[0-9a-f]+//g'

Output (complete; the sed calls keep the function and strip the node addresses, which change from run to run):

`-FunctionDecl <paren.c:1:1, col:50> col:5 f 'int (int, int, int)' external-linkage
  |-ParmVarDecl <col:7, col:11> col:11 used a 'int'
  |-ParmVarDecl <col:14, col:18> col:18 used b 'int'
  |-ParmVarDecl <col:21, col:25> col:25 used c 'int'
  `-CompoundStmt <col:28, col:50>
    `-ReturnStmt <col:30, col:47>
      `-BinaryOperator <col:37, col:47> 'int' '*'
        |-ParenExpr <col:37, col:43> 'int'
        | `-BinaryOperator <col:38, col:42> 'int' '+'
        |   |-ImplicitCastExpr <col:38> 'int' <LValueToRValue>
        |   | `-DeclRefExpr <col:38> 'int' lvalue ParmVar 'a' 'int'
        |   `-ImplicitCastExpr <col:42> 'int' <LValueToRValue>
        |     `-DeclRefExpr <col:42> 'int' lvalue ParmVar 'b' 'int'
        `-ImplicitCastExpr <col:47> 'int' <LValueToRValue>
          `-DeclRefExpr <col:47> 'int' lvalue ParmVar 'c' 'int'

What to notice: this is an AST in the sense of Definition 2.1.3. The C grammar derives a through a chain of seventeen nonterminals (expression ⇒ assignment-expression ⇒ … ⇒ primary-expression), and none of them appears; the only trace of the parentheses is one ParenExpr, kept for diagnostics and source fidelity. The ImplicitCastExpr nodes are not syntax at all: semantic analysis added them (Ch 6).

Ambiguity detection

Algorithm 2.1.7 (CountTrees, FindAmbiguity)

  • Input: \(G\) without cycles (no \(A \Rightarrow^{+} A\)) and \(w = t_1 \cdots t_n\); for FindAmbiguity a length bound \(L\).
  • Output: \(\#_{G}(w)\); or a witness \(w\) with \(\#_{G}(w) \ge 2\) and \(\lvert w \rvert \le L\), or "none up to \(L\)".
  • Precondition: \(G\) is cycle-free, so \(\#_{G}(w)\) is finite and the recursion on equal spans terminates.
  • Postcondition: Count(X, i, j) \(= \lvert \{\)trees with root \(X\) and yield \(t_{i+1} \cdots t_j\} \rvert\) (Lemma 2.1.11); CountTrees returns \(\#_{G}(w)\).
  • Invariant: every memoized entry holds its final value; Seq only splits at points leaving each remaining symbol at least minlen tokens.

Oracle: count_parse_trees in tools/course/lib/grammar.py.

function CountTrees(G, w):
    minlen(X) ← length of the shortest terminal string X derives   # least fixed point; minlen(t) = 1
    return Count(S, 0, n)

function Count(X, i, j):                              # trees for w[i..j) rooted at X, memoized
    if X is a terminal: return 1 if j = i + 1 and w[i] = X else 0
    return Σ over productions X → Y1 … Yk of Seq(Y1 … Yk, i, j)

function Seq(Y1 … Yk, i, j):                          # ways Y1 … Yk derives w[i..j), memoized
    if k = 0: return 1 if i = j else 0
    rest ← minlen(Y2) + … + minlen(Yk)
    total ← 0
    for m ← i + minlen(Y1) to j − rest:               # the split point after Y1
        total ← total + Count(Y1, i, m) · Seq(Y2 … Yk, m, j)
    return total

function FindAmbiguity(G, L):                         # semi-decision, bounded by length L
    for each w ∈ L(G) with |w| ≤ L, shortest first:   # from bounded enumeration
        if CountTrees(G, w) ≥ 2: return w             # a witness
    return "no ambiguous sentence of length ≤ L"      # proves nothing about longer ones

Bison prints an ambiguity witness

Reproduce (bison 3.8.2; any OS):

cat > flat.y <<'EOF'
%token ID
%%
e: e '+' e | e '*' e | '(' e ')' | ID ;
EOF
cat > layered.y <<'EOF'
%token ID
%%
e: e '+' t | t ;
t: t '*' f | f ;
f: '(' e ')' | ID ;
EOF
bison -Wcounterexamples -o /dev/null flat.y
bison -Wall -o /dev/null layered.y && echo "layered.y: no conflicts"

Output (complete):

flat.y: warning: 4 shift/reduce conflicts [-Wconflicts-sr]
flat.y: warning: shift/reduce conflict on token '+' [-Wcounterexamples]
  Example: e '+' e . '+' e
  Shift derivation
    e
    `-> 1: e '+' e
                 `-> 1: e . '+' e
  Reduce derivation
    e
    `-> 1: e                '+' e
           `-> 1: e '+' e .
flat.y: warning: shift/reduce conflict on token '*' [-Wcounterexamples]
  Example: e '+' e . '*' e
  Shift derivation
    e
    `-> 1: e '+' e
                 `-> 2: e . '*' e
  Reduce derivation
    e
    `-> 2: e                '*' e
           `-> 1: e '+' e .
flat.y: warning: shift/reduce conflict on token '+' [-Wcounterexamples]
  Example: e '*' e . '+' e
  Shift derivation
    e
    `-> 2: e '*' e
                 `-> 1: e . '+' e
  Reduce derivation
    e
    `-> 1: e                '+' e
           `-> 2: e '*' e .
flat.y: warning: shift/reduce conflict on token '*' [-Wcounterexamples]
  Example: e '*' e . '*' e
  Shift derivation
    e
    `-> 2: e '*' e
                 `-> 2: e . '*' e
  Reduce derivation
    e
    `-> 2: e                '*' e
           `-> 2: e '*' e .
layered.y: no conflicts

What to notice: each "Example" is a single sentential form with two derivation trees, i.e. a witness of Definition 2.1.5; the second one is id + id * id with the grouping id + (id * id) (shift) versus (id + id) * id (reduce), exactly the pair of trees in §3. Bison finds these by searching the LR automaton's conflicts, a sufficient-condition test (Corollary 2.1.13): the layered grammar passes it, which proves it unambiguous; a grammar that fails it may still be unambiguous, and Bison then prints two different examples instead of one [BISON-Manual].

Precedence and associativity by layering

Definition 2.1.8 (Precedence table)

A precedence table is a sequence of levels \(1, \dots, m\) from lowest to highest binding; level \(i\) has a set \(O_i\) of binary infix operators and an associativity \(\mathrm{assoc}(i) \in \{\mathrm{left}, \mathrm{right}\}\), the \(O_i\) pairwise disjoint. An expression's intended grouping puts, among the operators outside parentheses, one of the lowest level at the root: the last such operator if that level is left-associative, the first if it is right-associative; the operands are grouped recursively.

Algorithm 2.1.9 (Layer)

  • Input: a precedence table (Definition 2.1.8).
  • Output: a grammar \(G_{\mathrm{lay}}\) with nonterminals \(E_1, \dots, E_m, P\) and start \(E_1\).
  • Precondition: only binary infix operators; parentheses and id are not operators.
  • Postcondition: \(G_{\mathrm{lay}}\) is unambiguous, and the unique tree of every sentence groups it as intended (Theorem 2.1.14).
  • Invariant: after iteration \(i\), every \(E_j\) with \(j \le i\) has exactly one base alternative \(E_j \to E_{j+1}\) (or \(E_m \to P\)) and one recursive alternative per operator of \(O_j\).

Oracle: precedence_grammar.

function Layer(levels):
    for i ← 1 to m:
        Ei ← a new nonterminal;  next ← E(i+1) if i < m else P
        for each operator op of level i:
            if level i is left-associative:  add Ei → Ei op next      # left recursion
            else:                            add Ei → next op Ei      # right recursion
        add Ei → next                                                  # "no operator of this level"
    add P → ( E1 ) | id                                                # operands and grouping
    return the grammar with start E1

Associativity and precedence in Clang's AST

Reproduce (clang 23.1.2; any OS):

cat > assoc.c <<'EOF'
int g(int x, int y, int z) { x = y = z; return x - y - z; }
EOF
clang -fsyntax-only -Xclang -ast-dump -fno-color-diagnostics assoc.c \
  | sed -n '/FunctionDecl.* g /,$p' | sed -E 's/ 0x[0-9a-f]+//g'

Output (complete):

`-FunctionDecl <assoc.c:1:1, col:59> col:5 g 'int (int, int, int)' external-linkage
  |-ParmVarDecl <col:7, col:11> col:11 used x 'int'
  |-ParmVarDecl <col:14, col:18> col:18 used y 'int'
  |-ParmVarDecl <col:21, col:25> col:25 used z 'int'
  `-CompoundStmt <col:28, col:59>
    |-BinaryOperator <col:30, col:38> 'int' '='
    | |-DeclRefExpr <col:30> 'int' lvalue ParmVar 'x' 'int'
    | `-BinaryOperator <col:34, col:38> 'int' '='
    |   |-DeclRefExpr <col:34> 'int' lvalue ParmVar 'y' 'int'
    |   `-ImplicitCastExpr <col:38> 'int' <LValueToRValue>
    |     `-DeclRefExpr <col:38> 'int' lvalue ParmVar 'z' 'int'
    `-ReturnStmt <col:41, col:56>
      `-BinaryOperator <col:48, col:56> 'int' '-'
        |-BinaryOperator <col:48, col:52> 'int' '-'
        | |-ImplicitCastExpr <col:48> 'int' <LValueToRValue>
        | | `-DeclRefExpr <col:48> 'int' lvalue ParmVar 'x' 'int'
        | `-ImplicitCastExpr <col:52> 'int' <LValueToRValue>
        |   `-DeclRefExpr <col:52> 'int' lvalue ParmVar 'y' 'int'
        `-ImplicitCastExpr <col:56> 'int' <LValueToRValue>
          `-DeclRefExpr <col:56> 'int' lvalue ParmVar 'z' 'int'

What to notice: x = y = z groups as x = (y = z): the first = is at the root, as Definition 2.1.8 prescribes for a right-associative level, and x - y - z groups as (x - y) - z: the last - is at the root. The C standard specifies both with layered productions (C23 §6.5.6, §6.5.16); Clang produces the same trees from its precedence table [CLANG-OpPrec] by precedence climbing (§7).

3. Worked example

Running example: the sentence id + id * id in two grammars for the same language.

Flat (ambiguous):          Layered (Dragon book Example 4.1):
(1) E → E + E               (1) E → E + T      (4) T → F
(2) E → E * E               (2) E → T          (5) F → ( E )
(3) E → ( E )               (3) T → T * F      (6) F → id
(4) E → id

Derivations and parse trees on the running example

Layered grammar (oracle: one_parse_tree, tree_leftmost, tree_rightmost, replay_derivation):

step leftmost: production sentential form rightmost: production sentential form
0 E E
1 (1) E → E + T E + T (1) E → E + T E + T
2 (2) E → T T + T (3) T → T * F E + T * F
3 (4) T → F F + T (6) F → id E + T * id
4 (6) F → id id + T (4) T → F E + F * id
5 (3) T → T * F id + T * F (6) F → id E + id * id
6 (4) T → F id + F * F (2) E → T T + id * id
7 (6) F → id id + id * F (4) T → F F + id * id
8 (6) F → id id + id * id (6) F → id id + id * id

Both derivations use the same eight productions in different orders, and describe the same tree. Leftmost (preorder) gives 1 2 4 6 3 4 6 6; Rightmost gives 1 3 6 4 6 2 4 6. The CST on the left keeps the unit chains; ToAst keeps only the operators:

flowchart TD
  E1[E] --> E2[E]
  E1 --> P1(("+"))
  E1 --> T1[T]
  E2 --> T2[T] --> F1[F] --> I1((id))
  T1 --> T3[T]
  T1 --> S1(("*"))
  T1 --> F3[F] --> I3((id))
  T3 --> F2[F] --> I2((id))
  A1{{"+"}} --> B1((id))
  A1 --> A2{{"*"}}
  A2 --> B2((id))
  A2 --> B3((id))

The CST has 13 nodes, the AST 5: that ratio is why compilers such as Clang build ASTs directly (real-world box in §2) and why IDE tools that need every token (formatters, refactorings) keep lossless CSTs instead.

Classifying the grammars with ChomskyType: both are type 2 (every left side is one nonterminal) and neither is type 3 (\(E \to E + T\) has a nonterminal first). The language itself is not regular: it contains \((^{k}\,\mathtt{id}\,)^{k}\) for every \(k\), and a finite automaton cannot count the parentheses.

Ambiguity detection on the running example

The flat grammar has two leftmost derivations of id + id * id:

step tree 1: production form tree 2: production form
1 (1) E → E + E E + E (2) E → E * E E * E
2 (4) E → id id + E (1) E → E + E E + E * E
3 (2) E → E * E id + E * E (4) E → id id + E * E
4 (4) E → id id + id * E (4) E → id id + id * E
5 (4) E → id id + id * id (4) E → id id + id * id

CountTrees confirms it. Here \(\mathrm{minlen}(E) = 1\). The non-zero entries of \(\mathrm{Count}(E, i, j)\), shortest spans first (positions 0–5 between the tokens):

span tokens Count(E, span) why
0..1, 2..3, 4..5 id 1 each (4) E → id
0..3 id + id 1 (1) with split 0..1 · + · 2..3
2..5 id * id 1 (2) with split 2..3 · * · 4..5
0..5 id + id * id 2 (1): Count(0..1)·Count(2..5) = 1; (2): Count(0..3)·Count(4..5) = 1

The same chart for the layered grammar gives 1 for the whole sentence: the only split that works puts + at the root, because \(T\) cannot derive id + id. With \(k\) operators in a row the flat grammar has \(C_k\) (Catalan) trees: 1, 1, 2, 5, 14, 42, 132 for \(k = 0, \dots, 6\) (oracle, sentence id + id + … + id; Proposition 2.1.16). FindAmbiguity on the flat grammar returns a witness of length 5 (for example id + id * id): every sentence of length at most 4 has at most one operator, hence one tree.

Precedence and associativity by layering on the running example

The layered grammar above is Layer applied to two levels: + (left) and * (left). With four operators on two left-associative levels and a third, right-associative level ^, Layer produces:

(1) E0 → E0 + E1    (4) E1 → E1 * E2    (7) E2 → P ^ E2    (9)  P → ( E0 )
(2) E0 → E0 - E1    (5) E1 → E1 / E2    (8) E2 → P         (10) P → id
(3) E0 → E1         (6) E1 → E2
sentence the grammar's unique tree, parenthesized trees in the flat grammar
id - id - id ((id-id)-id): E0 → E0 - E1 puts the last - at the root 2
id ^ id ^ id (id^(id^id)): E2 → P ^ E2 puts the first ^ at the root 2
id - id * id ^ id (id-(id*(id^id))) 5

Try it

./course drill derivations --seed 5 --difficulty medium asks for exactly this parenthesization on a random operator table; --difficulty easy and hard ask for tree counts and derivations, and accept any valid derivation.

4. Invariants and correctness

Derivations and parse trees

Lemma 2.1.10 (Trees and leftmost derivations are in bijection)

For every \(w \in T^{*}\), Leftmost is a bijection from the parse trees of \(w\) to the leftmost derivations \(S \Rightarrow_{\mathrm{lm}}^{*} w\); symmetrically, Rightmost is a bijection onto the rightmost derivations. Consequently \(\#_{G}(w)\) equals the number of leftmost derivations of \(w\), and "ambiguous" can be defined with trees, leftmost derivations or rightmost derivations interchangeably.

Proof

Leftmost(t) is a leftmost derivation of the yield. By induction on the height of \(t\). A leaf contributes no step. For a root \(A\) with production \(A \to X_1 \cdots X_k\) and subtrees \(t_1, \dots, t_k\), the first step rewrites \(A\) into \(X_1 \cdots X_k\). By the induction hypothesis Leftmost\((t_j)\) derives the yield \(y_j\) of \(t_j\) from \(X_j\) leftmost. Performing the steps of \(t_1\) first, then those of \(t_2\), and so on, every step rewrites a nonterminal to whose left there are only terminals: \(y_1 \cdots y_{j-1}\) (already terminal) followed by the leftmost nonterminal of the partial form of \(X_j\). So the concatenation is a leftmost derivation of \(y_1 \cdots y_k\).

Injectivity. Two different trees differ at some node reached by the same path from the root: either the productions differ there or (for the same production) some deeper node differs. Preorder visits nodes in a fixed order determined by the shape so far, so the first differing node in preorder produces the first differing entry of the two sequences.

Surjectivity. By induction on the length \(m\) of a leftmost derivation \(S = \alpha_0 \Rightarrow_{\mathrm{lm}} \cdots \Rightarrow_{\mathrm{lm}} \alpha_m\), maintain a partial tree whose frontier (unexpanded leaves and terminal leaves, left to right) spells \(\alpha_i\). Step \(i+1\) rewrites the leftmost nonterminal of \(\alpha_i\), which is the leftmost unexpanded leaf; attach the production's children there. The finished tree has preorder equal to the derivation's production sequence, because each production was attached at the leftmost open leaf, which is the next node in preorder.

The rightmost case is the mirror image (right-to-left preorder).

Termination and correctness of the other routines. Replay performs \(m\) iterations and satisfies its invariant by construction (each iteration applies exactly the definition of \(\Rightarrow_{\mathrm{lm}}\) or \(\Rightarrow_{\mathrm{rm}}\)). ToAst visits each node once; on a layered grammar a node with one child is a unit step and a node ( X ) only groups, so dropping them loses no operator and keeps the operand order. When it breaks: ToAst would be wrong on a grammar whose unit productions carry meaning (a cast written as a one-child production), which is why real AST builders are written per production rather than generically.

Ambiguity detection

Lemma 2.1.11 (Correctness of CountTrees)

If \(G\) is cycle-free, then for all \(X\) and \(0 \le i \le j \le n\), \(\mathrm{Count}(X, i, j)\) is the number of trees with root \(X\) and yield \(t_{i+1} \cdots t_j\), and \(\mathrm{Seq}(Y_1 \cdots Y_k, i, j)\) is the number of tuples \((s_1, \dots, s_k)\) of trees with roots \(Y_1, \dots, Y_k\) whose yields concatenate to \(t_{i+1} \cdots t_j\). The recursion terminates.

Proof

Counting. By induction on the pair (span length \(j - i\), height of the trees counted), ordered lexicographically. A tree rooted at a nonterminal \(X\) is determined by its root production \(X \to Y_1 \cdots Y_k\) and the tuple of child subtrees, and different choices give different trees, so the trees are the disjoint union over productions of the tuples counted by \(\mathrm{Seq}\). A tuple is determined by the end position \(m\) of \(s_1\)'s yield together with \(s_1\) and the remaining tuple; the pairs for different \(m\) are disjoint, and for fixed \(m\) the choices are independent, hence the product. The loop range loses nothing: every \(Y_r\) with \(r \ge 2\) yields at least \(\mathrm{minlen}(Y_r)\) tokens, so \(m \le j - \mathrm{rest}\), and \(s_1\) yields at least \(\mathrm{minlen}(Y_1)\) tokens, so \(m \ge i + \mathrm{minlen}(Y_1)\). For a terminal the only tree is the leaf itself.

Termination. A call \(\mathrm{Count}(Y_1, i, m)\) from \(\mathrm{Seq}\) has \(m - i \le j - i\), with equality only when every \(Y_r\), \(r \ge 2\), has \(\mathrm{minlen}(Y_r) = 0\), i.e. is nullable. A chain of calls on the same span therefore follows nonterminals \(X \to \cdots Y \cdots\) with every other symbol of the right side nullable, which is a derivation \(X \Rightarrow^{+} Y\). If a chain on one span were infinite, some nonterminal would repeat and \(X \Rightarrow^{+} X\), contradicting cycle-freeness. So every chain of equal-span calls has length at most \(\lvert N \rvert\), and spans otherwise shrink.

Theorem 2.1.12 (Ambiguity is undecidable [Can62, Flo62, CS63])

There is no algorithm that decides, for an arbitrary CFG \(G\), whether \(G\) is ambiguous.

Proof sketch (full proof: [HU79, Ch. 8]; guided proof: [Sip12, Problem 5.21])

By reduction from Post's correspondence problem (PCP), which is undecidable [Pos46]: given pairs \((x_1, y_1), \dots, (x_k, y_k)\) of nonempty words over \(\Sigma\), is there a sequence \(i_1, \dots, i_m\) (\(m \ge 1\)) with \(x_{i_1} \cdots x_{i_m} = y_{i_1} \cdots y_{i_m}\)? Given an instance, build \(G\) over \(\Sigma \cup \{c_1, \dots, c_k\}\) with fresh terminals \(c_i\):

\[ S \to A \mid B, \qquad A \to x_i\, A\, c_i \mid x_i\, c_i, \qquad B \to y_i\, B\, c_i \mid y_i\, c_i \qquad (1 \le i \le k). \]

(1) \(A\) alone is unambiguous: a sentence of \(A\) ends in \(c_{i_m} \cdots c_{i_1}\), which spells the sequence of productions used from the outside in, so the tree is determined; likewise for \(B\). (2) Hence a sentence has two trees only if it has one tree through \(A\) and one through \(B\). (3) A sentence \(u\, c_{i_m} \cdots c_{i_1}\) is derived from \(A\) iff \(u = x_{i_1} \cdots x_{i_m}\) and from \(B\) iff \(u = y_{i_1} \cdots y_{i_m}\), with the same index sequence, read off the \(c\) suffix. So \(G\) is ambiguous iff the PCP instance has a solution. The construction is computable, so a decision procedure for ambiguity would decide PCP.

Corollary 2.1.13 (What can be decided)

(a) For fixed \(G\) and \(w\), \(\#_{G}(w)\) is computable (Lemma 2.1.11), and FindAmbiguity is a semi-decision procedure: it halts with a witness for every ambiguous \(G\) once \(L \ge\) the length of the shortest ambiguous sentence, and no bound \(L\) can certify unambiguity. (b) Sufficient conditions are decidable: an LL(1) grammar (Lesson 2.3, Corollary 2.3.9) or an LR(1) grammar [Knu65] is unambiguous.

Proof

(a) The enumeration visits every sentence of length at most \(L\) in order of length; if \(G\) is ambiguous with shortest witness \(w^{*}\), it reaches \(w^{*}\) as soon as \(L \ge \lvert w^{*} \rvert\), and CountTrees returns \(\ge 2\) by Lemma 2.1.11. If some bound \(L(G)\) computable from \(G\) certified unambiguity, the resulting total procedure would decide ambiguity, contradicting Theorem 2.1.12. (b) is proved in the lessons cited.

Precedence and associativity by layering

Theorem 2.1.14 (Layered grammars are unambiguous and group as intended)

Let \(G_{\mathrm{lay}}\) be the output of Algorithm 2.1.9 and write \(E_{m+1} \triangleq P\). For every \(i \in \{1, \dots, m+1\}\): \(L(E_i)\) is the set of well-parenthesized expressions all of whose operators outside parentheses have level \(\ge i\), and every \(w \in L(E_i)\) has exactly one tree rooted at \(E_i\); in that tree, if \(w\) has an operator of level \(i\) outside parentheses, the root production is \(E_i \to E_i\, \mathit{op}\, E_{i+1}\) with \(\mathit{op}\) the last such operator (left-associative level) or \(E_i \to E_{i+1}\, \mathit{op}\, E_i\) with \(\mathit{op}\) the first (right-associative level); otherwise it is \(E_i \to E_{i+1}\).

Proof

By induction on \(\lvert w \rvert\), and for equal lengths on \(m + 1 - i\) (outer induction on length, inner on level from the top). Level \(m+1\) (\(P\)). \(P \to \mathtt{id}\) or \(P \to (\,E_1\,)\); the first token decides, and inside the parentheses the claim holds for \(E_1\) by the induction hypothesis on the shorter string. Level \(i \le m\), left-associative. Let \(w \in L(E_i)\). If \(w\) has no level-\(i\) operator outside parentheses, the recursive alternatives are impossible, because each would place a level-\(i\) operator outside parentheses at the root; so the root is \(E_i \to E_{i+1}\) and uniqueness follows from the hypothesis for \(E_{i+1}\) on the same string. Otherwise, a recursive alternative \(E_i \to E_i\, \mathit{op}\, E_{i+1}\) splits \(w = u\, \mathit{op}\, v\) with \(v \in L(E_{i+1})\); by the hypothesis \(v\) has no level-\(i\) operator outside parentheses, so \(\mathit{op}\) must be the last one in \(w\). That fixes the split and the production (the operator determines it, since the \(O_i\) are disjoint), and \(u\) and \(v\) are shorter, so their trees are unique. The base alternative \(E_i \to E_{i+1}\) is impossible because \(w \notin L(E_{i+1})\). The right-associative case is symmetric with first. Membership: every string with operators of level \(\ge i\) outside parentheses splits this way, so it is in \(L(E_i)\), and conversely every derived string has this form. The grouping stated is exactly Definition 2.1.8's intended grouping.

When it breaks: an operator that is both prefix and infix (unary and binary minus) or a ternary ?: needs its own level and more care; a non-associative level (a < b < c is an error in Python-like languages) needs \(E_i \to E_{i+1}\, \mathit{op}\, E_{i+1}\); and the layered grammar is left-recursive, so a top-down parser needs Lesson 2.4 before it can use it.

5. Complexity

Variables: \(n\) = sentence length; \(\lvert G \rvert\), \(\lvert P \rvert\), \(r\) as in Definition 2.1.1; \(m\) = number of derivation steps (for Replay) or precedence levels (for Layer); \(k\) = number of operators in an expression; \(L\) = length bound.

Technique Time (worst) Time (typical) Space Variables
Derivations and parse trees Replay \(O(m \cdot (n + m r))\); Leftmost, ToAst \(O(\text{tree size})\) linear in the tree \(O(n + m r)\) \(m\) steps
Ambiguity detection CountTrees \(O(\lvert P \rvert \cdot r \cdot n^{3})\); FindAmbiguity \(O(\lvert T \rvert^{L} \cdot \lvert P \rvert \cdot r \cdot L^{3})\) CountTrees fast for \(n \lesssim 100\) \(O(\lvert P \rvert \cdot r \cdot n^{2})\) memo as above
Layering \(O(m + \sum_i \lvert O_i \rvert)\) grammar construction — \(m + 1\) nonterminals \(m\) levels

Proposition 2.1.15 (Cost of CountTrees)

With memoization, CountTrees runs in \(O(\lvert P \rvert \cdot r \cdot n^{3})\) time and \(O(\lvert P \rvert \cdot r \cdot n^{2})\) space.

Proof

The memo keys of Seq are (production, suffix position within it, \(i\), \(j\)): at most \(\lvert G \rvert \le \lvert P \rvert (r + 1)\) suffixes times \(O(n^{2})\) spans; the keys of Count are \(O(\lvert N \rvert n^{2})\). Each Seq entry loops over at most \(n + 1\) split points doing \(O(1)\) work besides memoized calls, and each Count entry sums over its productions, whose total over all \(X\) is \(\lvert P \rvert\) per span. Total: \(O(\lvert P \rvert r n^{2} \cdot n) + O(\lvert P \rvert n^{2}) = O(\lvert P \rvert r n^{3})\).

Proposition 2.1.16 (Catalan explosion of the flat grammar)

In the flat grammar, the sentence \(\mathtt{id} \,(+\, \mathtt{id})^{k}\) has exactly \(C_k = \frac{1}{k+1}\binom{2k}{k} \sim \frac{4^{k}}{k^{3/2}\sqrt{\pi}}\) parse trees.

Proof

A tree of this sentence has only \(E \to E + E\) and \(E \to \mathtt{id}\) nodes, so it is a full binary tree with \(k\) interior nodes (one per +) and \(k + 1\) leaves, and the yield fixes the in-order labelling; conversely every full binary tree with \(k\) interior nodes yields this sentence. Choosing which + is at the root, \(j + 1\)-th from the left, splits the problem into \(j\) and \(k - 1 - j\) operators, so \(T_k = \sum_{j=0}^{k-1} T_j T_{k-1-j}\) with \(T_0 = 1\): the Catalan recurrence, whose closed form and asymptotics are standard.

Pathological input: for the flat grammar that is exactly this family: 132 trees at \(k = 6\) and 16 796 at \(k = 10\). Counting stays polynomial (\(O(n^{3})\)) because Count shares sub-results, but a parser that enumerates the trees is exponential. For layering, the pathological family is the operand: a lone id at the top level derives through the whole chain \(E_1 \Rightarrow E_2 \Rightarrow \cdots \Rightarrow P \Rightarrow \mathtt{id}\), so a CST has \(m + 1\) unit nodes per operand.

At scale: C's grammar (C23 §6.5) has 17 expression levels from primary-expression to expression, so a naive CST spends 17 unit nodes on each identifier; this is one reason Clang builds its AST directly (real-world box in §2) and parses binary operators by precedence climbing (Parser::ParseRHSOfBinaryExpression [CLANG-ParseExpr], Ch 4) instead of one function per level.

6. Variants and refinements

Derivations and parse trees

  • Shared packed parse forests (SPPF) [Sco08]: one DAG represents every tree of an ambiguous sentence in \(O(n^{3})\) space — trade-off: needed by GLR/Earley parsers (Ch 3, Ch 4), overkill for deterministic parsers.
  • Lossless CST with trivia (red–green trees) (Roslyn; swift-syntax [SWIFTSYNTAX-Recovery]; Ch 4): keep whitespace and comments attached to tokens and share immutable subtrees — trade-off: 2–3× the memory of an AST, but enables incremental reparsing and exact source round-tripping.

Ambiguity detection

  • Conservative approximation [Sch07]: over-approximate the grammar's derivations by a finite structure and report possible ambiguities — trade-off: always terminates, but can report false positives.
  • Sufficient conditions [Knu65 for LR(k); Knu71 for LL(k)]: a grammar that passes the LL(1) or LR(1) test is unambiguous — trade-off: many useful unambiguous grammars fail the test (the layered grammar is LR(1) but not LL(1)). Bison's counterexamples (real-world box in §2) are a search guided by exactly this test.

Precedence and associativity by layering

  • Precedence declarations [AJU75; Joh75]: keep the flat grammar and resolve the resulting parser conflicts with %left/%right — trade-off: a much smaller grammar, but the grammar alone no longer defines the language (Ch 3).
  • Precedence climbing / Pratt parsing [Pra73]: parse all levels in one loop driven by a table of binding powers — trade-off: fast and compact, but the grammar becomes implicit in code (Ch 4).

7. In real compilers

Derivations and parse trees

  • Clang (LLVM 23.1.2) builds an AST directly and keeps no CST: clang/include/clang/AST/Expr.h — BinaryOperator has getLHS, getRHS and an opcode, and parentheses survive only as ParenExpr (real-world box in §2).
  • Roslyn (C#, dotnet/roslyn) keeps a lossless CST: src/Compilers/CSharp/Portable/Syntax/ holds the syntax nodes; the "red" tree adds parent pointers over an immutable "green" tree.
  • swift-syntax (601.0.1) — Sources/SwiftParser/Statements.swift, Parser.parseStatement, builds a lossless CST that swift-format and refactorings use [SWIFTSYNTAX-Recovery].
  • The C "lexer hack": T * x; is a declaration if T names a type and a multiplication otherwise, so C is not context-free at the token level. Clang resolves it during parsing by asking Sema: clang/lib/Parse/ParseStmt.cpp — Parser::ParseStatementOrDeclarationAfterAttributes calls TryAnnotateName before deciding [CLANG-ParseStmt].

Ambiguity detection

  • Bison reports every conflict of an ambiguous grammar at generation time, with counterexamples under -Wcounterexamples (real-world box in §2), and in %glr-parser mode detects a real ambiguity at run time ("syntax is ambiguous") unless %merge resolves it [BISON-Manual].
  • ANTLR 4 reports ambiguities at run time: runtime/Java/src/org/antlr/v4/runtime/atn/ParserATNSimulator.java — reportAmbiguity (4.13.2), called when full-context prediction finds two alternatives that match the same input (Lesson 2.6) [ANTLR4-PATN].
  • C++ is ambiguous by design (the "most vexing parse" T x(U());); the standard resolves it by rule (anything that can be a declaration is one), and Clang implements the rule with tentative parsing: clang/lib/Parse/ParseTentative.cpp — Parser::isCXXDeclarationStatement [CLANG-ParseTentative] (real-world box in Lesson 2.5).

Precedence and associativity by layering

  • C, C++, Java standards specify expressions by layering (C23 §6.5.5 multiplicative-expression, §6.5.6 additive-expression).
  • Clang turns the layers back into a table: clang/include/clang/Basic/OperatorPrecedence.h — prec::Level and getBinOpPrecedence (LLVM 23.1.2) [CLANG-OpPrec]; clang/lib/Parse/ParseExpr.cpp — Parser::ParseRHSOfBinaryExpression climbs it, with isRightAssoc true for ?: and assignment [CLANG-ParseExpr] (real-world box in §2).
  • GCC gcc/c/c-parser.cc — c_parser_binary_expression (GCC 15) does the same for C with an explicit operator-precedence stack [GCC-CParser].

Find where LLVM does it. Open clang/include/clang/Basic/OperatorPrecedence.h (LLVM 23.1.2) and read the prec::Level enumeration. Question: which enumerator do + and - get? (quiz clang-prec-level)

8. Comparison

Technique Power / precision Speed (asymptotic · practical) Output / error quality Implementation effort Typical use
Derivations and parse trees (CST vs AST) Describe every CFG; one tree ⇔ one leftmost ⇔ one rightmost derivation Replay O(m·n); CST O(n) nodes · negligible next to parsing CST is lossless (every token); AST keeps meaning only Low: node types and a printer CST in IDE tooling (Roslyn, swift-syntax); AST in Clang, GCC
Ambiguity detection Undecidable in general; counting decides one sentence; LL(1)/LR(1) tests are sufficient only CountTrees O(|P|·r·n³) · bounded search exponential in L Produces a witness sentence with two trees Medium: memoized counting + enumeration Grammar design and review; GLR/ANTLR run-time ambiguity reports
Precedence/associativity layering Any finite table of binary infix operators, unambiguously O(m) grammar; m unit steps per operand in the CST Grammar is the specification; deep trees Low, but left recursion then needs Lesson 2.4 Language standards (C, Java); LR grammars without %left

Choose a CST when tools need the exact source back (formatters, refactorings, incremental IDE parsing); choose an AST when the consumer is a compiler back end. Use ambiguity detection when designing or changing a grammar: run the tree counter over all short sentences, and prefer grammars that pass the LL(1) or LR(1) test, which proves unambiguity. Use layering when the grammar is the specification (a standard) or feeds an LR generator; hand-written parsers usually implement the same table with precedence climbing instead (Ch 4).

9. Assessment

Technique Quiz ids (solutions/quizzes/ch02.yaml) Drill Flashcard tag Exercises
Derivations and parse trees leftmost-derivation-order, chomsky-classes ./course drill derivations --difficulty hard derivations — (grammar model is provided)
Ambiguity detection catalan-trees, layering-parenthesize (flat-grammar count) ./course drill derivations --difficulty easy ambiguity —
Layering layering-parenthesize, clang-prec-level ./course drill derivations --difficulty medium layering — (Pebble's expression grammar in later chapters)

The Chomsky hierarchy is covered by quiz and flashcards but has no drill: classifying a grammar by production shape is a one-line check (ChomskyType), and the interesting question, whether \(L(G)\) is regular, is undecidable for context-free \(G\).

Ambiguity belongs to the grammar

The flat and the layered grammar generate the same language, and only the first is ambiguous. Rewriting the grammar can remove ambiguity, unless the language is inherently ambiguous (Definition 2.1.5), in which case no grammar can.

References

See the chapter references.