RIA

laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B.P. 5 78150 - Le Chesnay
France
Tél.: 954 90 20

Inv = 02251

laboratoire de recherche
en informatique
et automatique

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

STRUCTURES DE DONNÉES
ET TRADUCTION DÈS
LANGAGES DE PROGRAMMATION

Marie - Claude DENDIEN - GAUDEL

Rapport de Recherche N° 193
Octobre 1976

39p
STRUCTURES DE DONNÉES
ET TRADUCTION DES LANGAGES DE PROGRAMMATION :
un exemple de spécification de compilateur

Marie-Claude Dendien-Gaudel

Résumé :

Ce rapport présente à l'aide d'un exemple, une méthodologie originale de spécification de compilateurs que nous voulons utiliser pour un système d'écriture de traducteurs.

L'idée est d'appliquer un même formalisme au langage source et au langage objet : on leur associe une structure de données, cela permet de spécifier ensuite, d'une manière rigoureuse et lisible, la représentation des données du langage source par des données du langage objet.

Dans les systèmes actuels d'écriture de traducteurs, cette description n'est pas explicite, il nous semble que ce serait souhaitable et qu'il s'agit d'un complément indispensable des outils syntaxiques et sémantiques actuels.

Résumé :

This report presents some ideas about programming languages definition : we want to provide some tools for the specification and production of translators. The semantics of a programming language can be formalized using an associated data structure : to specify a compiler, we suggest the use of such a formalism for both the source and the object language, together with a description of the representation of the source language data types and operations in terms of those of the object language.

In current translator writing systems, this description does not appear explicitly. However we believe that it is worthwile and provides a useful addition to the syntactic and semantic tools currently used.
# PLAN

I. Données, Structures de données.

II. Langages de programmation et structures de données.

III. Application à la spécification de traducteurs.

IV. Exemple de traducteur.

IV.1. Le langage source.

IV.2. Le langage objet.

IV.3. Représentations des piles.

V. Spécification du traducteur : partie relative au langage source.

V.1. Description de la structure de données associée au langage source.

V.2. Syntaxe, Attributs, Modèles.

V.3. Les accès.

V.4. Les calculs.

V.5. Modèles et Attributs.

VI. Spécification du traducteur : partie relative au langage objet.

VII. Partie représentation.

VII.1. Les types.

VII.2. Les accès.

VII.3. Autre exemple de représentation.

VII.4. Preuves de correction.

## Conclusion.

## Bibliographie.

## Annexe : Description complète du compilateur du paragraphe IV.
## Introduction

Dans ses travaux J.P. Finance a exposé comment définir formellement la sémantique d'un langage de programmation en lui associant une structure de données [4], [5].

Pour décrire un compilateur, nous proposons d'utiliser ce formalisme pour le langage source et pour le langage objet. On peut alors spécifier les choix d'implantation qu'on a fait en donnant la représentation des données du langage source par des données du langage objet.

On va rappeler rapidement quelques définitions relatives aux données et structures de données d'après les travaux de Pair [1] et Rémy [2]. On présentera ensuite un exemple simple de compilateur : on montre comment définir le langage source, comment définir le langage objet et comment décrire une représentation. Deux représentations sont décrites, qui correspondent à des choix d'implantation différents du même langage.

## I. Données, structures de données

On va préciser rapidement, à partir d'exemples, la terminologie employée : donnée, accès à une donnée, modification d'une donnée. Pour un exposé plus formel et plus complet on peut se reporter à [1] et [2].

### Exemple 1 :

Considérons un tableau à deux dimensions : cette donnée est un groupement de données élémentaires (par exemple des réels), mais le point important est que pour accéder à celles-ci on doit fournir deux entiers, compris entre certaines bornes $a_1, b_1$ et $a_2, b_2$.

Un tel tableau peut donc être décrit comme une fonction d'accès définie sur un sous ensemble de $N^2$: $[a_1, b_1] \times [a_2, b_2]$, à valeur dans un ensemble V, par exemple celui des réels. L'ensemble T de ces fonctions formalise la structure de données "tableau à deux dimensions d'éléments de V".

D'une manière générale une donnée est définie par un certain nombre d'ensembles d'objets élémentaires $E_1, E_2, ... E_m$ d'une part, et d'autre part, un ensemble $\Lambda$ de fonctions partielles à valeurs dans $E_j$, dont les domaines de définition sont de la forme $E_{j1} \times E_{j2} \times ... \times E_{jq}$.
Revenons à l'exemple. Un tableau de nombres réels peut être considéré comme la donnée ($E_1, E_2, \Lambda$) avec $E_1 = R$,
$E_2 = [a_1, b_1] \times [a_2, b_2]$ et $\Lambda = \{t : E_2 \to E_1, E_2\}$

On appelle les éléments de $\Lambda$ des accès.

Dans un premier temps nous considérons qu'une structure de données est un ensemble de données ayant même entier m, et des ensembles $\Lambda$ "semblables" : intuitivement, si $(E'_1, ..., E'_m, \Lambda')$ et $(E''_1, ..., E''_m, \Lambda'')$ sont deux telles données, à toute fonction $f' : E'_{j_1}, ..., E'_{j_q} \to E'_j$ de $\Lambda'$ correspond une fonction $f'' : E''_{j_1}, ..., E''_{j_q} \to E''_j$ de $\Lambda''$ qui possède les mêmes propriétés (si $f'$ est bijective, $f''$ l'est, etc...). On a besoin pour exprimer ceci correctement d'un formalisme basé sur la logique qu'il n'est pas utile de présenter ici mais qui est exposé dans [2].

**Exemple 2 :**

Envisageons la donnée correspondant aux déclarations suivantes
(ALGOL 68) :

réel x = 3.2 ; complexe z = (x,4.1) ; réel y := im de z ;
où le signe '=' indique une identité et le signe ':=' une affectation à
une variable. Cette donnée peut se schématiser par la figure 1, où
possède, repère, re et im sont des accès.

<figure><img src="image_2.png" /><figcaption>Figure 1.</figcaption></figure>
Dans ce schéma apparaissent trois accès o-aires : les identificateurs x, y, z ; à partir de l'identificateur x, l'accès "possède" rend un réel, car x est apparu dans une déclaration d'identité ; à partir de y, "possède" donne accès à un nom, car y est apparu dans une affectation. A partir de ce nom on "repère" un réel.

En partant de cet exemple, on peut ébaucher une structure de données associée à ALGOL 68 ; parmi les ensembles on aurait :

I(les Identificateurs), N(les Noms), C(les Complexes), R(les Réels) et parmi les fonctions d'accès :

les éléments de I( accès o-aires ), possède, repère, re et im.

Ces accès peuvent se composer, au sens classique de la composition de fonction, mais aussi, dans ce cas, de manière collatérale ou conditionnelle.

Pour compléter la définition d'une structure de données nous introduisons maintenant la notion de modification. Grossièrement parlant, une modification est un traitement qui modifie une information en conservant sa structure : par exemple, dans le cas des tableaux à deux dimensions, la modification de la valeur d'un élément, et pour l'exemple 2, l'affectation d'une nouvelle valeur à une variable...

Plus formellement, une modification est une opération sur les données de la structure.

Une structure de données est complètement définie par des ensembles, des accès, des modifications.

En général, les modifications élémentaires d'une structure consistent à modifier un accès en changeant sa valeur en un point. On a donc deux sortes d'accès : les accès non modifiables, qui correspondent à des opérations (au sens classique de l'algèbre) sur des données de la structure, et les accès modifiables.

Les modifications peuvent se composer de manière séquentielle : on appelle calcul de la structure de données une telle suite de modifications.

On peut aussi, comme dans les langages de programmation, composer les modifications de manière conditionnelle, itérative, collatérale ; remarquons qu'une telle composition définit, en fait, un ensemble de calculs de la structure.
## II. Langages de programmation et structures de données

Dans l'exemple 2 nous avons présenté une structure de données en utilisant la terminologie de la définition d'ALGOL 68 [3] et nous avons donné la signification, dans cette structure, d'une partie de programme. On trouvera dans les travaux de J.P. Finance [4, 5] une étude de la séman-tique d'ALGOL 68 qui utilise cette formalisation.

On peut reprendre cette démarche pour tout langage de programmation et lui associer une structure de données : les types d'objets du langage correspondent à des ensembles $E_i$ de la structure (qui peut en comporter d'autres), les opérations et les sélections (éléments d'un tableau, champs d'une structure), à des accès, les instructions à des calculs. Un programme du langage définit un ensemble de calculs possibles dans la structure de données ; à une exécution du programme correspond un de ces calculs.

Dans ce cadre, la signification d'une phrase du langage est un ensemble de calculs (que l'on peut décrire sous forme de modifications composées) et un accès (ou un ensemble d'accès) [5] : cela correspond au cas du calcul d'une valeur avec des effets de bord. Dans les cas courants, à une expression correspond un accès, à une déclaration correspond la définition d'un nouvel accès o-aire de la structure, à une instruction une modification ou une composition de modifications.

## III. Application à la spécification de traducteurs

Dans notre méthode de description de traducteurs la définition d'un langage source se compose d'une description syntaxique et de la spécification pour chaque phrase de sa signification dans la structure de données. La syntaxe (y compris les contraintes contextuelles) est donnée par une des méthodes existantes : double-grammaire [3], [12], grammaire affixe [10], grammaire à attributs [11], [8]...

C'est cette dernière solution qui est retenue pour l'instant parce qu'elle paraît la plus commode et aussi parce que nous disposons à l'IRIA de moyens de traitement pour ces grammaires, le système DELTA [8] : une première application sera l'extension de DELTA. Mais quelle que soit la description syntaxique utilisée, le principe est d'associer à chaque règle de grammaire un modèle : ce modèle donne la signification, dans la structure de données, de la partie gauche de la règle, en fonction de la partie droite. Il s'agit
en fait d'une description des ensembles de calculs et des ensembles d'accès pouvant correspondre au composant syntaxique défini.

Exemple 3 :

Considérons la règle de grammaire :

<affectation> ::= <variable> ::= <expression>

Si on se place dans la structure de données définie pour l'exemple 2 du paragraphe précédent, le modèle associé à cette règle sera le modèle de modification :

rep(<variable>) = <expression>

où <variable> et <expression> désignent les modèles associés à ces non-terminaux ; ce sont respectivement un modèle d'accès à un nom et un modèle d'accès à une valeur.

On définit également le langage objet en lui associant une structure de données ; mais on a le problème inverse, puisqu'on veut passer des calculs dans la structure à du code objet : on spécifie donc le code associé aux modifications et aux compositions de modifications.

Enfin, on établit la correspondance entre données des deux structures dans une partie représentation.

La spécification d'un traducteur comporte donc :

- la définition du langage source avec, d'une part, la description de la structure de données "source", d'autre part la syntaxe accompagnée de définitions d'attributs et de modèles.

- la définition du langage objet avec la description de la structure de données "objet" et de la correspondance entre calculs de cette structure et code objet.

- la description de la représentation des données de la structure source par des données de la structure objet.

Cette dernière partie est essentielle car c'est là qu'on établit la correspondance entre les deux langages et que l'on précise les choix qu'on prend pour la traduction. On retrouve là une démarche fréquente de l'informatique en particulier de la programmation structurée : on décrit la représentation d'objets de certains types par des objets d'autres types en donnant des règles de correspondance [6], [7].
La figure 2 schématise notre méthode :

<figure><img src="image_3.png" /><figcaption>Figure 2.</figcaption></figure>

La première ligne exprime la démarche suivie pour concevoir le traducteur : on déduit des langages source et objet des structures de données, et on donne des règles de représentation entre données de ces structures. Cela permet de produire un traducteur en trois étapes qui agit sur un programme source comme l'indique la seconde ligne de la figure. Toutes ces notions vont être précisées à l'aide d'un exemple de traducteur : on présente dans le paragraphe IV un langage source, un langage objet et deux choix d'implantation possibles. On expose ensuite comment spécifier formellement ces deux traducteurs.

## IV. Exemple de traducteur

### IV.1. Le langage source

Le langage source est un langage où on peut déclarer et manipuler des piles d'entiers et dont la syntaxe est :

*   `<P> ::= <LD> ; <LI> .`
*   `<LD> ::= <LD> ; <D> | <D>`
*   `<D> ::= entier ID | pile ID`
*   `<LI> ::= <LI> ; <I> | <I>`
*   `<I> ::= ID ::= <E> | emp(ID, <E>) | dep(ID)`
*   `<E> ::= <E> <OP> <T> | <T>`
*   `<T> ::= (<E>) | ID | ENT | sommet(ID)`
*   `<OP> ::= + | - | x | /`
Exemple de programme :

entier x ; pile y ;
x := 6 ; emp (y,x) ;
x := sommet (y) * 2 ; ...

IV.2. Le langage objet

Le langage objet est un langage symbolique ; on travaille avec
deux registres R et L : L peut être utilisé pour faire de l'adressage
indirect ou de l'indexation. Parmi les instructions, on a :

On génère des adresses relatives ou des libellés de constantes hexadécimales.

IV.3. Représentation des piles

On traitera deux types de représentation : on choisit d'abord de
représenter chaque pile par une zone contigüe de 256 mots d'une part, et un
mot qui contient le nombre d'éléments dans la pile, d'autre part. Ce mot
est initialisé à 0. On s'arrête, avec sortie d'un diagnostic d'erreur, en
cas de débordement par le haut ou par le bas, ou en cas d'accès au sommet
d'une pile vide.
**Exemple :** configuration de la mémoire correspondant au programme précédent

<figure><img src="image_4.png" /><figcaption>Figure 3.</figcaption></figure>

L'allocation mémoire est donc tout à fait statique. On verra ensuite le cas où les piles sont représentées par des listes chaînées de blocs de deux mots. A chaque pile est associé statiquement un mot de mémoire qui contient l'adresse du sommet. Si la pile est vide, le contenu de ce mot est *nil* et l'appel des opérations *sommet* et *dep* du langage source provoque une erreur. L'adresse de début de la liste *vide* est contenu dans le mot d'adresse relative 0.

**Exemple :**

<figure><img src="image_5.png" /><figcaption>Figure 4.</figcaption></figure>

## V. Spécification du traducteur : partie relative au langage source

On a vu que la spécification d'un traducteur se compose de trois parties : une définition du langage source, une définition du langage objet, une partie représentation.

La partie relative au langage source comporte une description de la structure de données qui lui est associée et la syntaxe du langage où chaque règle est accompagnée de définitions d'attributs et d'un modèle.
## V.1. Description de la structure de données associée au langage source

Une structure de données est caractérisée par un certain nombre d'ensembles, de fonctions d'accès de certains de ces ensembles dans un autre, de modifications qui font passer d'une donnée de la structure à une autre.

Dans le cas des langages de programmation, les ensembles sont habituellement appelés *types*. On décrit une structure de données sous la forme d'une suite de déclarations de types et d'accès. Pour chaque accès on précise son "profil", c'est-à-dire les types de départ et le type d'arrivée. On indique les modifications admises en distinguant les accès modifiables : leur déclaration est suivie du symbole *mod* ; cela signifie que la modification "changer la valeur de l'accès en un point" est une modification de la structure.

Pour l'exemple 2 du paragraphe 1, (ALGOL 68) la fonction d'accès repère serait déclarée :

`_accès_ (nom) réel repère _mod_ ;`

Une structure de données possible pour le langage source du paragraphe précédent est décrite ci-dessous. On trouvera en [13] une autre structure possible pour le même langage.

`_type_ entier, pile ;`

`_accès_ (pile, entier) pile ajout ;`

`_accès_ (pile) pile suppr ;`

`_accès_ (pile) entier sommet ;`

`_accès_ (entier, entier) entier add, sous, mult, div ;`

Nous appelons la structure de données associée au langage source la "structure source".

On déclare que les objets manipulés sont des entiers ou des piles ; les accès déclarés correspondent aux opérations "ajouter un entier à une pile", "supprimer le sommet d'une pile", "accéder au sommet d'une pile", additionner, soustraire, multiplier et diviser des entiers ; on ne déclare pas ici d'accès modifiables, mais on en définira dans la suite de la description du langage.
## V.2. Syntaxe, Attributs, Modèles

La syntaxe du langage est donnée en B.N.F. Pour chaque règle, on peut donner des définitions d'attributs et un modèle.

Rappelons que le modèle associé à une règle indique quels calculs et quels accès peuvent, en fonction du contexte, correspondre au non-terminal en partie gauche. C'est le plus souvent une composition des modèles des non-terminaux de la partie droite, ce qu'on note en faisant apparaître les noms de ces non-terminaux, entre chevrons, dans le modèle (cf exemple 3 au § III.).

Le rôle des attributs est double : ils permettent de vérifier que les contraintes contextuelles (déclaration des identificateurs, par exemple) sont respectées ; ils permettent de paramétrer et de conditionner le modèle. Dans ce rapport les déclarations et les définitions d'attributs sont écrites en PASCAL [9] légèrement étendu (les fonctions procédures peuvent rendre un résultat de type quelconque).

Nous allons maintenant préciser ce qu'est un modèle : un modèle permet de décrire les ensembles de calculs et d'accès de la structure source qui formalisent la signification d'une certaine phrase. Les notations que nous utilisons pour les accès, les calculs et les ensembles de calculs d'une structure de données sont présentées dans les paragraphes suivants.

## V.3. Les accès

Les accès décrits par les modèles sont des accès o-aires de la structure source ; on peut avoir :

- une constante d'un type de la structure

- un accès o-aire précédemment défini

- un accès composé par composition de fonctions

- un ensemble d'accès défini par composition conditionnelle ou collatérale des précédents.

### V.3.1. Les constantes

Les constantes d'un type sont entre guillements et précédées de leur type. Par exemple :

entier '6'

pile 'vide'

Cela permet de ne pas alourdir la définition de la structure de données par une syntaxe des constantes des différents types. La chaîne de caractères
entre guillements est prise en compte et convertie à l'étape suivante de traduction, lorsqu'on veut obtenir des calculs de la structure objet.

### V.3.2. Définitions d'accès o-aires

Un accès o-aire peut avoir été déclaré au moment de la spécification de la structure source (V.1.). Mais on peut aussi considérer que la signification d'une déclaration d'un programme source est la définition d'un tel accès.

Par exemple, à la déclaration

entier x

correspond dans la structure source :

Définir accès entier x mod

De même à la déclaration

pile y

correspond la définition

Définir accès pile y mod

On trouvera en [13] une spécification du même langage où les déclarations sont considérées d'une manière différente.

### V.3.3. Accès composés

La composition des accès se note comme la composition des fonctions classiques.

Par exemple à l'expression du langage source

sommet (y) * 2

correspond l'accès composé

mult(sommet(y), entier '2')

### V.3.4. Compositions conditionnelle et collatérale

La composition conditionnelle se note

(ac1 | ac2 | ac3 | ac4)

Si les résultats de ac1 et ac2 sont égaux on effectuera l'accès ac3, sinon ac4.

La composition collatérale se note

(ac₁, ac₂, ..., acₚ)

et le résultat est un p-uple d'objets.
## V.4. Les calculs

Une modification de l'accès f au point $a_1$ se note

$$f(a1) = a2$$

où $a1$ et $a2$ sont des accès composés ou non.

Si f est un accès o-aire modifiable, on a :

$$f = a_2$$

Par exemple, à l'instruction

`emp(y,x)`

correspond la modification

$$y = ajout(y,x)$$

La composition séquentielle de modifications ou de calculs est indiquée par un ; . Le programme donné en exemple au § IV.1 a pour signification le calcul :

`Définir accès entier x mod ;`

`Définir accès pile y mod ;`

$x = entier '6' ; y = ajout(y,x) ;$

$x = mult(sommet(y), entier '2') ; ...$

Pour des langages faisant intervenir des structures de contrôle plus compliquées que la simple composition séquentielle, la signification d'une phrase pourra être un ensemble de calculs obtenu par composition conditionnelle, collaterale ou iterative de calculs.

La composition conditionnelle se note :

$(ac_1 | ac_2 | calc_1 | calc_2)$

La composition collatérale :

$(calc_1, ..., calc_p)$

et la composition itérative :

$(ac_1 || ac_2 \text{ itérer calc})$

## V.5. Modèles et attributs

Le modèle associé à une règle de grammaire permet de décrire la signification, en terme de structure de données, du non-terminal défini par la règle.

Cette signification est fonction de celle des composants syntaxiques de la phrase, et du contexte de celle-ci ; ce contexte est exprimé sous forme d'attributs [11] associés aux non-terminaux intervenant dans la règle.
Cette dépendance a pour conséquence que ces composants syntaxiques et ces attributs pourront apparaître dans le texte du modèle ; de plus un modèle peut être conditionné par la valeur d'un attribut.

Comme exemple, considérons le modèle associé aux expressions du langage source décrit en IV.1. :

<E> ::= <E> <OP> <T>

**Modèle**

Case signe (<OP>) of
'+' : add (<E>, <T>) ;
'-' : sous (<E>, <T>) ;
'*' : mult (<E>, <T>) ;
'/' : div (<E>, <T>) ;

end

où signe (<OP>) est un attribut chaîne de caractères dont la valeur dépend du signe en opérateur : en fonction de cette valeur on choisira l'un des quatre modèles possibles pour l'expression.

A partir des modèles, on va obtenir un texte intermédiaire décrivant les calculs de la Structure Source qui correspondent à un programme. Ce texte est en fait un attribut synthétisé de tous les non-terminaux de la grammaire, et il peut être aisément construit en utilisant DELTA.

On trouvera en annexe la spécification complète du traducteur, et en particulier la définition du langage source suivant les principes que nous venons de développer.

## VI. Spécification du traducteur : partie relative au langage objet

On associe également une structure de données au langage objet. On donne ensuite, pour chaque calcul de la structure le code correspondant.

On manipule dans ce langage des adresses, des registres et des valeurs ; à partir des adresses et des registres on peut accéder à un contenu qui peut être une adresse ou une valeur. Ce contenu est modifiable. D'autre part, on a les opérations courantes sur les valeurs. On peut donc associer à ce langage la structure de données suivante (les notations sont les mêmes que pour le langage source) :
type adresse, registre, valeur ;

type contenu = union (adresse, valeur) ;

accès (adresse) contenu cm mod ;

accès (registre) contenu c mod ;

accès (adresse, valeur) adresse index ;

accès (valeur, valeur) valeur plus, moins, mult, div ;

Figure 6.

Les accès c et cm donnent respectivement accès au contenu d'un registre et
au contenu du mot dont on donne l'adresse.

L'accès index permet de rendre compte de l'indexation dans les instructions
LRL et STRL.

Les modifications élémentaires possibles sont celles des accès cm et c : on
va préciser leur code en fonction de l'opérande en partie gauche et de l'accès
en partie droite. C'est ce qui est fait dans la partie II.1. de l'annexe.

D'autre part, pour les différents modes de composition des modifications on
donne les règles correspondantes de composition de leurs codes.

VII. La partie représentation

C'est la partie essentielle du traducteur puisque c'est là
que l'on décrit la représentation des données de la structure source par des
données de la structure objet. On va donc préciser tous les choix d'implan-
tation et ceci d'une manière très modulaire : pour chaque type de la struc-
ture source, on indique par quels objets de la structure objet est représenté
un objet de ce type ; pour chaque accès on donne les accès qui le représentent.

Cette partie représentation est donc une suite de rubriques relatives à
chaque type et accès déclaré dans le prologue du langage source : on a ainsi
les éléments pour passer de calculs et d'accès de la structure source à des
calculs et des accès de la structure objet.
Reprenons l'exemple de programme source donné au § IV :

entier x ; pile stack ;

x = 6 ; emp (stack, x) ;

x = sommet (stack) * 2 ;

Si on choisit le premier type de représentation proposé au § IV.3. (fig. 3)
la variable x est représentée par le contenu du mot d'adresse 0, la pile y
par un contenu de mot qui indique son niveau (et doit être initialisée à 0)
et par une zone qui commence à l'adresse 2. La définition de y dans la struc-
ture source devient, dans la structure objet la modification :

cm(adresse'1') = valeur '0'

L'affectation x := 6 devient

cm(adresse'0') = valeur '6' etc...

Nous allons voir comment spécifier ces correspondances.

VII.1. <u>Les types</u>

La rubrique associée à un type commence par la déclaration d'objets
de la structure objet. Ces déclarations indiquent d'une part par quels
types d'objets est représenté un objet du type et d'autre part, comment
désigner dans la suite les composants de la représentation ; par exemple :

Type entier ;

Type pile ;

valeur v ;

valeur niv ; adresse adz

...

...

ftype

ftype

Dans la suite de la rubrique on donne la représentation des constantes s'il
y en a ; il s'agit souvent d'appel à des sous-programmes de conversion :

v de entier 'I' : valeur 'CONVERTIR(I)'

CONVERTIR est un sous-programme de traduction dont la donnée est une chaîne I
et le résultat la chaîne de caractères obtenue en convertissant I, en
hexadécimal par exemple. On spécifie ensuite la représentation des définitions
d'accès o-aires du type envisagé et la représentation de ces accès o-aires :
une définition peut correspondre dans la structure objet à une ou plusieurs
définitions, des modifications ou ... rien si l'accès défini est représenté
par un accès constant de la structure objet : c'est le cas ici pour les accès
o-aires à des entiers ; l'allocation de mémoire est statique, on leur associe
donc une constante adresse.
Exemples :

Type entier ;

valeur v ;

v de entier 'I' → valeur 'CONVERTIR(I)' ;

Définir accès entier ID mod :

v de ID → cm(adresse 'ALLOUER(1)') ;

ftype

(ALLOUER est un sous-programme de "conversion" d'identificateur en une constante adresse : il permet d'effectuer l'allocation).

Type pile ;

valeur niv ; adresse adz ;

Définir accès pile P mod :

NP = ALLOUER(1);

cm(adresse 'NP') = valeur 'O' ; <commentaire initialisation de la variable ;

niv de P → cm(adresse 'NP') ;

adr de P → adresse 'ALLOUER(256)' ; <commentaire représentation de la variable ;

Le cas d'une allocation dynamique est donné en VI.3. Ces rubriques permettent d'établir pour le programme exemple que l'accès x à un entier sera représenté par l'accès `cm(adresse 'O')` à une valeur, que l'accès y à une pile sera représenté par les accès `cm(adresse '1')` et `adresse '2'`.

## VII.2. Les accès

Un accès de la structure source donne un résultat d'un "type source". Ce type source est représenté par un ou plusieurs composants de "type objet". Pour chaque composant, on donne l'"accès objet" correspondant. Cet accès est donc fonction, naturellement, de la représentation des opérandes de l'accès source qu'on décrit.

Un premier exemple simple est l'accès "sommet". C'est un accès à un entier, donc il sera représenté par un accès à une valeur :

v de sommet (p) → cm(index(adr de p, moins(niv de p, valeur '1')))
Si on veut tester le cas de la pile vide, on a une composition conditionnelle d'accès. On note (cf V.3.5.) (a | b | c | d) l'accès égal à c si les accès a et b donnent le même résultat, à d sinon. On a alors :

```pascal
v de sommet(p) : (niv de p | valeur '0' |
                  stoperreur (pile vide) ; nil |
                  cm(index(adz de p, moins(niv de p, valeur '1'))))

De même la rubrique pour l'accès "ajout" sera :

accès (pile, entier) pile ajout ;

niv de ajout(p,i) :
    (niv de p | valeur '100' |
     stoperreur (débordement) ; nil |
     cm(index(adz de p, niv de p)) = v de i ; plus(niv de p,
                                                valeur '1')))

adz de ajout(p,i) : adz de p ;

faccès
```

Cette description de la représentation associe au programme exemple la signification suivante dans la structure objet :

```pascal
cm(adresse'1') = valeur '0' ;
cm(adresse'0') = valeur '6' ;

( cm(adresse'1') | valeur '100' |
  stoperreur (débordement) ; cm(adresse'1') = nil |
  cm(index(adresse'2', cm(adresse'1'))) = cm(adresse'0') ;
  cm(adresse'1') = plus (cm(adresse'1'), valeur'1'))
;...
```

La partie représentation complète, dans le cas des piles représentées de manière contigue, est donnée en Annexe.

### VII.3. Autre exemple de représentation

Si on choisit d'implanter les piles de manière chaînée, comme prévu au § IV (fig. 4) seule la partie représentation du traducteur est modifiée ; on n'y change d'ailleurs que les rubriques relatives au type pile et aux accès où interviennent des piles ; une pile est représentée par l'adresse de son sommet ; cette adresse est contenue dans un mot d'adresse fixe ; le contenu de ce mot est initialisé à nil au moment d'une définition :
Type pile ;

adresse adp ;

Définir accès pile P mod :

A = ALLOUER(1) ;

cm(adresse'A') = adresse 'nil' ;

adp de P : cm(adresse'A')

ftype

L'accès ajout supprime le bloc de tête de la liste libre et rend l'adresse
de celui-ci dans le registre 1. Ce bloc contiendra la valeur à ajouter et
sera chaîné aux éléments précédents de la pile :

accès (pile,entier) pile ajout ;

adp de ajout (p,i) →

(c(registre'l') = cm(adresse'0') ;

cm(adresse'0') = cm(index(cm(adresse'0'), valeur'1')) ;

commentaire : on vient de retirer un bloc à la liste libre ;

cm(c(registre'l')) = v de i ;

cm(index(c(registre'l'), valeur'1')) = adp de p ;

commentaire : ce bloc contient le nouvel élément et est
chaîné aux éléments précédents ;

c(registre'l'))

faccès

On pourra comparer les deux parties "représentation" qui sont données dans
l'annexe. On peut remarquer qu'une modification dans la représentation des
données ne remet absolument pas en cause les parties de spécification du
langage source et du langage objet.

Le calcul de la structure objet correspondant au programme exemple est,
dans ce dernier cas :

cm(adresse'2') = adresse'nil' ;

cm(adresse'1') = valeur'6' ;

(c(registre'l') = cm(adresse'0') ;

cm(adresse'0') = cm(index(cm(adresse'0'), valeur'1')) ;

cm(c(registre'l')) = cm(adresse'1')

cm(index(c(registre'l'), valeur'1') = cm(adresse'2') ;

cm(adresse'2') = c(registre'l')) ; ...
En appliquant les règles de génération de code
(cf § VI et Annexe) à ce calcul, on obtient le code correspondant :

LR(=FFFF)
STR(DEB+2)
LR(=6)
STR(DEB+1)
LL(DEB)
STL(DEB+3)
LL(DEB)
LRL(1)
LL(DEB+3)
STR(DEB+1)
STRL(0) ... etc...

### VII.4. Preuves de correction

Une structure de données n'est complètement définie que si on
tient compte des propriétés des fonctions d'accès (bijection, identité, etc...).

Il est commode d'exprimer ces propriétés sous forme d'axiomes et par consé-
quent, de se placer, pour les étudier, dans le cadre de la logique [2].

Par exemple, parmi les axiomes caractérisant les piles on a (en utilisant les
notations de la structure source) :

sommet (ajout(p,i)) = i Vi, Vp

suppr(ajout(p,i)) = p Vp, Vi

Dans notre cas il est important de vérifier que les axiomes de la structure
source restent valables dans la structure objet, c'est-à-dire qu'ils sont
conservés par la représentation choisie. On aura ainsi fait la preuve de la
correction des choix d'implantation.

En exemple, nous allons montrer que

v de sommet (ajout(p,i)) = v de i

dans le cas de la représentation chaînée, si la liste libre n'est pas vide.

Nous avons choisi cet exemple car il est simple et ne fait pas intervenir
les axiomes relatifs aux valeurs de la structure objet.

D'après notre représentation, on a

v de sommet (ajout(p,i)) :
(adp de ajout(p,i) | adresse'nil' |
stoperreur (accès à une pile vide) ; nil |
cm(adp de ajout(p,i)))
Or on a :

```pascal
adp de ajout(p,i) :
  (c(registre'l') = cm(adresse'0') ;
   cm(adresse'0') = cm(index(cm(adresse'0'), valeur'l')) ;
   cm(c(registre'l')) = v de i ;
   cm(index(c(registre'l'), valeur'l')) = adp de p ;
   c(registre'l'))
```

ce qui donne pour v de sommet(ajout(p,i))
```pascal
c(registre'l') = cm(adresse'0') ;
cm(adresse'0') = cm(index(cm(adresse'0'),valeur'l')) ;
cm(c(registre'l')) = v de i ;
cm(index(c(registre'l'), valeur'l')) = adp de p ;
(c(registre'l') | adresse'nil' |
  stoperreur('accès à une pile vide) ; nil |
  cm(c(registre'l')))
```

On voit que si `cm(adresse'0')` est différent de adresse 'nil' (c'est-à-dire que la liste libre n'est pas vide) sommet(ajout(p,i)) est représenté par `cm(c(registre'l'))` qui est égal à v de i (d'après la 3è modification). Ceci n'est vrai que si les élaborations de v de i et `adp de p` ne modifient pas le registre 1 : dans notre exemple, le seul accès qui modifie le registre 1 est `adp de ajout(p,i)`, et les caractéristiques du langage source permettent d'affirmer qu'on ne le compose jamais avec lui-même.

Ces vérifications sont une des conséquences les plus intéressantes de notre méthode de spécification puisqu'il s'agit à la fois d'un outil d'aide à la mise au point lors de la spécification du traducteur et d'une preuve (partielle) de correction de celui-ci.
## Conclusion

Dans ce rapport, nous avons essayé, à partir d'un exemple simple, de montrer les caractéristiques essentielles de notre approche des problèmes de traduction des langages de programmation.

Dans le cas des langages sources réels, la structure de données source sera plus complexe : on pourra avoir un nombre infini de types (par exemple les tableaux à i dimensions) et donc d'accès. D'autre part il parait commode d'introduire des types, accès, modifications standards : la modification d'arrêt *stoperrreur* en est un exemple. Ce n'est pas indispensable, car il est possible de décrire complètement un langage de programmation par une structure de données ([4], [5]) à condition d'avoir le texte source parmi les objets de la structure (ceci pour rendre compte des procédures et des branchements). Cependant, dans le cadre d'un système d'écriture de traducteurs, il parait préférable de fournir un certain nombre d'éléments standards, communs à toutes les structures sources : on se base sur le fait que les instructions de contrôle (branchement, itérations, appels de procédures) sont à peu près communes à tous les langages de programmation ; seuls différent les détails syntaxiques et les types de données manipulées. L'utilisateur précise donc ces types ainsi que les accès correspondants et dans les modèles il établit une relation entre la syntaxe et les modes de composition de calculs standards : rappelons qu'on peut composer des définitions et des modifications de manière séquentielle, collatérale, conditionnelle, itérative. Les types standards sont les étiquettes et les procédures. Les modifications standards sont le branchement, l'arrêt (sur erreur ou non), l'appel de procédure.

Une définition d'ALGOL 60 selon ces principes a montré que, pour ce langage, ces éléments conviennent. Il reste à tenter l'expérience sur d'autres langages : PL1, PASCAL, LISP,...

On peut cependant d'ores et déjà remarquer que la méthode présentée permet de dissocier les aspects liés au langage source des aspects liés au langage objet, les relations entre ces deux langages étant décrites par une partie indépendante ou l'implanteur définit ses choix de mise en oeuvre.
De plus, dans la définition du langage source les différents niveaux sont nettement séparés : données traitées, syntaxe à contexte libre, contraintes contextuelles, signification des phrases.

Ces différents découpages, qui correspondent à des modules fonctionnels de traduction, doivent permettre de faciliter la conception et l'écriture des traducteurs, et, par conséquent, d'améliorer leur architecture et leur fiabilité.
# Description du traducteur présenté au paragraphe IV

## I. Description du langage source

### I.1. Prologue : définition de la structure source

type entier, pile ;

accès (pile, entier) pile ajout ;

accès (pile) entier sommet ;

accès (pile) pile suppr ;

accès (entier, entier) entier add, sous, mult, div ;

### I.2. Déclarations des attributs

Le langage utilisé ici est PASCAL ; les attributs sont déclarés comme des variables avec en commentaire, s'ils sont hérités ou synthétisés, à quels non-terminaux ils sont attachés, quelle est leur signification.

type genre = (scalaire, pile) ;

item = record id : string ; g : genre end ;

table = array [1::100] of item ;

var decl : item ; synthétisé, <D> , a pour valeur l'identificateur et le genre de la variable déclarée.

tdecl : table ; synthétisé, <LD> , table des variables déclarées dans la liste de déclaration.

correct : boolean ; synthétisé, <LD> , indique si la liste comporte des double déclarations.

tds : table ; hérité, (<LI>,<I>,<E>,<T>), table des variables utilisables.

signe : char ; synthétisé, <OP> , a pour valeur le signe (+,-,x,/)
en opérateur .

function presence(i : item ; t : table) : boolean ;

cette fonction teste si une variable est dans la table.

function testident(id : string ; t : talbe) : boolean ;

cette fonction teste si un identificateur est dans la table.

function citem(id : string ; g : genre) : item ;

cette fonction construit une valeur de type item à partir de ses composants.
function inittable(i : item) : table ;

Cette fonction construit une table qui contient uniquement l'item i.

function ajouter(i : item, t : table) : table ;

Cette fonction ajoute i à la table t.

I.3. Syntaxe avec Attributs et Modèles

Chaque définition d'attribut ou de modèle commence par le signe #.

On trouve à la ligne suivante la valeur de l'attribut ou du modèle (éventuellement
suivie d'un commentaire) sauf dans le cas d'une identité entre attributs.

<P> ::= <LD> ; <LI>.

*tds(<LI>) = tdecl(<LD>)

comment la table des variables utilisables dans <LI> est la table des variables déclarées dans <LD> ;

#modèle

<LD> ::= <LD> ; <LI>

comment on exécute séquentiellement les calculs (définitions) de <LD> et de <LI> ;

<LD> ::= <LD> ; <D>

#correct(<LD>)

not testident(decl(<D>).id, tdecl(<LD'>))

comment : <LD> est correcte si l'identificateur déclaré en <D> n'est pas déjà défini;

#tdecl(<LD>)

if correct(<LD>)

then ajouter(decl(<D>), tdecl(<LD'>))

else begin write('double déclaration') ; tdecl(<LD'>) end

comment on ajoute la nouvelle variable à la table des déclarations, mais seulement
si <LD> est correct ;

#modèle

if correct(<LD>)

then <LD'> ; <D>

else <LD'>

comment <D> est ignoré en cas de double déclaration ;
<LD> ::= <D>
#correct(<LD>)
    true
#tdecl(<LD>)
    initable(decl(<D>))
    comment la variable déclarée est mise en table ;
#modèle
    <D>          comment la signification de <LD> est identique à celle de <D> ;

<D> ::= entier ID
#decl(<D>)
    citem('ID', scalaire)
    comment on construit l'item correspondant à la variable ;
#modèle
    Définir accès entier ID mod

<D> ::= pile ID
#decl(<D>)
    citem('ID', pile)
#modèle
    Définir accès pile ID mod

<LI> ::= <LI>; <I>
#tds(<LI'>) = tds(<LI>)
#tds(<I>) = tds(<LI>)
    comment on hérite partout la table des valeurs ;
#modèle
    <LI>; <I>

<LI> ::= <I>
#tds(<I>) = tds(<LI>)
#modèle
    <I>
<I> ::= ID ::= <E>

#tds(<E>) = tds(<I>)

# modèle

if présence(citem('ID', scalaire), tds(<I>))

then ID = <E>

else erreur ('affectation à un identificateur incorrect')

comment le modèle est une erreur si la variable n'est pas déclarée ;

<I> ::= emp(ID, <E>)

#tds(<E>) = tds(<I>)

# modèle

if présence(citem('ID', pile), tds(<I>))

then ID = ajout(ID, <E>)

else erreur ('opérande incorrect dans empiler')

<I> ::= dep(ID)

# modèle

if présence(citem('ID', pile), tds(<I>))

then ID = suppr(ID)

else erreur('opérande incorrect à dépiler')

<E> ::= <E> <OP> <T>

#tds(<E'>) = tds(<E>)

#tds(<T>) = tds(<E>)

# modèle

case signe(<OP>) of
'+' : add(<E>, <T>) ;
'-' : sous(<E>, <T>) ;
'x' : mult(<E>, <T>) ;
'/' : div(<E>, <T>) ;
end

<E> ::= <T>

#tds(<T>) = tds(<E>)

# modèle

<T>
<T> ::= (<E>)
tds (<E>) = tds (<T>)

**modèle**

<E>

<T> ::= ID

**modèle**

if présence(citem('ID', scalaire), tds(<T>))
then ID
else erreur('identificateur incorrect dans une expression')

<T> ::= ENT

**modèle**

entier 'ENT'

comment l'accès est une constante entière, on en conserve le texte ;

<T> ::= sommet(ID)

**modèle**

if présence(citem('ID', pile), tds(<T>))
then sommet(ID)
else erreur('opérande de sommet incorrect')

## II. Description du langage objet

### II.1. Prologue : définition de la structure objet

type adresse, registre, valeur ;

type contenu = union (adresse, valeur) ;

accès (adresse) contenu cm mod ;

accès (registre) contenu c mod ;

accès (adresse, valeur) adressse index ;

accès (valeur, valeur) valeur plus, moins, mult, div ;
## II.2. Code associé aux modifications élémentaires

La première modification envisagée est celle de l'accès c. Elle est de la
forme :

c(<registre>) = <contenu>

D'après le prologue, un registre ne peut être qu'une "constante de type registre",
c'est-à-dire : registre 'r' ou registre 'l'. On teste ces deux cas ; pour chacun
la partie droite peut être, d'après le prologue : une constante adresse, une
constante valeur, le résultat d'un accès cm, le résultat d'un accès c, le résultat
d'une des quatre opérations ; c'est ce qui est testé dans la première instruction
cas.

Les identificateurs commençant par # sont des métavariables ou des méta-sous-programmes qui permettent de gérer les registres et les résultats intermédiaires, de générer des étiquettes, etc...

a) Modification de l'accès c :

Code (c(<registre>) = <contenu>) =
Si <registre> = registre'r'
Alors Cas<contenu> =
adresse'<const>' : LR(=<const>) .
valeur'<const>' : LR(=<const>) .
cm(<ad>) : Cas <ad> =
adresse'<cad>' : LR(DEB+<cad>) .
cm(<ad1>) : #INCR(#SAUV)
STL(#SAUV)
Code(c(registre'l')=cm(<ad1>))
LRL(O)
LL(#SAUV)
#DECR(#SAUV) .
c(registre'l') : LRL(O) .
index(<ad1>,<v1>):
    cas <ad1>,<v1>:=
        adresse'<cad1>', - : #INCR(#SAUV)
        STL(#SAUV)
        Code(c(registre'1')=<v1>)
        LRL(DEB+<cad1>)
        LL(#SAUV)
        #DECR(#SAUV) .
    -, valeur'<const1>': #INCR(#SAUV)
        STL( SAUV)
        Code(c(registre'1')=<ad1>)
        LRL(<const1>)
        LL(#SAUV)
        #DECR(#SAUV) .

autre : erreur

fcas .

autre : erreur

fcas .

c(registre'r') : .

c(registre'l') : TLR .

plus(<v1>,<v2>) : Code(c(registre'r')=<v1>)
    #INCR(#SAUV)
    STR(#SAUV)
    Code(c(registre'r')=<v2>)
    AR(#SAUV)
    #DECR(#SAUV) .

moins(<v1>,<v2>): Code(c(registre'r')=<v2>)
    #INCR(#SAUV)
    STR(#SAUV)
    Code(c(registre'r')=<v1>)
    SR(#SAUV)
    #DECR(#SAUV) .

mult( ) : . . . .

div( ) : . . . .
`autre` : erreur

`fcas`

`Sinsi <registre>≡ registre'l'`

`alors Cas<contenu>≡`

adresse'<const>' : LL(=<const>).

valeur'<const>' : LL(=<const>).

cm(<ad>) : Cas<ad>

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

adresse'<cad>' : LL(DEB+<cad>)

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

`fcas`

`fcas`

`sinon` erreur (nom de registre incorrect)

`fsi`

b) modification de cm

`Code(cm(<adresse>) = <contenu>) =`

`Cas<contenu>≡`

c(registre'r') : Cas<adresse>≡

adresse'<ad>' : STR(DEB+ ad ).

c(registre'l') : STRL(0).

cm(<ad1>) : #INCR(#SAUV)

STL(#SAUV)

Code(c(registre'l') = cm(<ad1>))

STRL(0)

LL(#SAUV)

#DECR(#SAUV).

index(<ad1>,<v1>) :

Cas<ad1>,<v1> ≡

adresse'<cad1>', - : #INCR(#SAUV)

STL(#SAUV)

Code(c(registre'l') = <v1>)

STRL(Deb+<cad1>)

LL(#SAUV)

#DECR(#SAUV),
-, valeur'<const1>' : #INCR(#SAUV)
STL(#SAUV)
Code(c(registre'1') = <ad1>)
STRL(<const1>)
LL(#SAUV)
#DECR(#SAUV).

autre : erreur
fcas.

c(registre'1') : Cas<adresse>≡
adresse'<ad>' : STL(DEB+<ad>)
cm(<ad1>) : Code(c(registre'1') = cm(<ad1>))
STRL(O).

autre : #INCR(#SAUV)
STR(#SAUV)
TLR
Code(cm(adresse) = c(registre'r'))
LR(#SAUV)
#DECR(#SAUV)

fcas

autre : #INCR(#SAUV)
STR(#SAUV)
Code(c(registre'r') = <contenu>)
Code(cm(<adresse>) = c(registre'r'))
LR(#SAUV)
DECR(#SAUV)

fcas

c) Code associé à la modification standard
stoperreur

Code(stoperreur(<chaîne>)) = (BSSPEXIT)
DATA(#L(<chaîne>))
DATA('<chaîne>'))
d) Code associé aux modifications composées

Pour notre exemple, la syntaxe des modifications est la suivante :

```
<calculs> ::= <mod.sequentielle> | <mod.simple>
<mod.sequentielle> ::= <mod.sequentielle> ; <mod.simple> |
                       <mod.simple> ; <mod.simple>
<mod.simple> ::= (<calculs>) | (<acceso> | <acceso> | <calculs>) |
               (<acèso> | <accèso> | <calculs> | <calculs>) | <modYA>
<modYA> ::= c(<registre>) = <contenu> |
           cm(<adresse>) = <contenu> | stoperreur(<chaîne>)
```

Les règles de génération de code correspondantes sont :

```
Code(<mod.sequentielle>) =
    Cas <mod.sequentielle>≡
        <mod.sequentielle> ; <mod.simple> : Code(<mod.sequentielle>)
                                          Code(<mod.simple>).
        <mod.simple> ; <mod.simple> : Code(<mod.simple>)
                                          Code(<mod.simple>).

fcas
Code(<mod.simple>) =
    Cas <mod.simple>≡
        (<calculs>) = Code(<calculs>).
        (<acceso> | <accèso'> | <calculs>) : #INCR(#SAUV)
                STR(#SAUV)
                Code(c(registre'r') =
                        moins(<acceso>, <acceso'>))
                #ETI = #GENETI
                BRNZ (#ETI)
                LR(#SAUV)
                Code(<calculs>)
                #ETI1 = #GENETI
                BR(#ETI1)
                #ETI LR(#SAUV)
                #ETI1
                DECR(#SAUV) .
        (<acceso> | <acceso'> | <calculs> | <calculs'>) : ...

<modYA> : Code(<modYA>)

fcas
```
### III. Partie représentation

#### III.1. Représentation des piles de manière contigue.

Type entier ;
valeur v ;
v de entier 'I' : valeur 'CONVERTIR(I)' ;
Définir accès entier ID mod :
v de ID : cm(adresse'ALLOUER(1)') ;
fvtype ;
Type pile ;
valeur niv ; adresse adz ;
Définir accès pile P mod :
NP = ALLOUER(1) ;
cm(adresse'NP') = valeur '0' ;
niv de P : cm(adresse'NP') ;
adz de P : adresse'ALLOUER(256)' ;
fvtype ;
Accès(pile, entier) pile ajout ;
niv de ajout(p,i) :
(niv de p | valeur '100' |
stoperreur(débordement) ; nil |
cm(index(adz de p, niv de p)) = v de i ;
plus(niv de p, valeur '1'))
adz de ajout(p,i) : adz de p ;
faccès ;
accès(pile) pile suppr ;
niv de suppr(p) :
(niv de p | valeur '0' |
stoperreur(débordement par le bas) ; nil |
moins(niv de p, valeur '1'))
adz de suppr(p) : adz de p ;
faccès ;
accès(pile) entier sommet ;
v de sommet(p) :
(niv de p | valeur '0' |
stoperrur(pile vide) ; nil |
cm(index(adz de p, moins(niv de p, valeur '1')))
faccès ;
accès(entier, entier) entier add ;
v de add(x,y) : plus(v de x, v de y)
faccès ;
accès(entier, entier) entier sous ;
v de sous(x,y) : moins(v de x, v de y)
faccès ;
accès(entier, entier) entier mult ;
v de mult(x,y) : mult(v de x, v de y)
faccès ;
accès(entier,entier) entier div ;
v de div(x,y) : div(v de x, v de y)
faccès ;

### III.2. Représentation des piles de manière chaînée.

Seules sont indiquées les rubriques modifiées par rapport au paragraphe précédent.

Type pile ;
adresse adp ;
Définir accès pile P mod :
A = ALLOUER(1) ;
cm(adresse'A') = adresse'nil' ;
adp de p : cm(adresse'A')
ftype

Accès(pile,entier) pile ajout :
adp de ajout(p,i) :
(c(registre'1') = cm(adresse'0') ;
cm(adresse'0') = cm(index(cm(adresse'0'), valeur'1')) ;
cm(c(registre'1')) = v de i ;
cm(index(c(registre'1'), valeur'1')) = adp de p ;
c(registre'1'))
faccès
Accès(pile) pile suppr ;

adp de suppr(p) :

(adp de p | adresse 'nil' |
stoperreur (débordement par le bas) ; nil |
c(registre'r') = cm(index(adp de p, valeur '1')) ;
cm(index(adp de p, valeur '1')) = cm(adresse'O') ;
c(adresse'O') = adp de p ;
c(registre'r'))

faccès

Accès(pile) entier sommet ;

v de sommet(p) :

(adp de p | adresse 'nil' |
stoperreur('accès à une pile vide) ; nil |
cm(adp de p))

faccès
[1] C. PAIR
Formalization of the notions of Data, Information and Information Structure.
Data Base Management. North Holland Publishing Company - Amsterdam (1974).

[2] J.L. REMY
Structures d'Information. Formalisation des notions d'accès et de modifications d'une donnée.
Thèse de 3e cycle. Université de Nancy I - Juin 1974.

[3] Revised Report on the Algorithmic Language Algol 68.
Acta Informatica Vol 5 Fasc 1-3 1975.

[4] J.P. FINANCE
Contribution à la formalisation de la sémantique d'un langage de programmation. Application à Algol 68. Thèse de 3e cycle - Université de Nancy I, 1974.

[5] J.P. FINANCE
Data Structure as a Framework to Formalize the Semantics of a Programming Language. 2e colloque international sur la programmation.
Paris Avril 1976.

[6] C.A.R. HOARE
Proof of correctness of data representations.
Acta Informatica 1 : 271 - 281 (1972).

[7] B. LISKOV and S. ZILLES
Programming with abstract data types.
Proceedings of ACM Sigplan Conference on Very High Level Languages, (1974).

[8] B. LORHO
De la définition à la traduction des langages de programmation :
méthode des attributs sémantiques. Thèse d'Etat - Université de Toulouse, 1974.

[9] K. JENSEN and N. WIRTH
PASCAL user's manual and report.
Springer Verlag - Lecture Notes in Computer Sciences n° 18, 1975.
[10] C.H.A. KOSTER
Affix grammars
Algol 68 Implementation North Holland publishing C° (1971).

[11] D.E. KNUTH
Semantics of context free languages.
Math. Systems Theory Vol 5 n° 1 p.95-96 (1971).

[12] G. de CHASTELLIER, A. COLMERAUER
W-Grammars
Université de Montréal, 1971, Document interne.

[13] M.C. DENDIEN-GAUDEL
Application des structures de données à la description et à la
production de traducteurs. Congrès AFCET-TTI 1976.