Finite automata cannot count without bound, so they cannot describe nested structures such as balanced parentheses, arithmetic expressions or blocks of code inside other blocks. These structures need a more expressive formalism: context-free grammars (CFGs). They are the foundation of the syntax of almost every programming language and of many data formats.
The definition
A context-free grammar is a 4-tuple G = (V, Σ, R, S) where:
- V is a finite set of variables (or nonterminals), representing syntactic categories;
- Σ is the alphabet of terminals, the symbols that actually appear in strings;
- R is a finite set of rules of the form A → α, where A is a variable and α is any string of variables and terminals (possibly empty);
- S ∈ V is the start variable.
"Context-free" means that the left side of every rule is a single variable with nothing around it: the variable A can be rewritten as α wherever it appears, regardless of what sits next to it.
Derivations
We start from the start variable and apply rules, replacing one variable at a time, until we get a string of terminals only. This sequence is a derivation. The language of the grammar, L(G), is the set of all terminal strings derivable from S.
A minimal example: the grammar with the single variable S and the rules
S → a S b
S → ε
generates exactly {aⁿbⁿ : n ≥ 0}. The derivation of aabb is S ⇒ aSb ⇒ aaSbb ⇒ aabb. The language no DFA can recognize is described with two rules.
Balanced parentheses
Strings of balanced parentheses are generated by:
S → ( S ) S
S → ε
The first rule says: a balanced sequence is empty, or it is a pair of parentheses enclosing a balanced sequence, followed by another balanced sequence. It is a recursive definition translated directly into rules.
Parse trees
A derivation can be represented as a parse tree: the root is S, each internal node is a variable whose children are the symbols on the right side of the rule applied, and the leaves read left to right form the string.
The tree forgets the order in which variables were replaced and keeps only the structure. This is why we distinguish the leftmost derivation, which always replaces the leftmost variable, from the rightmost one: every tree corresponds to one and only one leftmost derivation.
In compilers the tree is what really matters: it is where the meaning of the program comes from.
Ambiguity
A grammar is ambiguous if at least one string has two different parse trees. The classic case is arithmetic expressions:
E → E + E | E * E | ( E ) | n
The string n + n * n has two trees: one where the sum comes first, (n + n) * n, and one where the product comes first, n + (n * n). If the tree determines the computed value, ambiguity produces two different results.
Removing ambiguity with precedence levels
The standard solution introduces one variable per precedence level:
E → E + T | T
T → T * F | F
F → ( E ) | n
Now an expression is a sum of terms, a term is a product of factors, and a factor is a number or a parenthesized expression. The string n + n * n has a single tree, the one where the product is grouped inside the term. Left recursion in E → E + T also makes addition left-associative: n + n + n reads as (n + n) + n.
One important fact: there are inherently ambiguous languages, for which every possible grammar is ambiguous. Moreover, deciding whether an arbitrary CFG is ambiguous is undecidable: there is no general algorithm that always answers.
Normal forms
For proofs and for some algorithms it is convenient to bring a grammar into a standard form. The most widely used is Chomsky normal form, where every rule is of the form A → BC or A → a (with an exception for the empty string). Every CFG can be converted into this form without changing its language. The advantage is that every tree becomes binary, which enables algorithms such as CYK, which decides in cubic time whether a string belongs to the language.
Where they show up in real work
In my work grammars come up whenever I write a parser for a configuration format, a small query language or a validator for expressions typed by users. Starting from an explicit grammar, rather than from a series of hand-written conditions, makes the code shorter, easier to verify and far less fragile in the face of edge cases.
In short
- A CFG has rules with a single variable on the left and describes nested structures that DFAs cannot handle.
- Its language is the set of terminal strings derivable from the start variable.
- The parse tree represents structure and corresponds to exactly one leftmost derivation.
- A grammar is ambiguous if a string has two trees; precedence levels fix the expression case.
- Deciding whether a CFG is ambiguous is undecidable, and some languages are ambiguous by nature.
