# Projet delta: optimisation de code généré par attributs

Mahvash Michaneh Amirchahy, Monique Mazaud, Danielle Neel

► To cite this version:

Mahvash Michaneh Amirchahy, Monique Mazaud, Danielle Neel. Projet delta: optimisation de code généré par attributs. [Rapport de recherche] IRIA-RR-059, IRIA. 1974, pp.17. hal-04716001

HAL Id: hal-04716001

https://inria.hal.science/hal-04716001v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

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

Distributed under a Creative Commons Attribution 4.0 International License
RIA
laboria

Institut de Recherche
d'Informatique
et d'Automatique

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

laboratoire de recherche
en informatique
et automatique

Projet DELTA:
optimisation de code
généré par attributs

M.Amirchahy,M.Mazaud
D.Neel

Rapport de Recherche n° 59

Février 1974
# PROJET DELTA : OPTIMISATION DE CODE GÉNÉRÉ PAR ATTRIBUTS

M. Amirchahy, M. Mazaud, D. Neel

(présenté par B. Lorho)

## Résumé.

Nous développons ici quelques idées sur l'application d'attributs sémantiques, au sens de KNUTH, à la génération de code optimisé.

A partir de l'exemple précis de l'élimination des sous-expressions communes, nous montrerons que l'on peut définir deux sortes d'attributs :

- ceux qui servent à la génération de code et jouent un rôle dans l'optimisation.

- ceux créés dans un but d'optimisation et utilisés pour gérer le code-objet ou transmettre l'information.

Dans le même esprit, il sera possible de définir un ensemble d'attributs réalisant les fonctions d'optimisation pour tout langage algébrique. Ceci nous permet de dégager une certaine méthodologie au niveau de la description sémantique d'un langage. Par ailleurs cette description possède les qualités essentielles de : clarté, facilité d'écriture, rigueur.

## Abstract.

This paper deals with the application of the notion of semantic attributes (as developed by KNUTH), to generation of optimised code.

Taking common sub-expressions elimination as a starting point, it is demonstrated by means of an example that two kinds of attributes may be distinguished :

- those which serve to generate code and can also play a part in optimisations.

- attributes defined for optimisation and which may be used to handle object code or to pass on information along the programme tree.

Extending these basic ideas, it is then shown possible to create a set of attributes defining optimisation functions for all algebraic languages. Thus a certain methodology, at the level of semantic description of a language, may be outlined. Moreover, this description has the important properties of being easy to write, clear and rigorous.
OPTIMISATION DE CODE GENERE PAR ATTRIBUTS

Introduction :

L'optimisation de code consiste à traiter un programme en cours de
compilation pour produire un code généré le plus efficace possible.

Cette efficacité réside en un compromis entre la réduction du temps d'exécution et la limitation de l'encombrement mémoire.

Jusqu'à présent les recherches en optimisation ont porté sur l'écriture
d'algorithmes. Cependant il existe peu de compilateurs optimiseurs, essentiel-
lement à cause des deux difficultés suivantes :

1 - Certains langages permettent la production d'effets de bord dans les programmes. Ces effets de bord qui utilisent l'ordre dans lequel une instruction est traitée, peuvent être détruits par une optimisation. Le code fourni est alors sémantiquement faux par rapport au programme initial.

2 - De l'optimisation doit résulter un programme plus performant qui reste sémantiquement equivalent au programme initial. Cette équivalence n'est vraie que macroscopiquement, puisque la fonction réalisée par le programme est conservée. En fait au niveau microscopique, la sémantique du programme initial peut être notablement modifiée.

Ces deux difficultés prouvent que l'aspect sémantique d'un langage est
essentiel pour élaborer une méthodologie de l'optimisation. Malheureusement,
en compilation il existe des règles de description syntaxique des langages
(Backus-Naur Form), mais on ne connaît rien de semblable pour leur sémantique.
Il est donc difficile d'automatiser les méthodes classiques d'optimisation
puisqu'on ne peut les introduire dans une description sémantique du langage
source.

Or le projet de mécompilation DELTA [1,2] réalisé au LABORIA offre aux auteurs de compilateurs un outil de traitement systématique des descriptions sémantiques. Il est basé sur la notion d'attributs de KNUTH [3,4], le rôle de tels attributs est de décrire sémantiquement chaque non-terminal d'une grammaire.
Nous proposons donc de définir une méthodologie de l'optimisation en créant des attributs capables d'optimiser le code à générer. Cette recherche devrait contribuer à éliminer la deuxième difficulté.

Quant à la première, elle s'en trouvera automatiquement réduite dans la mesure où l'on pourra contrôler plus facilement l'application des algorithmes.

Généralement, pour obtenir un code objet optimisé, il est nécessaire d'effectuer plusieurs passes sur le programme traduit en langage intermédiaire (triplets¹ par exemple).

Dans un premier temps, on découpe le programme en blocs de base² sur lesquels on peut effectuer une optimisation dite "locale".

Puis à partir de ces blocs on détermine un ensemble d'intervalles³ disjoints recouvrant tout le programme. Sur chacun de ses intervalles, on peut effectuer l'optimisation "globale".

Cette méthode n'assure pas une synthèse suffisante de l'information, aussi il faut après chaque étape, gérer les triplets.

Selon les cas, on doit :

- supprimer des triplets (cas de la propagation des constantes et de la redondance).

- déplacer des triplets (cas d'affectation invariante).

- ajouter des triplets (cas de la transformation de multiplications en additions).

On pourra voir dans la suite de cet article que l'optimisation par attributs réduit sinon supprime cette manipulation de triplets indispensable mais lourde.

Parmi les attributs sémantiques, certains sont définis spécialement pour la génération de code, mais jouent cependant un rôle dans l'optimisation, les autres créés plus spécifiquement dans le but d'optimiser, servent à gérer le code objet ou transmettre l'information.

Cet article est volontairement limité au cas précis de l'élimination des sous-expressions communes, pour que le lecteur se familiarise avec les notations employées.

1. Un triplet est formé de deux opérandes et d'un opérateur :

exemple : + J, 1

réalise l'opération J + 1.

2. Un bloc de base est une suite d'instructions qui s'exécute séquentiellement de la première à la dernière.

3. Un intervalle est un sous-graphe maximum à une seule entrée, dans lequel tous les circuits passent par l'entrée.
Nous traiterons d'abord l'exemple par un algorithme classique, puis nous donnerons une description par attributs sémantiques.

D'autres publications présenteront un ensemble d'optimisations décrites par attributs et montreront qu'une telle description peut constituer une véritable méthodologie de l'optimisation.

## 1. Méthode classique :

La méthode utilisée est celle des "nombres de dépendance" [5]. Il s'agit d'attribuer un nombre de dépendance à chaque triplet d'un bloc.

### 1.1. Définitions :

- Le nombre de dépendance de chaque variable est initialisé à 0.

- Si le triplet (i) affecte la valeur d'une variable A (Ex. (i) = A, 1), alors le nombre de dépendance de A devient égal à i à partir du triplet (i + 1).

- Le nombre de dépendance d'un triplet est égal à 1 + MAX (nombre de dépendance de ses opérandes).

La base de cette méthode est le théorème suivant :

**Théorème :**

Soient deux triplets (i) et (j) identiques (avec $i < j$, compte tenu de la commutativité de leur opérateur), si leurs nombres de dépendance sont égaux, alors le triplet (j) est redondant.

### 1.2. Méthode :

a - si les triplets (i) et (j) sont identiques et si (j) est redondant, remplacer le triplet (j) par IDEM (i).

b - si un opérande est une référence à un triplet (j) du type IDEM(i) remplacer l'opérande (j) par l'opérande (i).

c - calculer le nombre de dépendances de chaque triplet en tenant compte de la définition précédente.

d - ne pas générer les triplets de type IDEM.

Nous proposons d'appliquer cette méthode à l'exemple suivant :

$$T(I,J) = T(I,J+1)$$

Pour un tableau implanté ligne par ligne, la borne inférieure étant 1, et $max2$ étant la deuxième dimension du tableau T, l'adresse de l'élément $T(K,L)$ est donnée par la relation :

$$ADR[T(K,L)] = ADR[T(1,1)] + (K-1) \times max2 + L-1$$
Un groupe de cinq triplets correspond au calcul de l'adresse de cet élément de tableau, nous l'appellerons GADR dans la suite de l'article :

$$
\text{GADR} \left\{
\begin{array}{ll}
(a) & - K,1 \\
(b) & * (a), \max2 \\
(c) & + (b),L \\
(d) & - (c),1 \\
(e) & + (d), \text{ADR}[T(1,1)]
\end{array}
\right.
$$

Nous pouvons maintenant écrire les triplets correspondant à l'affectation :

$$
T(I,J) = T(I,J+1)
$$

Puisqu'on reconnait à l'analyse d'abord T(I,J), il est naturel de générer
d'abord, les triplets correspondant à cette variable indicée.

$$
\left.
\begin{array}{ll}
(1) & - \text{I} ,1 \\
(2) & * (1) ,\max2 \\
(3) & + (2) ,\text{J} \\
(4) & - (3) ,1 \\
(5) & + \text{ADR}[T(1,1)] , (4) \\
(6) & + \text{J} ,1 \\
(7) & - \text{I} ,1 \\
(8) & * (7) ,\max2 \\
(9) & + (8) , (6) \\
(10) & - (9) ,1 \\
(11) & + \text{ADR}[T(1,1)] , (10) \\
(12) & = T[(5)] , T[(11)]
\end{array}
\right\}
\quad \begin{array}{l}
\text{GADR pour} \\
T(I,J)
\end{array}
$$
$$
\left.
\begin{array}{ll}
& \text{GADR pour} \\
& T(I,J+1)
\end{array}
\right\}
$$

La méthode des nombres de dépendance donne les résultats suivants :

<table>
  <thead>
    <tr>
      <th>numéro<br>triplet</th>
      <th>triplets non<br>optimisés</th>
      <th>nombre de<br>dép.</th>
      <th>optimisation du<br>triplet (7)</th>
      <th>optimisation du<br>triplet (8)</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>(1)</td>
      <td>- I , 1</td>
      <td>1</td>
      <td>- I , 1</td>
      <td>- I , 1</td>
    </tr>
    <tr>
      <td>(2)</td>
      <td>* (1) ,max2</td>
      <td>2</td>
      <td>* (1) ,max2</td>
      <td>* (1) ,max2</td>
    </tr>
    <tr>
      <td>(3)</td>
      <td>+ (2) , J</td>
      <td>3</td>
      <td>+ (2) , J</td>
      <td>+ (2) , J</td>
    </tr>
    <tr>
      <td>(4)</td>
      <td>- (3) ,1</td>
      <td>4</td>
      <td>- (3) ,1</td>
      <td>- (3) ,1</td>
    </tr>
    <tr>
      <td>(5)</td>
      <td>+ ADR[T(1,1)], (4)</td>
      <td>5</td>
      <td>+ ADR[T(1,1)], (4)</td>
      <td>+ ADR[T(1,1)], (4)</td>
    </tr>
    <tr>
      <td>(6)</td>
      <td>+ J ,1</td>
      <td>1</td>
      <td>+ J ,1</td>
      <td>+ J ,1</td>
    </tr>
    <tr>
      <td>(7)</td>
      <td>- I ,1</td>
      <td>1</td>
      <td>IDEM (1)</td>
      <td>IDEM (1)</td>
    </tr>
    <tr>
      <td>(8)</td>
      <td>* (7) ,max2</td>
      <td>2</td>
      <td>* (1) ,max2</td>
      <td>IDEM (2)</td>
    </tr>
    <tr>
      <td>(9)</td>
      <td>+ (8) , (6)</td>
      <td>3</td>
      <td></td>
      <td>+ (2) , (6)</td>
    </tr>
    <tr>
      <td>(10)</td>
      <td>- (9) ,1</td>
      <td>4</td>
      <td></td>
      <td>- (9) , 1</td>
    </tr>
    <tr>
      <td>(11)</td>
      <td>+ ADR[T(1,1)], (10)</td>
      <td>5</td>
      <td></td>
      <td>+ ADR[T(1,1)], (10)</td>
    </tr>
    <tr>
      <td>(12)</td>
      <td>= T[(5)] , T[(11)]</td>
      <td>1</td>
      <td></td>
      <td>= T[(5)] , T[(11)]</td>
    </tr>
  </tbody>
</table>
On constate que les triplets (1) et (7) sont identiques et qu'ils ont le même nombre de dépendance 1. On va donc remplacer le triplet (7) par IDEM(1) (cf a) puis on remplacera toutes les références au triplet (7) (de type IDEM) par des références au triplet (1) (cf b).

Alors le triplet (8) devient identique au triplet (2), on peut le remplacer par IDEM(2) (cf a) et les références au triplet (8) sont remplacées par des références au triplet (2) (cf b).

Une nouvelle passe sur les triplets est nécessaire pour supprimer ceux de type IDEM.

Les triplets générés sont :

(1) - I ,1

(2) * (1) ,max2

(3) + (2) ,J

(4) + (3) ,1

(5) + ADR[T(1,1)] , (4)

(6) + J ,1

(7) + (2) , (6)

(8) - (7) ,1

(9) + ADR[T(1,1)] , (8)

(10) = T[(5)] ,T[(9)]

## 2. La méthode des attributs

### 2.1 Les attributs de génération

Les attributs portent les informations sémantiques du langage source, ce qui permet de générer un code intermédiaire (triplets) déjà optimisé.

Reprenons l'exemple précédent :

$$T(I,J) = T(I,J+1)$$

Les règles de production nécessaires pour analyser cette affectation sont les suivantes :

* `<PROG>` ::= `<LIST>` ;

* `<LIST>` ::= `<LIST>` ; `<INS>`

* `<LIST>` ::= `<INS>`

* `<INS>` ::= `<VAR2>` = `<EX>`
<VAR2> ::= ID (<EX>, <EX>)

<EX> ::= <TERME>

<EX> ::= <VAR2>

<EX> ::= <EX> + <TERME>

<TERME> ::= CSTE

La signification des non-terminaux est :

PROG : programme

LIST : liste d'instructions

INS : instructions

VAR2 : variable indicée à deux dimensions

EX : expression numérique

TERME : terme numérique

L'arbre syntaxique de l'exemple : T(I,J) = T(I,J+1) est représenté sur la figure 1. Nous avons numéroté les différentes occurences d'un même non-terminal. Si on compte les triplets au fur et à mesure de leur génération, on peut repérer pour chaque non-terminal les numéros du premier et du dernier triplet qu'il génère. Les attributs P et D portant respectivement ces informations.

L'initialisation de l'attribut P se fait dans la règle :

<PROG> ::= <LIST>

P(LIST) = 1

Car par convention le premier triplet du programme porte le numéro 1.

Les informations portées par P descendent dans l'arbre syntaxique grâce aux règles :

<LIST> ::= <INS>

D(LIST) = D(INS)

P(INS) = P(LIST)

<LIST> ::= <LIST'><fnref n="1" /> ; <INS>

P(LIST') = P(LIST)

P(INS) = D(LIST') + 1

L'attribut P est un attribut hérité<fnref n="2" />.

<footnote n="1">1 Dans une règle syntaxique, on distingue la deuxième occurence d'un non-terminal à l'aide du caractère '.</footnote>

<footnote n="2">2 Un attribut hérité d'un noeud ne dépend que du prédécesseur immédiat. L'information part de la racine pour se propager vers les feuilles.</footnote>
<figure><img src="image_2.png" /><figcaption>Figure 1</figcaption></figure>
Au contraire D est un attribut synthétisé<fnref n="1" />, il assure le transfert de P depuis le non-terminal LIST' jusqu'au non-terminal INS et se calcule dans la règle qui définit LIST' par :

<LIST> ::= <LIST> ; <INS>

D(LIST) = D(INS)

Pour un non-terminal qui produit un seul triplet, on a : D = P,
s'il en produit deux : D = P + 1,
s'il n'en produit aucun : D = P - 1, (car P attribut hérité a été incrémenté
automatiquement : P(INS) = D(LIST') + 1, lorsqu'on a ajouté une instruction INS
à la liste LIST).
Les liaisons entre les attributs P et D pour chaque règle sémantique sont
donc les suivantes :

<PROG> ::= <LIST>

D(PROG) : D(LIST)

P(LIST) = 1

<LIST> ::= <INS>

D(LIST) = D(ins)

P(INS) = P(LIST)

<LIST> ::= <LIST'> ; <INS>

P(INS) = D(LIST') + 1

P(LIST') = P(LIST)

D(LIST) = D(INS)

<INS> ::= <VAR2> = <EX>

P(VAR2) = P(INS)

P(EX) = D(VAR2) + 1

D(INS) = D(EX) + 1

générer le triplet qui affecte à VAR2 le résultat de EX.

<footnote n="1">1 Un attribut synthétisé d'un noeud ne dépend que des successeurs immédiats.
L'information remonte dans l'arbre syntaxique, elle part des feuilles et se
propage vers la racine.</footnote>
<VAR2> ::= ID ( <EX> , <EX'> )
        P(EX) = P(VAR2)
        P(EX') = D(EX) + 1
        D(VAR2) = D(EX') + 5

générer les 5 triplets qui calculent l'adresse de VAR2.

<EX> ::= <TERME>
      P(TERME) = P(EX)
      D(EX) = D(TERME)

<EX> ::= <EX'> + <TERME>
      P(EX') = P(EX)
      P(TERME) = D(EX') + 1
      D(EX) = D(TERME) + 1

générer le triplet qui ajoute le résultat de EX' au résultat
de TERME.

<TERME> ::= ID
           D(TERME) = P(TERME) - 1

<TERME> ::= CSTE
           D(TERME) = P(TERME) - 1

Une fois ordonné, le programme d'évaluation sémantique des attributs est
le suivant :

P(LIST) = 1
P(INS) = P(LIST) = 1
P(VAR2 1) = D(INS) = 1
P(EX 1) = P(VAR2 1) = 1
P(TERME 1) = P(EX 1) = 1
D(TERME 1) = P(TERME 1) - 1 = 0
D(EX 1) = D(TERME 1) = 0
P(EX 2) = D(EX 1) + 1 = 1
P(TERME 2) = P(EX 2) = 1
D(TERME 2) = P(TERME 2) - 1 = 0
D(EX 2) = D(TERME 2) = 0
D(VAR2 1) = D(EX 2) + 5 = 5

générer les 5 triplets qui calculent l'adresse de T(I, I).
$$P(\text{EX } 3) = D(\text{VAR2 } 1) + 1 = 6$$

$$P(\text{VAR2 } 2) = P(\text{EX } 3) = 6$$

$$P(\text{EX } 4) = P(\text{VAR2 } 2) = 6$$

$$P(\text{TERME } 3) = P(\text{EX } 4) = 6$$

$$D(\text{TERME } 3) = P(\text{TERME } 3) - 1 = 5$$

$$D(\text{EX } 4) = D(\text{TERME } 3) = 5$$

$$P(\text{EX } 5) = D(\text{EX } 4) + 1 = 6$$

$$P(\text{EX'}) = P(\text{EX } 5) = 6$$

$$P(\text{TERME } 5) = P(\text{EX'}) = 6$$

$$D(\text{TERME } 5) = P(\text{TERME } 5) - 1 = 5$$

$$D(\text{EX'}) = D(\text{TERME } 5) = 5$$

$$P(\text{TERME } 4) = D(\text{EX'}) + 1 = 6$$

$$D(\text{TERME } 4) = P(\text{TERME } 4) - 1 = 5$$

$$D(\text{EX } 5) = D(\text{TERME } 4) + 1 = 6$$

générer le 1er triplet: + J, 1

$$D(\text{VAR2 } 2) = D(\text{EX } 5) + 5 = 11$$

générer les 5 triplets qui calculent l'adresse de T(I,J+1)

$$D(\text{EX } 3) = D(\text{VAR2 } 2) = 11$$

$$D(\text{INS}) = D(\text{EX } 3) + 1 = 12$$

générer le triplet d'affectation.

$$D(\text{LIST}) = D(\text{INS}) = 12$$

$$D(\text{PROD}) = D(\text{LIST}) = 12$$

$$D(\text{PROG}) = 12$$

## 2.2 L'attribut de redondance R.

Si on se contente de la sémantique qui a été définie précédemment, on génère les triplets (7) et (8) qui sont redondants. Afin de les éliminer on va définir un nouvel attribut R qui évite l'utilisation du triplet IDEM de la méthode classique.

R qualifie tous les non-terminaux dont la sémantique génère un triplet d'expression, le traitement de la redondance se fait alors de la façon suivante :

- Si le triplet (j) est redondant par rapport au triplet (i), on ne le génère pas. L'attribut D n'est donc pas incrémenté et reste égal à j-1 (dernier triplet généré), mais on donne à R la valeur i. Et toute référence future à (j) sera substituée par une référence à (i).
Détaillons cette sémantique au niveau des règles de grammaire qui produisent des triplets d'expression :

a) `<EX>` ::= `<EX'>` + `<TERME>`

P `<EX'>` = P `<EX>`

P `<TERME>` = D `<EX>` + 1

D `<EX>` = D `<TERME>` + 1

R `<EX>` = REDONDANCE (D `<EX>`)

c Sémantique de génération

IF R `<EX>`. NE. D `<EX>` GOTO 1

générer le triplet : + R `<EX>` , R `<TERME>`

1 D `<EX>` = D `<EX>` - 1 ...

FUNCTION REDONDANCE (D)

REDONDANCE = D si le triplet D n'est pas redondant.

REDONDANCE = I si le triplet D est redondant avec le triplet I.

RETURN

Nous remarquons que la génération se fait maintenant dans la sémantique de l'attribut R. De plus l'attribut D ayant été incrémenté systématiquement avant le calcul de l'attribut R, il faut le mettre à jour si le triplet considéré est redondant.

b) `<VAR2>` ::= ID (`<EX>`, `<EX'>`)

F `<EX>` = P `<VAR2>`

P `<EX'>` = D `<EX>` + 1

D `<VAR2>` = D `<EX>` + 5

R `<VAR2>`

test de redondance et mise à jour de D.

L'organigramme de la sémantique pour R `<VAR2>` est présenté en figure 2.

Dans notre exemple, la règle syntaxique considérée produit deux groupes de 5 triplets : (1), (2), (3), (4), (5) et (7), (8), (9), (10), (11). Il faut détecter dans le deuxième groupe de triplets les deux triplets redondants, c'est pourquoi nous plaçons un appel à la fonction REDONDANCE avant chacune des productions.

Pour tester la redondance du triplet (7) l'appel est :

R `<VAR2>` = REDONDANCE `<(7)`)

le résultat de cet appel est R `<VAR2>` = (1), puisque le triplet (7) est redondant par rapport au triplet (1).
<figure><img src="image_3.png" /><figcaption>Figure 2.</figcaption></figure>
Le triplet suivant (8) tient compte du résultat précédent puisqu'il s'exprime par :

* R(VAR2) , max2
soit * (1) , max2

Pour savoir s'il doit être généré on effectue le test en appelant la fonction REDONDANCE :

R(VAR2) = REDONDANCE ((8))

le résultat est R(VAR2) = (2)

ce triplet ne doit donc pas être généré.

Les tests suivants sont négatifs et il faut alors générer les triplets correspondants.

Par conséquent le résultat de l'optimisation est constitué par les triplets suivants :

(1) - I ,1

(2) * (1) ,max2

(3) + (2) ,j

(4) + (3) ,1

(5) + ADR[T(1,1)] , (4)

(6) + J ,1

(7) + (2) , (6)

(8) - (7) ,1

(9) + ADR[T(1,1)] , (8)

(10) = T[(5)] , T[(9)]

3. Comparaison entre les deux méthodes :

Examinons le travail de gestion à effectuer sur les triplets dans la méthode classique. Chaque fois qu'on traite un triplet (i) faisant appel à un triplet (j), il faut relire ce triplet (j). Si ce dernier est du type IDEM (1), on remplace le triplet (i), la référence à (j) par (1).

Enfin il faut relire tous les triplets d'un bloc pour supprimer les IDEM.

Dans la méthode par attributs, la sémantique attachée à R élimine les redondances, grâce à la définition même de cet attribut.

R est traité comme tous les attributs, mais son rôle est prévu de façon à ce que l'optimisation se fasse naturellement en cours de compilation.
Conclusion :

L'exemple traité est volontairement simple. Il a pour but d'introduire
un principe de description des attributs d'optimisation.

Nous pensons que les avantages d'une telle description purement
algorithmique sont importants :

clarté, facilité d'écriture, rigueur.

Dans le même esprit, il est bien sûr possible de définir un ensemble
d'attributs réalisant les fonctions d'optimisation pour un langage donné.

Cette structure d'attributs apporte une certaine méthodologie de
l'optimisation au niveau de la description sémantique d'un langage et permet
de se dégager des problèmes de réalisation et d'implémentation.
Références :

[1] L. BLAIZOT
"DELTA : Système de Description de Langages et Traducteurs par Attributs".
Rapport de Recherche LABORIA, 20, Juin 1973.

[2] F. BLAIZOT, P. BOULLIER
"Projet DELTA, Description d'un Langage algorithmique à structure de blocs".
Rapport de Recherche LABORIA, 35, Octobre 73.

[3] D.E. KNUTH
"Semantic of context free languages".
Mathematical Systems Theory, 2, 2, 1968.

[4] D.E. KNUTH
"Example of formal semantics".
Symposium on Semantics of Algorithmic Languages, 1970 SPRINGER VERLAG.

[5] D. GRIES
"Compiler construction for digital computers".
John Wiley & Sons, Inc. New York, 1971.