4.1 CFG, Terminals, Nonterminals, Productions, Start Symbols

Regular languages gave the lexer a finite amount of memory. That is enough for identifiers, numbers, operators, and whitespace, but it is not enough for the nested structure of a program. A lexer can recognize ( and ) as separate tokens. It cannot, with finite state alone, verify that an arbitrary number of opening parentheses are matched by the right number of closing parentheses, nor can it describe nested expressions, blocks, or recursive function calls.

A context-free grammar (CFG) describes this next layer of structure. It is a finite set of rewrite rules. Starting from one distinguished symbol, the rules generate exactly the token sequences that are syntactically legal in the language. A parser normally runs the idea in reverse: it receives a token stream and tries to prove that the stream could have been generated from the start symbol.

The word context-free has a precise meaning. A production replaces one nonterminal regardless of the symbols surrounding it. For example, if Expr -> Expr + Term, then an Expr may be expanded using this rule wherever that Expr appears. Rules such as "replace x only when it follows let" are not CFG productions; that kind of context-sensitive condition belongs in later name or type analysis.

The Formal Shape of a Grammar

We write a CFG as:

G = (V, T, P, S)

where:

• V is a finite set of nonterminals.

• T is a finite set of terminals.

• P is a finite set of productions.

• S is the distinguished start symbol, and S ∈ V.

The conventional requirement is that V and T are disjoint. A symbol should not be both a grammar variable and a final token. A production has a single nonterminal on its left-hand side:

A -> α

Here A is in V, while α is a finite sequence of terminals and nonterminals. It may be empty. The empty right-hand side is written as ε.

For a small expression language:

G = (V, T, P, Expr)

V = { Expr, Term, Factor }
T = { id, number, +, *, (, ) }

Expr   -> Expr + Term | Term
Term   -> Term * Factor | Factor
Factor -> id | number | ( Expr )

Expr, Term, and Factor are not words that the user types. They are structural categories invented by the language designer. In contrast, id, number, +, *, (, and ) are terminal categories that come from the lexer.

In a real compiler, a terminal is usually a token kind, not a raw character. The parser should normally see IDENT, INT, PLUS, LPAREN, and RPAREN, not individual Unicode code points. That keeps the lexer-parser contract clean: lexical spelling rules stay in the lexer, while grammar rules describe token order and nesting.

Terminals Are Final, Nonterminals Are Work

The most useful mental model is this:

• A terminal is a category that remains in a final sentence of the language.

• A nonterminal is unfinished structural work that can still be expanded.

For the expression grammar, the string:

id + number * id

is terminal-only. It is a candidate sentence in the language. The intermediate form:

Expr + Term

is not a source program. It is a sentential form: a temporary mixture of terminals and nonterminals during a derivation.

This distinction also prevents a common beginner mistake. A token named IDENT is a terminal in the grammar, even though it can stand for infinitely many lexemes such as total, count_2, or renderNode. The grammar needs the token category, not a separate production for every possible identifier spelling.

The same principle applies to literals. A grammar can say:

Primary -> IDENT | INT | STRING

It does not need a production for 42, one for 43, and so on. The lexer has already recognized each concrete lexeme and attached its value or text to the terminal token.

Productions Are Alternatives, Not Imperative Commands

The vertical bar in:

Factor -> id | number | ( Expr )

means "one of these alternatives may be used." It is shorthand for three separate productions:

Factor -> id
Factor -> number
Factor -> ( Expr )

Productions are declarative. They do not say which alternative a parser must pick at runtime. They define the legal shapes. A parsing strategy in later chapters decides how to choose an alternative from lookahead tokens, parser states, precedence declarations, or backtracking rules.

An ε production needs special care:

Params -> ParamList | ε

This says a call may have parameters or may have none. ε is not a character, a missing token, or a lexer error. It is the empty sequence. Because empty alternatives can create optional syntax, cycles, and parser conflicts, later chapters will repeatedly ask whether an ε rule is necessary and how it affects FIRST/FOLLOW sets.

The Start Symbol Defines the Program Boundary

The start symbol is the one category that represents a complete compilation unit. It is not automatically the first nonterminal written in a file. Pick it deliberately:

Program -> DeclarationList EOF

With this design, a parser accepts only if it can recognize an entire Program and then reaches EOF. If the start symbol were merely Expr, the parser could accept 1 + 2 while silently ignoring ; garbage, which is almost never desirable for a compiler frontend.

Some grammars introduce an augmented start symbol:

Start -> Program EOF

The extra wrapper is especially useful in LR parsing and in formal transformations. It gives the parser a single unambiguous acceptance target.

A Grammar Is a Contract Between Phases

Good grammar design makes later phases simpler. It should expose syntactic structure that semantic analysis, IR generation, formatting, and diagnostics need. Consider assignments:

Stmt -> IDENT = Expr ;

This grammar says an assignment begins with an identifier-shaped token. It does not prove that the identifier names a mutable variable. It does not prove that Expr has a compatible type. It only gives later stages a reliable syntax node with a left side, right side, and source ranges.

Likewise, a CFG cannot fully express every programming-language rule:

• "A variable must be declared before use" needs a symbol table.

• "The two sides of + must have compatible types" needs type checking.

• "break must occur inside a loop or switch" needs contextual semantic analysis.

• "A function must return a value on every control-flow path" needs control-flow reasoning.

The grammar should therefore be neither too weak nor overloaded with semantic work. Its job is to recognize hierarchical token structure and produce a stable foundation for the rest of the frontend.

Use the Grammar at the Right Layer

Stmt -> IDENT = Expr ; says the left side has identifier syntax and the right side has expression syntax. It does not prove that the identifier was declared, is mutable, or has a compatible type. Keeping those jobs separate makes diagnostics precise: the parser can report a missing semicolon, while later analysis can report an assignment to an immutable name.

For every new production, ask what complete unit the nonterminal represents, what token ends it, and whether the start symbol requires EOF. Those questions prevent a parser from accepting a valid prefix while silently ignoring trailing garbage.