RIA
laboria

laboratoire de recherche
en informatique
et automatique

Example of transformation
of a derivation tree
for an expression by
semantic attributes

D.Tusera

<figure><img src="image_1.png" /></figure>

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

Rapport de Recherche n°41
novembre 1973
# EXAMPLE OF TRANSFORMATION OF A DERIVATION TREE FOR AN EXPRESSION BY SEMANTIC ATTRIBUTES

D. Tusera

(Présenté par A. Marchal)

## Résumé

Telle qu'elle a été introduite par D.E.Knuth la notion d'attribut sémantique sert à définir le sens d'une expression donnée dans un langage particulier [1]. Nous allons présenter une application des attributs sémantiques: la transformation de l'arbre dérivé d'une expression en un arbre sémantiquement équivalent en vue de l'optimisation de l'exécution.

Suivant D.E.Knuth chaque attribut est défini par une fonction associée à chaque des règles de production de la grammaire du langage. On utilisera les notions d'attributs 'synthétisés' et 'hérités' suivant que les valeurs de ces derniers sont définies par ceux des noeuds respectivement au-dessous ou au dessus du noeud considéré dans l'arbre dérivé.

Le langage choisi pour notre exemple est un sousensemble d'APL dont certains opérateurs offrent une possibilité intéressante d'optimisation.

## Abstract

The notion of "semantics attributes" introduced by D.E. Knuth is used for assigning a 'meaning' to an expression in a context-free language [1]. We shall give one possible application of semantic attributes : transformation of a derivation tree for an expression into a tree, whose meaning is the same, with a view to computational optimization.<fnref n="1" />)

In accordance with D.E. Knuth, every attribute can be defined by functions associated with each production in the grammar of the language. The 'synthesized' and 'inherited' attributes are used. They are defined for a nonterminal node of the derivation tree in terms of attributes of its 'descendants' respectively 'ancestors'.

The language selected for our example is a sub-set of APL. Several operations of which offer an interesting chance of optimization.

<footnote n="1">1) From our point of view two trees have the same 'meaning' if their evaluation gives the identical results.</footnote>
# Introduction

## 1) Statement of the problem

The translation of a text written in one of the programming languages in a form nearer to the computer language can be made in three logical phases :

1. Transformation of the sequence of characters into a sequence of words and phrases - lexical analysis.

2. Transformation of the sequence of phrases in derivation trees generally reduced - syntactic analysis.

3. Transformation of the derivation tree into a standard tree. This transformation is justified by computational optimization.

This article concerns the third phase.

In our example, the transformation mechanism of the derivation tree is expressed by relations between "inherited" and "synthesized" attributes associated with each production in the grammar of language [1]. The calculation of values of the defined attributes realizes the transformation of the derivation tree in an optimized tree.

## 2) Objective of the method

The programming language APL, near to mathematical language, is designed for array handling. The interpretation of an APL expression contains implicit loops that the programmer cannot supervise. That is the point where optimization can intervene.

In the APL/IBM 360 interpreter all the operations are executed as soon as they are seen. There are two inconveniences :

a) explicit creation of temporary results (the dynamic memory requests can be extensive).

b) superfluous computations which do not take part in the final result.

### Example :

Let us consider the expression $(A + B)[5]^{1)}$ where A and B are vectors each of 10 elements. The interpreter will execute first the addition which involves 10 calculations (9 of them are useless) and

<footnote n="1">1) Semantics of the APL operations see [2],[3].</footnote>
it will create a temporary result for A + B. Then it will select the
fifth element of this result as the final result of the expression
evaluation.

For a great group of the APL operations the size of their result
can be determined before the operation execution. We have fixed as
our objective for this group of operations :

1) to avoid the creation of temporary results and the useless
computations - this is enabled by memorizing the derivation tree of the
expression (see section 1)

2) to optimize the access to the operand values during the
computation of the expression - this is realized by a proper transfor-
mation of the derivation tree. This point constitutes the main idea
of our report).<fnref n="1" />)

The generalized subscripting in APL was chosen as a representative
operation for our demonstration.<fnref n="2" />)

<footnote n="1">1) The optimization of the APL interpretation is also treated in [3], [4], [5], [6], [7].</footnote>

<footnote n="2">2) Semantics of generalized subscripting in APL see Appendix.</footnote>
# I. GRAMMAR OF SELECTED APL SUB-SET AND DERIVATION TREE OF AN EXPRESSION

Let us define the grammar of chosen language by the following
productions :

Z → ITEM
ITEM → TERM[INDEX] / TERM
TERM → 'var'/(ITEM)
INDEX → ITEM / INDEX ; ITEM 1)

The terminal symbol is :

'var' - symbolic name of the variable (array). We consider that values
have already been assigned to each variable.

The distinguished symbol of the grammar is Z.

The grammar assigns a certain tree structure to each expression
of the given language. For example the expression R↔(A[B;C]) [D;E]
leads to the structure on Fig 1 A.

Let be in expression (A[B;C]) [D;E].

<figure><img src="image_2.png" /></figure>

We can represent this structure in a reduced form which contains
all the necessary information for computation of the given expression
(fig 1B).

1) The grammar is taken from [7]

2) ↔ symbol of identify

3) size of A is a vector which gives the dimensions of A : ρA
rank of A is the size of the size of A : ρρA
The reduced tree is the derivation tree after deletion of those nodes of which attributes values are identical. The reader will be able to verify this fact later, after the introduction of semantic attributes (Fig 2).

If we calculate the rank (ρρ) and size (ρ) of every nonterminal node of the tree, according to the APL rules, we get the same tree as it is described by A. Marchal in his APL interpretation method [6].

Here is how one can use this tree for the execution of the expression :

For example, for calculation of the result value R[3;2] we take the indices 3 and 2 and go down the right branch with them from the tree root. The node INDEX distributes the index 3 to the variable D and the index 2 to the variable E. We select values D[3] ↔ 1 and E[2] ↔ 2 resp. this yields [1;2] and then we ascend to the root and descend the left branch. The node ITEM leads us to INDEX that sends the index 1 to variable B and the index 2 to variable C. We find the values B[1] ↔ 2 and C[2] ↔ 2 and these values considered as indices yields [2;2] allow us to find A[2;2] ↔ 2 : this is the sought result R[3;2] ↔ 5.

We see that in the computation process for finding, for example, the values of variable B, it is necessary to know the values of variable D. In the same time, we note that this tree is not very efficient : it is necessary to transport the values of D a considerable way in the tree. So, the computation is heavy (Fig 1B). Even more, for obtaining the whole result, the described calculations must be repeated for each result element (in our example the result is a matrix of 3 x 2 = 6 elements).

Therefore it is useful to transform the tree of the expression into a semantically equivalent tree<fnref n="1" />) that would be more advantageous for the expression evaluation (Fig 1C).

For clarity of our report, the example expression has been chosen so that the transformed tree is at the same time a derivation tree of an APL expression (Fig 1C).

<footnote n="1">1) From our point of view 'two semantically equivalent trees' are those, execution of which gives the identical results.</footnote>
In the transformed tree the variable B has a direct access to the values of variable D of which it needs (they are side by side in the tree structure) : the computation process is faster.

But because of existence of implicit loops in the interpretation of APL expressions it is not possible to express any expressions of the APL sub-set mentioned in the introduction (group of operations for which the size of the result can be determined before their execution) in its optimized form by APL, even complete.

We shall introduce another language for description of the transformed tree which will be suitable also for the execution process (section 3).

Subsequently we propose to realize the transformation of the derivation tree in an optimized tree by a proper choice of 'inherited' and 'synthesized' attributes for each nonterminal node of the derivation tree, and by their definition by semantic rules given for each rule of the grammar [1].

## II. CHOICE OF ATTRIBUTES AND DEFINITION OF THEIR RELATIONS

### II.1. Description language of transformation tree

Each node of the transformed tree will be described in a standard way by the following information :

<table><tr><td>n</td><td>°</td><td>OP</td><td>DL</td><td>ρ</td><td>ρρ</td></tr></table>

n° - relative address of the node

OP - operation to execute in the given node during the calculation process. As an APL sub-set has been taken, there are possible only two operations :

1. OP ↔ 'variable name' means the subscripting operation of the mentioned variable by indices specified in the list DL of the node.

2. OP ↔ 'root' means that it is the root node of the expression tree in question (its role in the calculation process will be made precise in Section 3).
DL - list of symbols pairs of type 'a(b)' where 'a' is the operand address of operation OP, 'b' (a number) specifies the loop that supercedes this operand.

The operand address can be either the number of the line where the operand occurs or a small letter : register address in which is stored the current index value of the corresponding loop.

* ρ - node size

* ρρ - node rank

**Note:**

The loop specification in DL is useful for the following reason :

Let us consider the transformed tree of Fig 1C. The expression result is a matrix of size ρ ↔ 3 2 (3 rows, 2 columns). We see that if we want the entire result, the calculation will perform :

1) At first, the calculation of the result values for two columns of the first row.

2) Next for two columns of the second row.

3) At last, for two columns of the third row.

It is an iteration in two loops : the external loop for the rows and the inner loop for the columns.

So, it is useful, and we show it in Section 3, to store the identification number of the loop to which the given node belongs.

The transformed tree of the expression (A[B;C]) [D;E] (Fig 1C), will be described in this language in the form of a table like that on Fig 1D.

Here is how to understand this table (example) :

- the line n°5 designates the subscripting operation of variable A by two indices (because its rank is 2), the first of which is the value of variable B (node n°4, it depends on the first loop <fnref n="1" />), and the second is the value of variable C (node n°3 - it depends on the second loop).

APL is executed from right to left. The syntactic analysis can be made in the same way, from where the order of nodes numbers (first column of the table Fig 1D).

The table of Fig 1D is only a representation in memory of the transformed expression tree. We can intuitively see how the 'standard' transformed tree is given by this table (Fig 1E).

<footnote n="1">1) Convention : the first loop ↔ the most external loop</footnote>
## II.2. Transformation algorithm of the derivation tree

For obtain the table Fig 1D which gives us the transformed tree we introduce the following semantic attributes :

* $\rho$ - node size (synthesized attribute)

* $\rho\rho$ - node rank (synthesized attribute)

* L - list of symbols pairs of type 'a(b)' where 'a' is the address of the node - index and '(b)' is the number of the loop which supervises the index (synthesized attribute)

* B - List of the loop numbers on which the node depends (it is not an attribute, it constitutes one part of the attribute DL - the numbers in round brackets).

* DL - the same as L (inherited attribute)

* OP - operation to execute in the given node during the calculation process.

While $O$, $DL$, $\rho$, $\rho\rho$ form the description language of the transformed trees, L helps only as intermediate tool.

Let us complete now the language productions by semantic rules which will express the attributes relations. Fig 2 shows these relations, where the symbol '=>' means that it is a question of calculation of an 'inherited' attribute, while '<=' reserved for 'synthesized' attributes.

Let us try to find the transformed tree from the derivation tree of expression $(A[B;C]) [D;E]$. The results will be represented in a form of tables.

The algorithm has two parts :

### II - 2 - 1 First part of the algorithm :

Representing of the nodes of the reduced derivation tree of expression and representing of the dependency relations between attributes of the nodes. They are defined by the semantic rules associated to each production (we represent only the nodes in which the semantic actions will change the attributes values).(Fig 3D).

The result of this operation is a directed graph (Fig 3D). In general case a 'partial ordering' would be deduced from this graph (by a topological sorting) before the attributes evaluation. The precedence rules of our language (APL sub-set) allows to avoid this step : the directed graph already constitutes a partial ordering (Fig 4).
If we simplify the table Fig 3D and calculate the attributes ρ and ρρ in the same time, we can say, that the attributes evaluation needs three passes for every node (Fig 4).

Fig 4B is Fig 4A turned 90 degrees. It permits one, with the help of the table of Fig 2 (attributes relations), to understand the meaning of the three passes and the role of each attribute :

1) The first pass (calculation of the attributes ρ and ρρ) determines the list of the result indices.

2) The second pass by a tree node (calculation of the attribute-DL) specifies the indices by which the node is indexed : DL - distribution of indices.

3) The third pass (calculation of the attribute L) constructs the list of indices for the possible indexed expression of the next subscript level.

### II.2.2 Second part of the algorithm (creation of the optimized code) :

Evaluation of attributes in the order determined during the first part. The evaluation applies the semantic rules of the table of Fig 2. The hatched parts of Fig 3E give us the table of Fig 1D and this is the desired result.

## III EXECUTION OF THE TRANSFORMED TREE OF AN EXPRESSION

As the syntactic analysis was effected in the execution order of APL expressions (from right to left), the nodes (lines) in the table of Fig 3E are already nearly in execution order. For realizing a sequential evaluation it will be necessary to arrange them also following the loop numbers which supervise them.

Therefore the lines are arranged following the value B (part of attribute DL), namely : at first all lines of which $B = 1^{1)}$, next those, of which $B = 2$ and so on, and for the same $B$ in the preceding order. At the same time, addresses of the beginnings of every loop are stored in the node 'root' (br). The result of this modification leads to Fig 3F.

Furthermore, we consider that the access to an element of the array is completely defined by the following parameters :

<footnote n="1">1) operation $\lceil V \rceil$ is the selection of the maximum value of vector V for inst $\lceil 1 \ 2 \ 3 \ 4 \rceil \leftrightarrow 4$</footnote>
The name of array (address of the values vector of array)

its rank ($\rho\rho \leftrightarrow n$)

its size ($\rho$)

the n co-ordinates of the given element (where n is the array rank).

We associate a register with each node of the transformed tree, that is to say, with each line of the table in Fig 3F.

During the execution the terms used in the transformed tree table are interpreted in following manner :

OP $\leftrightarrow$ 'variable name' : calculate the address of one variable element using the indices of which the values are in the registers specified by DL and store the value of this element in the register of the given node.

Example :

<table><thead><tr><th>n°</th><th>OP</th><th>ρ</th><th>ρρ</th><th>DL</th></tr></thead><tbody><tr><td>2</td><td>D</td><td>3</td><td>1</td><td>a(1)</td></tr></tbody></table>

calculate the

address of element of variable D selected by the index stored in the register 'a' and store the value of this element in the register of node n°2.

OP $\leftrightarrow$ 'root' : two steps

step 1 : initialize I $\leftarrow$ [B (B is the maximum value of B of node 'root')

step 2 : add 1 to the value of index that is in the register (DL(root))[I] ; compare this value with the corresponding size of the result (ρ(root))[I] :

- if value (DL(root))[I] > (ρ(root))[I] then
  set value (DL(root))[I] $\leftarrow$ 1

I $\leftarrow$ I - 1

test I = - if I = 0, then end of execution
else repeat step 2

- else go to the node which number is br[I]

The instruction 'root' commands the embedded loops.

### III-1 Execution of the expression (A[B;C])[D;E]:

At first the indices are initiated a $\leftarrow$ 1; b $\leftarrow$ 1. Then the operations shown in the table of Fig 3F are sequentially executed. It is necessary to repeat them up to exhaustion of the loops specified by the instruction 'root' (Fig 3G).
## Conclusion

We think we have shown that the method of semantic attributes is suitable to define the transformations of the derivation tree of an APL expression.

The algorithm that realizes this transformation is concise. This point merits to be emphasized, because the other optimization methods of APL interpretation [3][4][5] lead to complicated algorithms.

In our report, we have considered only the subscript operation. This fact does not limit the generality. The application of this method to the APL operations as : scalar operations, reductions, transpose, take, drop, external product, inner product do not pose any new problems.

The natural questions that come to mind is whether there is really an optimization of APL interpretation in its whole. It will be necessary to know if the work saved for the execution machine by reducing the length of loop nestings is not lost by use of the transformation algorithm. The only way to answer this question is to test and to make the measures on different programs. This is the object of our work and will be published next.

## Appendix

### Generalized subscripting in APL

**Example 1** If M is a matrix $M \leftrightarrow 2 4 6$
then $R \leftrightarrow M[2;3] \leftrightarrow 12$

M[2;3] means : selection of one matrix element, the co-ordinates of which are 2 (second row) and 3 (third column).

**Example 2** If M is a matrix $M \leftrightarrow 2 4 6$
then $R \leftrightarrow M[U;V] \leftrightarrow 12 10$
U a vector $U \leftrightarrow 2 I$
V a vector $V \leftrightarrow 3 2$

rank $\rho_M \leftrightarrow 2$
size $\rho_M \leftrightarrow 2 3$

rank $\rho_U \leftrightarrow 1$
size $\rho_U \leftrightarrow 2$

rank $\rho_V \leftrightarrow 1$
size $\rho_V \leftrightarrow 2$

$\rho_U, \rho_V \leftrightarrow 2 2$ 1)

1) operation ',' means in APL catenate for ex if $V \leftrightarrow 2 3$ $W \leftrightarrow 4 5$ then $X \leftrightarrow V$, $W \leftrightarrow 2 3 4 5$.
Here each value of result R is selected in the matrix M indirectly by a mask constituted by values of U and V :

$$R[I;J] \leftrightarrow M[U[I];V[J]]$$

For example :

$$R[1;1] \leftrightarrow M[U[1]; V[1]] \leftrightarrow M[2;3] \leftrightarrow 12$$

References :

[1] D.E. Knuth "Semantics of context free languages"
Mathematical Systems Theory, vol n°2 (1967).

[2] K.E. Iverson "A programming language"
John Wiley (1966).

[3] P.S. Abrams "An APL machine"
Stanford University Report N° SLAC 114 (1970).

[4] G. Battarel "Interpretation optimisée d'APL"
Thèse d'ingénieur docteur, Toulouse 1973.

[5] M. Delbreil "Interprétation optimisée d'APL"
Thèse d'ingénieur docteur, Toulouse 1973.

[6] A. Marchal 'Ph.D. Thesis, University of Utah 1972

[7] P. Kalfou "On a bottom-up method for evaluation of APL expressions"
APL Congress 1973 Copenhagen

[8] B. Robinet "Sémantique des tableaux - application au langage APL"
Thèse de IIIème cycle Paris 1972.
<figure><img src="image_3.png" /></figure>

B

<figure><img src="image_4.png" /></figure>

C

<figure><img src="image_5.png" /></figure>

D

<table><thead><tr><th>n°</th><th>OP</th><th>ρ</th><th>ρρ</th><th>DL</th></tr></thead><tbody><tr><td>1</td><td>E</td><td>2</td><td>1</td><td>b(2)</td></tr><tr><td>2</td><td>D</td><td>3</td><td>1</td><td>a(1)</td></tr><tr><td>3</td><td>C</td><td>2</td><td>1</td><td>1(2)</td></tr><tr><td>4</td><td>B</td><td>2</td><td>1</td><td>2(1)</td></tr><tr><td>5</td><td>A</td><td>2</td><td>3</td><td>4(1) 3(2)</td></tr><tr><td>6</td><td>root</td><td>3</td><td>2</td><td>a(1) b(2)</td></tr></tbody></table>

E

<figure><img src="image_6.png" /></figure>

I - I semantically identical

II -II semantically identical

III - III semantically identical

<caption>Fig.1 Derivation tree and transformed tree</caption>
<table><caption>Fig.2 Semantic rules</caption><thead><tr><th rowspan="2">Production rule</th><th colspan="5">Semantic rules</th></tr><tr><th>ρ</th><th>ρρ</th><th></th><th>DL</th><th>OP</th></tr></thead><tbody><tr><td>ITEM → TERM</td><td>ρ (ITEM) <= ρ (TERM)</td><td>ρρ (ITEM) <= ρρ (TERM)</td><td>L (ITEM) <= L (TERM)</td><td>DL (ITEM) =&gt; DL (TERM)</td><td></td></tr><tr><td>ITEM → TERM[INDEX]</td><td>ρ (ITEM) <= ρ (INDEX)</td><td>ρρ (ITEM) <= ρρ (INDEX)</td><td>L (ITEM) <= L (TERM)</td><td>DL (TERM) <= L (INDEX)<br>DL (ITEM) =&gt; DL (INDEX)</td><td></td></tr><tr><td>INDEX → ITEM</td><td>ρ (INDEX) <= ρ (ITEM)</td><td>ρρ (INDEX) <= ρρ (ITEM)</td><td>L (INDEX) <= L (ITEM)</td><td>DL (INDEX) =&gt; DL (ITEM)</td><td></td></tr><tr><td>INDEX1 → INDEX2; ITEM</td><td>ρ (INDEX1) <=<br>ρ (INDEX2), ρ (ITEM)<br>1)</td><td>ρρ (INDEX1) <=<br>ρρ (INDEX2) + ρρ (ITEM)</td><td>L (INDEX1) <=<br>L (INDEX2), L (ITEM)</td><td>ρρ (INDEX2) + DL (INDEX1) =&gt;<br>DL (INDEX2)<br>- ρρ (ITEM) + DL (INDEX1) =&gt;<br>DL (ITEM)</td><td></td></tr><tr><td>TERM → (ITEM)</td><td>ρ (TERM) <= ρ (ITEM)</td><td>ρρ (TERM) <= ρρ (ITEM)</td><td>L (TERM) <= L (ITEM)</td><td>DL (TERM) =&gt; DL (ITEM)</td><td></td></tr><tr><td>TERM → var</td><td>ρ (TERM) <= ρ (var)</td><td>ρρ (TERM) <= ρρ (var)</td><td>L (TERM) <= 3)<br>n° (TERM), ⌜B (TERM)</td><td></td><td>OP (TERM) -<br>variable name</td></tr><tr><td>Derivation tree root</td><td></td><td></td><td></td><td>DL (root) <= a(1) b(2) ...<br>ρρ (root)</td><td>OP (root) <= root</td></tr></tbody></table>

1) the operation '>' in APL means the concatenation for ex. if V↔2 3 W↔4 5 then X↔V, W↔2 3 4 5

2) the operation A↑V means: take the A first elements of the vector V, for ex. 2↑2 3 4 5 ↔ 2 3
the operation -A↑V means: take the A last elements of the vector V, for ex. -2↑2 3 4 5 ↔ 4 5

3) the operation ⌜V is the selection of the maximum value of the vector V for ex. ⌜1 2 3 4 ↔ 4
<figure><img src="image_7.png" /><figcaption>Fig.3 Transformation algorithm</figcaption></figure>
<table><thead><tr><th></th><th>n°</th><th>OP</th><th>pp.ρ</th><th>DL</th><th>L</th></tr></thead><tbody><tr><td>TERM</td><td>1</td><td>E</td><td></td><td></td><td></td></tr><tr><td>TERM</td><td>2</td><td>D</td><td></td><td></td><td></td></tr><tr><td>INDEX</td><td>3</td><td></td><td></td><td></td><td></td></tr><tr><td>TERM</td><td>4</td><td>C</td><td></td><td></td><td></td></tr><tr><td>TERM</td><td>5</td><td>B</td><td></td><td></td><td></td></tr><tr><td>INDEX</td><td>6</td><td></td><td></td><td></td><td></td></tr><tr><td>TERM</td><td>7</td><td>A</td><td></td><td></td><td></td></tr><tr><td>ITEM</td><td>8</td><td></td><td></td><td></td><td></td></tr><tr><td>ITEM</td><td>9</td><td>root</td><td></td><td></td><td></td></tr></tbody></table>

<figure><img src="image_8.png" /></figure>

ρ ρρ - determination of the list of the result indices

DL - indices distribution

L - construction of the indices list for the next level

<caption>Fig.4 Meaning of attributes</caption>