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 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 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  

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.

• the L-attributed stands for one pass from left-to-right.
• Intuitively, there are no right-to-left dependencies between attribute occurrences in the productions.
• L-attributed definitions include all syntax-directed definitions based on LL(1) grammars. We will admit this statement.

L-ATTRIBUTED DEFINITIONS. A syntax-directed definition is L-attributed if for each production A $\longmapsto$ X₁ ^... X_n, for each j = 1 ^... n, each inherited attribute of X_j depends only

• the attributes of X₁ ^... X_j-1,
• the inherited attributes of A.

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$ a₁ ^... a_n where a₁,..., 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 $\longmapsto$ X₁ ^... X_n where X₁,..., X_n 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 X₁,..., X_j-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 X_j. When all inherited attributes of X₁,..., 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. $\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$ X₁ ^... 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₁,..., X_n may be needed.)

Example 10   The following translation scheme does not satisfy Rule 1.

S	$\longmapsto$	A1 A2  {A1.in : = 1; A2.in : = 1}
A	$\longmapsto$	a  {print(A.in)}

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(A₁.in) and print(A₂.in) before the attributes A₁.in and A₂.in are assigned by the semantic rules A₁.in : = 1; A₂.in : = 1. In fact the above translation scheme needs to be changed to

S $\longmapsto$ {A₁.in : = 1; A₂.in : = 1}  A₁ A₂

A $\longmapsto$ a  {print(A.in)}

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	B.ps := 10
	S.ht := B.ht
B $\longmapsto$ B1 B2	B1.ps := B.ps
	B2.ps := B.ps
	B.ht := max( B1.ht, B2.ht)
B $\longmapsto$ B1 $\bf sub$ B2	B1.ps := B.ps
	B2.ps := shrink(B.ps)
	B.ht := disp( B1.ht, B2.ht)
B $\longmapsto$ $\bf text$	B.ht := $\bf text$.h×B.ps

Some comments.

• The nonterminal B represents a box which has been assigned to a mathematical formula.
• The production B $\longmapsto$ B B represents the juxtaposition of two boxes.
• When B $\longmapsto$ B₁ B₂ is applied,
  • the boxes B₁ and B₂ inherit the point size of B,
  • and the height of B represented by the synthesized attribute B.ht is given by max( B₁.ht, B₂.ht).
• The production B $\longmapsto$ B₁ $\bf sub$ B₂ represents a subscripted expression.
• When B $\longmapsto$ B₁ $\bf sub$ B₂ is applied,
  • the shrink(B.ps) returns a fraction of the B.ps, say 30%,
  • and disp( B₁.ht, B₂.ht) allows for downward displacement of the box B₂ and computes the height of B.

Consider the production  S  $\longmapsto$  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  $\longmapsto$  B₁ B₂ together with its semantic rules B₁.ps := B.ps, B₂.ps := B.ps and B.ht := max( B₁.ht, B₂.ht).

• Rule 1 implies that the actions {B₁.ps := B.ps} and {B₂.ps := B.ps} must occur before B₁ and B₂ are visited respectively.
• Rule 2 and Rule 3 imply that the action {B.ht := max (B₁.ht, B₂.ht)} must occur after B₁ and B₂ are visited.

Similar considerations with the other two productions lead to the following translation scheme.

S	$\longmapsto$		{B.ps := 10}
		B	{S.ht := B.ht}
B	$\longmapsto$		{B1.ps := B.ps}
		B1	{B2.ps := B.ps}
		B2	{B.ht := max( B1.ht, B2.ht) }
B	$\longmapsto$		{B1.ps := B.ps}
		B1
		sub	{ B2.ps := shrink(B.ps) }
		B2	{ B.ht := disp( B1.ht, B2.ht) }
B	$\longmapsto$	text	{ B.ht := $\bf text$.h×B.ps }

Example 12   To conclude this section we give a translation scheme for the let language

S	$\longmapsto$		{ E.env := initialEnv() }
		E
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$ }