← •   HOME  • UP  •   →
Top/Code generation/Syntax-directed translation  

14.2. Syntax-Directed Translation
(Dragon Book, Section 6.4)


Generating code as you go

Although the syntax-tree approach works well, syntax trees can be large. Compilers for relatively simple languages have another option that uses less time, less memory and fewer lines of semantic code in the compiler.

Let's look at expressions.


Generating intermediate code for expressions

While parsing an expression, the semantic actions write intermediate code into an array. The intermediate code computes the value of the expression and stores it into a variable.

If E is an expression then attribute E.addr is the name of the variable in which the value of E has been stored.

Here are some sample productions and associated actions. Actions are shown in blue just below the productions.

Production/Action
E → num
  E.addr = newTemporary();
  gen(E.addr = num.val);
E → id
  E.addr = id.name;
E → E1 + E2
  E.addr = newTemporary();
  gen(E.addr = E1.addr + E2.addr);
E → E1 * E2
  E.addr = newTemporary();
  gen(E.addr = E1.addr * E2.addr);
E → ( E1 )
  E.addr = E1.addr;

Note that the action for production E → E1 + E2 does not generate code to compute E1 or E2. That was generated while parsing E1 and E2.


Sample expression translation

Let's translate expression (x + 2*y) + 1 into 3-address codes using the above translation rules. The result is: 

  t1 = 2
  t2 = t1 * y
  t3 = x + t2
  t4 = 1
  t5 = t3 + t4

Attribute E.addr is t5.

Notice that no code is generated for expressions x and y, or for the parentheses. The first subexpression that leads to code being generated is 2.

Also notice that the generated 3-address codes are not the simplest way of computing the value of this expression. We don't care about that during syntax-directed translation. It is dealt with later.

 

← •   HOME  • UP  •   →
Top/Code generation/Syntax-directed translation