Next: Implementing translation schemes with YACC
Up: Compiler Theory: SyntaxDirected Translation
Previous: Translation Schemes
As in the previous section, we enhance the notion of syntaxdirected definitions
in order to specify the order of evaluation of the semantic rules.
This leads to the concept of a Lattributed definition.
KEY IDEAS. Both notions of translation scheme and Lattributed definition
are close. However
 the later provides more care for the treatment of inherited
attributed, leading to a more powerful theoretical concept.
 whereas the former is closer to a true computer program,
leading to a more practical concept.
THE DEPTHFIRST EVALUATION ORDER. We consider a syntaxdirected definition S and a parse tree T
for S showing the attributes of the grammar symbols of T.
Figure 1 shows an example of such a tree.
Algorithm 3
provides an order, called depthfirst evaluation order,
for evaluating attributes shown by T.
Algorithm 3
Remark 3
We now introduce a class of syntaxdirected definitions,
called Lattributed definitions, whose attributes
can always be evaluated in depthfirst order.
 the Lattributed stands for one pass
from lefttoright.
 Intuitively, there are no righttoleft dependencies
between attribute occurrences in the productions.
 Lattributed definitions include all syntaxdirected
definitions based on LL(1) grammars.
We will admit this statement.
LATTRIBUTED DEFINITIONS. A syntaxdirected definition is Lattributed
if for each production
A X_{1}^{ ... }X_{n},
for each
j = 1^{ ... }n,
each inherited attribute of X_{j}
depends only
 the attributes of
X_{1}^{ ... }X_{j1},
 the inherited attributes of A.
Theorem 1
The attributes of an Lattributed definition
can always be evaluated in depthfirst order.
Proof.
By induction on the depth of a parse tree
T.
Observe that a parse tree has at least depth 1 and two nodes.
If T has depth 1, then its root is labeled by S
and the associated production must have the form
S a_{1}^{ ... }a_{n} where
a_{1},..., a_{n}
are terminals.
Recall that terminals do not have inherited attributes.
Observe that every synthesized attribute of a terminal
must be known in advance since semantic rules
are only associated with productions (and thus cannot
define a synthesized attribute of a terminal).
Moreover, observe also that any inherited attribute of S
must be known in advance, too.
Now Algorithm 3
computes the synthesized attributes of S
and thus evaluates all the attributes in T.
Assume now that T has depth d > 1.
The production associated with the root has the form
S X_{1}^{ ... }X_{n} where
X_{1},..., X_{n}
are grammar symbols.
Each subtree rooted at a child of S can be viewed
as a parse tree of a Lattributed definition.
However the root of each of these subtrees may have
inherited attributes that must be computed
(we cannot assume that they are some known constants).
Let j be in
1^{ ... }n.
By virtue of the induction hypothesis and
by virtue of Algorithm 3
we can assume that all attributes of
X_{1},..., X_{j1} are known
Since the inherited attributes of S must be known constants,
by definition of an Lattributed syntaxdirected definition
we can compute the inherited attributes of X_{j}.
When all inherited attributes of
X_{1},..., X_{n}
are computed, then it is clear that all synthesized attributes
of S can be computed.
Therefore Algorithm 3
evaluates all the attributes in T.
Example 9
The syntaxdirected definition of the let language
is an Lattributed syntaxdirected definition.
Production 
Semantic Rule 
S E 
E.env := initialEnv() 
E_{1} E_{2} E_{3}

E_{2}.env := E_{1}.env 

E_{3}.env := Update(
E_{1}.env,, E_{2}.val) 

E_{1}.val := E_{3}.val 
E_{1} (E_{2} + E_{3}) 
E_{1}.val :=
E_{2}.val + E_{3}.val 

E_{2}.env := E_{1}.env 

E_{3}.env := E_{1}.env 
E 
E.val := LookUp(
, E.env) 
E 
E.val := 
E 
E.val := 
However the following syntaxdirected definition
is not Lattributed.
Production 
Semantic Rule 
A L M 
L.i := f_{1}(A.i) 

M.i := f_{2}(L.s) 

A.s := f_{3}(M.s) 
A Q R 
R.i := f_{4}(A.i) 

Q.i := f_{5}(R.s) 

A.i := f_{6}(Q.s) 
Indeed the inherited attribute Q.i depends on the attribute R.s
although R appears on the right of Q in the production
A Q R.
FROM LATTRIBUTED DEFINITIONS TO TRANSLATION SCHEMES. Every Lattributed definition can be converted
into a translation scheme that will always succeed
in evaluating the attributes in a parse tree,
provided that the following rules are observed.
Let
A X_{1}^{ ... }X_{n} be any production
and j be in the range
1^{ ... }n.
 Rule 1.
 The inherited attributes of X_{j}
must be computed in actions occurring
to the left of X_{j} in the translation.
(Indeed they may be needed when visiting
the subtree rooted at X_{j}.)
 Rule 2.
 An action can refer to a synthesized attribute X_{j}.s
of X_{j} only if X_{j} appears to the left of this action.
(Indeed X_{j}.s will be computed when visiting
the subtree rooted at X_{j}.)
 Rule 3.
 A synthesized attribute of A should be computed
in an action occurring at the end of the translation.
(Indeed all attributes of
X_{1},..., X_{n} may be needed.)
Example 10
The following translation scheme does not satisfy Rule 1.
S 

A_{1} A_{2} {A_{1}.in : = 1; A_{2}.in : = 1} 
A 

a {print(A.in)} 
Indeed consider the parse tree T of w = aa decorated with the necessary attributes and
semantic rules.
A depthfirst traversal of T will call
print(A_{1}.in)
and
print(A_{2}.in) before the attributes A_{1}.in and A_{2}.in are assigned
by the semantic rules
A_{1}.in : = 1; A_{2}.in : = 1.
In fact the above translation scheme needs to be changed to
S {A_{1}.in : = 1; A_{2}.in : = 1} A_{1} A_{2} 
A a {print(A.in)} 
Example 11
Consider the following syntaxdirected definition for the
point size and height of boxes containing mathematical formulas.
Production 
Semantic Rule 
S B 
B.ps := 10 

S.ht := B.ht 
B B_{1} B_{2} 
B_{1}.ps := B.ps 

B_{2}.ps := B.ps 

B.ht := max(
B_{1}.ht, B_{2}.ht) 
B B_{1} B_{2} 
B_{1}.ps := B.ps 

B_{2}.ps := shrink(B.ps) 

B.ht := disp(
B_{1}.ht, B_{2}.ht) 
B 
B.ht :=
.h×B.ps 
Some comments.
 The nonterminal B represents a box which has been assigned to a mathematical formula.
 The production
B B B represents the juxtaposition of two boxes.
 When
B B_{1} B_{2} is applied,
 the boxes B_{1} and B_{2} inherit
the point size of B,
 and the height of B represented by
the synthesized attribute B.ht is given by max(
B_{1}.ht, B_{2}.ht).
 The production
B B_{1} B_{2} represents
a subscripted expression.
 When
B B_{1} B_{2} is applied,
 the shrink(B.ps) returns a fraction of the B.ps, say 30%,
 and disp(
B_{1}.ht, B_{2}.ht) allows for downward displacement
of the box B_{2} and computes the height of B.
Consider the production
S B together with its semantic rules
B.ps := 10 and S.ht := B.ht.
 Rule 1 implies that the action {B.ps := 10} must occur
before B is visited.
 Rule 2 and Rule 3 imply that the action {S.ht := B.ht}
must occur after B is visited.
Consider the second production
B B_{1} B_{2} together with its semantic rules
B_{1}.ps := B.ps, B_{2}.ps := B.ps and B.ht := max(
B_{1}.ht, B_{2}.ht).
 Rule 1 implies that the actions {B_{1}.ps := B.ps}
and {B_{2}.ps := B.ps} must occur before B_{1} and B_{2} are visited respectively.
 Rule 2 and Rule 3 imply that the action {B.ht := max
(B_{1}.ht, B_{2}.ht)}
must occur after B_{1} and B_{2} are visited.
Similar considerations with the other two productions lead to
the following translation scheme.
S 


{B.ps := 10} 


B 
{S.ht := B.ht} 
B 


{B_{1}.ps := B.ps} 


B_{1} 
{B_{2}.ps := B.ps} 


B_{2} 
{B.ht := max(
B_{1}.ht, B_{2}.ht) } 
B 


{B_{1}.ps := B.ps} 


B_{1} 



sub 
{ B_{2}.ps := shrink(B.ps) } 


B_{2} 
{ B.ht := disp(
B_{1}.ht, B_{2}.ht) } 
B 

text 
{ B.ht :=
.h×B.ps } 
Example 12
To conclude this section we give a translation scheme
for the let language
S 


{ E.env := initialEnv() } 


E 

E_{1} 


{ E_{2}.env := E_{1}.env } 


E_{2}

{ E_{3}.env := Update(
E_{1}.env,, E_{2}.val) } 


E_{3}

{ E_{1}.val := E_{3}.val } 
E_{1} 


{ E_{2}.env := E_{1}.env } 



{ E_{3}.env := E_{1}.env } 


(E_{2} + E_{3})

{ E_{1}.val :=
E_{2}.val + E_{3}.val } 
E 


{ E.val := LookUp(
, E.env) } 
E 


{ E.val := } 
E 


{ E.val := } 
Next: Implementing translation schemes with YACC
Up: Compiler Theory: SyntaxDirected Translation
Previous: Translation Schemes
Marc Moreno Maza
20041202