A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
A grammar is ambiguous if some string has multiple parse trees (different derivations). Left recursion (A → Aα | β) complicates top-down parsing. These properties affect compiler construction: ambiguous grammars must be disambiguated via precedence rules; left-recursive grammars require transformation for LL parsing. Analyzing and fixing these properties is essential for language design.
You know that a context-free grammar defines a language through production rules — nonterminals expand into sequences of terminals and other nonterminals until only terminal symbols remain. But not all grammars that define the same language are equal. Two grammars can generate identical sets of strings yet differ dramatically in their structural properties, and these differences have real consequences for whether you can build an efficient parser from them.
The most important property is ambiguity. A grammar is ambiguous if there exists at least one string that can be derived in two or more structurally different ways — meaning it has two distinct parse trees. Consider the classic expression grammar: `E → E + E | E * E | (E) | id`. The string `id + id * id` can be parsed as either `(id + id) * id` or `id + (id * id)`, giving two different parse trees that imply two different evaluation orders. This is a problem because a compiler needs exactly one interpretation for each program. The grammar is not "wrong" — it generates the right strings — but it fails to impose the unique structure that a parser requires. The fix is to rewrite the grammar to encode operator precedence and associativity directly into the production rules, typically by introducing separate nonterminals for each precedence level (e.g., `E → E + T | T`, `T → T * F | F`, `F → (E) | id`).
Another important structural property is left recursion — a production like `A → Aα | β`, where a nonterminal's first symbol in an expansion is itself. Left recursion is perfectly valid as a grammar, and left-recursive grammars are common in theoretical presentations. But top-down parsers (LL parsers), which try to predict productions from left to right, cannot handle left recursion because they enter an infinite loop trying to expand A. The standard remedy is left-recursion elimination: transform `A → Aα | β` into `A → βA'` and `A' → αA' | ε`, which generates the same strings in a right-recursive form that top-down parsers can handle. Bottom-up parsers (LR parsers), by contrast, handle left recursion naturally.
Understanding these properties is essential for bridging the gap between theoretical grammars and practical compilers. A grammar that is elegant for proving a language is context-free may need substantial rewriting before it can drive a parser. The discipline of analyzing grammars for ambiguity, left recursion, and other structural issues is what turns a formal language specification into a working piece of software.