Slide 4.1: Translational semantics
Slide 4.3: Syntax-directed definitions
Home

Syntax-Directed Translation
Syntax-directed translation (SDT) is a method of translating a string into a sequence of actions by attaching one such action to each rule of a grammar.
Thus, parsing a string of the grammar produces a sequence of rule applications. Each language construct is associated information by attaching attributes to the grammar symbol(s) representing the construct. A syntax-directed definition specifies the values of attributes by associating semantic rules with the grammar productions. For example, an infix-to-postfix translator might have a product and rule where the symbol “||” is the operator for string concatenation:

Production Semantic Rule
<E> ::= <E1> + <T> Code(<E>) = Code(<E1>) || Code(<T>) || '+'

The subscript in <E1> distinguishes the <E> in the production body from the <E> in the head. Both <E> and <T> have a string-valued attribute Code. The semantic rule specifies that the string Code(<E>) is formed by concatenating Code(<E1>), Code(<T>), and the character ‘+’.

Syntax-Directed Translation Schemes
A translation scheme is a notation for attaching program fragments to the productions of a grammar. The program fragments are executed when the production is used during syntax analysis. The combined result of all these fragment executions, in the order induced by the syntax analysis, produces the translation of the program to which this analysis/synthesis process is applied. The translator parses the input token stream, builds the parse tree, and then traverses the tree as needed to evaluate the semantic rules at the parse-tree nodes. The following figure shows the translation: