# Delta. système de description de langages et de traducteurs par attributs

Laurent Blaizot

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

## To cite this version:

Laurent Blaizot. Delta. système de description de langages et de traducteurs par attributs. [Rapport de recherche] IRIA-RR-020, IRIA. 1973, pp.24. hal-04715986

HAL Id: hal-04715986

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

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_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
RIA
laboria

laboratoire de recherche
en informatique
et automatique

# DELTA.
Système
de D'Escription
de Langages
et de Traducteurs
par Attributs

Laurent Blaizot

<figure><img src="image_3.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° 20

juin 1973
Laurent Blaizot

(présenté par Bernard Lorho)

Résumé :

Nous développons ici quelques idées sur l'utilisation dans un système
complet de métacompilation, d'une méthode de description sémantique due
à Knuth.

Cette méthode de définition descriptive de la sémantique d'un langage
devrait permettre d'assouplir énormément l'utilisation d'un tel système.
Le projet DELTA (DEscription des Langages et de leurs Traducteurs par
Attributs) que nous nous proposons de réaliser devrait d'une part mettre
l'accent sur cette facilité d'utilisation et d'autre part accorder une
place importante aux techniques d'optimisation, qu'elles soient décrites
par l'utilisateur ou fournies par le système. La technique de définition
par attributs de Knuth s'applique en effet parfaitement à la description
par l'utilisateur des techniques d'optimisation qu'il souhaite éventuel-
lement incorporer à son processeur. Enfin, le problème de la portabilité
des traducteurs produits est sans aucun doute d'une grande importance
et donnera lieu à une étude approfondie.

Abstract :

Some ideas are developped about the application to a complete metacompi-
lation system of a semantics description method first exposed by Knuth.
This declarative method of language's semantics definition should allow
one to use such a system very easily.

Our purpose is to implement a system, DELTA (DEfinition of Languages and Translators by Attributes), in which a great importance will be attached to optimization techniques described by the user, as well as those supplied by the system, and to the problem of portability, so as to allow most people to use it conveniently.
Système de Description de Langages et de Traducteurs par attributs

étude préliminaire

Ce papier concerne le démarrage au LABORIA d'un projet d'étude d'un
TWS *. Nous ne parlerons ici que des aspects sémantiques. Les problèmes syn-
taxiques feront l'objet d'un autre papier. [14]

1. "Translator-oriented" ou "Interpreter-oriented" ?

Le problème de la conception de systèmes d'écriture de traducteurs a été
abordé dès 1964. Les premières réalisations étaient basées sur la notion
habituelle de compilateur, c'est-à-dire que l'utilisateur décrivait son
langage en termes relatifs à un autre langage supposé "connu", en d'autres
termes compilable ou assemblable. Ceci a pu faire dire depuis [12]
que cette solution n'était pas élégante car elle ramenait le problème posé
à un problème déjà connu, et ne s'intéressait pas à la véritable analyse du
problème, qui aurait dû être faite relativement à des bases universelles.
Une seconde approche s'est donc dessinée. La base universelle choisie était
l'ordinateur, ou plutôt la configuration de sa mémoire.

L'utilisateur, pour définir un langage, décrit l'effet de chaque instruction
de son langage sur la mémoire de la machine, c'est-à-dire sur les données
de son programme, en fonction de l'état antérieur de ces données. Cette
méthode permet évidemment une définition beaucoup plus élégante, car la
base de définition est la même pour tous.

<footnote>* TWS : Translator Writing System : système d'écriture de traducteurs</footnote>
Le formalisme le plus élaboré dans ce domaine est l'oeuvre du groupe IBM de Vienne et est appelé VDL (Vienna Definition Language).

L'inconvénient de ce mode de description apparaît dès que l'on se pose le problème de réaliser un T.W.S. qui utilise ce formalisme.

En effet, de par la nature même de la description, on ne peut en déduire qu'un interpréteur. De là vient le qualificatif de "interpreter-oriented" appliqué à cette approche. La première approche, dont nous avons déjà parlé, est qualifiée de "compiler-oriented", bien que "translator-oriented" paraisse plus approprié.

Il est bien certain qu'il existe deux catégories d'utilisateurs intéressés par la formalisation de la sémantique : d'une part les linguistes et les logiciens, qui s'intéressent à la formalisation elle-même, sans préoccupation d'implantation ; ces utilisateurs souhaitent appliquer cette formalisation à l'étude de schémas de programmes et à la démonstration automatique de théorèmes. Les travaux de Lucas et Walk [3,2], montrent que l'approche de Vienne convient parfaitement à cette utilisation.

Mais il y a d'autre part un ensemble d'utilisateurs spécialistes d'écriture de software, qui ont une grande habitude des traducteurs en général, et qui souhaitent être déchargés de toute une partie fastidieuse de leur travail, à savoir la mise en place du squelette d'un traducteur, analyseur syntaxique, analyseur lexicographique, diverses mises en tables etc...

Ces gens-là sont plus intéressés par l'efficacité et la commodité d'utilisation de l'outil qu'on leur propose que par l'esthétique de l'approche. En fait, ramener un problème posé à un problème connu est pour eux une habitude, et l'approche "translator-oriented" leur est plus familière que l'autre.

Certains auteurs [13] n'hésitent pas à dire que devant un problème précis d'application à résoudre, il est plus rentable d'utiliser un langage spécialisé dont on écrit le compilateur, que de se servir d'une petite partie d'un langage de haut niveau existant. Cela est d'ailleurs particulièrement vrai pour les petits ordinateurs, sur lesquels on ne dispose pas toujours du compilateur d'un langage de niveau suffisant pour couvrir l'application en question.
Cela montre qu'il serait très intéressant de disposer d'un TWS suffisamment maniable et efficace pour inciter les informaticiens à l'utiliser. C'est à quoi nous avons décidé de nous intéresser. Un autre aspect très intéressant serait évidemment la portabilité de ce TWS d'une machine sur une autre.
Nous en reparlerons plus loin.

## 2. Etude de l'approche "translator-oriented".

Nous avons étudié particulièrement :

- les système META [1]

- le Compiler - Compiler [4]

- le FSL de Feldman [5]

- le "Syntax directed Compiler" de IRONS [6]

- la formalisation de KNUTH [7,8]

Cette dernière, la plus élégante, est inspirée du travail d'IRONS. Elle consiste à exprimer la sémantique d'un non-terminal de la grammaire en fonction de celle des "ascendants" et "descendants" immédiats de ce non-terminal.

L'examen de ces diverses réalisations nous a permis de dégager les points délicats sur lesquels les solutions divergent.

### 2.1 Le méta-langage sémantique

Un méta-langage adéquat devrait être "universel", en ce sens que son rôle est de permettre de décrire n'importe quel concept. Le premier auquel on pense est évidemment le langage-machine, puisqu'il utilise une base commune à tous les utilisateurs d'une machine, l'ensemble des commandes câblées.

Malheureusement, l'utilisation du langage machine a deux inconvénients :

- tout d'abord, un programme écrit en LM n'est pas facilement compréhensible s'il n'est pas abondamment documenté, ce qui est particulièrement regrettable dans notre cas, où la description d'un langage doit pouvoir se communiquer d'un utilisateur à un autre,

- d'autre part, le fait que le TWS accepte une description dépendant étroitement de la machine rend complexe sa transférabilité, et n'atteint donc que partiellement les objectifs visés.
Le LM n'est donc pas adapté. Le problème est de déterminer à quel niveau de complexité se situe le langage sémantique idéal.

Des réalisations comme FSL ou META 5 utilisent une formulation proche du FORTRAN, avec en plus de nombreuses primitives de mise en table, génération et empilement. Malheureusement, ces primitives ne sont pas à notre connaissance modifiables par l'utilisateur, ce qui rend le système trop rigide.

En outre, on ne trouve pas dans ces systèmes, de primitives de description de données suffisamment évoluées, ce qui limite considérablement l'utilisateur quant à ses structures de données. D'un autre côté, une notation comme celle de Knuth se prête très facilement à l'adjonction de primitives et a l'avantage d'être très élégante. Nous pensons donc que le mieux serait d'adopter cette notation et d'y ajouter toute une bibliothèque de primitives dont le choix reste à faire.

Les primitives devraient permettre :

- de fournir à l'utilisateur des outils commodes de mise en table, génération, empilement etc...

- de mettre à sa disposition une base de données suffisante pour décrire toute structure

- enfin, de lui fournir également une base de description du contrôle de son programme (rupture de séquence, appels de procédure, tasking etc...).

C'est sur ces deux derniers points que l'accent devra être mis, car les réalisations existantes les ont toutes laissés dans l'ombre. Un des points sur lesquels cette réalisation doit se distinguer des autres sera également la clarté du formalisme de description sémantique. La notation de Knuth doit permettre d'atteindre cet objectif.

## 2.2 Le résultat de la phase d'analyse

C'est un autre aspect du problème, tout aussi délicat que le premier. Le but premier d'un T.W.S. est que l'utilisateur puisse en faire ce qu'il désire : un interprèteur, un compilateur ou un simple traducteur d'un langage dans un autre (compilation par couches, passage d'une implémentation à une autre etc...). Un système comme FSL ne permet que de réaliser un compilateur, puisque les seules sorties possibles sont des sorties par
génération de binaire. Par contre, les systèmes META ont été définis en vue de la traduction d'un langage dans un autre sous forme de chaînes de caractères. Mais ils sont mal adaptés à l'écriture de compilateurs ou d'interpréteur. Ces restrictions sont malcommodes. Un T.W.S. adéquat doit permettre de réaliser n'importe quel processeur.

On voit que selon que l'utilisateur aura décrit un traducteur, un compilateur ou un interpréteur, le résultat de l'exécution de ses routines sémantiques sera :

- un autre programme à passer dans un traducteur existant

- un binaire à charger et exécuter

- un ensemble de résultats.

Un point important est la façon dont sont exécutées ces routines sémantiques.

Nous pensons que, plutôt que de les exécuter une à une au fur et à mesure de la reconnaissance de l'entité syntaxique associée, comme cela est fait par exemple dans le Compiler-Compiler, il est préférable que l'analyseur syntaxique produise un véritable *programme* d'évaluation sémantique, qui est ensuite fourni au compilateur du méta-langage sémantique.

Cela doit améliorer considérablement l'efficacité du compilateur produit.

Un gros avantage est que, disposant d'un véritable programme, on peut éventuellement lui appliquer une phase d'optimisation.

Nous verrons plus loin que la méthode de Knuth se prête à une autre optimisation, moyennant une légère modification de l'algorithme de construction du programme d'évaluation sémantique.

## 3. Etude de la formalisation de Knuth

Dans un premier temps, il est nécessaire de réaliser un outil simple dont nous puissions nous servir sur quelques exemples de façon à évaluer les besoins, notamment en primitives. Nous avons donc choisi un méta-langage sémantique dont nous disposons du compilateur : le PL/1. Ce langage a l'avantage d'être assez vaste pour couvrir de nombreuses applications.

Nous utilisons ce méta-langage sémantique dans le cadre de la formulation de Knuth. D'autre part, les outils syntaxiques dont nous disposons sont :
- un constructeur de scanners

- un constructeur d'analyseurs produisant des règles de production FLOYD-EVANS.

## 3.1 Notion d'attribut synthétisé et hérité.

Par rapport à la notation introduite par IRONS, celle de KNUTH présente deux améliorations :

- les attributs sémantiques d'un non-terminal peuvent être plusieurs (IRONS n'en avait qu'un).

- les attributs peuvent dépendre non seulement de ceux des "descendants" immédiats du non-terminal dans l'arbre syntaxique (attributs "synthétisés"), mais aussi de ceux du père (attributs "hérités").

Cette possibilité introduit une grande souplesse de traitement en ce qui concerne des problèmes courants dans les langages de programmation, comme par exemple la structure de blocs d'ALGOL 60.

### Exemple

Nous allons prendre comme exemple d'utilisation de ces deux sortes d'attributs la description d'un interpréteur de nombres binaires.

Ils peuvent être représentés par la grammaire suivante :

```
< B > :: = 0
< B > :: = 1
< L > :: = < B >
< L > :: = < L > < B >
< N > :: = < L >
< N > :: = < L > . < L >
```

L'arbre d'analyse de la chaîne 1101.01 sera le suivant :
<figure><img src="image_4.png" /></figure>

Pour définir un interpréteur de ces nombres binaires, il suffit, par exemple, d'utiliser les attributs suivants :

Chaque < B > a une valeur v(B) entière

Chaque < L > a une valeur v(L) entière

Chaque < L > a une longueur l(L) entière

Chaque < N > a une valeur v(N) fractionnaire.

KNUTH associe alors à chaque production de la grammaire des règles d'évaluation sémantique, que nous pouvons par exemple écrire en PL/1 : (G1)

< B > ::= 0                      v(B) = 0 ;
< B > ::= 1                      v(B) = 1 ;
< L > ::= < B >                 v(L) = v(B) ; 1(L) = 1 ;
< L > ::= < L > < B >           v(L₁) = 2*v(L₂)+v(B) ;
             1(L₁) = 1(L₂) + 1 ;
< N > ::= < L >

< N > ::= < L > . < L >

v(N) = v(L) ;

v(N) = v(L₁) + v(L₂)/2**1(L₂) ;

On voit que nous n'avons employé que des attributs synthétisés. Mais on
peut donner une autre description de ces nombres binaires utilisant également
des attributs hérités.

Nous ajoutons un attribut hérité : l'échelle s de < B > ou < L >.

La description devient la suivante : (G2)

< B > ::= 0

< B > ::= 1

< L > ::= < B >

< L > ::= < L > < B >

< N > ::= < L >

< N > ::= < L > . < L >

v(B) = 0 ;

v(B) = 2**s(B) ;

v(L) = v(B) ;

s(B) = s(L) ;

1(L) = 1 ;

v(L₁) = v(L₂) + v(B) ;

s(B) = s(L₁) ;

s(L₂) = s(L₁) + 1 ;

1(L₁) = 1(L₂) + 1 ;

v(N) = v(L) ;

s(L) = 0 ;

v(N) = v(L₁) + v(L₂) ;

s(L₁) = 0 ;

s(L₂) = -1(L₂) ;

On devine que cette possibilité, pas très concluante à propos des
nombres binaires, est extrêmement séduisante quand il s'agit de traiter
certains aspects des langages de programmation.

Il suffit pour s'en persuader d'examiner l'exemple ci-dessous.

Cet exemple se place dans le cadre d'un compilateur devant reconnaitre les
expressions arithmétiques de type FORTRAN, et nous supposons que celui
qui décrit ce compilateur souhaite incorporer à son processus de génération
de code, un algorithme d'évaluation du nombre minimum de registres de
calcul nécessaires, de type SETHI et ULLMAN [15].
Il va avoir besoin, pour décrire cet aspect de son compilateur, de deux attributs :

- 1'un synthétisé, R, qui lui donnera le nombre minimum de registres de calcul

- 1'un hérité, G, qui lui indiquera si un non-terminal se trouve ou non à gauche d'un opérateur.

En admettant qu'un programme se réduise à une expression, sa description pourra être la suivante :

< PG > = < E >

R(PG) = R(E₁)

< E > = < E > + < T >

G(E₂) = 'VRAI'

G(T) = 'FAUX'

IF R(E₂) = R(T) THEN
  R(E₁) = R(E₂) + 1
ELSE
  R(E₁) = MAX(R(E₂), R(T))

< E > = < E > - < T >

G(E₂) = 'VRAI'

G(T) = 'FAUX'

IF R(E₂) = R(T) THEN
  R(E₁) = R(E₂) + 1
ELSE
  R(E₁) = MAX(R(E₂), R(T))

< E > = < T >

G(T) = G(E)

R(E) = R(T)
< T > = < T > * < P >

G(T₂) = 'VRAI'

G(P) = 'FAUX'

IF R(T₂) = R(P) THEN
R(T₁) = R(T₂) + 1
ELSE
R(T₁) = MAX(R(T₂), R(P))

< T > = < T > / < P >

G(T₂) = 'VRAI'

G(P) = 'FAUX'

IF R(T₂) = R(P) THEN
R(T₁) = R(T₂) = R(T₁) + 1
ELSE
R(T₁) = MAX(R(T₂), R(P))

< T > = < P >

G(P) = G(T)

R(T) = R(P)

< P > = ID

IF G(P) THEN R(P) = 1
ELSE R(P) = 0

< P > = NB

IF G(P) THEN R(P) = 1
ELSE R(P) = 0

< P > = (< E >)

R(P) = R(E)

G(E) = G(P)
Cet exemple très simple montre cependant clairement l'intérêt de la notion d'attribut hérité. L'utilisation des deux types d'attributs permet une souplesse d'écriture très appréciable, et qui va exactement dans le sens d'une systématisation de l'écriture des compilateurs.

A partir d'une telle description, deux problèmes principaux se posent :

- déterminer l'ordre d'évaluation des attributs quand un programme source a été analysé

- détecter les boucles de définition ou les définitions d'attributs manquantes en cas d'erreur de l'utilisateur. Dans le cas d'une description bien formée, l'analyseur produit par DELTA détermine l'ordre d'évaluation et en déduit un véritable programme d'évaluation sémantique.

Il existe deux possibilités pour construire un tel programme :

- ou bien le constructeur élabore lui-même, à partir de la description sémantique, un schéma de programme récursif qui sera ensuite exécuté après la phase d'analyse et qui aura comme paramètres le texte d'entrée et l'arbre d'analyse

- ou bien c'est l'analyseur qui, en utilisant des tables transmises par le constructeur, en déduit pour chaque programme source un programme d'évaluation non récursif et non paramétré.

## 3.2 Production d'un programme récursif et paramétré.

Il est possible, à partir d'une description sémantique donnée, d'en déduire un programme qui comporte une procédure par attribut.

Dans le cas de notre grammaire G2, ce sera par exemple : (en simili PL/1)

```pascal
V : PROCEDURE (N);
    IF s2 (N) = '.' THEN
        RETURN (V(s1 (N)) + V(s3 (N)));
ELSE IF s2 (N) = 'B' THEN
        RETURN (V(s1 (N)) + V(s2 (N)));
ELSE IF s1 (N) = 'B' THEN
        RETURN (V(s1 (N)));
```
ELSE IF $s_1(N) = 'L' THEN RETURN (V(s_1(N))) ;

ELSE IF $s_1(N) = '1' THEN RETURN (2**s(N)) ;

ELSE RETURN (O) ;

END V ;

S : PROCEDURE (N)

IF $s_2(\text{père}(N)) = '.' \land s_3(\text{père}(N)) = N$ THEN
    RETURN (-L(N));

ELSE IF $s_2(\text{père}(N)) = '.' \land s_1(\text{père}(N)) = N$ THEN
    RETURN (O);

ELSE IF \text{père}(N) = 'N' THEN RETURN (O);

ELSE IF N = 'B' THEN RETURN (s(\text{père}(N)));

ELSE IF $s_2(\text{père}(N)) = 'B' \land N = 'L' THEN
    RETURN (s(\text{père}(N)) + 1);

ELSE RETURN (s(\text{père}(N)));

END S ;

L : PROCEDURE (N);

IF $s_1(N) = 'B' THEN RETURN (1);

ELSE RETURN (L(s_1(N)) + 1);

END L ;

Les fonctions "père, $s_1$, $s_2$, $s_3$" sont des fonctions de traitement d'arbre incorporées au système. $s_i$ est le sélecteur d'ordre i au sens de V.D.L. [9].

Mais on voit que le paramètre N doit être un arbre ou un sous-arbre d'analyse de taille indéterminée, aux noeuds duquel se trouvent des chaines de caractères correspondant aux terminaux et aux non-terminaux. On ne peut en PL/I passer de tels paramètres que par l'intermédiaire d'un pointeur sur une liste. L'algorithme serait donc en fait légèrement différent de ce qu'il est ici.

En dehors de ces considérations, il semble que la solution du schéma récursif, qui paraissait au départ séduisante, car la construction avait lieu au niveau META, soit extrêmement lourde

- d'une part au niveau de la construction du schéma, qui semble compliquée
- d'autre part et surtout au niveau de l'exécution de ce programme d'évaluation, donc au niveau analyse, qui fait appel aux dispositifs de récursivité du compilateur utilisé, et qui utilise en plus des opérations de traitement d'arbre qui ne peuvent que ralentir l'ensemble.

### 3.3 Production d'un programme non paramétré.

La solution consistant à faire construire à l'analyseur un schéma linéaire non paramétré a un gros inconvénient : la taille du programme d'évaluation construit est proportionnelle à celle du texte source.
Considérons par exemple la grammaire G2 et supposons que le texte d'entrée soit 01.01 : l'évaluation des attributs peut se représenter comme un graphe orienté calqué sur l'arbre d'analyse :

<figure><img src="image_5.png" /></figure>
Le problème de la remise en ordre du calcul des attributs est donc
ramené au problème de déduire du graphe orienté ci-dessus une suite
partiellement ordonnée.

Un algorithme résolvant ce problème a été donné par Kahn [10] puis
amélioré par Knuth [11]. Il est assez rapide et semble convenir
parfaitement à notre problème. Appliqué à notre exemple, il donnerait
le programme d'évaluation suivant :

v₁ = 0 ;
1₂ = 1 ;
v₅ = 0 ;
1₆ = 1 ;
s₄ = 0 ;
v₂ = v₁ ;
1₄ = 1₂ + 1 ;
v₆ = v₅ ;
1₈ = 1₆ + 1 ;
s₃ = s₄ ;
s₂ = s₄ + 1 ;
s₈ = - 1₈ ;
v₃ = 2**s₃ ;
s₁ = s₂ ;
s₇ = s₈ ;
s₆ = s₈ + 1 ;
v₄ = v₃ + v₂ ;
v₇ = 2**s₇ ;
s₅ = s₆ ;
v₈ = v₇ + v₆ ;
v₉ = v₄ + v₈ ;

dont l'exécution serait très rapide, comparée à celle du programme
récursif déjà vu.
On voit en outre qu'ainsi que nous l'avions laissé entendre au § 2.2.,
une optimisation de ce programme est possible.

En effet, le graphe orienté ci-dessus contient ce que l'on pourrait
appeler des "impasses, c'est-à-dire des calculs d'attributs non utilisés
par la suite (par exemple 1(L₂), 1(L₁), s(L₂) et s(B₁)).

L'algorithme de tri dont nous avons parlé (et que Knuth qualifie de
"tri topologique") peut être légèrement modifié de façon à être chargé
de l'élimination de ces impasses.

Il va de soi que l'utilisateur disposerait de commandes de type
REDUCTIBLE - IRREDUCTIBLE dans le cas où il souhaiterait éviter la
suppression de ces calculs à cause d'effets de bord. Mais ce cas devrait
être extrêmement rare.

La modification apportée à l'algorithme de tri topologique de Knuth a pour
but d'obtenir que les différents noeuds d'une même impasse soient sortis
à la suite les uns des autres, ce qui fait qu'il est très facile, quand
on arrive au bout d'une impasse, de récupérer dans le fichier de sortie
en remontant jusqu'à la dernière fourche.

Sur l'exemple ci-dessus, l'ordre de sortie serait le suivant :

v (B₁)
v (L₂)
1 (L₂) } impasse supprimée
1 (L₁)
s (L₁)
s (L₂)
s (B₁)
s (B₂)
v (B₂)
v (L₁)
1 (L₄)
1 (L₃)
s (L₃)
s (L₄)
s (B₃)
s (B₄)
v (B₄)
v (B₃)
v (L₄)
v (L₃)
v (N)
ce qui permettrait d'obtenir un programme comprenant 6 instructions
de moins :

v₁ = 0 ;

v₅ = 0 ;

1₆ = 1 ;

s₄ = 0 ;

v₂ = v₁ ;

v₆ = v₅ ;

1₈ = 1₆ + 1 ;

s₃ = s₄ ;

s₈ = - 1₈ ;

v₃ = 2**s₃ ;

s₇ = s₈ ;

v₄ = v₃ + v₂ ;

v₇ = 2**s₇ ;

v₈ = v₇ + v₆ ;

v₉ = v₄ + v₈ ;

Il est évident que le gain dû à cette optimisation très élémentaire
peut être non négligeable pour des textes d'entrée importants.

On peut remarquer également que, de par la nature du système, le
programme d'évaluation sémantique obtenu contient beaucoup d'instructions
d'affectation de la forme "s₇ = s₈ ;" qui sont de simples transmissions
de valeurs dans l'arbre d'analyse.

Il semble relativement aisé d'incorporer à l'analyseur une procédure
d'élimination de ces règles par simple changement des numéros de non-
terminaux aux endroits où ces variables sont utilisées.
D'après nos évaluations, cela devrait aboutir à une diminution du temps d'évaluation de la sémantique du programme de l'ordre de 20 %.

### 3.4 Solution intermédiaire

A l'examen de ces différentes possibilités, nous pensons implémenter une solution intermédiaire qui consistera à transformer chaque définition d'attribut en un S/P paramétré rendant une valeur.

L'analyseur produira alors un programme d'évaluation qui se réduira à une suite d'appels à ces S/P.

La diminution de la taille du programme produit n'apparait pas sur l'exemple des nombres binaires mais s'avère très importante dès que les définitions d'attributs se compliquent.

Un gros avantage de cette méthode est que l'ensemble des sous-programmes peut être compilé dès l'étape de construction de l'analyseur. Cet analyseur peut ensuite produire la suite d'appels sous forme d'instructions écrites en binaire.

Il suffit donc ensuite d'effectuer une édition de liens entre ce binaire et la bibliothèque avant de lancer l'exécution de ce que l'on peut appeler la dernière passe du compilateur automatiquement produit.

### 4. Conclusion. Projet DELTA.

Dans un premier temps, nous avons réalisé un système produisant un programme PL/1 linéaire remis en ordre par un algorithme de tri topologique.

Cet outil nous servira pendant un certain temps à réaliser diverses implémentations automatiques destinées à nous permettre d'évaluer les besoins en primitives de base du futur langage de description sémantique. Ce langage devra certainement être de haut niveau, mais très spécialisé (déclarations implicites, compilable par morceaux etc...)

Le second axe dans lequel nous travaillons devrait permettre de produire automatiquement pour DELTA des traducteurs efficaces.
Pour cela, nous pensons permettre à l'utilisateur désirant écrire un
compilateur de générer non pas du binaire, mais des macros (triplets
ou autres). Cela lui permettrait :

- soit d'utiliser les macros standard que nous lui fournissons

- soit de redéfinir une ou plusieurs de ces macros.

Les conséquences directes de ceci sont qu'il serait facile de
greffer sur la partie expansion de macros une procédure d'optimisation
du code produit, et également que la portabilité des compilateurs
produits pourrait être assurée.

La souplesse très appréciable de la formalisation par attributs
s'accompagnerait alors de la possibilité de réaliser des outils
efficaces, ce qui a toujours été le point sur lequel ont buté les
diverses réalisations tentées jusqu'à présent.
<figure><img src="image_6.png" /><figcaption>SCHEMA RECURSIF</figcaption></figure>

MLS : Méta - langage sémantique

Limite du processeur produit automatiquement.
<figure><img src="image_7.png" /><figcaption>SCHEMA MIXTE</figcaption></figure>
SCHEMA LINEAIRE

(VERSION DE TRAVAIL ACTUELLE)

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

[1] C.C. RUSSELL
"META 5 MANUAL FOR XDS SIGMA 7
(OR CII 10070) UNDER BPM"

[2] BEKIC, WALK
"FORMALIZATION OF STORAGE PROPERTIES"
(Symposium on Semantics of algorithmic languages. 1970
Springer lecture notes Series)

[3] LUCAS, WALK
"ON THE FORMAL DESCRIPTION OF PL/1"
(Annual review in automatic programming. 1969)

[4] BROOKER, MC CALLUM, MORRIS, ROHL
"THE COMPILER-COMPILER"
(A.R.A.P. 1968)

[5] FELDMAN
"A FORMAL SEMANTICS FOR COMPUTER LANGUAGES AND ITS APPLICATION IN A
COMPILER-COMPILER"
(C.A.C.M. JV. 1966)

[6] IRONS
"A SYNTAX-DIRECTED COMPILER FOR ALGOL 60"
(C.A.C.M. JV. 1961)

[7] D.E. KNUTH
"SEMANTICS OF CONTEXT-FREE LANGUAGES"
(Mathematical Systems Theory 2. 1968)
[8] D.E. KNUTH
"EXAMPLES OF FORMAL SEMANTICS"
(Symposium on Semantics of algorithmic languages. 1970. SPRINGER VERLAG)

[9] LUCAS
"INTRODUCTION TO THE METHOD USED FOR THE FORMAL DEFINITION OF PL/!".
(Technical Report TR-25081. IBM Vienne)

[10] A.B. KAHN
(C.A.C.M 1962 pp 558-562)

[11] D.E. KNUTH
"THE ART OF COMPUTER PROGRAMMING 1"
(Addison-Wesley 1969)

[12] P. WEGNER
"THE VIENNA DEFINITION LANGUAGE"
(Computing Surveys 1972)

[13] E. BOOK et al.
"THE CWIC/360 SYSTEM"
(Sigplan notices Juin 1970)

[14] J.L. BOUCHENEZ
"DELTA : un système d'écriture automatique de traducteurs".
(Publication LABORIA à paraitre)

[15] SETHI, ULLMAN
"THE GENERATION OF OPTIMAL CODE FOR ARITHMETIC EXPRESSIONS"
(J.A.C.M., 17, 4, 1970)