Skip to content
Tutorials Center
My learning

Topics

Lesson 28 of 61 ยท Semantic Analysis

Syntax-Directed Translation

Learn syntax-directed translation: attributes, synthesized and inherited values, S-attributed and L-attributed grammars, and semantic actions with Python code.

A parser can tell you that 2 + 3 * 4 is a valid expression and show its tree. It cannot, by itself, tell you the answer is 14, what type it has, or what machine code it should become. All of those require meaning, and meaning has to be computed from the structure the parser found. Syntax-directed translation (SDT) is the technique for doing so: you attach pieces of information and small computations to the rules of the grammar, and the structure of the parse tree decides the order in which they are evaluated.

This idea powers type checking, symbol-table construction, building the abstract syntax tree and generating intermediate code. It is also the bridge between the parsing chapter and the rest of the track. By the end of this lesson you will know what attributes are, why there are two kinds, which grammars allow a one-pass evaluation, and how to put it all into running Python code.

Attributes

An attribute is a value attached to a grammar symbol, which means to every node of the parse tree labelled with that symbol. A node for expr might carry its numeric value val, its type type, the generated code code, or the line number line. Attributes are written with dot notation: E.val, T.type.

A semantic rule says how to compute an attribute from other attributes. The classic example is a desk calculator:

TEXT
E -> E1 + T      E.val = E1.val + T.val
E -> T           E.val = T.val
T -> T1 * F      T.val = T1.val * F.val
T -> F           T.val = F.val
F -> ( E )       F.val = E.val
F -> num         F.val = num.lexval

Here lexval is an attribute supplied by the lexer. The grammar is the same one we used in bottom-up parsing; only the rules on the right are new. A grammar plus semantic rules is called a syntax-directed definition (SDD). If you draw the parse tree and write each node's attribute values beside it, you have an annotated parse tree.

Synthesized attributes

An attribute is synthesized if its value at a node is computed from the attributes of that node's children (and perhaps the node's own token). Information flows upward, from the leaves to the root. The desk calculator above uses only synthesized attributes: E.val depends on E1.val and T.val, which are the node's children.

Synthesized attributes are the easy ones. To compute them, you visit the children first and the parent afterwards, which is a post-order traversal. That is exactly what happens in a bottom-up (LR) parser: each time it reduces a rule, all the children are already on the stack with their values, so the parser can run the semantic rule right then and store the result with the new nonterminal. This is what $$ = $1 + $3 does in a Bison file (parser generators).

Inherited attributes

An attribute is inherited if its value at a node is computed from the attributes of its parent or its siblings. Information flows downward or sideways. Inherited attributes are natural wherever context decides meaning. For example, in a declaration float x, y, z;, the type float appears once, on the left, but every name in the list needs it:

TEXT
D -> T L         L.type = T.type
T -> int         T.type = integer
T -> float       T.type = float
L -> L1 , id     L1.type = L.type ; addType(id.entry, L.type)
L -> id          addType(id.entry, L.type)

L.type is inherited: it is passed from the T sibling to L, and then from each L to its child L1. A pure bottom-up evaluator cannot compute it directly, since the information flows against the direction of reduction.

flowchart TD
    D["D"] --> T["T<br/>type = float"]
    D --> L["L<br/>type = float (inherited)"]
    L --> L1["L1<br/>type = float (inherited)"]
    L --> id3["id: z"]
    L1 --> id1["id: x"]
    L1 --> id2["id: y"]
    T -. "copied to sibling" .-> L

Information flows upward (synthesized) from the keyword into T, then sideways and downward (inherited) to every name.

A good rule of thumb: use synthesized attributes for results that depend on what is below (values, types of expressions, generated code), and inherited attributes for facts that depend on what is around (the expected type, the declared type, the current scope, the loop depth).

Evaluation order and the two useful classes

Given an arbitrary SDD, the attributes might depend on each other in a circle, and then no order exists. The dependencies form a graph (the dependency graph) over the parse tree's attribute instances, and the evaluator must process the attributes in a topological order. Checking an arbitrary SDD for cycles is expensive, so compilers use two restricted classes where the order is guaranteed.

Class Allowed attributes Evaluation order Fits
S-attributed only synthesized any bottom-up (post-order) traversal; evaluate at each reduce LR parsers (Yacc, Bison)
L-attributed synthesized, and inherited ones that depend only on the parent and left siblings depth-first, left to right LL parsers, recursive descent

Every S-attributed definition is also L-attributed. The "L" stands for left-to-right: an inherited attribute of a symbol on the right side of a rule may depend on the symbols to its left, but never on the ones to its right, which a left-to-right parser has not seen yet.

The name of an attribute does not matter. What matters is the direction of the flow of information.

Evaluating attributes on an AST

In a real compiler you rarely attach attributes to a full parse tree. You build an abstract syntax tree first and then run passes over it. A pass that computes synthesized attributes is simply a recursive function: evaluate the children, then compute the node's attributes from theirs. The example below stores attributes in a dictionary on each node and computes three at once: the numeric value, the postfix form of the expression, and the height of the tree.

Python Synthesized attributes on a tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Study the output from the bottom up: the leaves get their attributes straight from their tokens (val for x comes from the environment), and each operator node combines the attributes of its two children. The post attribute is the translation of the expression into another notation. That is the "translation" in syntax-directed translation: the output is built from the output of the parts.

Inherited attributes in code

For recursive descent, inherited attributes become function parameters, and synthesized attributes become return values. That is the whole trick. The example below shows two classic uses.

The first is the declaration list: T.type is passed to parse_L as an argument, and each name uses it.

The second is a very important one. When you remove left recursion to write a recursive descent parser (see eliminating left recursion), E -> E - T becomes E -> T E' and E' -> - T E'. The new tree leans to the right, which would make subtraction right-associative and give the wrong answer. The fix is to pass the running value into E' as an inherited attribute, so evaluation still proceeds left to right.

Python Inherited attributes as parameters

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the last two lines. With the inherited accumulator, 10 - 4 - 3 is 3, which is the correct left-associative answer. Evaluating the right-leaning tree naively would produce 10 - (4 - 3) = 9. The attribute E'.inh is carrying "everything to my left" as the parse goes along.

Semantic actions and translation schemes

An SDD says what to compute but not when. A syntax-directed translation scheme (SDT scheme) gives the order explicitly by placing semantic actions, pieces of program code in braces, at exact positions inside the right-hand sides:

TEXT
R -> + T { print('+') } R

The action runs when the parser reaches that point, after T has been parsed and before the next R. This is how Yacc and Bison actions work, and it is how hand-written parsers commonly produce output while parsing. The classic demonstration is converting infix to postfix.

Python A translation scheme: infix to postfix

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The operators are emitted after both operands, which is why 9 - 5 + 2 becomes 9 5 - 2 +. Note that precedence and associativity come out right with no extra work, because they are already encoded in the grammar layers. A translation scheme must respect the dependency rules: an action may use only attributes that have already been computed at that point of the parse.

Where SDT is used

Syntax-directed translation is a way of thinking more than a single algorithm. You will use it repeatedly:

  • Building the AST. Each action creates a node from the children's nodes (a synthesized attribute node).
  • Type checking. The type of an expression is synthesized from its operands, and an expected type can be inherited downward (see type checking).
  • Symbol tables. Declarations add entries, and the current scope is an inherited attribute (see symbol tables and scopes).
  • Code generation. Each node synthesizes the code for its subtree, and a parent concatenates its children's code (see generating three-address code).

Hand-written compilers usually separate the phases: the parser builds an AST, and later passes compute attributes by walking it. That is cleaner than packing semantics into parser actions, and it works for languages whose evaluation order does not follow the parse order. The attribute-grammar vocabulary stays valuable because it names the direction of every piece of data.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which attribute is synthesized?

    A synthesized attribute is computed from the attributes of the node's children, so the information flows up the tree.
  2. 2. Which kind of definition can be evaluated by an LR parser during reductions, without extra tricks?

    In S-attributed definitions every attribute depends only on children, which are already on the LR stack when a rule is reduced.
  3. 3. In a recursive descent parser, how are synthesized and inherited attributes usually implemented?

    A function receives inherited information from its caller as arguments and hands its own computed result back to the caller as its return value.
  4. 4. Why is an inherited accumulator used after left recursion is removed from E -> E - T?

    After the rewrite the tree is right-leaning. Passing the running result down as an inherited attribute preserves the left-to-right evaluation order.
  5. 5. What distinguishes an L-attributed definition from an arbitrary one?

    L-attributed means information never flows from right to left, so a single left-to-right depth-first pass can compute all attributes.

Summary

  • Attributes attach meaning (values, types, code) to grammar symbols; semantic rules compute them, and a grammar with such rules is a syntax-directed definition.
  • Synthesized attributes flow up from the children; inherited attributes flow down or sideways from the parent and siblings.
  • S-attributed definitions use only synthesized attributes and fit bottom-up parsers; L-attributed definitions allow inherited attributes from the parent and left siblings and fit top-down parsers.
  • In recursive descent, inherited attributes are parameters and synthesized attributes are return values.
  • A translation scheme embeds semantic actions in rules to control exactly when they run.
  • Real compilers often build an AST first and compute attributes in separate passes over it.

Next: Symbol Tables and Scopes