Formal Grammar

A formal grammar is a set of rules that precisely defines which strings belong to a formal language and which do not. Unlike the informal grammars of natural language — which tolerate ambiguity, recursion without base cases, and context-dependent interpretation — a formal grammar is unambiguous, decidable, and mechanically processable. It is the contract between the language designer and the compiler writer: the designer promises that all valid programs conform to the grammar, and the compiler promises to recognize all such programs and reject all others.

The most widely used framework is the Chomsky hierarchy, which classifies grammars by the complexity of their rules. Regular grammars generate the languages recognized by finite automata. Context-free grammars generate the languages recognized by pushdown automata and parsed by the algorithms — LL, LR, recursive descent — that dominate programming language implementation. Context-sensitive and unrestricted grammars occupy the upper reaches of the hierarchy and rarely appear in compiler design, not because they are unimportant but because parsing them is computationally intractable.

The choice of grammar class is a trade-off between expressiveness and tractability. A language that requires context-sensitive rules to parse is a language that cannot be compiled in linear time by standard algorithms. This trade-off is not merely technical. It is a constraint on the design space of programming languages: the grammars that are efficiently parseable are the grammars that can be used in practice. Formal grammar theory is therefore not an abstract branch of mathematics but the engineering boundary that separates conceivable languages from implementable ones.