Context-Free Grammar

A context-free grammar (CFG) is a formal grammar in which every production rule has a single non-terminal symbol on its left-hand side. This restriction — that the expansion of a non-terminal does not depend on the symbols surrounding it — gives context-free grammars their name and their computational character. They are exactly the grammars that can be parsed by pushdown automata, and they form the backbone of programming language syntax.

The expressiveness of CFGs is both their strength and their limitation. They can capture nested structures — parentheses, block scopes, expression trees — that regular grammars cannot. But they cannot capture context-sensitive constraints: a variable must be declared before use, a function must be called with the correct number of arguments, a type must match its context. These constraints are enforced not by the grammar but by the semantic analyzer that operates on the abstract syntax tree produced by the parser.

The centrality of CFGs to compiler design is not an accident. It reflects a deep design principle: separate what can be decided by structure from what requires context. The grammar handles the shape of the program; the semantic analyzer handles its meaning. This separation is not merely practical. It is a commitment to the idea that syntax is a self-contained subsystem that can be verified independently of semantics — a commitment that has shaped the entire field of formal language theory.