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

HAL
open science

# Un langage intermédiaire pour la traduction des langages algorithmiques

Monique Mazaud

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

## To cite this version:

Monique Mazaud. Un langage intermédiaire pour la traduction des langages algorithmiques. [Rapport de recherche] IRIA-RR-178, IRIA. 1976, pp.56. hal-04716364

HAL Id: hal-04716364

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

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_3.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
B.P. 5 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

UN LANGAGE INTERMÉDIAIRE
POUR LA TRADUCTION
DES LANGAGES ALGORITHMIQUES

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

M. MAZAUD

Rapport de Recherche N° 178

Juillet 1976
UN LANGAGE INTERMÉDIAIRE POUR LA TRADUCTION
DES LANGAGES ALGORITHMIQUES

M. Mazaud

Résumé :

Nous présentons ici un langage intermédiaire $\mathcal{L}_1$ permettant de décrire la traduction des langages algorithmiques à structure de blocs. Les structures de données et les opérateurs de $\mathcal{L}_1$ sont paramétrés par les modes primitifs des données des langages source. Nous présentons successivement les structures de données, les opérations et les structures de contrôle de $\mathcal{L}_1$.

La définition de ce langage fait partie de la définition d'une chaîne de traduction complète en trois étapes, faisant intervenir deux langages intermédiaires dont le premier est le langage $\mathcal{L}_1$. La présentation du second langage intermédiaire orienté machine, ne sera pas abordée dans ce rapport.

Abstract :

This paper is concerned with the definition of an intermediate language $\mathcal{L}_1$ in which the translation of block structured languages will be described. The data structures and operators of $\mathcal{L}_1$ are parameterized by the primitive data types of a particular language.

We define in turn the data structures, operators and control structures of $\mathcal{L}_1$.

The definition of this language is the first aspect of the definition of a complete translator writing system. The entire system comprises two intermediate languages, namely $\mathcal{L}_1$ and machine oriented intermediate language, which will not be dealt with in this report.
# INTRODUCTION

L'écriture traditionnelle des traducteurs est à renouveler pour chaque langage source et chaque langage objet.

Afin de réduire le coût considérable de cette opération si on change seulement de langage objet, Orgass et Waite (1) (2) ont proposé un traitement par un macroprocesseur. Comme cette méthode est orientée vers un langage source, l'idée d'un langage de macros universel a été développée par Steel dans UNCOL (3) (4). Cette tentative a été un échec essentiellement pour deux raisons : d'une part, il est pratiquement impossible de décrire tous les langages source, d'autre part, la description de la structure des machines est extrêmement masquée dans le codage des macros.

Afin de réutiliser certaines parties des traducteurs déjà écrits lorsqu'on change le langage source ou le langage objet, l'idée d'une traduction vers un langage intermédiaire a été introduite.

C'est l'approche de Coleman dans le système JANUS, le langage intermédiaire introduit dans ce système opère sur une famille de machines abstraites. Les instructions de ce langage intermédiaire permettent de manipuler soit l'opérande placé dans l'accumulateur, soit des opérandes explicitement nommés par un symbole, soit les opérandes anonymes au sommet de la pile. Malgrè tout cette famille de machines abstraites est plus spécialement orientée vers les machines à registres adressables possédant des registres d'index et de base, et il n'est pas facile de passer du code intermédiaire de JANUS au code d'une machine à pile.

Un tel langage qui se veut universel, ne peut l'être en fait car il devrait recouvrir les caractéristiques combinées de tous les langages source et de tous les langages objet. L'adaptation à un nouveau langage source ou à un nouveau langage objet est assez difficile.

Notre démarche propose un découpage accru du processus de traduction, avec l'introduction de deux étapes intermédiaires. Notre objectif est de rendre compatible la première étape de traduction avec toutes les machines cibles : il faut donc que cette étape ne dépende que des langages sources.

Dans toute la suite de ce texte, nous appellerons $\ell i_1$ le langage intermédiaire dans lequel est réalisé cette première traduction. Nous montrerons plus loin qu'on peut définir un langage $\ell i_1$ suffisamment général pour qu'il convienne à la traduction de la classe $L_B$ des langages algorithmiques suivants : FORTRAN, ALGOL 60, ALGOL W, PL 1, PASCAL, ALGOL 68. Nous désirons résoudre durant la première étape de traductions tous les problèmes liés à la compilation, pour effectuer
ensuite un traitement séquentiel : le langage $\ell i_1$ doit donc être un langage pratiquement "hors contexte". La traduction du langage source en langage $\ell i_1$ consiste à construire l'arbre syntaxique d'un programme du langage source, décoré par l'ensemble des informations sémantiques associées aux noeuds de l'arbre. La syntaxe de $\ell i_1$ reflète exactement les propriétés de cet arbre décoré.

Supposons que l'on réalise directement la traduction de $\ell i_1$ en assembleur d'une IRIS 80, puis d'une IBM 370. Les mécanismes d'adressage étant très voisins dans ces deux machines, on conçoit que la traduction sera très voisine. Pour regrouper les modules de traduction communs à ces deux machines, on va donc définir une deuxième étape de traduction commune à toutes les machines à registres adressables.

Cette étape fait passer du langage $\ell i_1$ à un langage $\ell i_2$, comportant des instructions de manipulation de pseudo-registres (dont le nombre n'est pas borné).

Mais cette étape intermédiaire ne peut être utilisée pour les machines à pile (PDP 11, Burroughs 6700, 7700...) pour lesquelles l'adressage est fondamentalement différent de celui des machines à registres adressables. Il faudrait donc définir deux langages $\ell i_2$ :

- $\ell i_2$R langage intermédiaire destiné à l'écriture des traducteurs pour les machines à registres et à mémoire adressables.

- $\ell i_2$P langage intermédiaire destiné à l'écriture des traducteurs pour les machines à pile.

Dans notre réalisation, nous nous sommes limités à la définition du langage $\ell i_2$P. La définition du langage $\ell i_2$P destiné à l'écriture des traducteurs pour les machines à pile, est une extension prévue de ce travail.

Montrons à l'aide de quelques exemples comment l'introduction des deux langages intermédiaires facilite l'écriture des compilateurs.

Nous prendrons des exemples dans les deux classes de machines :

- la classe des machines à registres adressables notée C.

- la classe des machines à pile notée C'.

a/ Considérons une machine M.

Il existe un compilateur ALGOL 60 et on veut écrire un compilateur PL1 pour cette machine

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

ALGOL 60 et PL1 appartiennent à la classe des langages $L_B$ définie précédemment, par conséquent le premier langage intermédiaire à générer est bien $\ell i_1$.

Si la deuxième étape de traduction est très modulaire, on peut reprendre dans les compilateurs ALGOL 60, les modules de traduction correspondant aux structures de données communes à ALGOL 60 et PL/1. Pour les structures de
données inhérentes au langage PL1, il faut écrire les modules de traduction.
Quant à la troisième étape de traduction, elle est identique puisque la
machine cible est la même.

b/ Soit toujours la machine M.

On veut écrire un compilateur PASCAL pour la machine M, on possède un
compilateur PASCAL, pour une autre machine M' (de la même classe de machine ou
non) et on possède un compilateur ALGOL 60 pour la machine M.

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

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

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

La première partie de la traduction de PASCAL en $\ell i_1$ existe déjà et peut être
reprise telle quelle dans le compilateur $C_1$. La troisième partie de la tra-
duction existe déjà et peut être reprise telle quelle dans le compilateur $C_2$
puisque la machine cible est identique. Quant à la deuxième étape de traduction,
elle peut être reprise telle quelle dans le compilateur $C_1$ si la machine M'
appartient à la même classe de machine que la machine M ; sinon on reprend dans
le compilateur $C_2$ les modules correspondant aux structures de données communes
à PASCAL et à ALGOL 60 (si les choix d'implantation sont identiques).

c/ On veut écrire un compilateur Pascal pour une machine M de la classe C.
on possède un compilateur Pascal pour une machine M' de la classe C'.

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

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

La première étape de traduction peut être reprise telle quelle dans le compilateur C, il faut choisir dans les modules de traduction de $LI_1$ et $LI_2$ que nous proposons ceux qui correspondent aux structures des données de Pascal et écrire la traduction de $\ell i_2$ en langage machine de la machine cible M.
En résumé, l'écriture d'un compilateur se ramène à trois étapes de traductions :

- une étape de traduction du langage LS en langage $\ell i_1$, celui-ci dépendant uniquement d'une classe de langage source.

- une étape de traduction de $\ell i_1$ en $\ell i_2$, où $\ell i_2$ dépend de la structure de la machine (essentiellement de l'organisation de l'unité de traitement).

- une étape de traduction de $\ell i_2$ en langage machine où on introduit alors les caractéristiques fines de la machine (taille des mots, adressage, nombre des registres disponibles).

Nous allons maintenant établir la comparaison entre l'écriture classique d'un compilateur et l'écriture que nous proposons. Plus précisément nous allons récapituler les fonctions usuelles d'un compilateur et montrer comment elles sont réparties dans notre système.

Nous supposerons que la traduction du langage source en langage $\ell i_1$ est effectuée à l'aide du système DELTA [6] implanté à l'I.R.I.A., mais ceci n'est pas impératif, l'auteur de compilateur pouvant utiliser les outils dont il dispose.

On peut considérer que le travail d'un compilateur comporte quatre fonctions principales.

a/ La vérification syntaxique du texte source.

La grammaire du langage source à compiler est décrite sous forme de règles BNF et le constructeur syntaxique de DELTA génère l'analyseur syntaxique correspondant à cette grammaire.

Les vérifications syntaxiques correspondant au langage "context free" sont donc réalisées par cet analyseur.

La réalisation des tests contextuels (concernant la validité de l'utilisation des données, des paramètres...) est effectuée à l'aide des attributs sémantiques de KNUTH [7] au cours de la première étape de traduction du langage en langage $\ell i_1$.

b/ La création d'une table de symboles où sont rangées les informations concernant les types, adresses des données, toutes informations contextuelles qui servent à effectuer la génération de code machine.

Dans notre système, la fonction de la table des symboles est réalisée par un attribut sémantique. Cette table est remplie lorsqu'on reconnaît dans la syntaxe les instructions de déclarations des données, des étiquettes, des procédures. Les informations concernant les déclarations de ces objets sont transmises (grâce à l'attribut table des symboles) aux instructions y faisant référence et intégrées à la syntaxe du texte $\ell i_1$ généré.
Dans notre système, une fois la génération du code $\ell i_1$ effectuée, la table des symboles disparaît car les informations nécessaires à la suite de la traduction ont été intégrées au code $\ell i_1$ généré.

c/ Les optimisations.

On distingue ordinairement les optimisations indépendantes de la machine et celles qui en dépendent.

Les premières concernent la propagation des constantes, l'élimination des sous-expressions communes redondantes, le déplacement des invariants des boucles. Comme elles mettent en jeu des informations contextuelles, il est naturel de les effectuer par attributs sémantiques, lors de la traduction du langage source en $\ell i_1$.

Les secondes dépendent de la machine, elles consistent essentiellement à minimiser les transferts entre l'unité de traitement et la mémoire centrale, donc à adopter une stratégie optimale d'assignation des registres.

Ces optimisations dépendent de la structure fine de la machine, elles doivent donc être traitées lors de la traduction du langage $\ell i_2$ en langage machine.

Cependant cette dernière phase d'optimisation peut être préparée lors de la traduction de $\ell i_1$ en $\ell i_2$. On peut en particulier rechercher la durée de vie de chaque variable et réaliser, pour les machines à registres adressables, la phase d'allocation des registres (conformément à la terminologie de BEATTY [8]).

d/ La génération de code machine.

Nous avons vu au début de cette introduction que nous ne voulions effectuer la génération de code machine qu'à la fin de la troisième étape de traduction.

Cette génération dépend naturellement des choix d'implantation des données, ces choix ne sont pas inhérents au langage source à compiler (sauf pour ce qui concerne le traitement des précisions des données arithmétiques de PL1) : ils dépendent des objectifs de l'auteur du compilateur, c'est pourquoi nous les introduisons seulement lors de la deuxième étape de traduction de $\ell i_1$ en $\ell i_2$.
Première Partie

LE LANGAGE LII
La méthode de définition du langage $\mathcal{L}i_1$.

Notre système doit pouvoir aider à la traduction des langages algorithmiques usuels et de ceux qui en sont dérivés et sont utilisés pour traiter des applications plus spéciales. Nous définirons les caractéristiques du langage $\mathcal{L}i_1$ à partir de la comparaison des langages algorithmiques suivants : FORTRAN, ALGOL 60, ALGOL W, PL1, PASCAL, ALGOL 68. La comparaison portera sur les structures de données, la structure des programmes, les opérations, les structures de contrôle valides dans ces langages.

La suite de ce rapport se compose de l'examen de ces différents points sachant que l'objectif à atteindre après la première étape de traduction est la résolution de tous les problèmes liés à la compilation.

La traduction du langage source en langage $\mathcal{L}i_1$ consiste donc à construire l'arbre syntaxique d'un programme du langage source, décoré par l'ensemble des informations sémantiques associées aux noeuds de l'arbre. La syntaxe de $\mathcal{L}i_1$ reflétant les propriétés de cet arbre décoré est donc pratiquement "hors contexte". Le langage $\mathcal{L}i_1$ est un langage de triplets généralisé, car une adresse dans le code $\mathcal{L}i_1$ généré est un numéro de triplet (nous l'écrirons : entier T).

# 1. LES STRUCTURES DE DONNEES DE LI1

## 1.1. La méthode de construction.

Pour construire les structures des données de $\mathcal{L}i_1$, deux méthodes viennent à l'esprit. La première consiste à choisir les structures de données du langage le plus riche. Or la comparaison des structures de données des langages source n'est pas aisée ; elle l'est d'autant moins que certains langages autorisent la définition des types.

La seconde méthode consiste à construire une structure de données pour $\mathcal{L}i_1$ qui serait l'union des structures de données valides dans les langages usuels. Cette méthode permet évidemment de décrire l'ensemble de ces derniers langages, mais elle manque de souplesse et ne permettrait pas une adaptation à la traduction d'autres langages algorithmiques (A titre d'exemple, la définition de types arithmétiques variant dans une gamme de précisions particulières, ne peut être traitée si on n'a prévu en $\mathcal{L}i_1$ qu'un seul type arithmétique réel). Aucune de ces approches intuitives ne permet de résoudre notre problème, seule une solution de paramétrisation des types est acceptable. Pour définir ces paramètres nous allons rappeler comment sont construits les objets des langages algorithmiques. Nous ferons ce rappel en divisant les langages
algorithmiques en trois classes : les langages qui n'autorisent que les types prédéfinis (FORTRAN, ALGOL 60, ALGOL W, PL1), PASCAL qui autorise la définition de types, ALGOL 68 qui introduit l'orthogonalisation.

## 1.2. Les objets des langages algorithmiques.

Nous distinguerons ici l'ensemble E des langages qui autorisent exclusivement les types prédéfinis (FORTRAN, ALGOL 60, PL1, ALGOL W) ; et les langages PASCAL et ALGOL 68 qui autorisent les définitions de type.

### 1.2.1. Les types prédéfinis.

Les langages de l'ensemble E permettent de manipuler des objets simples possédant un type simple prédéfini : entier, réel, logique en FORTRAN et en ALGOL 60, types artithmétiques, logique, et type chaîne en PL1 et en ALGOL.

Des objets composés peuvent être construits à partir de certains groupements d'objets élémentaires de même type ou de types différents. Dans la terminologie de ces langages, on dit que l'on traite des types complexes : ainsi un tableau d'entiers est un groupement de valeurs entières de type simple entier, le type de ce groupement est le type tableau.

Chaque langage source possède ses règles de construction ou types complexes : le type tableau est valide dans l'ensemble des langages. Le langage PL1 possède en outre le type structure comme type complexe, le langage Algol W le type enregistrement comme type complexe.

Certains langages autorisent l'application de manière répétée de ces constructions par des règles de composition. PL1 permet ainsi de traiter des objets de type tableau de structure ou structure de tableau. En ALGOL 60 ou FORTRAN, il est impossible de répéter la construction tableau ; il est impossible de définir des objets du type tableau de tableau.

### 1.2.2. Les définitions de type

Le langage PASCAL permet de décrire les objets qui gardent une valeur invariable à l'exécution par une déclaration de constante. Le traitement à la compilation peut toujours s'effectuer par la méthode de propagation des constantes. Tous les autres objets sont appelés dans le langage des variables. Ils possèdent un type prédéfini, ou un type défini dans le programme. La définition du type permet ici aussi de créer une hiérarchie conformément à certaines règles : ainsi le type tableau d'ensemble est valide, le type ensemble de tableau ne l'est pas ...
### 1.2.3. Les objets d'ALGOL 68.

La terminologie d'ALGOL 68 diffère de la terminologie usuelle des langages algorithmiques : on dit que chaque objet possède un mode : le mode est une généralisation du type des autres langages algorithmiques. Il caractérise une classe de valeurs sur lesquelles les mêmes opérations et relations sont définies.

Les types simples des autres langages algorithmiques sont appelés modes primitifs en ALGOL 68. Les modes en sont élaborés essentiellement à partir de quatre règles de construction qui sont :

- la construction tableau,

- la construction structure,

- la construction procédure,

- la construction repère.

L'application répétée de ces constructions dans un ordre et un nombre quelconque est autorisée : c'est ce qu'on appelle l'orthogonalisation des modes.

Comme dans tous les langages algorithmiques, un objet est désigné par un identificateur. La déclaration d'un objet peut se faire par deux méthodes : soit la déclaration d'un identificateur suivie d'une description de mode, soit la déclaration d'un identificateur suivie d'un indicateur de mode (nom servant à désigner un mode qui a été déclaré précédemment).

Revenons aux quatre règles de constructions valides en ALGOL 68 pour préciser les constructions procédure et repère.

Les valeurs des objets de mode procédure, peuvent être manipulées comme n'importe quelles autres valeurs, être affectées, incluses dans des structures etc...

Une procédure est un objet quelconque en ALGOL 68, c'est-à-dire qu'il est possible d'effectuer entre autres des affectations entre objets procédure.

La construction repère permet la construction de "noms". En pratique à l'implantation d'ALGOL 68 un nom est représenté par l'adresse d'un emplacement destiné à contenir la valeur qu'il repère (cette valeur pouvant être un autre nom).

Un nom peut aussi être manipulé comme n'importe quel autre objet. En particulier, il est possible de déclarer que deux identificateurs sont synonymes, car ils désignent les mêmes noms, donc les mêmes adresses.

Exemple : `ent j ; ... rep ent i = j`

Cette déclaration d'identité comporte deux informations ; d'une part la déclaration d'un objet de mode repère d'entier désigné par l'identificateur i, d'autre part la synonymie des identificateurs i et j.

A l'implantation, on peut représenter cette identité par le schéma suivant

<figure><img src="image_11.png" /></figure>
Le langage ALGOL 68 permet de définir les constantes en faisant désigner des valeurs par des identificateurs. Ces valeurs qui sont des notations de constantes ou des valeurs d'expressions sont indépendantes de toute exécution. Des déclarations d'identité permettent de réaliser ces déclarations de constantes.

$$ 
\begin{array}{l}
\underline{\text{ent}} \ c = 3 \\
\underline{\text{réel}} \ r_2 = \text{rac2}(i)
\end{array}
$$

L'identificateur déclaré désigne la même valeur calculée (cas de $r_2$), ou écrite (cas de c) aussi longtemps qu'on n'a pas quitté la région où on peut utiliser cet identificateur. Pour les valeurs calculées, il faut réserver à l'implantation une zone de mémoire effective ; les références aux objets constants seront donc traitées exactement comme les références aux objets variables. C'est le travail du compilateur de vérifier que dans le programme les constantes sont utilisées comme telles et non comme des variables.

Pour les valeurs des constantes écrites, on peut effectuer la propagation des constantes. En PASCAL les identificateurs constants désignent uniquement des valeurs écrites et il est toujours possible d'effectuer la propagation des constantes.

En conséquence en $\ell i_1$ on ne traitera que des variables, puisqu'à la compilation on a pu résoudre le problème des constantes en les traitant soit comme des variables, soit en effectuant leur propagation.

## 1.3. Les objets de $\ell i_1$

### 1.3.1. Leur méthode de définition.

Nous venons de voir que tous les langages algorithmiques permettent de manipuler des objets simples ou des objets composés. Le langage $\ell i_1$ doit donc permettre de manipuler des objets simples ou des objets composés. Pour décrire les structures de données de $\ell i_1$ nous adopterons la terminologie d'ALGOL 68 : les modes primitifs permettent de décrire les objets simples. L'application des règles de construction sur un ou plusieurs modes primitifs constitue un moyen de décrire des objets plus complexes. L'application répétée de ces constructions constitue une composition.

Les modes primitifs et constructions valides dans le langage $\ell i_1$ décrit ici sont ceux qui permettent de décrire l'ensemble des langages algorithmiques usuels définis précédemment : FORTRAN, ALGOL 60, ALGOL W, PL1, PASCAL, ALGOL 68. Nous verrons que la construction repère d'ALGOL 68 peut être traitée comme un mode primitif pointeur. Nous décrirons donc les constructions, tableau,
structure, ensemble, procédure. Les compositions de $\ell i_1$ sont toutes les combinaisons possibles de ces constructions. Cependant il est toujours possible d'introduire d'autres modes primitifs et d'autres constructions pour décrire d'autres langages (par exemple la construction liste pourra être introduite à moins de la ramener à la construction structure comme en ALGOL 68).

Les modes primitifs et les constructions sont donc considérées ici comme des paramètres du langage $\ell i_1$.

Revenons à l'ensemble des langages algorithmiques usuels que nous nous proposons de décrire. Etant donné que les structures de données de $\ell i_1$ se composent de l'union des modes primitifs et des constructions valides dans ces langages, comment peuvent-elles refléter les structures de données d'un langage particulier. Pour répondre à cette question, il faut revenir au schéma fonctionnel de notre système de traduction.

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

Le système d'aide à l'écriture des traducteurs que nous fournissons se compose de la syntaxe des langages $\ell i_1$ et $\ell i_2$, et des modules de traduction entre ces deux langages. A la charge de l'auteur de compilateur reste l'écriture des actions sémantiques à effectuer pour réaliser la traduction d'un langage source en $\ell i_1$.

A titre d'exemple, décrivons le mécanisme d'écriture d'un compilateur ALGOL 60. Seule la construction "tableau" existe dans la syntaxe d'ALGOL 60, dans la règle syntaxique de description d'un tableau on décrira la génération d'une déclaration de tableau en $\ell i_1$.

Les autres constructions "structure", "ensemble" etc... n'existent pas en ALGOL 60, on ne pourra donc jamais atteindre leur représentation en $\ell i_1$ lorsqu'on traduit ALGOL 60. De façon plus générale, seul le sous-ensemble de structures de données de $\ell i_1$, correspondant aux structures de données de langage source, pourra être atteint lors de la première traduction.

### 1.3.2. La traduction des déclarations des modes en $\ell i_1$

Les langages ALGOL 68 et PASCAL offrent la possibilité de représenter un mode (respectivement un type) par un symbole appelé indicateur de mode (respectivement identificateur de type). Afin de simplifier la rédaction, nous limiterons les explications au traitement des déclarations de mode d'ALGOL 68; mais ce qui suit s'applique également au langage PASCAL. Les indicateurs de mode présentent l'intérêt de simplifier l'écriture de certaines déclarations.
En particulier dans le cas où un programmeur veut déclarer en plusieurs endroits du programme des identificateurs de même mode, il lui serait fastidieux de réécrire à chaque fois la définition de ce mode. Mais les déclarations de mode constituent un facteur de la puissance du langage ALGOL 68. En effet les indicateurs de mode qui figurent dans une déclaration de mode peuvent apparaître en partie droite d'une autre déclaration de mode, ou de la même déclaration de mode : le langage autorise sous certaines conditions (voir paragraphe 1.3.3) la récursivité des modes, on obtient ainsi des modes qu'il serait impossible de déclarer autrement. (Notons que la récursivité des modes est interdite en PASCAL).

La simplicité et la clarté de l'écriture au contraire ne sont pas les objectifs fondamentaux du langage $\mathcal{L}_1$ car la syntaxe de ce langage doit être le reflet de la solution apportée au traitement des informations contextuelles. Par conséquent, pour la traduction des déclarations d'identificateurs dont le mode est représenté par un indicateur de mode, nous adopterons la règle suivante : l'expansion de la définition de ce mode $m$ est effectuée dans la déclaration $\mathcal{L}_1$ de l'objet. Si ce mode fait appel à un autre mode $m'$, on fera l'expansion également du mode $m'$.

La syntaxe du langage $\mathcal{L}_1$ ne comporte donc pas de déclaration de mode ; seules les déclarations d'objets comprenant la description de leur mode appartiennent à la syntaxe du langage $\mathcal{L}_1$.

### 1.3.3. Le traitement des modes récursifs.

Le seul problème qui se pose réellement pour réaliser l'objectif précédent est le traitement des modes récursifs.

Les restrictions imposées par le langage ALGOL 68 lui-même sur la récursivité des modes, nous permettent de mettre en évidence la solution à ce problème. Deux écritures sont possibles :

- soit l'utilisation du symbole `rep` devant l'indicateur de mode qui figure en partie droite de la définition d'un mode récursif.

- soit l'utilisation du symbole `rep` au début de la définition de ce mode.

En ALGOL 68 la déclaration de mode suivante est incorrecte `mode a = struct (réel x, a suivant) car après des déclarations d'identité telles que a x = (3.1, fant) ; a y = (4.1, x)`

Les valeurs désignées par $x$ et $y$ auraient en mémoire des représentations différentes

x

<table><tr><td>3.1</td><td>fant</td></tr></table>

y

<table><tr><td>4.1</td><td>3.1</td><td>fant</td></tr></table>

Pour éviter cet inconvénient on pourra par exemple déclarer le mode $a$ de la façon suivante :
mode a = struct (réel x, rep a suivant)

Le deuxième champ d'un objet de mode a à l'implantation est un pointeur

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

On constate que dans ce cas la construction repère d'ALGOL 68 est traduite par un mode primitif pointeur (ou adresse) de $\ell i_1$. Ce résultat peut-être généralisé, c'est ce que nous allons examiner dans le paragraphe suivant en traitant les noms d'ALGOL 68.

#### 1.3.4. Le traitement de la construction repère d'ALGOL 68.

Le traitement des synonymes d'ALGOL 68 constitue un autre cas d'application de la construction repère. Soit en ALGOL 68 la déclaration de nom suivante : `rep réel z = t [i]`. Cette déclaration signifie que z désigne le nom du ième élément du tableau t. Elle ne constitue pas la déclaration d'un nouvel objet, puisque à l'implantation la place occupée par z et la place occupée par t [i] sont identiques. Remarquons alors que le mode `rep réel` associé à l'identificateur z sert uniquement à vérifier que les utilisations de z dans les instructions sont valides.

Dans une implantation classique, on associe à z une zone de mémoire contenant son nom puisque ce nom est dynamique.

Ici on peut générer en $\ell i_1$ le code du calcul de l'adresse de t [i] par une série de triplets. Au cours de la traduction, on mémorise dans les tables le numéro du triplet ayant pour résultat cette adresse, et lorsqu'on rencontre une référence au nom de z dans les instructions, on remplace ce nom par la référence à ce triplet. Nous reprendrons page 30 la traduction précise de cet exemple.

Remarquons que la solution ainsi adoptée permet d'éviter de mémoriser dans le code généré les noms associés aux identificateurs. Une variable de mode `rep ent` d'ALGOL 68 pourra donc être traitée comme une variable de type entier des autres langages (dans la zone associée à cette variable on trouve directement la valeur).

Cette optimisation peut être étendue aux objets d'ALGOL 68 pour lesquels la construction repère est appliquée en nombre répété.

Soit la déclaration `rep ent zz ;` zz est de mode `rep rep ent`. A la traduction en $\ell i_1$ on pourra déclarer un objet de mode pointeur. Soit l'effetuation `zz := z ;` zz a pour valeur le nom de z, il suffira de générer en $\ell i_1$ une affectation sur des adresses.
Si on veut atteindre la valeur pointée, il faut effectuer un certain nombre d'opérations de derepérage. Pour traduire l'affectation suivante d'ALGOL 68 $z := zz + 1$, on écrira symboliquement

$z := \text{dereperer}(\text{dereperer}(zz)) + 1$

Le mode primitif de la valeur pointée _ent_ est conservé dans les tables durant la traduction, pour effectuer les contrôles de validité et générer les opérations portant sur la valeur pointée avec l'indication du mode primitif.

Nous reviendrons plus loin sur la traduction exacte de ces exemples.

### 1.3.5. Le traitement de la construction procédure des langages algorithmiques.

Tous les langages algorithmiques autorisent la description d'objets constants de mode procédure. Dans ALGOL 68, on a généralisé ce concept en introduisant les variables de mode procédure.

Une procédure est une construction qui s'applique aux modes des paramètres formels. Est-il nécessaire de conserver la description des modes des paramètres formels ? Si la réponse est non, cela signifie que procédure n'est pas une construction de $\ell i_1$.

Les paramètres formels d'une procédure, permettent la communication entre le corps de procédure et l'endroit du programme où elle est activée. Ils font intervenir à l'exécution du corps de procédure, des quantités qui n'y sont pas normalement accessibles, les arguments. A la traduction il faut vérifier que pour chaque appel les types des paramètres effectifs correspondent aux types des arguments. Ceci peut être effectué dans la plupart des cas de façon statique pour les langages que nous considérons, en conservant dans les tables les types des paramètres formels.

Les paramètres formels n'ont en général pas de zone réservée localement à la procédure (sauf dans le cas du passage par valeur d'ALGOL 60 car le rapport ALGOL 60 précise que les paramètres formels déclarés par valeur doivent être traités comme des variables locales à la procédure).

Par conséquent l'information concernant leur type ne sert pas à construire la place qui leur est réservée. Elle est utile évidemment pour traiter les références aux paramètres formels dans le corps de la procédure, dans la suite du processus de traduction. Le type des paramètres formels doit apparaître en $\ell i_1$ dans les opérations ayant un paramètre formel comme opérande. Ceci est un problème de traduction et non un problème de langage intermédiaire : il suffit de conserver à la traduction le type du paramètre formel dans les tables.

Pour traiter en $\ell i_1$, le cas d'un paramètre formel d'ALGOL 60 spécifié par valeur, on effectuera pour celui-ci une déclaration d'un objet local à la procédure.
Ainsi il est inutile de spécifier en $\ell i_1$ les types des paramètres formels, un objet constant de mode procédure peut être considéré comme un mode primitif de $\ell i_1$, nous l'appelerons dans la suite du texte mode primitif texte de routine.

En conséquence, comment traduire les variables de mode procédure d'ALGOL 68. La valeur d'une variable de mode procédure est un texte de routine, on peut considérer que le texte de routine est la valeur pointée ; dans ces conditions on peut décrire une variable procédure en $\ell i_1$ comme un objet de mode primitif adresse.

### 1.3.6. Les modes de $LI_1$.

En résumé, on peut dire que le langage $\ell i_1$ possède des modes primitifs qui sont :

- l'union des modes primitifs des langages algorithmiques,

- les modes primitifs adresse et texte de routine.

Sur ces modes primitifs s'appliquent en $\ell i_1$ les constructions tableau, structure, ensemble.

Les objets de $\ell i_1$ sont des variables. Les seules constantes de $LI_1$ sont les textes de routine qui font l'objet d'une déclaration particulière.

## 1.4. La désignation des objets en $\ell i_1$

L'ensemble des langages source que nous désirons pouvoir traduire est constitué par des langages procéduraux à structure de blocs ainsi que FORTRAN.

### 1.4.1. Rappel des mécanismes d'adressage classiques des langages procéduraux à structure de blocs.

Activer une procédure c'est théoriquement insérer le corps de la procédure à la place de l'appel et l'exécuter après avoir fait le remplacement des paramètres par les arguments.

La récursivité des procédures dans les langages à structure de blocs implique que le corps de chaque procédure soit compilé en un sous-programme réentrant. Pour cela il faut créer à chaque appel d'une procédure une zone de travail dont elle se servira. Cette zone de travail contient les données locales à la procédure ainsi que les mémoires du travail qu'elle utilise. L'adresse de début de cette zone s'appelle adresse de base de la procédure. L'adressage final des données doit s'effectuer relativement à l'adresse de base. Il est possible de réserver la place des objets dont la taille est connue à la compilation, pour ceux dont la taille est dynamique, on réserve une zone appelée vecteur de renseignements qui comporte les renseignements utiles pour réaliser l'adressage de ces objets. L'existence de la structure des blocs permet l'utilisation
d'identificateurs locaux et l'utilisation répétée d'un même symbole pour désigner
des objets différents. Afin d'attribuer à chaque signification une adresse
différente on peut construire une fonction d'adressage à trois ou deux paramètres.

1.4.1.1. *L'adressage classique à trois paramètres.*

Chaque objet est désigné par trois paramètres

- np niveau d'imbrication de la procédure à laquelle appartient l'objet
à adresser.

- nb niveau d'imbrication du bloc.

- adr adresse de chaque donnée relative à chaque début de procédure

Cette adresse relative est évidemment fonction de l'encombrement réel
des données.

A l'exécution un calcul d'adresse est fait à partir de ces trois
paramètres : on repère dans deux piles BLOC et PROC placés en pile dynamique
le début d'implantation des variables de chaque bloc et de chaque procédure.

La fonction d'adressage est :

$$
f(np,nb,ad) = \mathrm{BLOC}(\mathrm{PROC}(\mathrm{np})+\mathrm{nb}) + \mathrm{ad}
$$

Cette méthode d'adressage nécessite de mémoriser deux piles et d'effectuer à
l'exécution deux indirections. L'encombrement maximal de données est l'encom-
brement maximal des blocs.

1.4.1.2. *L'adressage classique à deux paramètres.*

Il est possible de concevoir un adressage plus rapide à l'exécution
et comportant seulement deux paramètres (np,adr). Pour tenir compte de la
structure de blocs l'adresse relative est calculée conformément à l'algorithme
suivant :

- à la lecture d'une instruction d'entrée de procédure, on réinitialise la
valeur de l'adresse relative à l,

- à l'entrée d'un bloc, on mémorise la dernière valeur de l'adresse relative
avant l'entrée dans ces blocs. Après la lecture de chaque déclaration on
incrémente la valeur de l'adresse relative de la taille de la donnée déclarée,

- à la sortie d'un bloc, on remet à jour l'adresse relative en lui affectant
la valeur qu'elle possédait avant l'entrée dans ce bloc.

Cette méthode ne nécessite qu'une pile de traitement appelée le display des
procédures, par contre, l'encombrement maximal à réserver est égal au maximum
de la somme des encombrements des blocs imbriqués les uns dans les autres.

1.4.2. La désignation à deux paramètres des objets en $l_i$.

Quelque soit le langage source, un objet est désigné par un identificateur ;
par analogie on peut dire qu'une adresse est la désignation en langage d'assemblage
d'un objet.
Nous appellerons "descriptif" la désignation en $l_i$ d'un objet. Cette désignation doit refléter uniquement les caractéristiques du langage source : on peut donc choisir soit les trois paramètres, soit les deux paramètres. Nous choisirons une désignation à deux paramètres dans le but de prévoir un adressage final plus rapide à l'exécution. Les deux paramètres sont :

- le niveau d'imbrication de procédure np,

- le rang $rg$ : le rang de chaque objet est évalué en affectant à chaque objet une unité de "mémoire abstraite" car la taille réelle des données ne peut être prise en compte ici.

L'algorithme de calcul du niveau d'imbrication de procédure np est :

- la procédure externe porte le niveau de procédure 0 (nous ne traiterons pas ici le problème de la compilation séparée des procédures, nous supposerons donc que tout programme à traduire se compose d'une seule procédure externe).

- quand on lit une instruction de déclaration de procédure incrémenter np de une unité.

- quand on lit une instruction de fin du corps d'une procédure décrémenter np de une unité.

L'algorithme de calcul du rang est identique à l'algorithme de calcul de l'adresse relative dans l'adressage classique à deux paramètres à la différence près qu'on ne peut tenir compte ici de la taille réelle des données. On accroît donc le rang de une unité après la lecture de chaque déclaration de donnée.

A titre d'exemple, montrons quelles sont les valeurs des descriptifs des objets du programme ALGOL 60 suivant :

```
begin integer a,b,c;      descriptif(A) = (0,1) descriptif(Z) = (0,2) descriptif
procedure p(x); integer x; descriptif(P) = (0,4)                      (C) = (0,3)
begin real y; integer i;  descriptif(Y) = (1,1) descriptif(I) = (1,2)
procedure g(u); real u;    descriptif(G) = (1,3)
begin real z;               descriptif(Z) = (2,1)
```

```
end;
```

```
procedure h(t); integer t; descriptif (H) = (1,4)
begin integer array tab (1:10,1:10) descriptif (TAB) = (2,1)
```

```
end;
```

```
end;
```

Remarquons que les procédures sont traitées comme n'importe quel autre objet donc qu'elles possèdent un descriptif.
## 2. LA DECLARATION DES DONNEES EN LI 1

### 2.1. La syntaxe de déclaration

La syntaxe des déclarations de tous les objets en $li_1$ débute par le code opération ALLC, sauf pour les textes de routines qui comportent la traduction du corps de la procédure. Nous avons déjà indiqué au paragraphe 1.2.3 qu'il n'était pas nécessaire de faire en $li_1$ la distinction entre constantes et variables car à ce niveau tous les objets sont traités comme des variables. Au paragraphe 1.3.4 on a montré qu'il n'était pas nécessaire de conserver les noms de chaque objet parce qu'on peut ramener dans tous les cas la construction repère à un mode primitif adresse en $li_1$.

La syntaxe de déclaration des données en $li_1$ est présentée dans les lignes qui suivent. Conformément aux notations utilisées chez I.B.M., nous plaçons entre crochets les unités syntaxiques dont l'occurrence peut apparaître ou non. Lorsqu'un non terminal apparaît entre accolades, l'accolade droite étant suivie d'une astérisque, cela s'interprète comme une suite de ce non terminal : exemple pour {<dim>}* il faudrait écrire en forme normale stricte de Backus <ldim>=<dim>|<ldim><dim> la désignation d'un objet est le descriptif, ou un triplet d'entiers quand il s'agit d'un paramètre formel ou du résultat qui possèdent une zone réservée dans la procédure.

```
<déclaration> = ALLC <descriptif> <déclareur effectif> |
               ALLC (entier,entier,entier) <déclareur effectif>
<texte de routine> = ROUTINE <descriptif> entier ; <ltrip> ; END|
               ROUTINE* (entier,entier,entier)entier; <ltrip> ; END
<déclareur effectif> =
<mode primitif> | <déclareur effectif de tableau> | <déclareur effectif de
structure> | <déclareur d'ensemble>
<déclareur effectif de tableau> =
TAB [COMPRESSE] entier ; <dim> ; [{<dim>;}*] <déclareur effectif>
<dim> = DIM E <borne>, <borne>
<borne> = <constante entière> | <ldereperage> <descriptif> |* (entier T) | Id
<ldereperage> = <derep> { <derep>}*
<derep> = *
<déclareur effectif de structure> =
STRUCTURE [COMPRESSE] (entier,entier) <champ effectif> ; { <champ effectif>}*
<champ effectif> = (entier,entier) <déclareur effectif>
<déclareur d'ensemble> = ENS <déclareur effectif>
```

**Remarque** : Cette syntaxe est conforme au principe d'orthogonalisation des modes. Remarquons qu'elle n'utilise que des déclareurs effectifs. Rappelons que les déclareurs formels ont été introduits dans la syntaxe d'ALGOL 68 pour
spécifier les modes des paramètres formels. Comme en $\ell i_1$ on ne déclare pas les paramètres formels (la mémorisation de leur mode a été faite par le traducteur), il n'apparaît pas dans la syntaxe de $\ell i_1$ des déclareurs formels.

Les modes primitifs du langage $\ell i_1$ sont le mode primitif adresse et l'union de modes primitifs des langages source. Ces derniers pourront être décrits par l'implanteur au moment de l'écriture de la première traduction.

Dans les paragraphes qui suivent nous décrivons le mode primitif adresse et nous donnerons des exemples de description des modes primitifs des différents langages source.

Puis nous décrivons les différentes constructions de $\ell i_1$ : construction tableau, construction structure, construction ensemble. Dans ce chapitre consacré à la description des déclarations de données, nous ne décrirons pas les textes de routine. Pour la commodité de l'exposé, il est plus clair de présenter en même temps la déclaration et l'appel des routines ou la traduction de l'appel des routines fait intervenir des affectations ou des identités qui seront décrites au paragraphes 4 et 5. Le chapitre 6 sera consacré aux textes de routine.

## 2.2. Le paramètre de $\ell i_1$ mode primitif

### 2.2.1. Le mode primitif adresse.

Le mode primitif adresse sert à décrire les pointeurs de PL 1, et la construction repère d'ALGOL 60. Les exemples intéressants d'utilisation de la construction repère font intervenir les autres constructions, c'est pourquoi nous les décrirons plus loin.

### 2.2.2. La description des modes primitifs d' ALGOL 60

ALGOL 60 n'autorise que les modes primitifs arithmétique ou logique

$$ <\text{mode primitif}(\text{ALGOL 60})> = E|R|L $$

On pourra par exemple coder le mode primitif 'integer' par la chaîne E, le mode primitif 'real' par la chaîne R, le mode primitif 'boolean' par la chaîne 'L'.

Exemple

boolean x; ALLC (np_x, rg_x)L

integer u; ALLC (np_u, rg_u)E

### 2.2.3. La description des modes primitifs de PL 1.

PL 1 autorise les modes primitifs arithmétiques, logique, étiquette, pointeur et chaîne.
Les modes primitifs arithmétiques possèdent quatre paramètres, la base, le mode, l'échelle et la précision :

- la base est soit décimale, soit binaire ;

- le mode est soit réel, soit complexe ;

- l'échelle est soit la virgule fixe, soit la virgule flottante ;

- la précision indique le nombre de chiffres que la donnée arithmétique peut comporter.

* en virgule fixe la précision spécifie la position de la virgule par rapport au chiffre le plus à droite du nombre

* en virgule flottante la précision est le nombre minimal de chiffres significatifs (exposant non compris) qui doit être conservé.

Exemple

### DCL A FIXED DECIMAL (5,4)

est la déclaration d'un nombre décimal ne comportant pas plus de 5 chiffres dont 4 à droite de la virgule

### DCL B FIXED DECIMAL (6)

est la déclaration d'un nombre entier ne comportant pas plus de 6 chiffres.

En LI₁ il faut évidemment conserver toutes ces informations et décrire complètement le mode primitif arithmétique.

On pourra traduire les déclarations de A et B par :

ALLC (npₐ, rgₐ) REAL FIX DEC (5,4)

ALLC (np, rgb) REAL FIX DEC (6)

Le mode primitif pointeur de PL 1 sera traduit en $\ell i_1$ par le mode adresse.

Le mode primitif étiquette de PL 1 sera traduit en $\ell i_1$ par le mode Et.

On en verra l'application dans le chapitre des structures de contrôle de $\ell i_1$.

Le mode primitif chaîne de PL 1 sera également décrit en $\ell i_1$ par un mode primitif chaîne avec par exemple :

<mode chaîne> = <fvar> <nature> <valeur entière>

<fvar> = FIX|VAR chaîne de longueur constante ou
chaîne de longueur variable mais bornée

<nature> = BIT|CH chaîne des bits ou de caractères

<valeur entière> = <constante entière> | entier T

Exemples de traduction :

dcl n character (10) varying (1) ALLC(np_n, rg_n) VAR CH 10 C

dcl id bit (i + j) varying (2) + REAL FIX BIN (15) * (np_i, rg_i), * (np_j, rg_j)

(3) ALLC (np_id, rg_id) VAR BIT 2 T

Dans le dernier exemple la longueur maximale de la chaîne est dynamique, il s'agit de la valeur de i+j, qui est calculée en $\ell i_1$ par le triplet 2.
### 2.2.4. La description des modes primitifs de PASCAL.

PASCAL autorise les modes primitifs standards entier, réel, logique, caractère. Une chaîne de caractères en PASCAL n'est pas considérée comme un mode primitif, elle est traitée comme un tableau de caractères.

Nous traiterons les types scalaires définis par le programmeur comme des modes primitifs car les constructions définies plus haut s'appliquent également à eux.

En PASCAL un type scalaire est une suite de valeurs, désigné par un identificateur. Exemple :

```
type couleur = (blanc, rouge, bleu)
type jour = (lundi, mardi, mercredi, jeudi, vendredi, samedi)
la suite des valeurs représenté par un type scalaire est ordonné.
```

Lors de la traduction de PASCAL en $\ell i_1$, on numérote les types scalaires définis, et on code les valeurs de chaque type par une suite de nombres entiers compris entre 1 et n (n étant le nombre de valeurs discrètes). Afin de simplifier l'écriture du codage des valeurs discrètes, on note $[1 \dots n]$ ces valeurs ce qui signifie que toutes les valeurs des entiers successifs compris entre 1 et n sont valides.

```
type couleur = (blanc, rouge, bleu)
var x : couleur;                 (1) ALLC (np_x, rg_x) CODE 1 [1 ... 3]
type jour = (lundi, mardi ... dimanche)
var j : jour                      (2) ALLC (np_j, rg_j) CODE 2 [1 ... 7]
```

### 2.2.5. La description des modes primitifs d'ALGOL 68.

ALGOL 68 autorise les modes primitifs arithmétiques, booléens, binaires et alphanumériques. Les modes primitifs *ent* et *réel* peuvent être complétés en spécifiant la précision souhaitée par l'adjonction en nombre répété de *court* ou *long* : *long ent* est un déclareur de mode entier de double longueur. L'implanteur d'ALGOL 68 devra formaliser les précisions en $\ell i_1$, puis à la seconde étape de traduction spécifier quel est le plus grand nombre entier admis. Le mode primitif *bool* permet de spécifier des valeurs logiques, le mode primitif *bit* des chaînes de bit de longueur bloquée (fixée lors de la deuxième étape de traduction).

Le mode primitif *car* permet de déclarer une valeur de caractères, le mode primitif *cat* une suite de caractères de longueur bloquée ; le mode primitif *chaîne* une suite de caractères de longueur quelconque. La traduction des déclarations d'objets élémentaires d'ALGOL 68 pourra se faire par exemple de la façon suivante :
ent x,
ALLC (np_x, rg_x) E

long long reel a ;
ALLC (np_a, rg_a) L 2R

variables réelles de triple longueur

bit face ;
ALLC (npFace, rgFace) BIT

bool flip
ALLC (npFlip, rgFlip) BOOL

ent i = 3 ;

ent k ;
(1) ALLC (np_k, rg_k) E

ent l ;
(2) ALLC (np_l, rg_l) E

ent j = k+l;
(3) + E* (np_k, rg_k), * (np_l, rg_l)

____
(4) ALLC (np_j, rg_j) E

l : j+i ;
(5) := E 3T, (np_j, rg_j)

(n) + E* (np_j, rg_j), 3C
(n+1) := E nT, (np_l, rg_l)

La déclaration de la constante i ne donne lieu à aucune génération de triplet,
on propagera seulement la valeur de la constante dans la suite du texte (en
particulier dans la traduction de l'affectation l : = j+i). La valeur de la
constante j est calculée, il faut réserver une mémoire pour j, on génère un
triplet de code opération ALLC.

2.2.6. *Les conversions.*

Les expressions arithmétiques des langages source peuvent comporter des
opérandes de modes arithmétiques différents. Les règles de conversions à
appliquer à certains de ces opérandes sont le plus souvent implicites. Cependant
en ALGOL 68, il n'existe pas de modification qui convertirait automatiquement
une valeur complexe en une valeur réelle ou une valeur réelle en valeur entière.
En effet il n'existe pas en général de réel équivalent à un complexe, ni
d'entier équivalent à un réel. Le choix de la valeur équivalente est laissé
aux soins du programmeur par l'utilisation d'opérateurs monadiques de conver-
sions : les opérateurs *entier* et *arrd* permettent de passer d'une valeur réelle
à une valeur entière.

En PL 1 les modifications sont faites automatiquement par le compilateur quand les conversions sont implicites dans le programme source. Mais le programmeur a également le droit de choisir la modification arithmétique qui lui convient en utilisant les fonctions incorporées TRUNC, CEIL, FLOOR pour choisir la valeur entière équivalente à une valeur réelle donnée.

Remarquons que la modification *entier* d'ALGOL 68 est identique à la fonction incorporée FLOOR de PL 1.
Les opérateurs de conversion de $\ell i_1$ doivent rassembler ces différentes modifications.

En PL 1 la définition d'un mode arithmétique comporte la description du mode (REAL, COMPLEX), de la base (BINARY ou DECIMAL) de l'échelle (FIXED ou FLOAT), de la précision. Les deux opérandes d'une opération arithmétique peuvent différer en base, mode, précision et échelle. Lorsqu'ils diffèrent une conversion a lieu suivant des règles très précises. Rappelons en les grandes lignes :

a/Si les bases des deux opérandes sont différentes le facteur décimal est converti en binaire.

b/Si les modes des deux facteurs sont différents l'opérande de mode réel est converti en mode complexe.

c/Si les échelles des deux opérandes sont différentes, l'opérande en virgule fixe est converti en virgule flottante. Il existe une exception à cette règle dans le cas d'une élévation à une puissance.

d/Les règles de calcul de la précision du résultat varient suivant l'opérateur concerné. A titre d'exemple rappelons que pour une addition ou une soustraction, la précision $(p,q)$ du résultat se calcule de la façon suivante

$$p = 1 + \max(p_1 - q_1, p_2 - q_2) + \max(q_1, q_2)$$

$$q = \max(q_1, q_2)$$

où $p$ représente le nombre total de chiffres du résultat, $q$ le facteur d'échelle du résultat.

Les règles de conversion de la base, du mode, de l'échelle, de la précision peuvent être appliquées statiquement par le traducteur. Par exemple si $i$ et $j$ ont été déclarés :

$dc\ell$ i fixed decimal (9,4)

$dc\ell$ j fixed decimal (8,5)

et que l'on trouve dans une expression arithmétique l'opération $i + j$. Le traducteur peut calculer la précision du résultat à l'aide des règles précédentes, ce qui donne (11,5). Il va donc pouvoir générer les conversions correspondantes des valeurs de $i$ et $j$. On pourra écrire par exemple en $\ell i_1$ :

(n) CV REAL FIX DEC ((9,4),(11,5)) \* (npᵢ, rgᵢ)

(n+1) CV REAL FIX DEC ((8,5),(11,5)) \* (npⱼ, rgⱼ)

(n+2) + REAL FIX DEC (11,5) n T, n+1 T
On vérifie que les conversions sont paramétrées ici par les caractéristiques du mode arithmétique.

En ALGOL 60 les modes arithmétiques ne comportent que le mode entier ou le mode réel. Les opérations de conversion peuvent être soit conversion d'une valeur entière en une valeur réelle, soit conversion d'une valeur réelle en une valeur entière.

La paramétrisation de l'opérateur $\ell i_1$ des conversions est donc plus simple, on pourra écrire par exemple :

CVER qui signifie conversion d'une valeur entière en une valeur réelle

CVRE qui signifie conversion d'une valeur réelle en une valeur entière
Soit en ALGOL 60 l'affectation $s := a - t/3$. Supposons que toutes les variables
qui interviennent dans cette affectation aient été déclarées comme entiers.
L'occurrence de l'opérateur de division / implique que le résultat de la
division soit un réel, le deuxième opérande de la soustraction est un nombre
réel, il faut donc convertir la valeur du premier opérande en valeur réelle.
L'expression évaluée $a-t/3$ a ainsi un mode réel, comme la valeur à laquelle
on l'affecte est de mode entier, il faut faire une conversion de réel en
entier avant de traduire l'affectation.

$$ (1) \ CVER \ * (np_t, rg_t) $$

$$ (2) \ CVER \ 3C $$

$$ (3) \ / \ R \ 1 \ T, \ 2 \ T $$

$$ (4) \ CVER \ * (np_a, rg_a) $$

$$ (5) \ - \ R \ 4 \ T, \ 3 \ T $$

$$ (6) \ CVRE \ 5 \ T $$

$$ (7) \ := \ E \ 6 \ T, \ (np_s, rg_s) $$

## 2.3. Description de la construction tableau

Rappelons la syntaxe du déclareur effectif

**<déclareur effectif de tableau> =**

TAB [COMPRESSE] entier <dimension> ; { <dimension>}* <déclareur effectif>
<dimension> = DIME <borne> , <borne>
<borne> = <constante entière> |*(entier,entier) | entier T | Id

TAB est le code $\ell i_1$ de la construction tableau

COMPRESSE est un attribut indiquant que les éléments du tableau seront compressés en mémoire à l'implantation (c'est l'attribut PACKED de PL 1 ou PASCAL).
entier est le nombre de dimension du tableau.

En FORTRAN et en PASCAL une borne ne peut être que constante, par conséquent dans la traduction en $\ell i_1$, on ne pourra atteindre que l'alternative
<constante entière>

PASCAL

Var m : array [0...10] of integer (1) ALLC (np_m, rg_m) TAB 1

(2) DIM E 0C, 10 C

(3) E

Var mm : array [1...10] of array [3...7] of integer

(1) ALLC (mp_mn, rg_mn) TAB 1

(2) DIM E 1 C, 10 C

(3) TAB 1

(4) DIM E 3C, 7C

(5) E

Var t : packed array [0...10] of char (1) ALLC (np_t, rg_t) TAB COMPRESSE 1
est la déclaration d'une chaîne (2) DIM E 0C, 10 C
de caractère de longueur 11 (3) CH

En PL 1 une borne peut être une constante, une variable, ou le résultat
d'une expression (dans ce cas on évalue d'abord l'expression, la description
de la borne comporte alors la référence au triplet résultat de l'expression).

PL 1

dcL u (1: i,1:j) char (k-L) varying ; (1) - REAL FIX BIN(15) * (np_k, rg_k), *(np_j, rg_j)
(2) ALLC (np_u, rg_u) TAB 2
(3) DIM E 1 c, * (np_i, rg_i)
(4) DIM E 1 C, * (np_j, rg_j)
(5) VAR CH 1 T

En ALGOL 60 une borne peut être une constante entière, une variable, une expression arithmétique simple ou une expression conditionnelle. Dans ce dernier cas suivant le résultat du test cette borne peut prendre deux valeurs (et davantage dans le cas de IF imbriqués).

Puisque nous nous imposons de générer la traduction de l'expression de
test avant la description du tableau, il faut mémoriser la valeur de cette
borne dans une mémoire temporaire.

Le traitement de ce cas particulier d'ALGOL 60 nous oblige à réintro-
duire les noms au niveau du langage $L_i$ (mais ils ne s'identifient jamais
aux objets du langage source). Ces noms sont les désignations de mémoires
temporaires qui possèdent un type et une zone réservée à la suite des données
 locales à la procédure, cette zone est libérée après la dernière utilisation de
cette mémoire de manoeuvre.
integer array t (1 : if x > 3 then i, else p, 1 : j)

(1) >E * (np_x, rg_x), 3 c

(2) SINON 6 T

(4) = E * (np_i, rg_i), TEMP 1

(5) ALLERA 7 T

(6) = E * (np_p, rg_p), TEMP 1

(7) ALLC (np_t, rg_t) TAB 2

(8) DIM E 1 C, TEMP 1

(9) DIM E 1 C * (np_j, rg_j)

Le premier triplet effectue la comparaison entre la valeur de x, et la valeur 3.
Si ces valeurs sont différentes, on va se brancher au triplet 6, où on mémorise
la borne supérieure de la première dimension dans TEMP 1 ; sinon on continue
en séquence au triplet 4.

Dans tous les cas la déclaration du tableau en li_1 commence au triplet 7.

En ALGOL 68, une borne est une proposition unitaire, en $\ell i_1$ on génère
la traduction de la proposition unitaire avant la déclaration proprement dite
du tableau.

L'exemple ci-dessous montre quelle est la traduction de la déclaration
d'un rang de nombres entiers.

[10] ent t,

(1) ALLC (np, rg) TAB 1

(2) DIM E 1 C, 10 C

(3) E

L'exemple qui suit montre la traduction de la déclaration d'un tableau
de rang de 5 caractères.

[10, 0 : a+b] [5] car x,

(1) + E * (np_a, rg_a), * (np_b, rg_b)

(2) ALLC (np_a, rg_a) TAB 2

(3) DIM E 1 C, 10 C

(4) DIM E 0 C, 1 T

(5) TAB 1

(6) DIM E 1 C, 5 C

(7) CH

2.4. La construction structure

Cette construction existe dans les langages PL 1, PASCAL et ALGOL 68.

Rappelons la syntaxe d'un déclareur effectif de structure.

<déclareur effectif de structure> =

STRUCTURE [COMPRESSE] (entier,entier); <champ effectif>, { <champ effectif>}*<champ effectif> = (entier,entier) [COMPRESSE] <déclareur effectif>
Un des principaux objectifs de la traduction du langage source en langage $li_1$
est la suppression de la plupart des informations contextuelles ; c'est pourquoi
nous mémorisons la fin de la génération de chaque sous-structure.

STRUCTURE (entier,entier) marque le début de la génération d'une sous-
structure (explicité par le premier nombre entier), la fin de la génération de
la sous-structure est le triplet dont le rang est le deuxième nombre entier.
Pour la description de chaque champ on précise le début et la fin de la géné-
ration dans le doublet (entier,entier).

Afin de clarifier l'exposé, nous allons faire une remarque concernant
les modes des sélections d'un identificateur du mode structuré.

Soit en ALGOL 68 la déclaration d'identificateur suivante :

``` ALGOL 68
struct (ent no, reel prix) article ;
    l'identificateur article a pour mode rep struct (ent no, reel prix), no de
    article a pour mode rep ent, mais en li_1 comme en ALGOL 68 la description du
    champ no aura pour mode entier ; par contre une référence à la selection no de
    article aura pour mode rep ent
```

``` ALGOL 68
struct (ent no, reel prix) article ; (1) ALLC (np$_{article}$, rg$_{article}$) STRUCTURE (1,3)
```

Exemple 2

``` ALGOL 68
struct (ent no, ent nb, [1:7] struct (chaîne cheflieu, ent pop)ar)d ;
```

Exemple 3

``` mode article = struct (ent i, rep article p) :
```
Cet exemple comporte une déclaration de mode structuré d'indicateur article, deux déclarations d'identificateurs dep et dep₁ de mode article. En $\ell i_1$ on déclare deux données dont le mode est la traduction du mode article

(1) ALLC ($np_{dep}, rg_{dep}$) STRUCTURE (1,3)

(2) (2,2) E

(3) (3,3) A

(4) ALLC ($np_{dep_1}, rg_{dep_1}$) STRUCTURE (4,6)

(5) (5,5) E

(6) (6,6) A

(7) := A ($np_{dep_1}, rg_{dep_1}$), (($np_{dep}, rg_{dep}$), (2,2))

Le deuxième champ du mode structure est un nom pour traduire la récursivité.

Exemple de traduction d'une structure PL 1

DCL 1 Z

2 U

10 A FIXED DECIMAL (6)

10 B CHARACTER (II+JJ)

2 V

6 C FIXED DECIMAL (8)

6 D (1 : x,1 : y) BIN FIXED

(1) + E * ($np_{ii}, rg_{ii}$), *($np_{jj}, rg_{jj}$)

(2) ALLC ($np_z, rg_z$) STRUCTURE (2,11)

(3) STRUCTURE (3,5)

(4) (4,4) REAL FIX DEC (6)

(5) (5,5) FIX CH 1 T

(6) STRUCTURE (5,10)

(7) (6,6) REAL FIX DEC (8)

(8) (8,10) TAB 2

(9) DIM E 1 C, *($np_x, rg_x$)

(10) DIM E 1 C, *($np_y, rg_y$)

(11) REAL FIX BIN (15)

Les déclarations des niveaux disparaissent, elles sont remplacées par le code STRUCTURE suivi par un couple d'entiers indiquant le premier et le dernier triplet généré pour la structure correspondante.

Les feuilles d'une structure PL 1 sont des variables, dans la traduction $\ell i_1$ on ne décrit que le mode du champ comme en ALGOL 68, mais une sélection a pour mode _rep_ (mode du champ).

Par exemple la sélection Z.A. a bien pour mode _rep_ ent.
Autre exemple de traduction d'un tableau de structures de PL 1

<table><tr><td>DCL 1 METEO (12)</td><td>(1) ALLC (np<sub>meteo</sub>, rg<sub>meteo</sub>) TAB 1</td></tr><tr><td>2 TEMPERATURE (31)</td><td>(2) DIM E 1 C, 12 C</td></tr><tr><td>3 MAXI FIXED DEC (5,3)</td><td>(3) (3,13) STRUCTURE (3,13)</td></tr><tr><td>3 MINI FIXED DEC (5,3)</td><td>(4) (4,8) TAB 1</td></tr><tr><td>2 PRECIPITATIONS</td><td>(5) DIM E 1 C, 31 C</td></tr><tr><td>3 CUMUL MOIS FIXED DEC (6,2)</td><td>(6) (6,8) STRUCTURE (6,8)</td></tr><tr><td>3 JOURNEE (31) FIXED DEC (6,2)</td><td>(7) (7,7) FIXED DEC (5,3)</td></tr><tr><td></td><td>(8) (8,8) FIXED DEC (5,3)</td></tr><tr><td></td><td>(9) (9,13) STRUCTURE (9,13)</td></tr><tr><td></td><td>(10) (10,10) FIXED DEC (6,2)</td></tr><tr><td></td><td>(11) (11,13) TAB 1</td></tr><tr><td></td><td>(12) DIM E 1 C, 31 C</td></tr><tr><td></td><td>(13) FIXED DEC (6,2)</td></tr></table>

Exemple de traduction d'un enregistrement de PASCAL

<table><tr><td><u>type</u> date = <u>record</u> mo : (janv,fev,...)</td><td>(1) ALLC (np<sub>x</sub>, rg<sub>x</sub>) STRUCTURE (1,4)</td></tr><tr><td>day : 1...31</td><td>(2) (2,2) CODE 1 [1...12]</td></tr><tr><td>year : integer</td><td>(3) (3,3) CODE 2 [1...31]</td></tr><tr><td><u>end</u></td><td>(4) (4,4) E</td></tr><tr><td><u>var</u> x : date</td><td></td></tr></table>

## 2.5. Description de la construction ensemble

<déclareur d'ensemble> = ENS <déclareur effectif>

La syntaxe de `ci_1` autorise ainsi toutes les compositions comportant la construction ensemble. Ceci est une extension du langage PASCAL qui n'autorise que les ensembles de valeurs de type scalaire ou rang.

<table><tr><td>PASCAL</td><td>ci<sub>1</sub></td></tr><tr><td><u>type</u> jour = (lundi,mardi,...dimanche)</td><td>(1) ALLC (np<sub>s</sub>, rg<sub>s</sub>) ENS</td></tr><tr><td><u>type</u> semaine : <u>set</u> of jour</td><td>(2) CODE 1 [1...7]</td></tr><tr><td></td><td>(3) ALLC (np<sub>travail</sub>, rg<sub>travail</sub>) ENS</td></tr><tr><td><u>Var</u> s, travail, libre : semaine</td><td>(4) CODE 1 [1...7]</td></tr><tr><td>j : jour</td><td>(5) ALLC (np<sub>libre</sub>, rg<sub>libre</sub>) ENS</td></tr><tr><td></td><td>(6) CODE 1 [1...7]</td></tr><tr><td></td><td>(7) ALLC (np<sub>j</sub>, rg<sub>j</sub>) CODE 1 [1...7]</td></tr></table>

les constantes de modes ensemble pourront être décrites de la façon suivante :

* C[ ] est la formalisation en $ci_1$ de l'ensemble vide.

* C [1 {1...7}] est l'ensemble des valeurs du type jour, c'est la traduction de l'ensemble [lundi, mardi, mercredi...samedi,dimanche]

* C [* (np<sub>j</sub>, rg<sub>j</sub>)] est l'ensemble [j] construit à partir de la variable j.
## 2.6. La description de la construction repère d'ALGOL 68

Exemple 1 : traduction de la récursivité des modes.

mode article = struct (ent i, rep article p) (1) ALLC (np<sub>dep</sub>, rg<sub>dep</sub>) STRUCTURE (1,3)
article dep, dep 1 ;
(2) (2,2) E

(3) (3,3) A

p of dep := dep 1
(4) ALLC (np<sub>dep</sub><sub>1</sub>, rg<sub>dep</sub><sub>1</sub>) STRUCTURE (4,6)

(5) (5,5) E

(6) (6,6) A

(7) := A (np<sub>dep</sub> rg<sub>dep</sub>)
((np<sub>dep</sub>, rg<sub>dep</sub>),(3,3))

Le 2ème champ des objets de mode article est un pointeur. Si on veut chaîner les deux listes, on place l'adresse de dep 1 dans la 2ème feuille de la structure dep.

Exemple 2 : la traduction de la synonymie

rep ent z = t [i] (1) ORIG (np<sub>t</sub>, rg<sub>t</sub>) TAB 1

rep ent fred = t [j] (2) IND E * (np<sub>i</sub>, rg<sub>i</sub>)

(3) E

z := fred + 3 (4) ORIG (np<sub>t</sub>, rg<sub>t</sub>) TAB 1

(5) IND E * (np<sub>j</sub>, rg<sub>j</sub>)

rep ent zz ; (6) E

(7) + E 3 C, * (6T)

(8) := E 7T, 3T

zz := z,

(9) ALLC (np<sub>ZZ</sub>, rg<sub>ZZ</sub>) A

(10) := A 6T, (np<sub>ZZ</sub>, rg<sub>ZZ</sub>)

Lorsque le traducteur lit l'identité rep ent z = t [i], il place dans sa table des symboles l'identificateur z, son mode rep ent et son adresse (qui est l'adresse calculée de la variable indicée t [i], c'est-à-dire le numéro de triplet (3). Ensuite il appelle la routine de génération du code $ℓ_{i1}$ de l'adresse d'une variable indicée : la séquence de triplets (1) à (3) est générée.

Le même processus est appliqué à l'identificateur fred et la séquence de triplets (4) à (6) est générée.

Lorsque le traducteur rencontre l'affectation z := fred + 3, il doit aller rechercher en table des symboles le nom de z qui est le triplet 3 T et la valeur de fred qui est le contenu de l'adresse 6 T.
Exemple 3. Autre exemple

mode m = [1 : 10] rep ent
m x ;

ent i ;

x [2] :=i ;

rep ent (x [2]) := 100 ;

(1) ALLC (np_x, rg_x) TAB 1

(2) DIM E 1 C, 10 C

(3) A

(4) ALLC (np_i, rg_i) E

(5) ORIG (np_x, rg_x) TAB 1

(6) INDE 2 C

(7) A

(8) := A (np_i, rg_i), 5 T

(n) := E 100 C, * (7T)

x a pour mode rep [1:10] rep ent c'est-à-dire que x est un tableau de
pointeurs.

L'affectation x [2] := i signifie que l'on attribue à x 2 l'adresse de i.
Le triplet (8) traduit ce chaînage en $\ell i_1$.

L'affectation rep ent (x [2]): = 100 ; signifie qu'on attribue la valeur 100 à
la mémoire pointée par x [2]. L'adresse de cette cellule en $\ell i_1$ est * (7T)
### 3. LES REFERENCES AUX OBJETS

On trouve des références aux objets dans les instructions, instructions qu'on peut en première approximation diviser en instruction de contrôle et instructions d'affectations.

Dans une instruction d'affectation l'objet à affecter et la valeur qu'on affecte ne sont pas traitées de façon symétrique. Nous considérerons l'objet à affecter comme un contenant, en $\ell i_1$ nous en prendrons donc l'adresse. Nous considérerons la valeur qu'on affecte comme un contenu (en $\ell i_1$ nous effectuerons donc le nombre d'opérations de derepérage nécessaires pour obtenir la valeur).

En résumé, une référence à un objet en $\ell i_1$ sera soit la référence à l'adresse de cet objet, soit la référence à la valeur de cet objet.

#### 3.1. Les références aux adresses d'objets.

La référence à l'adresse d'un objet peut être une référence à l'adresse d'un objet pris dans sa totalité (c'est le descriptif, ou le triplet d'un paramètre formel, voir le paragraphe 6.2.3 "désignation de paramètres formels"), ou la référence à l'adresse d'une partie de cet objet (tranche d'un tableau, variable indicée, feuille d'une structure, sous structure). Les références aux noms de procédure qui sont les appels de procédure ne seront pas traitées ici mais dans le chapitre concernant les textes de routines.

```
<référence adresse> = <reference adresse objet> | <reference adresse element>
<référence adresse objet> = <descriptif> | (entier,entier,entier)
<référence adresse élément> = <adresse variable indicée> | <adresse tranche>
<adresse sous structure> | <adresse feuille>
<adresse variable indicée> =
ORIG <origine> TAB entier ; <indice> { <indice>; }* <déclareur effectif>
<origine> = <descriptif> | entier T
<indice> = IND E <valeur entière>
<valeur entière> = <constante entière> | *<descriptif>|**<descriptif> | entier T
<adresse tranche> =
TRANCHE entier ORIG <origine> TAB entier ; <rang> { <rang>; }*<déclareur effectif>
<rang> = <gamme> | <indice>
<gamme> = IND E <domaine>
<domaine> = ? | <valeur entière>,<valeur entière>
<adresse sous structure> = ( <descriptif> , (entier,entier))
```
### 3.1.1. Référence à l'adresse d'un objet global.

L'adresse d'un objet en $l_i$ est le descriptif ou le triplet pour un paramètre formel.

### 3.1.2. Référence à une variable indicée ou une tranche.

Pour obtenir l'adresse d'une variable indicée, il faut décrire sa fonction d'accès :

- l'adresse de l'origine du tableau est décrite par le triplet ORIG <origine> TAB entier.

Comme le tableau peut être aussi une tranche la désignation de ce tableau se fait soit par le descriptif, soit par l'adresse de la tranche.

- la valeur de chaque indice est décrite par un triplet de syntaxe IND E <valeur entière>.

Exemple

integer array u [1 : n, 1 : m] (1) ALLC (np_u, rg_u) TAB 2

(2) E

u [i,j]

(n) ORIG (np_u, rg_u) TAB 2

(n+1) IND E * (np_i, rg_i)

(n+2) IND E * (np_j, rg_j)

(n+3) E

L'exemple qui suit montre comment on décrit la référence au nom x [1,3][2] élément du tableau de tableau de caractères dont la déclaration [10,0 : a + b][5] car x ; a été traduite dans la description de la construction tableau au paragraphe 2.3

x [1,3][2]

(1) ORIG (np_x, rg_x) TAB 2

(2) IND E 1 C

(3) IND E 3 C

(4) TAB 1

(5) IND E 2 C

(7) CH

En ALGOL 68, il est possible de sélectionner une tranche d'un tableau c'est-à-dire un de ces sous tableaux. Pour prendre une tranche d'un tableau on fixe les valeurs de certains indices, les autres restent indéterminés (c'est-à-dire variant entre les bornes inférieures et supérieures) soit variant dans un domaine de valeurs plus restreint.
Exemple

[10,10] réel x ;
x [2,] est une tranche.

On peut faire désigner cette tranche par un nouvel identificateur :
rep [] réel y = x [2,] . Cette déclaration est en ALGOL 68 une synonymie entre les noms de y et le nom de la tranche x [2,] donc il ne faut pas effectuer des nouvelles allocations pour les valeurs de y. Mais la fonction d'accès des éléments de la tranche n'est pas identique à la fonction d'accès des éléments du tableau car la tranche possède une nouvelle adresse origine et les distances entre les éléments de la tranche ne sont pas forcément identiques aux distances entre les éléments du tableau (suivant que le tableau est implanté ligne par ligne ou colonne par colonne).

Il faut donc construire un nouveau vecteur de renseignements pour la
tranche sans allouer de mémoire pour les valeurs de la tranche. La déclaration
d'une tranche ne peut se traduire en $l_i_1$ par la déclaration d'un tableau

ALLC (np,r) TAB n

on utilisera un code différent le code TRANCHE. Comme on ne mémorise pas à
l'implantation le nom de la tranche on n'effectue pas en $l_i_1$ des désignations
de cette tranche par

TRANCHE (np_y, rg_y) TAB 1

mais on précise de quel tableau cette tranche est un sous tableau.

[10,10] réel x,

rep [] réel y = x [2,]

rep [] réel yy = x [2,3 :7]

yy [4] := 0 ;

(1) ALLC (np_x, rg_x) TAB 2

(2) DIM E 1 C, 10 C

(3) DIM E 1 C, 10 C

(4) R

(5) TRANCHE 1 ORIG (np_x, rg_x) TAB 2

(6) IND E 2 C

(7) IND E ?

(8) R

(9) TRANCHE 2 ORIG (np_x, rg_x) TAB 2

(10) IND E 2 C

(11) IND E 3 C, 7 C

(12) R

(14) ORIG 12 T TAB 1

(15) IND E 4 C

(16) R

(17) := R 0 C, 16 T
Comme il est possible de prendre plusieurs tranches d'un même tableau, on les numérote (il faudra réserver un vecteur de renseignements différent pour chacun). Le triplet de fin de description de chaque tranche a pour résultat l'adresse de cette tranche (le triplet 12 a pour résultat l'adresse de yy), donc pour décrire l'adresse de la variable indicée yy [4] on fait référence au triplet 12 pour décrire la fonction d'accès.

### 3.1.3. Adresse d'une feuille ou d'une sous structure.

Une sous structure ou une feuille d'une structure peut se caractériser à l'implantation par un déplacement par rapport à l'adresse de l'origine de la structure majeure. En $\ell i_1$ on peut décrire le nom d'une feuille ou d'une sous structure par deux renseignements :

- le nom de la structure majeure qui est un descriptif,

- le doublet caractérisant les triplets de début et de fin de génération de la déclaration de la feuille ou de la sous structure.

La syntaxe est donc identique pour une sous structure ou une feuille d'arbre.

`<adresse sous structure> = ( <descriptif>, (entier,entier))`

Exemple

<table><tr><td>DCL</td><td>1 Z</td><td>(1) ALLC (np<sub>Z</sub>, rg<sub>Z</sub>) STRUCTURE (1,7)</td></tr><tr><td></td><td>2 U</td><td>(2) STRUCTURE (2,4)</td></tr><tr><td></td><td>3 A BIN FIXED</td><td>(3) (3,3) REAL FIX BIN (15)</td></tr><tr><td></td><td>3 B CHARACTER (8)</td><td>(4) 4,4) FIX CH 8C</td></tr><tr><td></td><td>2 V</td><td>(5) STRUCTURE (5,7)</td></tr><tr><td></td><td>3 C BIN FIXED</td><td>(6) (6,6) REAL FIX BIN (15)</td></tr><tr><td></td><td>3 D BIN FIXED</td><td>(7) (7,7) REAL FIX BIN (15)</td></tr><tr><td>Z.A</td><td>= 3</td><td>(8) := 3 C, ((np<sub>Z</sub>, rg<sub>Z</sub>), (3,3))</td></tr></table>

### 3.2. Les références aux valeurs des objets

On peut classer les références aux valeurs des objets en trois catégories - les références aux valeurs globales des objets quel que soit leur mode, seront exprimées en $\ell i_1$ par un certain nombre d'opérations de derepérage appliquées à la désignation de l'objet en $\ell i_1$ qui est le descriptif, ou la référence à la désignation d'un paramètre formel.
La syntaxe de $\ell i_1$ recouvrant ces deux premiers cas est
$$ [ \{\langle \text{derepérage} \rangle\}^* ] \langle \text{descriptif} \rangle \mid \{\langle \text{dereperage} \rangle\}^* \quad (\text{entier, entier, entier}) $$

- les références aux valeurs d'éléments d'objets composés. On calcule d'abord le nom par une série de triplets dépendant des constructions qui interviennent dans le mode de l'objet, la valeur de l'élément est le contenu de cette adresse (il faut donc faire une opération de dérepérage sur le nom).

La syntaxe correspondante de $\ell i_1$ est :

* (entier T)

- Les références aux valeurs de constantes décrites explicitement.

La syntaxe est :
$$ <valeur> C $$

avec

$$ <valeur> = < valeur \ mode \ primitif> \mid <valeur \ construction> $$

Nous ne préciserons pas plus ici la description des valeurs de mode primitif, cela est sans intérêt.

Pour les valeurs d'une construction tableau, nous utiliserons les notations des propositions collatérales d'ALGOL 68 par exemple (9,10,11) est un rang de trois nombres entiers.

Pour les valeurs d'une construction ensemble, nous utiliserons la notation `entier[{entier...entier}]` où le premier nombre entier situé immédiatement après le crochet ouvrant a pour valeur le numéro du code, les entiers situés entre accolades décrivent les valeurs scalaires.
## 4. INSTRUCTIONS D'AFFECTATION

La traduction en $\ell i_1$ d'une affectation du langage source ne fera pas
jouer le même rôle à la partie gauche qu'à la partie droite. Considérons
une instruction source A = B ; cette instruction signifie que la valeur de A
est modifiée par la valeur de B, il faut donc traduire la partie gauche
d'une affectation par une adresse et la partie droite par une valeur

En $\ell i_1$ on dira que la référence à l'objet A est une référence à son
nom et que la référence à l'objet B est une référence à sa valeur.

La syntaxe d'une instruction d'affectation en $\ell i_1$ est :

`<affectation> = : = <description mode> <reference valeur>, <reference adresse> | <mode primitif> TAB entier ( <lentier> ) <reference valeur>, ( <lentier> )`

`<reference adresse>`

`<description mode> = <mode primitif> | ENS`

Les exemples qui suivent illustrent cette syntaxe (nous rappelons d'abord
la traduction des déclarations) :

[10] ent t;

(1) ALLC (np_t, rg_t) TAB 1
(2) DIM E 1 C, 10 C
(3) E

rep ent z = t [i];

(4) ORIG (np_t, rg_t) TAB 1
(5) IND E * (np_i, rg_i)
(6) E
(7) ALLC (np_x, rg_x) E
(8) := E 3C, 6T

ent x;
(9) := E * (np_z, rg_z), (np_x, rg_x)
z := 3;
(10) := E * (np_x, rg_x), 6T
x := z;
(11) ALLC (np_zz, rg_zz) A
z := x;
(12) := A (np_z, rg_z), (np_zz, rg_zz)
rep rep ent zz;
(13) ALLC (np_u, rg_u) TAB 1
zz := z;
(14) DIM E 1C, * (np_x, rg_x)
[1 : x] ent u;
(15) E
t := u;
(16) := TAB 1 (14) * (np_u, rg_u), (2) * (np_t, rg_t)

14 est la référence au triplet qui décrit la dimension de u,
2 est la référence au triplet qui décrit la dimension de t.

Ces informations permettront de générer le code de comparaison des bornes
à l'exécution.
# 5. OPERATIONS SUR LES DONNEES

## 5.1. Les opérations associées aux modes primitifs.

A chaque mode primitif d'un langage algorithmique sont associés des opérateurs binaires ou unaires.

Aux modes arithmétiques sont associés les opérateurs binaires, d'addition, de soustraction, les opérateurs de relations, les opérateurs unaires (moins, conversions).

Au mode logique on peut associer les opérateurs binaires intersection, union, l'opérateur unaire négation... . Au mode primitif chaîne on associera naturellement l'opérateur de concaténation.

Les modes primitifs sont un paramètre de langage $\ell i_1$, les opérateurs associés à ces modes primitifs sont donc des paramètres du langage $\ell i_1$. Dans la traduction d'un langage source particulier en $\ell i_1$ on ne pourra atteindre que quelques unes des alternatives de la règle de définition des opérateurs, celles qui correspondent à ce langage source spécifique. Les opérations portent sur les valeurs des objets qui sont soit des objets de mode primitif, soit des parties d'objets de mode primitif. La syntaxe des opérateurs associés aux modes primitifs peut se formaliser de la manière suivante :

<opération simple> = <binaire simple> <mode primitif> <opérande>, <opérande> |
<unaire simple> <mode primitif> <opérande>
<opérande> = <référence valeur>
<binaire simple> = + | - | × | / | < | ≪ | > | ≫ | EG | || | ET | OU
<unaire simple> = - | NON

Exemples

$$a \geq b$$

$$\geq E \quad *(np_a, rg_a), \quad *(np_b, rg_b)$$

$$i + j$$

$$+ E \quad *(np_i, rg_i), \quad *(np_j, rg_j)$$

$$t(i,j) + k$$

(1) ORIG (np_t, rg_t) TAB 2

(2) IND E * (np_i, rg_i)

(3) IND E * (np_j, rg_j)

(4) E

(5) + E *(4T), *(np_k, rg_k)
## 5.2. Les opérations associées aux constructions

### 5.2.1. Les opérations associées à la construction tableau.

En PL 1 il est possible d'effectuer des opérations infixées entre deux tableaux de même mode ayant même dimension et dont les bornes sont identiques. Dans notre système la vérification des modes et des dimensions se fait pendans la première étape de traduction ainsi que la vérification des bornes si elles sont constantes.

Si les bornes sont dynamiques la sémantique du code opérateur en $\ell i_1$, comportera la génération de code permettant de tester l'égalité de ces bornes à l'exécution.

Exemple

DCL A(I,J) BIN FIXED;

DCL B(I,K) BIN FIXED;
A = A + B;

(1) ALLC (np_a, rg_a) TAB 2
(2) DIM E 1 C, *(np_i, rg_i)
(3) DIM E 1 C *(np_j, rg_j)
(4) E;

(5) ALLC (np_b, rg_b) TAB 2
(6) DIM E 1 C, *(np_i, rg_i)
(7) DIM E 1 C, *(np_j, rg_j)
(8) E;

(n) + E TAB 2 (2,3) *(np_a, rg_a), (6,7)* (np_b, rg_b)
(n+1):=E TAB 2 (2,3) (n T), (2,3) (np_a, rg_a)

Les bornes des tableaux A et B sont dynamiques, lorsqu'on génère en $\ell i_1$ le triplet d'addition entre les deux tableaux, il faut mémoriser les informations sur les bornes qui permettront de générer à l'étape suivante les instructions de comparaison entre les bornes. C'est pourquoi nous rappelons les numéros de triplets de description de chaque dimension.

La syntaxe $\ell i_1$ des opérations globales entre deux constructions tableaux peut donc s'écrire :

<opération tableau> = <opération tableau binaire> | <opération tableau unaire>
<opération tableau binaire> =
<binaire simple> <mode primitif> TAB entier ( <lentier> ) <reference valeur>,
( <lentier> ) <reference valeur>
<opération tableau unaire> =
<unaire simple> <mode primitif> TAB entier ( <lentier> ) <reference valeur>
<lentier> = entier {,entier}*

### 5.2.2. Les opérations associées à la construction ensemble.

Seul le langage PASCAL autorise la construction ensemble. Les opérateurs associés à ces objets sont : l'union, l'intersection, la différence au sens des ensembles et les opérateurs de relations (tests d'égalité ou d'inégalité, test d'inclusion).

<opération ensemble> = <operateur d'ensemble> ENS <reference valeur>,
<reference valeur>
<opérateur d'ensemble> = + | × | - | = | ≠ | < = | > =

Les opérateurs ainsi décrits conformément à la terminologie de Wirth sont l'union, l'intersection, la différence, les tests d'égalité, d'inégalité, d'inclusion.

En PASCAL on peut tester l'appartenance d'une valeur de type scalaire à un ensemble, cet opérateur agit donc sur une valeur de mode primitif et une construction ; il faut donc définir en $l_i_1$ une syntaxe particulière pour traduire la relation d'appartenance :

<opération appartenance> =
DANS CODE entier *<descriptif>, ENS *<descriptif>
on recherche si la valeur de la variable de type scalaire est une des valeurs composant l'ensemble.

Exemple de traduction de quelques instructions de PASCAL :

type jour = (lundi, mardi, mercredi, jeudi, vendredi, samedi, dimanche)

type semaine = set of jour (1) ALLC (np_s, rg_s) ENS

Var s, travail, libre : semaine (2) CODE 1 (1...7)

j : jour (3) ALLC (np_travail, rg_travail) ENS

(4) CODE 1 (1...7)

(5) ALLC (np_libre, rg_libre) ENS

(6) CODE 1 (1...7)

begin travail := [] ; (7) ALLC (np_j, rg_j) CODE 1 (1...7)

libre := [] ; (8) := ENS C [], (np_travail, rg_travail)

(9) := ENS C [], (np_libre, rg_libre)

s := [lundi,mardi,...dimanche]; (10) := ENS C [1{1...7}], (np_s, rg_s)

j := samedi; (11) := CODE 1 C {6} , (np_j, rg_j)

libre := [j] + libre + [dimanche] (12) + ENS C [* (np_j, rg_j)], *(np_libre, rg_libre)

(13) + ENS (12 T), C [1{7}]

(14) = ENS (13 T), (np_libre, rg_libre)
On peut faire quelques remarques à propos de la traduction de la dernière instruction libre : = [j] + libre + [dimanche]

J a été déclarée comme variable de type scalaire, en plaçant j entre crochets on créé un ensemble dont la portée est l'instruction, en $\ell i_1$ la valeur de cet ensemble est représentée par

C [*(np_j, rg_j)] constante de mode ensemble qui comporte un seul élément la valeur de j*(np_j, rg_j). De même, dimanche est une valeur scalaire dont on fait un ensemble en le plaçant entre crochets, en $\ell i_1$ on représente cette constante de mode par [1{7}] où 1 est le codage du type scalaire et 7 la valeur appropriée.
## 6. LES TEXTES DE ROUTINE

Rappelons la syntaxe $LI_1$ de la déclaration d'un texte de routine.

<texte de routine> = ROUTINE <descriptif> entier ; <ltrip> ; END; |
ROUTINE * (entier,entier,entier) entier ; <ltrip> ; END ;

Il est inutile de déclarer les types des paramètres formels, mais dans les références aux paramètres formels dans les instructions, il faut évidemment les indiquer. Il faut également désigner en $l_i_1$ les paramètres formels comme on a désigné les variables locales, un moyen simple de coder cette désignation est de concatenéner à la désignation du texte de routine, un nombre entier qui est le rang du paramètre formel. La désignation d'un paramètre formel est donc un triplet de nombres entiers.

Au résultat d'une procédure on attribuera par convention le rang 0. Le résultat d'une procédure doit avoir une mémoire qui lui est réservée, on fera donc une déclaration de variable pour le résultat.

### 6.1. La traduction des procédures d'ALGOL 68

proc (ent,ent) ent c : (ent a, ent b) = ax(a+b)

proc (ent,ent) ent d ;
d := c ;

(1) ROUTINE (np_c, rg_c) 2

(2) ALLC (np_c, rg_c, 0) E

(3) + E * (np_c, rg_c, 1), * (np_c, rg_c, 2)

(4) x E * (np_c, rg_c, 1), 3T

(5) := E 4T, (np_c, rg_c, 0)

(6) END

(7) ALLC (np_d, rg_d) Et

(8) := Et 1T, (np_d, rg_d)

Pour traduire la déclaration de variable procédure d, on génère le triplet (7) qui est une réservation d'étiquette. En effet, l'adresse d'un texte de routine est une adresse dans le code, et il faut distinguer l'adresse dans le code de l'adresse en mémoire pour l'étape suivante de traduction.

L'affectation d'un texte de routine à cette variable peut donc s'exprimer en $l_i_1$ par une affectation d'étiquette, la valeur de l'étiquette du texte de routine c est le triplet (1).

En ALGOL 68 le mécanisme de passage des arguments s'exprime par définition par une identité entre le paramètre formel et le paramètre effectif. Dans l'exemple
qui précède le mécanisme de passage des paramètres peut s'écrire :

ent a = 3 ;

ent b = 2 ;

a et b étant des paramètres formels, on ne peut évidemment pas effectuer la propagation de constantes dans le code du texte de la routine, puisque le paramètre effectif varie avec chaque appel. Il faut donc traiter le paramètre effectif comme une valeur calculée et remplir une zone de mémoire attribuée au paramètre formel avec la valeur calculée du paramètre effectif. Ceci sera réalisé par une opération d'affectation.

d (3,2) ;

APPEL* (np<sub>d</sub>, rg<sub>d</sub>) 2

:= E 3C, (* (np<sub>d</sub>,rg<sub>d</sub>), 1)

:= E 2C, (* (np<sub>d</sub>,rg<sub>d</sub>), 2)

FINAPPEL

un triplet de code opération APPEL désigne la procédure appelée, il comporte également le nombre d'arguments. Pour chaque argument on exprime l'équivalence paramètre formel paramètre effectif par une affectation.

La syntaxe d'un appel de procédure en $\ell i_1$ est :

APPEL <descriptif> entier ; [<ℓ<sub>equi</sub>>] ; FINAPPEL

<ℓ<sub>equi</sub>> = {<affectation>}*

Dans l'exemple précédent le passage des arguments se traduit par une affectation des valeurs. Dans l'exemple qui suit le passage des arguments se traduit par une affectation de noms.

proc kwic (rep chaîne r) neutre :

(1) ROUTINE (np<sub>kwic</sub>, rg<sub>kwic</sub>) 1

début ... fin ;

(2)

chaîne s := "algol" ;

(n) END

(n+1) APPEL (np<sub>kwic</sub>, rg<sub>kwic</sub>) 1

kwic (s) ;

(n+2) := A (np<sub>s</sub>, rg<sub>s</sub>), (np<sub>kwic</sub>, rg<sub>kwic</sub>, 1)

## 6.2. La traduction des procédures d'ALGOL 60

En ALGOL 60 les modes de passage sont par valeur ou par nom.

### 6.2.1. La traduction du passage par valeur.

Si un paramètre formel est déclaré par valeur, une zone de mémoire lui est effectivement réservée, cette zone est initialisée avec la valeur de l'argument. La valeur du paramètre formel peut être modifiée en cours d'exécution du corps de la procédure, le paramètre formel est une variable au sens d'ALGOL 68. Dans le passage par valeur la procédure ne peut en aucune façon
modifier la valeur de l'argument. En $\ell i_1$ on réserve une zone de mémoire au
paramètre passé par valeur en générant un triplet ALLC. Le passage des paramètres
s'exprime en $\ell i_1$ par l'affectation des valeurs des arguments aux paramètres.

procedure h (x,y) ; value x,y ;

integer x,y ;

begin

x := x + 5

y := y - 1 .

end ;

h(0,1) ;

(1) ROUTINE (np_h, rg_h) 2

(2) ALLC (np_x, rg_x) E

(3) := E (np_h, rg_h, 1), (np_x, rg_x)

(4) ALLC (np_y, rg_y) E

(5) := E (np_h, rg_h, 2), (np_x, rg_x)

(6) + E 5C, (np_x, rg_x)

(7) := E 6T, (np_x, rg_x)

(8) - E (np_y, rg_y), 1C

(9) := E 8T, (np_y, rg_y)

(10) END

(11) APPEL (np_h, rg_h) 2

(12) := E O°C, (np_h, rg_h, 1)

(13) := E 1C, (np_h, rg_h, 2)

(14) FINAPPEL

6.2.2. La traduction du passage par nom.

Le mécanisme du passage par nom d'ALGOL 60 peut se traduire par la
génération d'une procédure qui calcule l'adresse de l'argument. A chaque
référence au paramètre formel dans le corps de la procédure, on génère un
appel à ce sous-programme.

procédure r (x,i) ;

x := 2,

i := 5 ;

end ;

r(b [j×2],j)

(1) ROUTINE (np_r, rg_r) 2

(2) APPEL * (np_r, rg_r, 1) 0

(3) FINAPPEL

(4) := E 2C, (* (np_r, rg_r, 1),0)

(5) APPEL * (np_r, rg_r, 2) 0

(6) FINAPPEL

(7) := E 5C, (* (np_r, rg_r, 2),0)

(8) END

(9) ROUTINE (np_ax,rg_ax) 0

(10) ALLC (np_ax,rg_ax,0) A

(11) ×E 2C , * (np_j,rg_j)

(12) ORIG (np_b,rg_b) TAB 1

(13) IND E 11T

(14) E

(15) :=A 14T , (np_ax,rg_ax,0)

(16) END
(17) ROUTINE (np_ai, rg_ai) 0
(18) ALLC (np_ai, rg_ai, 0) A
(19) :=A (np_j, rg_j) , (np_ai, rg_ai, 0)
(20) END

(21) APPEL (np_r, rg_r) 2

(22) :=ET 9T , (np_r,rg_r,1)

(23) :=ET 17T , (np_r,rg_r,2)

(24) FINAPPEL

Avant l'appel de la procédure r, on génère les textes de routine de calcul
de l'adresse des arguments.

Le texte de routine (np_ax, rg_ax) calcule l'adresse de b [j×2], le texte de
routine (np_ai, rg_ai) calcule l'adresse de j.

A chaque référence au paramètre formel x dans la procédure, on génère un appel
au texte de routine (np_ax, rg_ax) pour transmettre l'adresse du dernier texte
de routine, on considère que le paramètre formel x est de mode adresse, donc
le passage de paramètre de r se traduit par une identité des adresses du
paramètre formel x et de la routine (np_ax, rg_ax). Soit l'identité suivante
= A (np_ax, rg_ax), (np_r, rg_r, 1)

Pour traduire l'instruction ALGOL x := 2, on génère d'abord un appel à la
routine de calcul de l'adresse de x: cette routine a pour adresse
(np_r, rg_r, 1).

6.2.3. La désignation des paramètres formels

Dans ce qui précède, nous avons désigné un paramètre formel par un
triplet d'entiers constitué par le descriptif de la procédure auquel se
rapporte ce paramètre formel suivi du rang de ce paramètre formel. On aurait
pu se contenter du rang puisque dans les références aux paramètres formels
dans le corps de la procédure, il n'y a pas d'ambiguité et dans l'appel non
plus. Cependant dans le cas où le paramètre effectif est le paramètre formel
d'une autre procédure, on ne peut pas se contenter du rang pour décrire le
paramètre formel d'une autre procédure.

Exemple

begin

procedure p(u); integer u;
value u;
procédure g(y); integer y;
value y,

g(u);

ROUTINE (np_p, rg_p) 1

ALLC (np_p, rg_p, 1) E

ROUTINE (np_g, rg_g) 1
ALLC (np_g, rg_g, 1) E

APPEL (np_g, rg_g) 1
= E * (np_p, rg_p, 1), (np_g, rg_g, 1)

FINAPPEL
### 6.2.4. La génération de la vérification des types.

Lorsque le paramètre formel est une procédure spécifiée par nom, il n'est pas possible de vérifier statiquement la concordance des types. Il faut générer en $\ell i_1$ une routine de vérification des types. Montrons comment cela peut être réalisé sur un exemple.

```
begin integer x; real y;
    procedure h(a,b): integer a;
        real b;
    procedure p (g); procédure g
        g(x,y)
end

A
    ROUTINE (np_h, rg_h) 2
    END

B
    ROUTINE (np_p, rg_p) 1
    APPEL (np_verif, rg_verif)
        = chaîne 'E'C, *(np_verif, rg_verif, 1)
        = chaîne 'R'C, *(np_verif, rg_verif, 1)
    FINAPPEL

C
    APPEL (np_p, rg_p, 1) 2
        = E* (np_x, rg_x), *(np_p, rg_p, 1) 1
        = E* (np_y, rg_y), (* (np_p, rg_p, 1), 2)
    FINAPPEL
end

p(h)

D
    ROUTINE (np_verif, rg_verif) 2
        * Comparer la valeur du 1er paramètre formel et la chaîne constante 'E' type du 1er paramètre formel de h
        * Comparer la valeur du 2ème paramètre formel et la chaîne constante 'R' type du 2ème paramètre formel de h
END

E
    APPEL (np_p, rg_p) 1
    :=ET 1T, (np_p,rg_p,1)
    FINAPPEL
```

Lors de l'appel de p ; le traducteur connaît le nom h, donc les types des paramètres formels de h ; entier, réel.

On peut donc définir à ce niveau le texte d'une routine désigné en $\ell i_1$ par $(np_{verif}, rg_{verif})$ à deux paramètres formels de type chaîne. Dans le corps de cette procédure on compare la valeur du type du 1er paramètre formel de h (la constante chaîne 'E') à la valeur du paramètre formel ; on effectue le même test pour la valeur du 2ème paramètre formel.
Puis on génère en $\ell i_1$ l'appel de la procédure p proprement dite dans la séquence de code E, le paramètre effectif A étant une procédure, le passage de paramètre se traduit par une affectation d'adresse dans le code, c'est-à-dire d'étiquette or la valeur de l'étiquette de la routine h est le triplet numéro 1 :

$$ :=ET \ 1T, (np_p, rg_p, 1) $$

Pour traduire l'appel g(x,y) il faut d'abord vérifier que les types de x et y sont corrects, pour cela on appelle en $\ell i_1$ la procédure ($np_{verif}, rg_{verif}$) avec pour arguments les chaînes de caractère codant les types de x et y. Ceci est constitué par la séquence de code $\ell i_1$ B. Puis on appelle la procédure dont l'adresse est la valeur du 1er paramètre formel de p sa désignation est $*(np_p, rg_p, 1)$ et on traduit le passage des arguments x et y. Ceci est constitué en $\ell I_1$ par la séquence de code C.

### 6.3. La traduction des procédures PL 1.

En PL 1 les paramètres sont passés par référence ; c'est-à-dire qu'on communique à la procédure qui va s'exécuter les adresses des arguments. Le passage des paramètres s'exprime donc en $\ell i_1$ par des affectations de noms.

dcl i ;                      (1) ALLC (np_i,rg_i) REAL FIX BIN (15)
dcl tab(20) ;                 (2) ALLC (np_tab,rg_tab) TAB 1
f:proc(j) ;                  (3) DIM E iC, 20C
dcl j ;                      (4) REAL FIX BIN (15)
dcl k ;                      (5) ROUTINE (np_f,rg_f) 1
j=k ;                        (6) ALLC (np_k,rg_k) REAL FIX BIN (15)
end ;                       (7) := REAL FIX BIN (15) *(np_k,rg_k) , (np_f,rg_f,1)
call f.tab(i)) ;              (8) END
                            (9) ORIG (np_f,rg_f) TAB 1
                        (10) IND E *(np_i,rg_i)
                        (11) REAL FIX BIN (15)
                        (12) APPEL (np_f,rg_f) 1
                        (13) := A 11T , (np_f,rg_f, 1)
                        (14) FINAPPEL
# 7. LES STRUCTURES DE CONTROLE DE LI 1

En résumé on peut dire que les structures de contrôle des langages algorithmiques sont constituées par les instructions de branchement inconditionnelles, les instructions de branchement conditionnelles, les boucles.

## 7.1. Les instructions de branchement inconditionnelles.

En langage source, elles se présentent sous la forme d'une instruction de branchement à une constante étiquette alphanumérique, ou une variable indicée de mode primitif étiquette (cas des tableaux d'étiquettes de PL 1). On peut traiter un aiguillage d'ALGOL 60 comme un tableau à une dimension d'étiquettes.

### 7.1.1. La traduction des branchements aux constantes étiquettes.

Au cours de la traduction du langage source en langage $l_i$, il est possible d'associer à chaque définition de constante étiquette, le numéro du triplet où commence la traduction de l'instruction étiquetée. Dans une instruction de branchement, on remplace la référence à une constante étiquette par le numéro du triplet où commence la traduction de l'instruction étiquetée.

Dans un langage à structure de blocs, il est possible qu'à l'exécution cette instruction de branchement provoque un changement de niveau de procédure. Comme le traducteur peut mémoriser le niveau de procédure de la définition de l'étiquette, il est possible de reporter ce niveau dans l'instruction de branchement. Cette information permettra dans la suite du processus de traduction de restaurer les registres locaux comme pour une instruction de sortie de procédure.

La syntaxe d'une instruction de branchement à une constante étiquette est donc en $l_i$

ALLERA (entier) entier T

Exemple

```
goto toto;

i := j + 1;

toto : l := i;
```

(n) ALLERA ($np_{toto}$) n+3 T
(n+1) + E 1C, *(np_j, rj_j)

(n+2) := E n+1 T, (np_i, rj_i)

(n+3) := E *(np_i, rg_i), (np_l, rg_l)

### 7.1.2. La traduction des branchements aux étiquettes d'un tableau.

En PL 1 il est possible de déclarer un tableau constant d'étiquettes de la façon suivante :
DCL Z(3) LABEL;

Z(1) : ____
____

Z(2) : ____

Z(3) : ____

goto Z(i);

A la traduction, il est possible d'associer à chaque variable indicée Z(1), Z(2), Z(3), le numéro du triplet où commence la traduction des trois instructions étiquetées. On va donc traiter en $\ell i_1$ le tableau Z comme un tableau constant d'étiquettes dont les valeurs sont les adresses dans le code $\ell i_1$ c'est-à-dire des numéros de triplets. Une instruction de branchement goto Z(i) se traduit par un branchement à une adresse dans le code qui est le contenu de l'adresse Z(i)

dcl Z(3) label;

(1) ALLC (np<sub>Z</sub>,rg<sub>Z</sub>) TAB 1

(2) DIM E 1C, 3C

(3) Et

(4) := Et TAB 1 (2) (n<sub>1</sub>, n<sub>2</sub>)T, (2) (np<sub>sw</sub>,rg<sub>sw</sub>)

Z(1) : ____

(n<sub>1</sub>) ____

Z(2) : ____

(n<sub>2</sub>) ____

Z(3) : ____

(n<sub>3</sub>) ____

goto Z(i)

(n) ORIG (np<sub>Z</sub>,rg<sub>Z</sub>) TAB 1

(n+1) IND E* (np<sub>i</sub>,rg<sub>i</sub>)

(n+2) Et

(n+3) ALLERA* (n+2 T)

Ici il est inutile de préciser le niveau de procédure, puisqu'on reste toujours dans le niveau en cours.

On peut traiter de façon absolument identique un aiguillage d'ALGOL 60.

begin aiguillage sw : E,F,

(1) ALLC (np<sub>sw</sub>,rg<sub>sw</sub>) TAB 1

(2) DIM E 1C, 2C

(3) Et

(4) := Et TAB 1 (2) (n<sub>1</sub>, n<sub>2</sub>)T, (2) (np<sub>sw</sub>,rg<sub>sw</sub>)

E : ____

(n<sub>1</sub>) ____

F : ____

(n<sub>2</sub>) ____

goto sw [i+j]

(n) + E* (np<sub>i</sub>,rg<sub>i</sub>), (np<sub>j</sub>,rg<sub>j</sub>)

end

(n+1) ORIG (np<sub>sw</sub>,rg<sub>sw</sub>) TAB 1

(n+2) IND E* (n T)

(n+3) Et

(n+4) ALLERA* (n+3 R)
### 7.1.3. La traduction des branchements aux variables étiquettes.

En PL 1 on peut déclarer une variable de type LABEL. Elle peut prendre comme valeurs des constantes étiquettes d'instructions, par l'intermédiaire d'instructions d'affectation.

Une instruction de branchement peut être traduite par une instruction de branchement à la valeur d'une variable de type étiquette.

Mais il se peut qu'en certains points du programme une référence à cette valeur soit illégale.

Exemple :

```
begin dc l x label;
```

```
x = b;
```

```
goto x;
```

```
b : ______
```

```
begin
```

```
c : ______
```

```
x = c;
```

```
end;
```

```
goto x; |*la référence à x est incorrecte ici car x a pour valeur c
```

```
end;      qui est inconnu en ce point du programme* |
```

En général le contrôle de la validité du branchement n'est possible qu'à l'exécution. Il faut donc conserver les informations qui permettent d'effectuer ce contrôle à l'exécution, dans la syntaxe de $\ell i_1$. Le niveau d'imbrication des blocs n'est pas une information suffisante car il ne permet pas de lever l'ambiguité entre deux blocs parallèles.

A la traduction entre PL 1 et $\ell i_1$ on pourra associer deux numéros :

- un numéro d'ordre,

- et le niveau d'imbrication du bloc.

L'exemple suivant montre comment on peut appliquer cette numérotation.

```
h : proc ;
```

<table><tbody><tr><td>begin</td><td>(1,1)</td></tr><tr><td>begin</td><td>(2,2)</td></tr><tr><td>begin<br>end</td><td>(3,3)</td></tr><tr><td>begin<br>end</td><td>(4,3)</td></tr><tr><td>end</td><td></td></tr><tr><td>begin</td><td>(5,2)</td></tr><tr><td>begin</td><td>(6,3)</td></tr><tr><td>begin</td><td>(7,4)</td></tr></tbody></table>
En $\ell i_1$ on assurera à chaque constante étiquette le niveau de procédure, le numéro d'ordre du bloc, le niveau d'imbrication du bloc où elle est définie. Dans une instruction de branchement à une variable label on indique le niveau de procédure en cours, le numéro d'ordre du bloc, le niveau d'imbrication du bloc en cours.

begin dcℓ x label;

x = b

goto x;

b : ______

begin

c : ______

x = c

end

goto x;

(1) ALLC (np_x, rg_x) Et

(2) : = Et (np, (1,1))n₁ T, (np_x, rg_x)

(3) ALLERA (np, (1,1)) *(np_x, rg_x)

(n₁) ______

(n₂) ______

(n) : = Et (np, (2,2))n₂T, (np_x, rg_x)

(m) ALLERA (np, (1,1)) *(np_x rg_x)

### 7.1.4. La syntaxe $LI_1$ des instructions de branchements :

<branch> = ALLERA entier T | ALLERA *(entier T) | ALLERA (entier, (entier, entier)) *<descriptif>

## 7.2. Les instructions de branchement conditionnelles.

En langage source, elles comportent toutes un test de la valeur d'une expression. Le résultat de ce test peut posséder une valeur binaire (cas des instructions conditionnelles d'ALGOL 60, PL/1) ou ternaire (cas des "IF" arithmétiques de FORTRAN) ou n-aire (CASE de PASCAL, GOTO calculé de FORTRAN).

Dans tous les cas on peut décomposer le test en une suite de tests ayant chacun pour résultat une valeur binaire. Nous adoptons donc en $\ell i_1$ la forme syntaxique correspondant au test d'une expression logique. Comme on peut toujours générer le code de la clause "alors" à la suite du triplet de test, le triplet de test fait référence seulement au début de la clause "sinon".

### SINON entier T

Exemple 1 : traduction du IF arithmétique de FORTRAN.

IF (a+b) 1,2,3 (1) + a,b

1 ______

(2)' <E 1T, OC

(3) SINON n T

2 ______ (a+b) <0 { traduction de la suite d'instructions commençant par l'étiquette 1
ALLERA n'' T

3 ——

(n) EG E 1T, OC

(n₁) SINON n' + 1 T

{ traduction de la suite d'instructions
(a+b) = 0 { commençant par l'étiquette 2

(n') ALLERA n'' T

{ traduction de la suite d'instructions
(n'-1) commençant par l'étiquette 3

(a+b) >0

Exemple 2 : instruction conditionnelle d'ALGOL 60.

IF i < j + 1 THEN IF i < j-2 THEN L := 2 ELSE L := 1 ELSE L := 0

(1) + E *($np_i$, $rg_i$), *($np_j$, $rg_j$)

(2) < E *($np_i$, $rg_i$), (1 T)

(3) SINON 11 T

(4) - E *($np_j$, $rg_j$), 2C

(5) < E *($np_i$, $rg_i$), (4T)

(6) SINON 9 T

(7) := E 2C, ($np_\ell$, $rg_\ell$)

(8) ALLERA 12 T

(9) := E 1C, ($np_\ell$, $rg_\ell$)

(10) ALLERA 12 T

(11) := E 0C, ($np_\ell$, $rg_\ell$)

### 7.3. Les boucles.

Dans le langage source, elles possèdent la même forme syntaxique externe : après un code opération indiquant qu'il s'agit d'une boucle (DO ou FOR), on définit une variable de contrôle agissant sur les instructions de la boucle.

Or l'interprétation d'une instruction de boucle diffère suivant les langages : en PL 1 les valeurs limites de la variable de contrôle sont calculées une fois pour toutes (la variable de contrôle, et les variables intervenant dans les expressions limites peuvent cependant être modifiées en cours d'exécution dans la boucle) ; en ALGOL 60 la valeur limite supérieure de la variable de contrôle et le pas sont recalculés à chaque itération.

C'est pourquoi une expansion complète de la boucle combinant le test et les instructions de saut est la seule traduction compatible avec les différentes sémantiques des langages considérés.
Exemple 1 : Traduction d'une boucle d'ALGOL 60.

for i := a + b step 2 until a + 2 × b (1) + E* (np_a, rg_a, (np_b, rg_b)

do ... (2) := E 1T, *(np_i, rg_i)

begin (3) × E 2C, *(np_n, rg_b)

a := a + 1 (4) + E (np_a, rg_a), 3T

end (5) ≤ E (np_i, rg_i), 4T

(6) SINON n+5 T

...

(n) + E 1C, *(np_a, rg_a)

(n+1) := E n T, (np_a, rg_a)

(n+2) + E (np_i, rg_i), 2C

(n+3) := E n+2 T, (np_i, rg_i)

(n+4) ALLERA 3T

Exemple 2 : Traduction d'une boucle PL 1

do i = 2 to a × b; (1) := 2 2C, *(np_i, rg_i)

...

(2) × E *(np_a, rg_a), *(np_b, rg_b)

(3) < E *(np_i, rg_i), 2T

(4) SINON n+3 T

end;

...

(n) + E 1C, *(np_a, rg_a)

(n+1) := E nt, *(np_i, rg_i)

(n+2) ALLERA 3T

Pour les boucles PL 1, puisque les valeurs limites de la variable de contrôle sont calculées une fois pour toutes, on doit effectuer l'expansion de la boucle en générant d'abord le test sur les variables de contrôle.

Certaines boucles possèdent une clause supplémentaire, la clause tant que (boucles FOR WHILE d'ALGOL 60, DO WHILE de PL 1, REPEAT WHILE de FORTRAN).

On doit donc faire l'expansion de la boucle en introduisant un test supplémentaire.

Exemple de traduction d'une boucle DO WHILE de PL 1

Do i = 1 to 10 while (A = B); (1) := E 1C, *(np_i, rg_i)

...

(2) < E *(np_i, rg_i), 10 C

(3) SINON n+3 T
end;

(4) EG E *(np<sub>a</sub>,rg<sub>a</sub>), *(np<sub>b</sub>,rg<sub>b</sub>)

(5) SINON n+3 T

⋮

(n) + E 1C, *(npᵢ,rgᵢ)

(n+1) = E n T, *(npᵢ,rgᵢ)

(n+2) ALLERA 2T

(n+3)

### 7.4. La syntaxe $\ell i_1$ des instructions de contrôle.

<contrôle> = <branch> | SINON entier T
<branch> = ALLERA entier T | ALLERA *(entier T) |
ALLERA (entier,(entier,entier))*<descriptif>
## 8. LA SYNTAXE DE LI 1

```
<prog> = <lcode>

<lcode> = <lcode> <code> | <code>
<code> = <texte de routine> | <ltrip> | <call>

<ltrip> = <ltrip> <trip> | <trip>
<texte de routine> = ROUTINE <descriptif> entier; <ltrip>; END |
ROUTINE * (entier,entier,entier) entier; <ltrip>; END

<trip> = <declaration> | <affectation> | <opération> | <contrôle>
<declaration> = ALLC <descriptif> <déclareur effectif> |
ALLC (entier,entier,entier) <declareur effectif>

<declareur effectif> = <mode primitif> | <declareur effectif de tableau> |
<declareur effectif de structure> | <declareur d'ensemble>

<declareur effectif de tableau> =
TAB [COMPRESSE] entier; <dim> ; [{<dim>;}*] <déclareur effectif>
<dim> = DIM E <borne>, <borne>
<borne> = <constante entière> | <ldereperage> <descriptif> |*(entier T) | Id
<ldereperage> = <derep> { <derep>} *

<derep> = *

<declareur effectif de structure> =
STRUCTURE [COMPRESSE] (entier,entier) <champ effectif>; { <champ effectif>} *
<champ effectif> = (entier,entier) <declareur effectif>

<declareur d'ensemble> = ENS <declareur effectif>
<call> = APPEL <desproc> entier ; [{<affectation>}*] ; FINAPPEL
<desproc> = <descriptif> | *<descriptif> | * (entier,entier,entier)

<affectation> = : = <description mode> <reference valeur>, <reference adresse> |
<mode primitif> TAB entier ( <lentier> ) <reference valeur>, (<lentier>)
<reference adresse> )

<description mode> = <mode primitif> | ENS
<lentier> = entier { ,entier} *
<reference adresse> = <reference adresse objet> | <reference adresse element>
<reference adresse objet> = <descriptif> | (entier,entier,entier)
<reference adresse element> = <adresse variable indicee> | <adresse tranche>
<adresse sous-structure> | <adresse feuille>

<adresse variable indicee> =
ORIG <origine> TAB entier; <indice> { <indice>} * <déclareur effectif>
<origine> = <descriptif> | entier T
<indice> = IND E <valeur entière>

<valeur entière> = <constante entière> |*<descriptif> |** <descriptif> | entier T
```
<adresse tranche> =
TRANCHE entier ORIG <origine> TAB entier; <rang>;{<rang>;}*<declareur effectif>
<rang> = <gamme> | <indice>
<gamme> = IND E <domaine>
<domaine> = ? | <valeur entière>, <valeur entière>
<adresse sous structure> = ( <descriptif>, (entier,entier))
<adresse feuille> = ( <descriptif>, (entier,entier))
<reference valeur> = [{<dereperage>}*] <descriptif> | {<dereperage>}*
entier,entier,entier)
* (entier T) | <valeur> C | entier T
<operation> = <operation simple> | <operation tableau> | <operation ensemble> |
<operation appartenance>
<opération simple> = <binaire simple> <mode primitif> <operande>, <operande> |
<unaire simple> <mode primitif> <operande>
<operande> = <reference valeur>
<binaire simple> = + | - | × | / | < | < | > | ≫ | EG | || | ET | OU
<unaire simple> = - | NON
<opération tableau> = <opération tableau binaire> | <opération tableau unaire>
<opération tableau binaire> =
<unaire simple> <mode primitif> TAB entier ( <entier> ) <reference valeur>
<operation ensemble> = <operateur d'ensemble> ENS <reference valeur>, <reference
valeur>
<operateur d'ensemble> = + | × | - | EG | ≠ | < = | > =
<contrôle> = <branch> | SINON entier T
<branch> = ALLERA entier T | ALLERA * (entier T) |
ALLERA (entier,(entier,entier))* <descriptif>