Syntax Directed Translation (SDT)
Discover how compilers assign meaning to parsed syntax by attaching attributes and semantic rules directly to grammar productions.
Syntax Directed Definitions (SDD)
A Syntax Directed Definition is a context-free grammar where every grammar symbol has a set of attributes, and every production rule has a set of semantic rules for computing the values of those attributes.
The attribute value at a parse tree node is determined solely from the attribute values of its children (and itself).
Evaluated using a bottom-up traversal. Common in arithmetic expression evaluation.
The attribute value at a parse tree node is determined from the attribute values of its parent, itself, and its siblings.
Evaluated using a top-down or sideways traversal. Used for passing context like variable types down the tree.
Evaluation Order (Dependency Graphs)
To evaluate attributes in a parse tree, we must follow their dependencies. If attribute B.b depends on A.a, then A.a must be computed before B.b. This forms a directed graph called a Dependency Graph.
If the dependency graph has no cycles, a topological sort gives a valid evaluation order. If cycles exist, the SDD cannot be evaluated.
L-Attributed vs S-Attributed
S-Attributed Definitions
An SDD is S-attributed if every attribute is Synthesized.
Implementation: Can be easily evaluated during bottom-up LR parsing. The attributes can simply be pushed onto the parser's stack alongside the grammar symbols.
L-Attributed Definitions
An SDD is L-attributed (Left-to-Right) if inherited attributes of a symbol Xj on the RHS of a production A → X1 X2 ... Xn depend ONLY on:
- Inherited attributes of the head
A. - Either synthesized or inherited attributes of the symbols
X1, X2, ..., X(j-1)located to the left ofXj. - Attributes associated with
Xjitself.
Implementation: Can be evaluated during top-down LL parsing or during a single left-to-right depth-first traversal of the parse tree.
Syntax Directed Translation Schemes
An SDT Scheme is a context-free grammar in which program fragments (semantic actions) are embedded within the right sides of productions.
rest → + term { print("+") } rest1In an SDT, the semantic action is executed precisely when all the symbols to its left have been successfully parsed. This makes SDTs incredibly practical for real-world compilers generating intermediate code directly during parsing.