Context-free grammar

A context-free grammar (CFG) is a formal grammar whose production rules are of the form A → α, where A is a single nonterminal symbol and α is a string of terminal and/or nonterminal symbols (and can be empty). The term "context-free" derives from the fact that the nonterminal A can always be replaced by α, regardless of the context (the surrounding symbols) in which it appears. Context-free grammars are a central formalism in computer science, particularly in the description of programming language syntax and the design of parsers, and they generate the class of context-free languages, which properly contains the class of regular languages.

Formal Definition

A context-free grammar G is formally defined as a 4-tuple G = (V, Σ, R, S) where:

• V is a finite set of nonterminal symbols (or variables).
• Σ is a finite set of terminal symbols (disjoint from V).
• R is a finite set of production rules. Each rule is a pair (A, α) where A ∈ V and α ∈ (V ∪ Σ)*. It is conventionally written as A → α.
• S ∈ V is the designated start symbol.

The language generated by the grammar, denoted L(G), is the set of all strings of terminal symbols that can be derived from the start symbol S by repeatedly applying the production rules. A string w ∈ Σ is in L(G) if and only if there exists a derivation S ⇒ w.

Derivations and Parse Trees

A derivation is a sequence of string replacements starting from the start symbol. For example, given rules S → aSb and S → ε (where ε denotes the empty string), a derivation for the string aabb is: S ⇒ aSb ⇒ aaSbb ⇒ aabb. Derivations can be leftmost (always replacing the leftmost nonterminal first) or rightmost. A parse tree (or derivation tree) is a hierarchical, graphical representation of a derivation, where the root is labeled S, internal nodes are labeled with nonterminals, leaves are labeled with terminals (or ε), and the children of a node labeled A are the symbols of α for some production A → α. The yield of the tree is the string formed by reading the leaves left-to-right.

Normal Forms

To simplify analysis and parsing algorithms, CFGs are often converted into restricted, equivalent forms. Two of the most important are Chomsky Normal Form (CNF) and Greibach Normal Form (GNF).

• Chomsky Normal Form (CNF): Every production rule is of one of two forms: A → BC (where B and C are nonterminals) or A → a (where a is a terminal). Rules like S → ε are also permitted if the empty string is in the language. Any CFG that does not generate the empty string can be converted into an equivalent CFG in CNF.
• Greibach Normal Form (GNF): Every production rule is of the form A → aα, where a is a terminal and α is a (possibly empty) string of nonterminals. This form is particularly useful for proving properties of pushdown automata and for certain parsing algorithms.

Relationship to Pushdown Automata

The class of languages generated by context-free grammars is exactly the class of languages recognized by nondeterministic pushdown automata (PDA). This equivalence is fundamental to formal language theory. A PDA provides a machine model for a CFG: its stack is used to store nonterminals, allowing it to handle the nested structures characteristic of context-free languages, such as balanced parentheses {(, )} or palindromes.

Ambiguity

A CFG is ambiguous if there exists at least one string in its generated language that has two or more distinct parse trees (or, equivalently, two or more distinct leftmost derivations). Ambiguity is generally undesirable in practical applications like programming languages because it can lead to multiple interpretations of the same statement. For example, the classic grammar for arithmetic expressions E → E + E | E E | id is ambiguous, as the string id + id id can be parsed to give different operator precedence. This is typically resolved by designing an unambiguous grammar or using a disambiguating rule (e.g., operator precedence and associativity rules in parser generators like Yacc/Bison).

Applications

The primary application of context-free grammars is in the specification and parsing of the syntax of programming languages and domain-specific languages. Tools like lexer and parser generators (e.g., ANTLR, Yacc, Bison) take a CFG (often with added semantic actions) as input and produce a parser for that language. CFGs are also used in computational linguistics for modeling natural language syntax, in document type definitions (e.g., XML schemas), and in the design of compilers and interpreters.

Limitations

While more powerful than regular expressions, context-free grammars cannot describe all possible formal languages. Languages that require matching of arbitrarily nested counts or cross-serial dependencies, such as {a^n b^n c^n | n ≥ 0}, are not context-free (as per the pumping lemma for context-free languages). Such languages fall into the more powerful classes of context-sensitive or recursively enumerable languages.