Ambiguous Grammars
A grammar is ambiguous when one token sequence has two parse trees. `1 + 2 * 3` reading as both 9 and 7 is the toy case; the dangling `else` is the one that shipped in C, and both are fixed the same three ways.
What exactly makes a grammar ambiguous, and what are my options once it is?
The token sequence is unchanged; what is at stake is the *set* of parse trees over it. An unambiguous grammar makes that set a singleton, and every later phase — evaluation order, type checking, code generation — is written assuming it is. When the set has two members the program has two meanings and the compiler picks one, usually silently.
A disambiguation is legal only if it selects exactly one of the trees the grammar already generated, for every input, and never changes which inputs are accepted. Adding precedence declarations, layering nonterminals or specifying a matching rule are all legal in that sense. Silently dropping an alternative is not: it changes the language, and programs that used to compile stop.
Key points
- Ambiguity means two distinct parse trees for one token sequence — not that the input is confusing and not that the parser errors.
1 + 2 * 3under a flat grammar derives as both 9 and 7; nothing in the grammar prefers either.- The dangling
elseis the same defect in production languages; C, C++, Java, C# and JavaScript all fix it with a specification sentence rather than a grammar change. - There are three fixes: layer the grammar, declare precedence beside it, or change the syntax so the ambiguity cannot be written.
- A generator conflict is a decidable approximation of ambiguity, not the thing itself — unambiguous grammars can conflict and the two need different fixes.
- Bison resolves conflicts silently by default, so an unexamined warning is a language decision made by a tool.
One input, two trees
Return to the two-production grammar from [[formal-grammars]], extended with *. It generates 1 + 2 * 3, and it generates it twice — once with the addition at the root and once with the multiplication at the root. Both are valid derivations. Nothing in the grammar prefers either, so the grammar has not specified what 1 + 2 * 3 means.
This is worth being precise about, because "ambiguous" is used loosely. It does not mean the input is confusing, or that a human would hesitate, or that the parser reports an error. It means: there exist two distinct parse trees for one sentence. Equivalently, two distinct leftmost derivations. The compiler will not tell you; it will pick whichever its algorithm reaches first and produce a number.
The two readings differ by four, which is the entire visible symptom. There is no diagnostic, no warning, and no crash — which is why this class of bug is found by a user reporting that arithmetic is wrong rather than by a test suite.
| expression | → | number | |
| expression | → | expression "+" expression | No level below it, so nothing says `*` binds tighter. |
| expression | → | expression "*" expression | Two recursive binary rules at the same level is the standard recipe for ambiguity. |
expression with the * rule first.expression with the + rule first. This is the reading every mainstream language specifies.The dangling else
if rule is stated normatively in the C standard, the C++ standard, the Java Language Specification and ECMA-262, so all five languages agree and the reading is portable. What is *not* portable is the reader's expectation: source indentation frequently suggests the other tree, which is why several style guides and -Wdangling-else in GCC and Clang exist.The arithmetic case is a teaching example. The dangling else is the one that is actually in the languages you use. Write the obvious grammar for conditionals — a statement is if (e) s, or if (e) s else s, or something else — and if (a) if (b) x = 1; else x = 2; has two parse trees. The else can attach to the inner if or to the outer one, and the two programs behave differently whenever a is true and b is false.
C, C++, Java, C# and JavaScript all inherit this grammar and all resolve it with a rule stated outside the grammar: an `else` binds to the nearest preceding unmatched `if`. The grammar remains ambiguous; the specification adds a sentence. Bison, given the naive grammar, reports one shift/reduce conflict and resolves it by shifting, which happens to implement exactly that rule — which is why the default resolution is usually right and always worth checking.
The languages that do not have this problem removed it by syntax. Python has no braces to omit, so the indentation settles it. Go and Rust require braces around every branch, so there is no bare statement for the else to be confused about. Ada writes end if, which closes explicitly. Each of those is a deliberate cost paid at the keyboard to avoid a cost paid in the specification.
| stmt | ::= | "if" "(" expr ")" stmt | The unmatched form. |
| stmt | ::= | "if" "(" expr ")" stmt "else" stmt | The matched form. Both are `stmt`, so a nested `if` can be either. |
| stmt | ::= | assignment ";" |
a is false, nothing happens. This is the reading C, C++, Java, C# and JavaScript all specify, and the one Bison's default shift produces.a is false, x becomes 2. Indentation in the source can suggest this reading strongly while the compiler does the other one.The three fixes, and what each costs
Given an ambiguous grammar there are exactly three moves, and choosing between them is a real design decision rather than a matter of taste.
Layer the grammar. Introduce a nonterminal per precedence level — expression, term, factor — so that only one tree exists. The grammar is then unambiguous by construction, machine-checkably, with no declarations beside it. You pay one nonterminal per level, a deeper parse tree, and an edit to several rules whenever an operator is added. This is what [[productions-and-derivations]] showed and what most published language grammars do.
Declare the disambiguation. Keep the flat, ambiguous grammar and add a precedence and associativity table beside it — Bison's %left, %right, %nonassoc, or a Pratt parser's binding-power table. Adding an operator is one line. You pay by having a grammar that is ambiguous as written, so the document alone no longer specifies the language, and by making conflicts easy to silence without understanding them.
Change the syntax. Make the ambiguity unrepresentable: mandatory braces, an explicit terminator, a different token. You pay in verbosity forever, and you buy a grammar with nothing bolted on. Go, Rust and Ada all took this route for the dangling else, and Rust took it again with the turbofish.
expression ::= number
| expression "+" expression
| expression "*" expressionexpression ::= expression "+" term | term
term ::= term "*" factor | factor
factor ::= number | "(" expression ")"Legal because the layered grammar generates exactly the same sentences as the flat one — every string of numbers joined by + and * is still accepted — while generating exactly one tree for each. The "(" expression ")" alternative is load-bearing: without it, the layering would also remove the author's ability to request the other grouping, which *would* change the language.
The same layering applied to an operator set where the intended precedence differs from the layer order silently produces the wrong tree everywhere. Putting << below + gives C's precedence, where a + b << c is (a + b) << c; putting it above gives Go's, where the same source is a + (b << c). Both grammars are unambiguous, both compile, and one of them computes something the author did not write.
Conflicts are not ambiguity
A parser generator reporting shift/reduce conflict is telling you that its construction — LALR(1) for Bison, by default — could not decide what to do in some state with one token of lookahead. That is evidence, and it is often evidence of ambiguity, but it is not the same claim. Unambiguous grammars can produce conflicts because the *algorithm* is weaker than the grammar class; ambiguous grammars can occasionally avoid conflicts entirely in the states you happen to reach.
The practical rule: never silence a conflict without producing the two derivations. Bison 3.8 and later will do most of the work for you — -Wcounterexamples prints an actual input string that the grammar parses two ways, or explains that the conflict is a limitation of the lookahead rather than a genuine ambiguity. That flag turned a research skill into a two-second check, and it is the single most useful thing to know about Bison.
The reason this matters is the default. Bison resolves shift/reduce conflicts by shifting and reduce/reduce conflicts by preferring the earlier rule, and it does so quietly unless you count them with %expect. A grammar that "builds with warnings" is a grammar whose meaning was decided by a tool default, and the difference between that default and your intent is a class of bug that produces no error at any stage.
How it works
The steps, in the order the compiler takes them.
- Suspect ambiguity when two recursive productions for the same nonterminal can both apply to the same input position.
- Confirm it by constructing two leftmost derivations of one concrete input and drawing both trees.
- Evaluate both trees under a non-commutative operator so the difference is a visible number rather than a shape.
- Choose a fix: layering for a specification, a precedence table for an extensible implementation, a syntax change when the construct is genuinely error-prone for readers too.
- Re-run the generator and confirm the conflict count went to zero, or is exactly the number declared with
%expect. - Add a regression test that evaluates the disambiguated construct, since a grammar test that only checks acceptance cannot detect a tree change.
How it breaks
What the engineer observes when it goes wrong — not what goes wrong internally.
- A calculator or a query language ships with a flat expression grammar, and
1 + 2 * 3returns 9. No error, no warning; a user reports that the totals are wrong. - Source is indented as though the
elsebelonged to the outerif, the compiler binds it to the inner one, and a branch that looks like it always runs never runs when the outer condition is false. - A shift/reduce conflict is silenced with a precedence declaration that also, unnoticed, changes how an unrelated construct parses — the build is clean and one expression in the codebase changes meaning.
- A grammar is "fixed" by deleting an alternative rather than by disambiguating, and code that compiled last release now fails to parse — a breaking change delivered as a bug fix.
When it helps
- Reviewing a new operator or statement form: asking "what else could this parse as" before implementation is far cheaper than after.
- Diagnosing wrong-answer bugs in an interpreter or a query engine, where the arithmetic is right and the tree is wrong.
- Reading a conflict report meaningfully instead of adding declarations until the warning count reaches zero.
When it hurts
- Deliberately ambiguous grammars are the right tool for natural language and for tolerant tooling, where an Earley or GLR parser produces every reading and a later phase chooses. Insisting on unambiguity there removes capability.
- Chasing unambiguity in a grammar for a language that is not context-free anyway — C++ being the standing example — spends effort on a property the language cannot have.
What it costs
Every one of these is paid by something.
- Layering the grammar buys machine-checkable unambiguity and costs a nonterminal per precedence level, deeper trees, and a multi-rule edit for every new operator.
- A precedence table beside a flat grammar buys single-line extensibility and costs the property that the grammar alone specifies the language — the table is now part of the specification and nothing checks that it matches the prose.
- Removing the ambiguity by syntax buys a clean grammar and clean diagnostics and costs every user of the language a small permanent tax in keystrokes and visual noise.
What else you could do
What a different compiler or language does instead, and when that is better.
- GLR or Earley parsing, which produce a parse *forest* rather than a tree and defer the choice to a later phase that can consult types or symbols. This is how several C++ and natural-language frontends work, and it costs both time and a great deal of machinery downstream.
- PEG, whose ordered choice makes ambiguity structurally impossible: the first alternative that matches wins. The cost is that a grammar with a genuinely unintended second reading now silently prefers the first, and no tool can tell you the second existed — see
[[parser-generators]]. - Pratt parsing, which replaces the whole question with a binding-power table consulted at run time; there is no grammar to be ambiguous, and precedence becomes data rather than structure — see
[[pratt-parsing]].
See it for yourself
The flag, dump or tool that shows you this directly.
bison -Wcounterexamples grammar.yprints a concrete input parsed two ways, or reports that the conflict is a lookahead limitation rather than an ambiguity. Bison 3.8 and later.bison -v grammar.ywritesgrammar.outputlisting every conflict with the state and the competing rules — read it before adding any precedence declaration.gcc -Wdangling-else x.candclang -Wdangling-else x.cwarn when anelsebinds somewhere the indentation does not suggest.python3 -c "import ast; print(ast.dump(ast.parse('1 + 2 * 3')))"shows the tree an unambiguous grammar produced:BinOp(1, Add, BinOp(2, Mult, 3)).
Plausible wrong readings
Stated the way a confident engineer states them.
- "An ambiguous grammar makes the parser fail." It makes the parser choose. Failure would be the good outcome; silence is what actually happens.
- "Bison reported a conflict, so my grammar is ambiguous." Possibly. Conflicts also arise from the one-token lookahead limit on grammars that are perfectly unambiguous, and the two need different fixes.
- "Adding
%left '+'fixes the grammar." It fixes the *parser*. The grammar is still ambiguous as written, and anyone implementing from the grammar alone will get a different answer. - "The dangling else is a theoretical problem." It is normatively resolved in five mainstream language specifications precisely because it was not.
Misconceptions
The claim, and what is actually true.
Go deeper
The same idea at increasing depth. Stop wherever it stops being useful.
overview
A grammar is ambiguous when one input has two possible tree shapes. 1 + 2 * 3 can group as (1+2)*3 or 1+(2*3), and unless the grammar says which, the compiler picks one silently. The fix is either to write the grammar in levels, to declare precedence beside it, or to change the syntax so only one reading can be written.
practical
Treat every generator conflict as a bug report until proven otherwise. Run bison -Wcounterexamples; if it hands you an input parsed two ways, you have real ambiguity and must decide which reading is meant. If it says the conflict is a lookahead limitation, the fix is a grammar refactor rather than a precedence declaration. Adding %left until the warnings stop is how a language quietly acquires a meaning nobody chose.
advanced
The deep point is that ambiguity is a property of the grammar, not of the language: many ambiguous grammars generate languages for which an unambiguous grammar exists, and the ambiguity is a defect of the writing. But not always — there are *inherently ambiguous* context-free languages for which no unambiguous grammar exists at all. Programming languages are essentially never in that class, which is why "rewrite the grammar" is always available. The reason implementations still keep ambiguous grammars plus declarations is not theory but maintenance: a flat rule with a table is one line per operator, and a layered grammar is a multi-rule edit each time. That is a real, defensible engineering trade, and the cost is that the specification and the implementation now live in two artefacts that must agree.
How much this depends on
Nothing in this domain is true of every compiler. These say how much.
if resolution is likewise normative in C, C++, Java, C# and JavaScript.%expect suppresses it. ANTLR 4 instead resolves ambiguity by preferring the textually first alternative and does so without a warning by default, so a grammar ported between the two tools can change meaning.* higher precedence than + holds across C, C++, Java, C#, JavaScript, Python, Go and Rust, but precedence tables differ elsewhere in ways that matter: << sits above + in Go and below it in C, and APL evaluates strictly right to left with no operator precedence at all.If you were asked this in an interview
- Show me two parse trees for
1 + 2 * 3and say what each evaluates to. - Explain the dangling else, and give me two ways a language could remove it.
- Bison reports one shift/reduce conflict. What do you do before shipping?