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.

Not sure where to start? Take the ten-question placement test.