View source for Context-Free Grammar

A '''context-free grammar''' (CFG) is a [[Formal Grammar|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 Automaton|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|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.

''See also: [[Formal Grammar]], [[Compiler]], [[Parser]], [[LL Parser]], [[LR Parser]], [[Abstract Syntax Tree]], [[Pushdown Automaton]], [[Chomsky Hierarchy]], [[Programming Language]]''

[[Category:Computer Science]]
[[Category:Mathematics]]
[[Category:Language]]