next up previous
Next: Implementing translation schemes with YACC Up: Compiler Theory: Syntax-Directed Translation Previous: Translation Schemes

L-attributed Definitions

As in the previous section, we enhance the notion of syntax-directed definitions in order to specify the order of evaluation of the semantic rules. This leads to the concept of a L-attributed definition.

KEY IDEAS. Both notions of translation scheme and L-attributed definition are close. However

THE DEPTH-FIRST EVALUATION ORDER. We consider a syntax-directed 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 depth-first evaluation order, for evaluating attributes shown by T.

Algorithm 3  

\begin{minipage}{12 cm}
\item[{\bf Input:}] A node $n...
...he synthesized attributes of $n$; \\
\> {\bf end}.

Remark 3   We now introduce a class of syntax-directed definitions, called L-attributed definitions, whose attributes can always be evaluated in depth-first order.

L-ATTRIBUTED DEFINITIONS. A syntax-directed definition is L-attributed if for each production A $ \longmapsto$ X1 ... Xn, for each j = 1 ... n, each inherited attribute of Xj depends only

Theorem 1   The attributes of an L-attributed definition can always be evaluated in depth-first 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 $ \longmapsto$ a1 ... an where a1,..., an 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 $ \longmapsto$ X1 ... Xn where X1,..., Xn are grammar symbols. Each subtree rooted at a child of S can be viewed as a parse tree of a L-attributed 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 X1,..., Xj-1 are known Since the inherited attributes of S must be known constants, by definition of an L-attributed syntax-directed definition we can compute the inherited attributes of Xj. When all inherited attributes of X1,..., Xn are computed, then it is clear that all synthesized attributes of S can be computed. Therefore Algorithm 3 evaluates all the attributes in T. $ \qedsymbol$

Example 9   The syntax-directed definition of the let language is an L-attributed syntax-directed definition.
Production Semantic Rule
S $ \longmapsto$ E E.env := initialEnv()
E1 $ \longmapsto$ $ \bf let$ $ \bf id$ $ \bf =$ E2 $ \bf in$ E3 $ \bf end$ E2.env := E1.env
E3.env := Update( E1.env,$ \bf id$, E2.val)
E1.val := E3.val
E1 $ \longmapsto$ (E2 + E3) E1.val := E2.val + E3.val
E2.env := E1.env
E3.env := E1.env
E $ \longmapsto$ $ \bf id$ E.val := LookUp( $ \bf id$, E.env)
E $ \longmapsto$ $ \bf 1$ E.val := $ \bf 1$
E $ \longmapsto$ $ \bf0$ E.val := $ \bf0$
However the following syntax-directed definition is not L-attributed.
Production Semantic Rule
A $ \longmapsto$ L M L.i := f1(A.i)
M.i := f2(L.s)
A.s := f3(M.s)
A $ \longmapsto$ Q R R.i := f4(A.i)
Q.i := f5(R.s)
A.i := f6(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 $ \longmapsto$ Q R.

FROM L-ATTRIBUTED DEFINITIONS TO TRANSLATION SCHEMES. Every L-attributed 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 $ \longmapsto$ X1 ... Xn be any production and j be in the range 1 ... n.

Rule 1.
The inherited attributes of Xj must be computed in actions occurring to the left of Xj in the translation. (Indeed they may be needed when visiting the subtree rooted at Xj.)
Rule 2.
An action can refer to a synthesized attribute Xj.s of Xj only if Xj appears to the left of this action. (Indeed Xj.s will be computed when visiting the subtree rooted at Xj.)
Rule 3.
A synthesized attribute of A should be computed in an action occurring at the end of the translation. (Indeed all attributes of X1,..., Xn may be needed.)

Example 10   The following translation scheme does not satisfy Rule 1.
S $ \longmapsto$ A1 A2  { : = 1; : = 1}
A $ \longmapsto$ a  {print(}
Indeed consider the parse tree T of w = aa decorated with the necessary attributes and semantic rules. A depth-first traversal of T will call print( and print( before the attributes and are assigned by the semantic rules : = 1; : = 1. In fact the above translation scheme needs to be changed to
S $ \longmapsto$ { : = 1; : = 1}  A1 A2
A $ \longmapsto$ a  {print(}

Example 11   Consider the following syntax-directed definition for the point size and height of boxes containing mathematical formulas.
Production Semantic Rule
S $ \longmapsto$ B := 10 :=
B $ \longmapsto$ B1 B2 := := := max(,
B $ \longmapsto$ B1 $ \bf sub$ B2 := := shrink( := disp(,
B $ \longmapsto$ $ \bf text$ := $ \bf text$.h×
Some comments. Consider the production  S  $ \longmapsto$  B  together with its semantic rules := 10 and := Consider the second production B  $ \longmapsto$  B1 B2 together with its semantic rules :=, := and := max(, Similar considerations with the other two productions lead to the following translation scheme.
S $ \longmapsto$ { := 10}
B { :=}
B $ \longmapsto$ { :=}
B1 { :=}
B2 { := max(, }
B $ \longmapsto$ { :=}
sub { := shrink( }
B2 { := disp(, }
B $ \longmapsto$ text { := $ \bf text$.h× }

Example 12   To conclude this section we give a translation scheme for the let language
S $ \longmapsto$ { E.env := initialEnv() }
E1 $ \longmapsto$ { E2.env := E1.env }
$ \bf let$ $ \bf id$ $ \bf =$ E2 { E3.env := Update( E1.env,$ \bf id$, E2.val) }
$ \bf in$ E3 $ \bf end$ { E1.val := E3.val }
E1 $ \longmapsto$ { E2.env := E1.env }
{ E3.env := E1.env }
(E2 + E3) { E1.val := E2.val + E3.val }
E $ \longmapsto$ $ \bf id$ { E.val := LookUp( $ \bf id$, E.env) }
E $ \longmapsto$ $ \bf 1$ { E.val := $ \bf 1$ }
E $ \longmapsto$ $ \bf0$ { E.val := $ \bf0$ }

next up previous
Next: Implementing translation schemes with YACC Up: Compiler Theory: Syntax-Directed Translation Previous: Translation Schemes
Marc Moreno Maza