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$).