Context-Free Grammars
Productions, derivations, parse trees, and ambiguity.
The idea
A context-free grammar describes a language by generating its strings, one rewriting at a time.
To illustrate the idea, consider how an English sentence is assembled: a sentence is a noun phrase followed by a verb phrase, a noun phrase is an article followed by a noun, and so on, until every part has been replaced by an actual word. The rules are written once, may be applied in any order, and nest freely.
Formally, a context-free grammar consists of variables, symbols standing for something still to be expanded; terminals, the actual symbols of the alphabet; a designated start variable; and productions, rules $A \to w$ with $A$ a variable and $w$ any string of variables and terminals. To generate a string, begin with the start variable and repeatedly replace a variable by the right-hand side of one of its productions, stopping when only terminals remain. Such a sequence of replacements is a derivation. The grammar itself is a finite set of rules; its language is the set of strings its derivations reach.
Context-free names the restriction that the left-hand side of a production is a single variable, so a variable may be expanded wherever it occurs, whatever surrounds it.
A parse tree records a derivation without the order of the replacements: its root is the start variable, each internal node is a variable with its production's right-hand side as children, and its leaves, read left to right, spell the generated string.
Ways to work on it
- Walkthrough. Derive a string, identify the language, and read a parse tree.
- Practice. Trace a derivation and count the terminals produced.
- Hardest. Find two parse trees for one string and conclude ambiguity.
Builds on
Leads to
Not sure where to start? Take the ten-question placement test.