Every parsing technique covered so far in this series answers a single, focused question: does this sequence of tokens follow the grammar of the language? Useful as that is, a compiler ultimately needs to do far more than simply confirm that a program is structurally valid. It needs to actually compute something from that structure, whether that is the value of a constant expression, the type of a variable, or the intermediate code that corresponds to a statement. Syntax directed translation is the framework that bridges this gap, attaching meaningful computation directly onto the grammatical structure a parser has already built.
The central idea behind syntax directed translation is elegantly simple once it clicks. Every node in a parse tree is assigned one or more pieces of information called attributes, and every production rule in the grammar is paired with a small rule describing how to compute those attributes based on the attributes of related nodes nearby. Once this pairing is in place, walking through a parse tree and evaluating these rules allows the compiler to compute almost anything it needs directly from the program's grammatical structure.
In this tutorial, you will learn what attributes are and the difference between synthesized and inherited attributes, how an annotated parse tree represents these computed values, what syntax directed definitions and syntax directed translation schemes are, how S-attributed and L-attributed definitions differ, and why this framework is so central to the phases of compilation that come after parsing.
Syntax directed translation refers to the general approach of associating semantic rules with the productions of a context-free grammar, so that meaningful values, referred to as attributes, can be computed for each node of a parse tree as it is built or traversed. Rather than treating parsing purely as a yes-or-no correctness check, syntax directed translation treats the grammar as a framework for organizing computation, with each grammar rule doubling as a small formula for calculating something useful.
This idea might sound abstract at first, but it maps onto something programmers already do intuitively when evaluating an arithmetic expression by hand. Given an expression like "3 + 4 * 2", a person naturally breaks it down according to its structure, computing the multiplication first and then adding the result, following exactly the same hierarchical grouping that a parse tree would represent. Syntax directed translation formalizes this intuitive process into a set of precise rules a compiler can apply automatically.
An attribute is simply a piece of information associated with a grammar symbol, whether that symbol is a terminal or a non-terminal. Attributes can represent almost anything relevant to compilation, including the numeric value of an expression, the data type of a variable, the number of a source code line for error reporting, or a piece of generated intermediate code. Attributes come in two broad categories, distinguished by the direction in which their values are computed within a parse tree.
| Type of Attribute | Description |
|---|---|
| Synthesized Attribute | An attribute whose value at a given node is computed using the attribute values of that node's children. Information flows upward, from the leaves of the parse tree toward the root. |
| Inherited Attribute | An attribute whose value at a given node is computed using the attribute values of that node's parent or its siblings. Information flows downward or sideways through the parse tree. |
Understanding this distinction is essential, since it directly determines how and when a particular attribute can be evaluated during parsing, and it forms the basis for classifying different kinds of syntax directed definitions, which are discussed later in this tutorial.
Synthesized attributes are the more intuitive of the two categories, since their values are built up from the bottom of the parse tree toward the top, mirroring how a person would naturally evaluate a nested arithmetic expression by first computing the innermost values and then combining them outward.
Grammar with Synthesized Attributes:
Expression -> Expression1 + Term { Expression.value = Expression1.value + Term.value }
Expression -> Term { Expression.value = Term.value }
Term -> Term1 * Factor { Term.value = Term1.value * Factor.value }
Term -> Factor { Term.value = Factor.value }
Factor -> Number { Factor.value = Number.lexval }
Each rule shown here describes how to compute the value attribute of a non-terminal directly from the value attributes of the symbols on the right-hand side of the same production. For the input "3 + 4 * 2", this set of rules would compute Factor.value as 3, 4, and 2 individually at the lowest level, then combine 4 and 2 into Term.value equal to 8, and finally combine 3 and 8 into Expression.value equal to 11, correctly respecting the usual precedence of multiplication over addition based purely on the grammar's structure.
Inherited attributes handle situations where a piece of information needs to flow downward or sideways through the parse tree, rather than being built up purely from a node's own children. A classic example involves tracking the data type declared at the beginning of a statement and making that type information available to each variable listed afterward.
Grammar with an Inherited Attribute:
Declaration -> Type IdentifierList { IdentifierList.inherited_type = Type.value }
IdentifierList -> Identifier , IdentifierList1
{ IdentifierList1.inherited_type = IdentifierList.inherited_type
Identifier.type = IdentifierList.inherited_type }
IdentifierList -> Identifier { Identifier.type = IdentifierList.inherited_type }
Here, the declared type is first computed as a synthesized attribute of the Type non-terminal, but it must then be passed down into every identifier listed in the declaration, which requires an inherited attribute, since this information originates from a node's parent and needs to reach nodes elsewhere in the tree rather than being computed purely from a node's own children.
An annotated parse tree, sometimes called a decorated parse tree, is simply an ordinary parse tree with the computed value of every attribute written alongside its corresponding node. Building an annotated parse tree by hand is a useful exercise for understanding exactly how syntax directed translation works, since it makes the flow of information through the tree completely explicit.
Annotated Parse Tree for: 3 + 4 * 2
Expression (value = 11)
/ | \
Expression + Term (value = 8)
(value = 3) / | \
| Term * Factor (value = 2)
Term (value=4)
(value = 3) |
| Factor
Factor (value=4)
(value = 3)
Reading this tree from the leaves upward shows exactly how the individual numeric literals are combined step by step, following the grammar's structure, until the final value at the root reflects the correctly computed result of the entire expression.
Compiler Design distinguishes between two closely related but slightly different ways of writing down the semantic rules associated with a grammar, each suited to a different stage of compiler construction.
| Aspect | Syntax Directed Definition | Syntax Directed Translation Scheme |
|---|---|---|
| Notation Style | Attaches semantic rules to productions without specifying exactly when each rule should be evaluated during parsing. | Embeds semantic actions directly within the right-hand side of a production, specifying the exact point at which each action should be executed. |
| Primary Purpose | Serves as a high-level, implementation-independent specification of what should be computed. | Serves as a more concrete, implementation-oriented guide for how to actually evaluate those computations during parsing. |
| Typical Usage | Used to describe and reason about the intended translation in a clear, declarative way. | Used more directly when implementing a parser that computes attribute values as it processes the input. |
Syntax Directed Translation Scheme:
Expression -> Expression1 + Term { print('+') }
Term -> Number { print(Number.lexval) }
In a translation scheme, the action to print a value is placed at a specific position within the production, indicating precisely when, relative to matching the surrounding symbols, that action should be carried out, which is especially useful for generating output, such as intermediate code, incrementally as parsing proceeds.
Because inherited and synthesized attributes flow through a parse tree in different directions, not every combination of attribute dependencies can be evaluated conveniently during a single top-to-bottom or bottom-to-top pass over the tree. Two important, well-behaved categories of syntax directed definitions address this practical concern.
| Category | Description |
|---|---|
| S-Attributed Definition | A syntax directed definition that uses only synthesized attributes. These definitions can be conveniently evaluated during a bottom-up parse, computing attribute values as reductions occur. |
| L-Attributed Definition | A syntax directed definition that may use both synthesized and inherited attributes, but restricts inherited attributes so that a symbol's inherited attribute only depends on attributes of symbols appearing to its left in the same production, or on inherited attributes of the parent. These definitions can be evaluated during a single left-to-right traversal of the parse tree. |
S-attributed definitions are particularly convenient for bottom-up parsers, since a synthesized attribute for a non-terminal can be computed at the exact moment that non-terminal is produced by a reduction, using the already-known attribute values of the symbols being reduced. L-attributed definitions, while slightly more restrictive than syntax directed definitions in full generality, are broad enough to cover a very large proportion of practical translation tasks, and are especially well suited to implementation using recursive descent, top-down parsers.
Syntax directed translation is not simply a theoretical curiosity discussed for its own sake. It is the practical mechanism through which nearly every later phase of a compiler is actually implemented. Semantic analysis relies on synthesized and inherited attributes to check types and track scope information as the parse tree is processed. Intermediate code generation relies on synthesized attributes to build up code fragments as each part of an expression or statement is recognized, combining smaller fragments into larger, complete pieces of intermediate code.
Beyond compiler construction, the same underlying idea, attaching computation directly to grammatical structure, appears in a variety of related tools, including some template engines, structured document processors, and domain-specific interpreters, wherever a well-defined grammar naturally maps onto a corresponding computation that needs to happen as that structure is recognized.
| Mistake | Correct Understanding |
|---|---|
| Assuming synthesized and inherited attributes are just two names for the same concept. | Synthesized attributes are computed from a node's children, flowing upward, while inherited attributes are computed from a node's parent or siblings, flowing downward or sideways. |
| Believing every syntax directed definition can be evaluated equally easily during any parsing strategy. | S-attributed definitions fit naturally with bottom-up parsing, while general inherited attributes often require the additional restrictions of an L-attributed definition to be evaluated conveniently during parsing. |
| Treating syntax directed definitions and syntax directed translation schemes as identical in every respect. | A syntax directed definition describes what should be computed without specifying timing, while a translation scheme explicitly places actions within a production to indicate exactly when they should be executed. |
| Overlooking the annotated parse tree as merely a diagram, rather than a genuine computational result. | An annotated parse tree represents the actual, computed values of every attribute across the tree, forming the concrete outcome that syntax directed translation is designed to produce. |
Syntax directed translation attaches meaningful computation directly to the grammatical structure a parser produces, using attributes to represent values such as expression results, types, or generated code fragments at every node of a parse tree. Synthesized attributes carry information upward from children to parents, while inherited attributes carry information downward or sideways, and together they allow an annotated parse tree to represent a fully computed result. Syntax directed definitions describe what to compute, while translation schemes specify exactly when to compute it, and the S-attributed and L-attributed categories identify well-behaved subsets of these definitions that align naturally with bottom-up and top-down parsing respectively.
In this tutorial, you learned what syntax directed translation is, the difference between synthesized and inherited attributes with worked examples, how annotated parse trees represent computed results, the distinction between syntax directed definitions and translation schemes, what S-attributed and L-attributed definitions mean, and why this framework underlies so much of what happens after parsing. With this foundation in place, you are ready to explore semantic analysis, where these same attribute-based techniques are used to check a program for type correctness and other meaning-related rules.