Introduction to Context-free Grammars

Formal grammar

The term “grammar” conjures up memories of grammar school, where we learned the rules of our native language. A formal grammar, as we have already seen, is an attempt to codify the structure of languages in the abstract, based on research conducted in the 1950s, most notably by Noam Chomsky. A formal grammar consists of the following:

• Nonterminal symbols (also called variables), one of which is the start symbol.
• Terminal symbols (the “letters” of the alphabet in use, $\Sigma$).
• A set of rewrite rules, whereby one begins with the start variable, then substitutes replacements for the variables, and finally obtains a string in the language consisting only of terminal symbols.

The rewrite rules are also called production rules, or just productions, for short. Consider the following simplistic grammar, which generates random sentences: