Formal grammar

A formal grammar generates strings by repeatedly replacing symbols according to production rules. It is commonly written as G = (N, Σ, P, S): N is a finite set of nonterminals, Σ is a terminal alphabet, P is a finite set of productions, and S is the start symbol.¹

For example, the rules S → aSb and S → ε generate strings containing equal numbers of as followed by bs, including the empty string. A derivation records the successive replacements, while the language L(G) is the set of terminal strings that can be derived from S. The grammar is therefore a generator and a precise description of structural well-formedness.

The Chomsky hierarchy classifies grammars by the restrictions placed on their productions and by the computational resources needed to recognize their languages.² Regular grammars correspond to finite automata and describe relatively simple patterns; context-free grammars correspond to pushdown automata and can express nested constructions such as balanced parentheses. Context-sensitive grammars are associated with bounded linear-space computation, while unrestricted grammars characterize the recursively enumerable languages recognized by Turing machines.

Each successive class contains the preceding one in expressive power, although membership and parsing can become more difficult. The hierarchy is a classification of formal mechanisms, not a claim that every natural language belongs neatly to one level. In practical software, regular and context-free methods account for much lexical analysis and programming-language syntax.

Formal grammars support recognition and parsing: a recognizer tests whether a string belongs to a language, while a parser constructs a derivation or syntax tree explaining its structure. Compiler front ends commonly use regular expressions or finite automata for tokens and context-free grammars for expressions, statements, and nested blocks.³

A grammar is ambiguous when some string has more than one distinct parse tree. Arithmetic expressions illustrate the issue: without precedence and associativity rules, a string such as a + b × c may receive competing structures. Parser designers remove ambiguity, impose disambiguation conventions, or preserve multiple parses when uncertainty is meaningful. Grammars also appear in protocol specifications, markup languages, natural-language processing, and formal verification.

Formal grammars can be equivalent as language generators even when their rules look very different, and deciding equivalence is generally undecidable for unrestricted grammars.⁴ Some apparently minor choices also matter: allowing ε-productions affects empty-string behavior, and useless or unreachable symbols can be removed without changing the generated language.

Context-free grammars have several normal forms, including Chomsky normal form, that simplify theoretical proofs and algorithm design without changing the language except for controlled treatment of ε. More specialized systems extend ordinary productions with attributes, probabilities, or mildly context-sensitive mechanisms. These variants connect grammar theory with syntax-directed translation, statistical language processing, and descriptions of dependencies that ordinary context-free rules cannot capture efficiently.⁵

Terminal

A symbol that appears in strings of the generated language and is not replaced during derivation.

Nonterminal

A grammar symbol used to represent an intermediate syntactic category.

Production

A rule specifying how one sequence of grammar symbols may be replaced by another.

Derivation

A sequence of rule applications beginning with the start symbol.

Ambiguous grammar

A grammar in which at least one generated string has more than one distinct parse tree.