Introduction
Regular languages cannot count or nest: aⁿbⁿ and balanced brackets are beyond them. Yet nesting is everywhere in computing, from brackets in arithmetic to blocks in programs and tags in HTML. Context-free grammars (CFGs) describe exactly this kind of structure. They are the formal basis of every programming language's syntax, and of the parsers that read it.
How it works
A grammar has four parts: variables (such as S and E), terminals (the symbols of the strings, such as a, b, ( and )), productions (rules A → body) and a start variable. The body may mix variables and terminals, or be empty (ε).
To derive a string, start from the start variable and repeatedly replace one variable by the body of one of its rules, until only terminals remain. "Context-free" means a rule can be used whatever surrounds the variable.
The grammar S → aSb | ε (two rules, written with |) generates aⁿbⁿ. Each use of the first rule adds an a on the left and a b on the right, so the counts always match:
form = "S"
steps = [form]
for body in ["aSb", "aSb", ""]:
form = form.replace("S", body, 1)
steps.append(form or "ε")
print(" ⇒ ".join(steps))More grammars:
- Balanced brackets: S → (S)S | ε.
- Palindromes over {a, b}: S → aSa | bSb | a | b | ε.
- Arithmetic: E → E+T | T, T → T*F | F, F → (E) | x.
A parse tree records a derivation as a tree: the start variable at the root, each variable's children being the body of the rule used. A leftmost derivation always replaces the leftmost variable, and each parse tree corresponds to exactly one leftmost derivation.
A grammar is ambiguous if some string has two parse trees. With E → E+E | EE | x, the string x+xx can be grouped as x+(x*x) or (x+x)*x, which compute different values. The arithmetic grammar above avoids this with separate levels (E, T, F) for each precedence.
To list a grammar's strings in Python, expand the leftmost variable in every possible way, and stop growing forms that already have too many terminals.
Syntax
grammar = {"S": [["a", "S", "b"], []]} # S → aSb | ε
form = ("S",) # a sentential form
i = next(k for k, s in enumerate(form) if s in grammar) # leftmost variable
form[:i] + tuple(body) + form[i + 1:] # apply one rule
Example
def generate(grammar, start, max_len):
found, seen = set(), set()
todo = [(start,)]
while todo:
form = todo.pop()
terminals = [s for s in form if s not in grammar]
if form in seen or len(terminals) > max_len or len(form) > 2 * max_len + 2:
continue
seen.add(form)
i = next((k for k, s in enumerate(form) if s in grammar), None)
if i is None:
found.add("".join(form))
continue
for body in grammar[form[i]]:
todo.append(form[:i] + tuple(body) + form[i + 1:])
return sorted(found, key=lambda w: (len(w), w))
anbn = {"S": [["a", "S", "b"], []]}
balanced = {"S": [["(", "S", ")", "S"], []]}
print("aⁿbⁿ: ", [w or "ε" for w in generate(anbn, "S", 6)])
print("balanced:", [w or "ε" for w in generate(balanced, "S", 6)])Line by line
- A grammar is a dictionary from each variable to its list of bodies;
[]is ε. generatekeeps a stack of sentential forms. It always expands the leftmost variable, in every possible way.- Forms with too many terminals, or that are too long, are dropped, and
seenstops the same form being expanded twice, so the search ends. - aⁿbⁿ gives ε, ab, aabb and aaabbb up to length 6.
- Balanced brackets give 1, 1, 2 and 5 strings of lengths 0, 2, 4 and 6: the Catalan numbers.
Expected result
aⁿbⁿ: ['ε', 'ab', 'aabb', 'aaabbb']
balanced: ['ε', '()', '(())', '()()', '((()))', '(()())', '(())()', '()(())', '()()()']
In the real world
The syntax of Python, Java and SQL is published as a grammar, and parser generators such as ANTLR and Bison turn a grammar into a parser automatically. JSON, XML and Markdown processors, query languages and configuration formats all start from grammars. Compilers rewrite ambiguous grammars into unambiguous ones so that a - b - c and a + b * c always mean the same thing.
Common mistakes
- Writing a grammar that generates too much, such as S → aS | Sb for aⁿbⁿ; check short strings.
- Forgetting the empty case, so ε (or the base case of the nesting) cannot be produced.
- Assuming ambiguity is a property of the language; usually a better grammar fixes it.
- Expanding forever when generating in code: limit the number of terminals.
Best practices
- Write one rule per kind of structure, and name variables after what they produce (E for expression, T for term).
- Check every grammar by generating its shortest strings.
- Encode precedence with one variable per level, and associativity with left or right recursion.
Summary
A context-free grammar generates strings by rewriting variables with productions, starting from the start variable. It can describe nesting, such as aⁿbⁿ and balanced brackets. Derivations and parse trees show how a string is produced, and a grammar is ambiguous when some string has two parse trees.
Quick check
Key takeaways
- A context-free grammar replaces one variable at a time, whatever surrounds it.
- Context-free grammars describe nesting, such as aⁿbⁿ and balanced brackets, which regular languages cannot.
- Ambiguity is a property of a grammar; it can often be removed by adding levels.
Practice problems for this lesson
My notes
Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.