Lesson 3.5 — Conflicts, precedence declarations and operator-precedence parsing

Techniques: shift/reduce and reduce/reduce conflicts, their classification and counterexamples (Isradisaikul and Myers 2015, as in Bison's -Wcounterexamples); precedence and associativity declarations (Aho, Johnson and Ullman 1975; yacc) and when resolving by them is safe; operator-precedence parsing (Floyd 1963) as the historical special case · Pebble implements: nothing in pebblec (its expressions use precedence climbing, Ch 4); the lab resolves conflicts with %left/%right/%nonassoc (exercise E4) · Lab: labs/ch03-lr-toolkit (SPEC R5–R6; buildTable(G, A, M, &Prec); lr report tests/ch03/Inputs/expr-prec.grammar) · Prerequisites: Lessons 3.1–3.3; layered expression grammars (Lesson 2.1) · Time: 3 hours

Every grammar you feed to an LR generator for the first time has conflicts. Some are ambiguity (the flat expression grammar, the dangling else), some are a lack of lookahead, and in LALR some are merge artifacts (Lesson 3.3). This lesson is about reading, classifying and removing them — and about the most widely used removal technique: instead of rewriting an ambiguous expression grammar into precedence layers, keep it flat and declare which operator binds tighter, letting the generator delete the wrong actions. You will also see where that idea came from: Floyd's operator-precedence parsing, which needed no automaton at all.

1. Problem and motivation

Input: an LR table with conflicting cells, and optionally precedence declarations. Output: for each conflict, its kind and an explanation (a counterexample input), and a deterministic table that parses the language the grammar author meant.

Shift/reduce and reduce/reduce conflicts

A cell with two actions is a shift/reduce conflict if one of them is a shift and a reduce/reduce conflict otherwise. yacc resolved every conflict by default — shift over reduce, the earlier rule over the later — and printed only counts [Joh75]; authors then either rewrote the grammar or acknowledged the count with %expect. Explaining a conflict means finding an input on which both actions look valid; Isradisaikul and Myers' counterexample search [IM15] is what Bison 3.7+ prints with -Wcounterexamples: a unifying counterexample (one input, two trees: the grammar is ambiguous) or a nonunifying one (two inputs sharing a prefix: more lookahead or a merge artifact).

Precedence and associativity declarations

Aho, Johnson and Ullman [AJU75] showed that an ambiguous grammar plus disambiguating rules can yield a smaller, faster parser than the equivalent unambiguous layered grammar, and yacc turned the rules into declarations: %left, %right, %nonassoc give tokens levels, a rule takes the level of its last token, and a shift/reduce conflict between a rule and a token is decided by comparing them [Joh75]. Bison, Menhir, lemon and tree-sitter (prec.left, prec.right) all keep this design [BISON-Manual, MENHIR-Manual, TS-docs].

Operator-precedence parsing

Floyd's 1963 paper [Flo63] defined three relations between terminals — \(a \lessdot b\) (\(b\) starts a phrase inside \(a\)'s), \(a \doteq b\) (same phrase), \(a \gtrdot b\) (\(a\)'s phrase ends before \(b\)) — and a parser that shifts while the relation is \(\lessdot\) or \(\doteq\) and reduces when it is \(\gtrdot\). It needs no states and no items and works for operator grammars (no \(\varepsilon\), no two adjacent nonterminals). It was the method of the early 1960s ALGOL compilers, and survives today as the operator stack inside hand-written parsers — GCC's C front end says so in its source (§7).

2. Definitions and algorithms

Definition 3.5.1 (Conflict kinds; default resolution)

A cell ACTION\([q, t]\) with \(\ge 2\) actions is a shift/reduce conflict if it contains a shift and a reduce/reduce conflict otherwise (a cell with a shift and two reductions is shift/reduce in the lab's classification; Bison counts it once per kind). The default resolution keeps the shift if there is one, else the reduction by the lowest-numbered production [Joh75].

Definition 3.5.2 (Counterexamples [IM15])

For a conflict in state \(q\) on \(t\) between two actions, a unifying counterexample is a sentential form with two derivations (trees) that differ exactly in the conflicting choice at the point marked \(\bullet\) (so \(G\) is ambiguous). A nonunifying counterexample is a pair of forms \(\gamma \bullet t\, x_1\) and \(\gamma' \bullet t\, x_2\) whose stacks \(\gamma, \gamma'\) both lead to \(q\), one requiring each action.

Definition 3.5.3 (Precedence declarations)

A declaration list assigns each declared token \(t\) a level \(\mathrm{lev}(t) \in \{1, 2, \dots\}\) (later lines bind tighter) and an associativity \(\mathrm{assoc}(t) \in \{\mathrm{left}, \mathrm{right}, \mathrm{nonassoc}\}\). A production \(p\) gets the level of the last terminal of its right side that has one (yacc's %prec can override it; the lab does not implement %prec). A shift/reduce conflict between reduce \(p\) and shift on \(t\), both with levels, is resolved: reduce if \(\mathrm{lev}(p) > \mathrm{lev}(t)\); shift if \(\mathrm{lev}(p) < \mathrm{lev}(t)\); if equal, reduce for left, shift for right, and an error entry for nonassoc. Conflicts without levels stay (and get the default resolution).

Definition 3.5.4 (Operator grammar and Floyd's relations [Flo63])

\(G\) is an operator grammar if no right side is \(\varepsilon\) and none contains two adjacent nonterminals. With \(\mathrm{LEADING}(A) = \{ a \mid A \Rightarrow^{+} a \cdots \text{ or } A \Rightarrow^{+} B\, a \cdots \}\) and \(\mathrm{TRAILING}(A) = \{ a \mid A \Rightarrow^{+} \cdots a \text{ or } A \Rightarrow^{+} \cdots a\, B \}\), for terminals (and \(\$\)):

• \(a \doteq b\) if some right side contains \(a\, b\) or \(a\, B\, b\);
• \(a \lessdot b\) if some right side contains \(a\, B\) with \(b \in \mathrm{LEADING}(B)\), and \(\$ \lessdot b\) for \(b \in \mathrm{LEADING}(S)\);
• \(a \gtrdot b\) if some right side contains \(A\, b\) with \(a \in \mathrm{TRAILING}(A)\), and \(a \gtrdot \$\) for \(a \in \mathrm{TRAILING}(S)\).

\(G\) is an operator-precedence grammar if every pair has at most one relation.

Shift/reduce and reduce/reduce conflicts

Algorithm 3.5.5 (Classify conflicts and find a nonunifying witness)

• Input: an ACTION table on the LR(0) automaton (any method).
• Output: per conflicting cell \((q, t)\): its kind, and for each action a shortest stack \(\gamma\) reaching \(q\) plus a completion showing the action is needed.
• Precondition: \(G\) reduced.
• Postcondition: the kinds of Definition 3.5.1; each witness is a viable prefix \(\gamma\) with \(\delta^{*}(q_0, \gamma) = q\) of minimum length.
• Invariant: BFS distances are shortest path lengths in \(\mathcal{A}_0\).

function Conflicts(ACTION, A0):
    dist, parent ← BFS over A0 from q0            # shortest symbol strings to each state
    for each cell (q, t) with |ACTION[q, t]| ≥ 2:
        kind ← shift/reduce if some action is a shift else reduce/reduce
        γ ← symbols along parent pointers from q0 to q
        for each action act in ACTION[q, t]:
            if act = shift:  witness ← γ • t …   (an item [C → μ • t ν] of q explains it)
            if act = reduce A → β:  witness ← γ • t …  (item [A → β •] with t in its lookahead)
        report (q, t, kind, witnesses)

A unifying counterexample needs a search over pairs of derivations (Bison's src/counterexample.c [IM15]); the lab only classifies.

Precedence and associativity declarations

Algorithm 3.5.6 (Precedence resolution)

• Input: an ACTION table and declarations.
• Output: the resolved table and a log of resolutions.
• Precondition: actions in each cell sorted (shift first).
• Postcondition: every shift/reduce conflict where both the rule and the token have levels is gone (Definition 3.5.3); others are untouched.
• Invariant: cells are processed in the order (state, token name), and each (cell, reduction) pair is logged once — the lab's Resolved list.

Reference solution: resolve in solutions/labs/ch03-lr-toolkit/src/Table.cpp; oracle lr._resolve_precedence.

function Resolve(ACTION, prec):
    for each cell (q, t) holding a shift and ≥ 1 reduction, in (state, name) order:
        keep ← ACTION[q, t]
        for each reduction r = reduce p in the cell:
            if lev(t) or lev(p) undefined: continue
            if lev(p) > lev(t):          drop the shift from keep;  why ← "reduce (rule has higher precedence)"
            elif lev(p) < lev(t):        drop r from keep;          why ← "shift (token has higher precedence)"
            elif assoc(t) = left:        drop the shift;            why ← "reduce (%left)"
            elif assoc(t) = right:       drop r;                    why ← "shift (%right)"
            else:                        drop the shift and r;      why ← "error (%nonassoc)"
            log (q, t, p, why)
        ACTION[q, t] ← keep if keep ≠ ∅ else {error}

Operator-precedence parsing

Algorithm 3.5.7 (Operator-precedence parsing [Flo63])

• Input: the relations of Definition 3.5.4; \(w\).
• Output: accept with the reduced skeletons (right sides with nonterminals replaced by a placeholder \(N\)), or error.
• Precondition: an operator-precedence grammar.
• Postcondition: each reduced skeleton is a prime phrase of the current form (Theorem 3.5.11).
• Invariant: between consecutive terminals on the stack the relation is \(\lessdot\) or \(\doteq\); nonterminals on the stack are anonymous (\(N\)).

Oracle: lr.op_precedence_relations, lr.op_precedence_parse.

function OpPrecParse(rel, w):
    stack ← [$];  input ← w $
    loop:
        a ← topmost terminal on stack;  b ← next input token
        if a = $ and b = $:  return accept if stack = [$, N] else error
        if rel(a, b) = ⋖ or ≐:  push b; advance
        elif rel(a, b) = ⋗:
            repeat: pop symbols (N's go with their terminal) until the terminal now
                    on top ⋖ the last terminal popped
            if the popped skeleton is no right side (N for nonterminals): error
            push N
        else: error

3. Worked example

The ambiguous expression grammar (tests/ch02/Inputs/expr-ambiguous.grammar): \((1)\ E \to E + E\), \((2)\ E \to E * E\), \((3)\ E \to (\,E\,)\), \((4)\ E \to \mathit{id}\). Its LALR automaton has 10 states; the two with conflicts are

state	items (kernel)	LALR lookaheads of the reduce item
I8	\(E \to E \bullet + E\), \(E \to E + E \bullet\), \(E \to E \bullet * E\)	\(\{), *, +, \$\}\)
I9	\(E \to E \bullet + E\), \(E \to E \bullet * E\), \(E \to E * E \bullet\)	\(\{), *, +, \$\}\)

Shift/reduce and reduce/reduce conflicts on the example

cell	actions	kind	nonunifying witness	unifying?
ACTION[8, +]	s5, r1	shift/reduce	\(E + E \bullet + E\)	yes: \((E+E)+E\) vs \(E+(E+E)\)
ACTION[8, *]	s6, r1	shift/reduce	\(E + E \bullet * E\)	yes
ACTION[9, +]	s5, r2	shift/reduce	\(E * E \bullet + E\)	yes
ACTION[9, *]	s6, r2	shift/reduce	\(E * E \bullet * E\)	yes

All four are unifying: the grammar is ambiguous, so no lookahead or state splitting can help (Theorem 3.2.13; the canonical LR(1) table has 8 such cells). Contrast tests/ch03/Inputs/nonlalr.grammar, whose two reduce/reduce conflicts are nonunifying merge artifacts (Lesson 3.3), and \(S \to A\,A \mid a\,A\,b\), \(A \to a\): after one a with lookahead a, shift (for \(S \to a \bullet A\,b\)) competes with reduce \(A \to a\) (for \(S \to A\,A\)) — nonunifying, and resolving it by "shift wins" makes the parser reject the sentence a a.

Precedence and associativity declarations on the example

Declarations %left + (level 1) and %left * (level 2) (tests/ch03/Inputs/expr-prec.grammar uses the same idea with five operators). Algorithm 3.5.6's log (oracle, identical to lr report of the lab):

state	token	rule (level)	token level	decision	why
8	*	(1) \(E+E\) (1)	2	shift	token has higher precedence
8	+	(1) \(E+E\) (1)	1	reduce	equal, %left
9	*	(2) \(E*E\) (2)	2	reduce	equal, %left
9	+	(2) \(E*E\) (2)	1	reduce	rule has higher precedence

The resolved parser on id + id * id + id (stack shows states; reductions are the numbered productions):

step	stack	input	action
1	0	id + id * id + id $	shift 2
2	0 id 2	+ id * id + id $	reduce (4) E → id
3	0 E 3	+ id * id + id $	shift 5
4	0 E 3 + 5	id * id + id $	shift 2
5	0 E 3 + 5 id 2	* id + id $	reduce (4) E → id
6	0 E 3 + 5 E 8	* id + id $	shift 6 (resolved: * binds tighter)
7	0 E 3 + 5 E 8 * 6	id + id $	shift 2
8	0 E 3 + 5 E 8 * 6 id 2	+ id $	reduce (4) E → id
9	0 E 3 + 5 E 8 * 6 E 9	+ id $	reduce (2) E → E * E (resolved)
10	0 E 3 + 5 E 8	+ id $	reduce (1) E → E + E (resolved: %left)
11	0 E 3	+ id $	shift 5
12	0 E 3 + 5	id $	shift 2
13	0 E 3 + 5 id 2	$	reduce (4) E → id
14	0 E 3 + 5 E 8	$	reduce (1) E → E + E
15	0 E 3	$	accept

The tree is \(((\mathit{id} + (\mathit{id} * \mathit{id})) + \mathit{id})\): the tree of the layered grammar \(E \to E + T \mid T\), \(T \to T * F \mid F\) (Theorem 3.5.10).

Operator-precedence parsing on the example

Floyd's relations for the layered expression grammar tests/ch03/Inputs/expr.grammar (an operator grammar), from \(\mathrm{LEADING}(E) = \{(, *, +, \mathit{id}\}\), \(\mathrm{LEADING}(T) = \{(, *, \mathit{id}\}\), \(\mathrm{LEADING}(F) = \{(, \mathit{id}\}\) and TRAILING symmetrically; rows are the stack terminal \(a\), columns the input \(b\):

\(a \backslash b\)	+	*	(	)	id	$
+	⋗	⋖	⋖	⋗	⋖	⋗
*	⋗	⋗	⋖	⋗	⋖	⋗
(	⋖	⋖	⋖	≐	⋖
)	⋗	⋗		⋗		⋗
id	⋗	⋗		⋗		⋗
$	⋖	⋖	⋖		⋖

Every cell has at most one relation: an operator-precedence grammar. The parse of id + id * id (oracle op_precedence_parse):

step	stack	input	relation and action
1	$	id + id * id $	$ ⋖ id: shift
2	$ id	+ id * id $	id ⋗ +: reduce id
3	$ N	+ id * id $	$ ⋖ +: shift
4	$ N +	id * id $	+ ⋖ id: shift
5	$ N + id	* id $	id ⋗ *: reduce id
6	$ N + N	* id $	+ ⋖ *: shift
7	$ N + N *	id $	* ⋖ id: shift
8	$ N + N * id	$	id ⋗ $: reduce id
9	$ N + N * N	$	* ⋗ $: reduce N * N
10	$ N + N	$	+ ⋗ $: reduce N + N
11	$ N	$	accept

The parser never reduces the unit productions \(E \to T\), \(T \to F\): it works on skeletons, which is both its speed and its weakness (it cannot tell \(E\) from \(T\) and so accepts some non-sentences, §4).

Try it

./course drill shift-reduce-trace --difficulty hard traces the resolved expression parser (and the dangling else); ./course drill lr-table --difficulty hard asks you to classify every conflict.

4. Invariants and correctness

Shift/reduce and reduce/reduce conflicts

Proposition 3.5.8 (What a conflict tells you)

(a) A conflict in the canonical LR(1) table means \(G\) is not LR(1): it is ambiguous or needs more than one token of lookahead. (b) A conflict with a unifying counterexample proves \(G\) ambiguous. (c) A reduce/reduce conflict in LALR(1) or SLR(1) that is absent from LR(1) is an artifact of the method (Theorem 3.3.9). (d) Resolving a conflict by the default rule can remove sentences from the accepted language.

Proof

(a) is Theorem 3.2.12. (b): two trees for one sentential form extend (expanding the remaining nonterminals identically) to two trees for one sentence. (c): the canonical table is conflict-free there, so the method added the conflict. (d): in \(S \to A\,A \mid a\,A\,b\), \(A \to a\), the canonical LR(1) state after the first a holds \([S \to a \bullet A\,b,\ \$]\), \([A \to a \bullet,\ a]\) and \([A \to \bullet a,\ b]\): on lookahead a, shift and reduce \(A \to a\) conflict. With the shift, a a leads to the state \(\{[A \to a \bullet,\ b]\}\), which has no action on \(\$\): the sentence a a (\(S \Rightarrow A\,A \Rightarrow^{*} a\,a\)) is rejected. The oracle confirms it on \(L(G) \cap T^{\le 5}\).

Theorem 3.5.9 (Resolution is sound)

For any declarations, the resolved table's parser reduces only by productions of \(G\), so every tree it builds is a parse tree of \(G\) and the resolved language is a subset of \(L(G)\).

Proof

Resolution only deletes actions (or replaces a cell by error), so every run of the resolved parser is a run of the nondeterministic shift-reduce parser for \(G\); by Theorem 3.1.13 an accepting run spells a rightmost derivation of \(G\).

Theorem 3.5.10 (Precedence declarations reproduce the layered grammar [AJU75])

Let \(G_{\mathrm{flat}}\) have \(E \to E \circ E\) for binary operators \(\circ\) and \(E \to (\,E\,) \mid \mathit{id}\), with every operator declared (distinct levels per line, %left or %right). Then the resolved LALR(1) parser accepts exactly \(L(G_{\mathrm{flat}})\), and for each sentence it builds the unique tree in which, for every node \(E \to E_1 \circ E_2\), every operator \(\circ'\) at the top level of \(E_1\) has \(\mathrm{lev}(\circ') > \mathrm{lev}(\circ)\) or (\(=\) and \(\circ\) is left-associative), and every top-level \(\circ'\) of \(E_2\) has \(\mathrm{lev}(\circ') > \mathrm{lev}(\circ)\) or (\(=\) and \(\circ\) right-associative) — the tree of the precedence-layered grammar (Lesson 2.1).

Proof

Invariant. Outside parentheses, the stack has the shape \(E\, \circ_1\, E\, \circ_2 \cdots \circ_k\, E\) (the last \(E\) possibly still to come) with \(\mathrm{lev}(\circ_1) < \mathrm{lev}(\circ_2) < \cdots\), except that equal adjacent levels are allowed only for right-associative operators. It holds initially. When the lookahead is an operator \(\circ\) and the top is \(\cdots \circ_k\, E\), the LALR state is the one with \(E \to E\, \circ_k\, E \bullet\) and a shift item on \(\circ\); Definition 3.5.3 reduces exactly when \(\mathrm{lev}(\circ_k) > \mathrm{lev}(\circ)\), or equal and left-associative, which pops \(\circ_k\); this repeats until the condition fails, then \(\circ\) is shifted, preserving the invariant. On ) or $ every pending operator is reduced (these tokens have no level and there is no shift on them in those states, so the reduction is the only action). Tree property. An operator \(\circ\) is reduced (becomes a node \(E_1 \circ E_2\)) only when the next operator binds less tightly (or equally, left-assoc) — so no operator of lower or equal (for left) level ends up inside \(E_2\) — and it was shifted only after every tighter operator to its left had been reduced — so none of lower level is inside \(E_1\). Uniqueness and language. The layered grammar is unambiguous and generates the same strings, and for every sentence its tree satisfies the property; a tree with the property is determined by the levels (compare the root: it must be the top-level operator of minimum level, rightmost among equals for left-assoc, leftmost for right-assoc; recurse). The resolved parser never errs on a sentence: every resolved cell keeps an action, and the kept action is the one the property-tree needs. So the resolved language is \(L(G_{\mathrm{flat}})\).

When it is safe. Resolution by precedence is safe exactly when, for every sentence, some tree survives all the choices it makes; Theorem 3.5.10 is the canonical safe case, and the dangling else under "shift wins" is another (Lesson 2.3, Proposition 2.3.12). It is unsafe when a declaration decides a conflict that is not an operator ambiguity — for instance a token that is also used in a non-operator production, or a nonunifying conflict as in Proposition 3.5.8(d). %nonassoc is deliberately unsafe: id < id < id is removed from the language (tests/ch03/Inputs/nonassoc.grammar, test ch03.Driver.NonassocRejectsChains).

Operator-precedence parsing

Theorem 3.5.11 (Floyd's parser reduces prime phrases [Flo63])

For an operator-precedence grammar, Algorithm 3.5.7 accepts every sentence of \(L(G)\), and each reduction pops a prime phrase of the current right-sentential form (a phrase containing at least one terminal and no smaller such phrase) with nonterminals abstracted to \(N\).

Proof sketch (full proof: [Flo63]; textbook version: [ASU86 §4.6])

In a right-sentential form, consecutive terminals \(a\, (N)\, b\) satisfy \(a \doteq b\) if they belong to the same prime phrase, \(a \lessdot b\) if \(b\)'s phrase is nested inside the phrase containing \(a\) (so \(b\) is in LEADING of the nonterminal after \(a\)), and \(a \gtrdot b\) if \(a\)'s phrase ends before \(b\) (TRAILING). The leftmost prime phrase of a form is therefore delimited by the first \(\gtrdot\) from the left and the closest \(\lessdot\) before it, which is what the pop loop finds; the relations are functions of adjacent terminals only, so a parser that keeps terminals on the stack and consults the pair (top terminal, next token) finds the delimiters. Uniqueness of relations (the operator-precedence condition) makes every decision deterministic. What it does not guarantee: nonterminals are anonymous, so the parser only checks skeletons; when two nonterminals have right sides with the same skeleton in different contexts it can accept non-sentences [ASU86 §4.6]. The oracle rejects skeletons that match no right side, which is the usual partial check.

5. Complexity

Variables: \(c\) conflicting cells; \(\lvert T \rvert\) terminals; \(L\) declared levels; \(n\) input length.

Technique	Time (worst)	Time (typical)	Space	Variables
Conflict classification	\(O(\lvert Q \rvert \cdot (\lvert T \rvert + \lvert N \rvert))\) BFS + \(O(c)\)	instant	\(O(\lvert Q \rvert)\)	as above
Unifying counterexample search	exponential in the worst case (search over pairs of derivations; ambiguity is undecidable); Bison uses a time limit	fractions of a second on typical conflicts	as searched	[IM15]
Precedence resolution	\(O(c \cdot r \cdot L)\) with \(r\) reductions per cell	free at parse time	\(O(\lvert T \rvert)\) levels	as above
Operator precedence	relations \(O(\lvert T \rvert^2 + \lvert G \rvert \cdot \lvert N \rvert)\); parse \(O(n)\)	a few comparisons per token	\(\lvert T \rvert^2\) relations, or \(2\lvert T\rvert\) with precedence functions	as above

Proposition 3.5.12 (Declarations beat layering in states and in reductions)

For \(k\) left-associative binary operators in \(k\) distinct levels, the layered grammar (\(E_i \to E_i \circ_i E_{i+1} \mid E_{i+1}\) for \(i = 1..k\), \(E_{k+1} \to (\,E_1\,) \mid \mathit{id}\)) has \(2k + 2\) productions and an LR(0) automaton of \(3k + 6\) states, and its parser performs \(k + 1\) reductions per operand; the flat grammar with declarations has \(k + 2\) productions, \(2k + 6\) states and one reduction per operand.

Proof

Layered. States: \(I_0\) and \(S' \to E_1 \bullet\) (with \(E_1 \to E_1 \bullet \circ_1 E_2\)); for each \(i\) the state after \(E_i\) in a context expecting \(E_i\) (\(E_{i-1} \to E_i \bullet\) together with \(E_i \to E_i \bullet \circ_i E_{i+1}\)), the state after \(\circ_i\), and the state after \(E_{i} \circ_i E_{i+1}\) (\(E_i \to E_i \circ_i E_{i+1} \bullet\) and \(E_{i+1} \to E_{i+1} \bullet \circ_{i+1} \cdots\)); plus the states after (, id, ( E_1 and ( E_1 ). Counting per level gives \(3k\) plus a constant, which the oracle confirms: \(9, 12, 15, \dots, 27\) states for \(k = 1..7\). An operand id is reduced by \(E_{k+1} \to \mathit{id}\) and then climbs the unit chain \(E_k \to E_{k+1}, \dots, E_1 \to E_2\) as far as its context requires — up to \(k\) more reductions. Flat: one state after each operator (\(E \to E \circ \bullet E\) plus the closure) and one after each \(E \circ E\), plus six shared states: \(2k + 6\) (\(8, 10, \dots, 20\) by the oracle); an operand is one reduction \(E \to \mathit{id}\). This is Aho, Johnson and Ullman's argument for declarations: smaller tables and faster parsing, because the unit reductions disappear [AJU75]. The ch02 corpus confirms it: precedence.grammar (four layered levels) has 22 LR(0) states, expr-prec.grammar (five operators, flat) 16.

At scale: PostgreSQL 17's grammar declares 23 precedence lines (from %left UNION EXCEPT through %nonassoc '<' '>' '=' …, %left '+' '-' and %right UMINUS to %left JOIN CROSS …) and still reaches %expect 0 [PG-gram].

6. Variants and refinements

Shift/reduce and reduce/reduce conflicts

• %expect / %expect-rr [BISON-Manual]: declare the number of expected conflicts; the build fails when it changes — trade-off: cheap regression guard, but it counts, it does not identify.
• Menhir's .conflicts explanations [MENHIR-Manual]: for each conflict, a derivation pair rooted at the conflict's origin — trade-off: always produced, but can be long for merge-induced conflicts.
• Rewrite vs declare: layering the grammar (Lesson 2.1) instead of declaring — trade-off: an unambiguous grammar you can prove things about, at the price of more states (Proposition 3.5.12).

Precedence and associativity declarations

• %prec [Joh75]: give a rule the level of a pseudo-token (unary minus) — trade-off: needed for context-dependent operators, easy to misuse.
• tree-sitter's static and dynamic precedence [TS-docs]: prec.left(n, …) works like yacc's; prec.dynamic compares completed alternatives at runtime in GLR mode (Lesson 3.6) — trade-off: resolves conflicts that no static rule can, at runtime cost.
• Menhir's %on_error_reduce and precedence on productions [MENHIR-Manual] — trade-off: finer control, Menhir-specific.

Operator-precedence parsing

• Precedence functions \(f, g : T \to \mathbb{N}\) with \(a \lessdot b \iff f(a) < g(b)\) etc. — trade-off: \(O(\lvert T \rvert)\) space instead of \(O(\lvert T\rvert^2)\), but lose the ability to mark errors (every pair compares).
• Simple precedence (Wirth–Weber) [WW66]: relations between all grammar symbols — trade-off: labelled nonterminals, more grammars, bigger tables.
• Precedence climbing / Pratt parsing (Ch 4): the recursive-descent descendants used by Clang and LLVM's assembler — trade-off: no tables at all, precedence as numbers in code.

7. In real compilers

Shift/reduce and reduce/reduce conflicts

• Bison (3.8.2) src/conflicts.c — set_conflicts, count_state_sr_conflicts, count_state_rr_conflicts, and src/counterexample.c (counterexample_report_state, the search of [IM15]) [BISON-src].

Bison's counterexamples for the flat expression grammar

Reproduce (bison 3.8.2; any OS):

export LC_ALL=C   # plain '.' and '`->' in Bison's output; UTF-8 locales print '•' and '↳'
cat > expr.y <<'EOF'
%%
e: e '+' e | e '*' e | '(' e ')' | 'n' ;
EOF
bison -Wcounterexamples -o /dev/null expr.y 2>&1 | sed -n '1,20p'

Output (abridged: the first 20 lines; the other two counterexamples have the same shape):

expr.y: warning: 4 shift/reduce conflicts [-Wconflicts-sr]
expr.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 .
expr.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

What to notice: one Example: line with two derivations: a unifying counterexample (Definition 3.5.2), so the grammar is ambiguous — compare the two different examples of the merge-induced conflict in Lesson 3.3. The four conflicts are the four cells of §3.

Precedence and associativity declarations

• Bison (3.8.2) src/conflicts.c — resolve_sr_conflict implements Definition 3.5.3; log_resolution prints the messages below [BISON-src].
• PostgreSQL (REL_17_0) src/backend/parser/gram.y — the precedence block (%left UNION EXCEPT, …, %left Op OPERATOR, %left '+' '-', %right UMINUS, %left JOIN CROSS …) with comments on why several levels exist [PG-gram].

Bison logs each precedence resolution

Reproduce (bison 3.8.2; any OS):

cat > prec.y <<'EOF'
%left '+'
%left '*'
%%
e: e '+' e | e '*' e | '(' e ')' | 'n' ;
EOF
bison --report=solved --report-file=prec.output -o /dev/null prec.y
grep -E "^State (9|10)$|Conflict between" prec.output

Output (complete):

State 9
    Conflict between rule 1 and token '+' resolved as reduce (%left '+').
    Conflict between rule 1 and token '*' resolved as shift ('+' < '*').
State 10
    Conflict between rule 2 and token '+' resolved as reduce ('+' < '*').
    Conflict between rule 2 and token '*' resolved as reduce (%left '*').

What to notice: Bison's states 9 and 10 are our I8 and I9 (Bison inserts its accept state earlier), and the four decisions are the four rows of §3's log in the same words: equal level + %left ⇒ reduce; lower rule level ⇒ shift.

Operator-precedence parsing

• GCC (15.1.0) gcc/c/c-parser.cc — c_parser_binary_expression parses binary expressions "using operator-precedence parsing" with an explicit stack (box below) [GCC-CParser]; gcc/cp/parser.cc — cp_parser_binary_expression does the same for C++ with a precedence table [GCC-CPParser].
• LLVM's assembler (23.1.2) llvm/lib/MC/MCParser/AsmParser.cpp — AsmParser::parseBinOpRHS with getBinOpPrecedence, whose GNU and Darwin variants (getGNUBinOpPrecedence, getDarwinBinOpPrecedence) are two different precedence tables [LLVM-AsmParser].

GCC's C parser describes itself as an operator-precedence parser

Reproduce (GCC source at tag releases/gcc-15.1.0; needs network):

curl -sS https://raw.githubusercontent.com/gcc-mirror/gcc/releases/gcc-15.1.0/gcc/c/c-parser.cc \
  | sed -n '/A binary expression is parsed using operator-precedence parsing/,/as appropriate when the operators are pushed and popped/p'

Output (complete):

  /* A binary expression is parsed using operator-precedence parsing,
     with the operands being cast expressions.  All the binary
     operators are left-associative.  Thus a binary expression is of
     form:

     E0 op1 E1 op2 E2 ...

     which we represent on a stack.  On the stack, the precedence
     levels are strictly increasing.  When a new operator is
     encountered of higher precedence than that at the top of the
     stack, it is pushed; its LHS is the top expression, and its RHS
     is everything parsed until it is popped.  When a new operator is
     encountered with precedence less than or equal to that at the top
     of the stack, triples E[i-1] op[i] E[i] are popped and replaced
     by the result of the operation until the operator at the top of
     the stack has lower precedence than the new operator or there is
     only one element on the stack; then the top expression is the LHS
     of the new operator.  In the case of logical AND and OR
     expressions, we also need to adjust c_inhibit_evaluation_warnings
     as appropriate when the operators are pushed and popped.  */

What to notice: "the precedence levels are strictly increasing" on the stack is the invariant of Theorem 3.5.10's proof, and popping "triples E[i-1] op[i] E[i]" while the new operator's level is lower or equal is Floyd's ⋗ reduction of a prime phrase N op N (Algorithm 3.5.7) — inside a hand-written recursive-descent parser.

LLVM's assembler has two precedence tables

Reproduce (llvm-mc 23.1.2; any OS):

printf '.long 2+3*4\n.long 10-4-3\n.long 1+2<<3\n' | llvm-mc -triple=x86_64-unknown-linux-gnu
printf '.long 1+2<<3\n' | llvm-mc -triple=x86_64-apple-macosx

Output (complete):

    .long   14
    .long   3
    .long   17
    .long   24

What to notice: 10-4-3 = 3 is left associativity; 1+2<<3 is 17 with the GNU table (<< binds tighter than +: \(1 + (2 \ll 3)\)) and 24 with the Darwin table (\((1+2) \ll 3\)). Same parser (parseBinOpRHS), two relation tables — the essence of precedence parsing [LLVM-AsmParser].

Find where LLVM does it. Open llvm/lib/MC/MCParser/AsmParser.cpp (LLVM 23.1.2) and read getGNUBinOpPrecedence. Which precedence number does it assign to + and -? (quiz mc-plus-precedence)

8. Comparison

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Conflict classification and counterexamples	Diagnoses every conflict; unifying ones prove ambiguity	Linear classification · counterexamples usually < 1 s	The best explanation a generator can give	Classification low; unifying search high	Every generator (Bison -Wcounterexamples, Menhir .conflicts)
Precedence and associativity declarations	Resolves operator ambiguities exactly (Theorem 3.5.10); can remove sentences if misapplied	Free at parse time; fewer states than layering	Silent once resolved; Bison logs with --report=solved	Trivial for the user	yacc/Bison/Menhir/tree-sitter expression grammars, PostgreSQL
Operator-precedence parsing	Operator-precedence grammars only; skeletons, may accept non-sentences	\(O(n)\), tiny tables	Weak: errors only on missing relations	Very low	Historical compilers; the operator stack inside RD parsers (GCC, LLVM MC)

Choose explicit conflict analysis when a generator reports conflicts: classify first (unifying ⇒ ambiguity ⇒ declare or rewrite; nonunifying ⇒ lookahead or merge artifact ⇒ IELR or refactor). Choose precedence declarations when the conflicts are binary-operator ambiguities: it is the smallest, fastest and most readable fix. Choose operator precedence when you parse expressions by hand inside another parser and want a table-driven loop; today precedence climbing (Ch 4) usually wins.

9. Assessment

Technique	Quiz ids (solutions/quizzes/ch03.yaml)	Drill	Flashcard tag	Exercises
Conflicts	conflict-kinds, unifying-counterexample	./course drill lr-table --difficulty hard	conflicts	E4
Precedence declarations	prec-resolution, prec-trace, mc-plus-precedence	./course drill shift-reduce-trace --difficulty hard	precedence	E4
Operator precedence	floyd-relation, mc-plus-precedence	none: a historical special case; its relations appear in the quiz and flashcards, and its modern form (precedence climbing) gets its own drills in Ch 4	op-precedence	—

%left does not mean 'this operator is left-associative everywhere'

It means: in a shift/reduce conflict between a rule whose last declared token is at this level and a token at this level, reduce. If a token also appears in a non-operator rule (a comma in argument lists vs the comma operator), the declaration silently decides conflicts you did not intend. Read --report=solved after adding declarations.

References

See the chapter references.