6.5 Parser Generators

A parser generator turns a grammar specification into parser tables or source code. It does not remove parsing design; it makes the design executable and reproducible. A serious grammar file is a public interface between lexer, parser, AST builder, diagnostics, and build system.

Two broad implementation paths exist, and choosing between them is a real engineering decision:

Neither is universally better: pick based on these dimensions, not on habit.

The Specification Is More Than Productions

Generator inputs commonly contain:

• Terminal declarations and their token/value types.

• Nonterminals and productions.

• Precedence and associativity declarations.

• Semantic actions that construct AST nodes or other values.

• Start symbol, error token rules, and generated-parser configuration.

Keep the lexer/parser boundary explicit. A grammar should reference stable token kinds such as IDENT, INT, PLUS, and LBRACE, not character-level spelling rules already handled by the lexer. Give every AST-producing production source spans deliberately; synthesized nodes need locations for diagnostics and tooling.

Semantic Actions, Precedence, and Error Hooks

Semantic actions run when the parser reduces. Use positional values such as $1, $2, and $$ only as a thin bridge; central AST constructors with named fields make actions easier to review. Treat actions as parser code: type-check them, test them, and avoid hidden mutable state that recovery can leave inconsistent.

Precedence declarations should document a language decision, not camouflage a conflict. A clear specification might say that * outranks +, both are left-associative, and unary - has a distinct precedence. Tests should assert AST shape for witness expressions, not merely that parsing succeeds.

Many generators support an error pseudo-token or recovery productions. Use it at stable syntax boundaries, such as statement terminators or block closers. A broad error rule can accept too much and hide the original failure; pair it with the precise diagnostic/recovery principles from Chapter 5.

Generated Does Not Mean Unreviewed

Check generated-parser output into version control only when the repository's build model calls for it. Otherwise regenerate in a deterministic build step and pin tool versions. Always preserve the grammar source, conflict reports, and golden AST/diagnostic tests; generated tables alone are hard to review.

Choose a generator by language, ecosystem, algorithm, error-recovery support, typed actions, IDE integration, and table size, not by nostalgia. A hand-written recursive-descent or Pratt parser remains a strong choice for a small, evolving language. A generator earns its place when grammar scale, established tooling, or LR expressiveness makes a declarative specification more valuable than bespoke control flow.

Treat the Grammar File as Production Code

Suppose a rule reads Expr: Expr PLUS Term. Its action should construct one well-named AST node, preserve the operator span, and avoid performing type checking or code generation. That separation keeps parse failures local and makes the same AST usable by formatters, IDEs, and later compiler phases. If an action needs ten lines of logic, move that logic into a typed helper; grammar files should show language structure, not hide business logic in braces.

Generator diagnostics are part of the workflow. Check the conflict report whenever grammar changes, keep expected conflicts documented, and save a counterexample input for each intentional precedence choice. Generated code should not be hand-edited: either commit it as a reproducible artifact when the repository requires that, or regenerate it during the build from pinned tool versions.

Practical Review Questions

• Does each terminal have one lexer owner and one stable token type?

• Does every production either build an AST node or intentionally forward a value?

• Are precedence declarations backed by AST-shape tests?

• Can an error production recover at a real boundary without swallowing the next valid declaration?