Syntax-directed translation

Syntax-directed translation connects each grammar production with semantic actions or equations that describe what should be computed when the production is recognized. A production such as expr → expr + term can therefore specify construction of an abstract-syntax-tree node, calculation of a type, emission of intermediate code, or evaluation of a constant expression. The grammar supplies the structural order; the attached rules supply the translation.

The method is broader than simply executing code inside a parser. A translation scheme places actions at selected points in the right-hand side of productions, while an attribute grammar describes values associated with grammar symbols and equations governing them. Synthesized attributes move information upward from children to parents; inherited attributes pass contextual information downward or across a tree. Knuth’s formal treatment of attribute grammars made these dependencies explicit and gave the approach a foundation for analyzing evaluation order.¹

The central engineering problem is evaluating attributes in an order that respects their dependencies. An S-attributed definition uses only synthesized attributes, so values can usually be computed during bottom-up parsing. This makes it a natural fit for shift-reduce parsers and for tasks such as expression evaluation or abstract-syntax-tree construction.

L-attributed definitions permit restricted inherited information: an inherited attribute of a symbol may depend on attributes of its parent and symbols to its left. That restriction supports left-to-right, depth-first evaluation and is useful for propagating declared types, symbol-table environments, and expected contexts. Unrestricted attribute dependencies may require a separate dependency graph or multiple passes; cyclic dependencies are invalid unless a language-specific fixed-point method is supplied. In practical compiler pipelines, semantic analysis often combines syntax-directed rules with explicit traversal passes rather than forcing every computation into parser actions.¹²

Syntax-directed translation is used to build intermediate representations and to perform early semantic processing. Typical translations include converting concrete syntax into abstract syntax trees, generating three-address code, resolving implicit conversions, recording declarations in symbol tables, and producing diagnostics tied to source locations. Parser generators such as GNU Bison support semantic values and actions associated with grammar rules, while ANTLR supports parse-tree listeners and visitors that separate grammar recognition from later tree-based translation.²³

The technique also clarifies the boundary between parsing and later compiler phases. A small expression language may translate directly from parser reductions to postfix notation or machine-like instructions. A production compiler usually preserves an intermediate representation instead, because later passes need opportunities for type checking, control-flow analysis, optimization, register allocation, and target-specific lowering. LLVM’s intermediate representation illustrates this staged approach: front ends translate source syntax into a structured, typed form that can be analyzed and transformed independently of the original parser.⁴

Syntax-directed translation is not limited to conventional compilers or to producing executable code. The same framework describes interpreters, source-to-source translators, syntax highlighting, documentation generators, query processors, and domain-specific-language tooling. A grammar can attach actions that emit formatted text, construct XML-like trees, or accumulate static facts rather than machine instructions.

A subtle distinction separates translation schemes from attribute grammars. Translation-scheme actions are ordered operational events embedded in a production, so their correctness depends on when the parser executes them. Attribute grammars state declarative dependencies and can be implemented by different evaluation strategies. Another practical edge case occurs with error recovery: a parser may execute actions on partially recognized or repaired input, so side effects such as symbol-table insertion or code emission must be designed to tolerate failure or be delayed until the relevant construct is validated. Modern parser frameworks often favor parse trees and visitors for this reason, trading some immediacy for clearer phase separation and easier testing.³⁵

Attribute grammar

A context-free grammar augmented with attributes and semantic equations that define information flow among grammar symbols.

Synthesized attribute

An attribute computed from attributes of a symbol’s children and passed toward the parent.

Inherited attribute

An attribute supplied to a symbol from its parent or from neighboring symbols in the derivation.

Translation scheme

A grammar whose productions contain explicitly positioned semantic actions executed during parsing.