Cours d'introduction à la compilation.C. Jard. Notes de cours.
1. Définition.
Structure.
2. Analyse lexicale. Automates
3. Analyse syntaxique.
Grammaires
4. Analyse syntaxique
LL(1)
5. Analyse
sémantique. Calcul de types
6. Génération
de code
7. Analyse de flot.
Optimisation de code et architecture machine
Exercices des travaux pratiques (K. Heydemann) :
1. Automates et expressions rationnelles (énoncé)
2. Grammaires
3. Analyse LR et LALR
COURS 1. Introduction. Structure d'un compilateur.
programme
---> diagnostic
source
---> compilateur ---> programme objet
L'habitude est de travailler avec des formats textuels en entrée, d'où l'importance de la manipulation de chaînes de caractères (analyse lexicale).
Le compilateur va en fait représenter le texte source en une
forme intermédiaire abstraite qui va capturer la structure pertinente
du programme. On parlera
souvent de l'arbre abstrait d'un programme. Cette notion s'étend
actuellement à la notion de meta-modélisation d'un langage.
Ces différentes phases vont travailler sur une représentation
interne du programme source, qui va progressivement se rapprocher du langage
cible, dans la structure
générale suivante :
texte -> analyseur syntaxique -> représentation abstraite ->
décompilateur -> texte
|
^
----------l
Dans les langages à format libre (non tabulés), l'analyseur
lexical ignore les espaces, les retour-lignes, les tabulations, les
commentaires, qui servent seulement
à séparer les unités.
Exemple de la boucle (en Pascal) :
for i := 1 to 10 do sum:=sum+term[i]; (* sum array *)
Sortie de l'analyseur lexical :
<for, mot-clé> <i, identificateur> <:=, affectation>
<1, constante-entière> <to, mot-clé> <10, constante-entière>
<sum, identificateur>
<:=, affectation> <sum, identificateur> <+, plus> <term,
identificateur> <[, crochet-ouvrant> <i, identificateur> <], crochet-fermant>
Il ne fait effectivement qu'une toute petite partie du travail. Ne regarde
pas la structure syntaxique de la phrase (ex. une affectation a un membre
gauche et
un membre droit). Ne fait pratiquement aucune vérification (ex.
term
est
un tableau).
En général, l'analyseur lexical reconnaît les mots-clés
du langage et les symboles réservés (représentés
par exemple par un index dans une table). Il a
aussi pour tâche de construire la "table des symboles" contenant
l'ensemble des identificateurs. Ils sont généralement représentés
par un index (il peut
y avoir des identificateurs identiques, distingués par leur
portée). Des techniques de stockage et de recherche rapide sont
en général mises en oeuvre (table de hashage).
L'analyse est quelquefois difficile à faire au vol, caractère par caractère.
Exemple de la boucle en Fortran :
DO 1 I = 1
qui sera ici interprétée comme une affectation DO1I = 1, car il n'y a pas de virgule après I. Il faut donc que l'analyseur regarde "en avant" (look ahead)pour décider du symbole (a noter que ce langage est peu sûr dès la phase lexicale, puisque non robuste à une faute de frappe : exemple de la perte de la sonde Mariner).
Autre exemple :
position := initiale + vitesse*60
unités lexicales ? (id.aff.id.plus.id.mult.cste)
Sur notre exemple, l'arbre est le suivant :
(boucle-for, id(i), from(expression(constante-entière(1))),
to(expression(constante-entière(10))), corps(bloc(instruction(
affectation(gauche(id(sum)),droit(expression(somme(gauche(id(sum)),
ref-tab(id(term),index(expression(id(i))))))))
Arbre syntaxique de l'autre exemple ?
La reprise en cas d'erreur est un aspect important d'un compilateur. C'est une question difficile qui consiste à corriger en ligne le programme. Il n'y a pas de théorie spéciale, mais des langages plus ou moins adaptés (ex. continuer l'analyse de la catégorie courante en ignorant tous les symboles jusqu'à le symbole marqueur de fin de la catégorie : parenthèsage début-construction/fin-construction; non seulement on gagne en lisibilité, bien que beaucoup de "sucre" syntaxique, mais aussi en robustesse). L'analyseur syntaxique va se débarrasser de ce sucre syntaxique.
Il existe un continuum entre la forme et le fond. La forme concerne
la syntaxe, le fond concerne la sémantique (le sens de ce l'on écrit).
On distingue la sémantique "statique" (ce que le compilateur peut
calculer ou vérifier) et la sémantique "dynamique" (ce que
révèle l'exécution). Pour des raisons de sûreté,
on aimerait que le maximum de choses soit détecté statiquement
à la compilation (penser aussi que l'on compile rarement et que
l'on exécute souvent). Même si la performance des
compilateurs sur ce sujet augmente, elle reste limitée à
la barrière de la calculabilité.
Exemple :
while (n>1) do
if n pair then n:=n/2 else n:=(3*n+1)/2
On pourra vérifier statiquement que n reste entier (en utilisant une axiomatisation de l'arithmétique), mais on ne pourra que constater que le programme s'arrête et ne boucle pas (ce qui reste une conjecture mathématique fameuse).
Exemple de table des symboles :
id, type,
adresse
position réel id_1
initiale réel id_2
vitesse réel id_3
Sortie de l'analyseur sémantique :
(affectation-flottante(id_1,somme-flottante(id_2, mult-flottante(id_3,conv-ent-flottant(60)))))
Exemple (machine :=, conv, + et * binaires) :
Code intermédiaire
temp_1 := Ent-vers-Fl(60)
temp_2 := id_3*temp_1
temp_3 := id_2+temp_2
id_1 := temp_3
L'optimisation utilise des techniques très générales (simplifications, ré-ordonnancement d'instructions, ...) qui sont aussi souvent locales (on balaye le code intermédiaire avec une fenêtre).
Code amélioré
temp_2 := id_3*60.0
id_1 := id_2 + temp_2
Le code cible final dépend bien sûr de la machine cible.
Exemple d'utilisation des registres de l'unité de calcul du processeur (assembleur).
Code cible
MOVF id_3,R2
MULF #60.0,R2
MOVF id_2,R1
ADDF R2,R1
MOVF R1,id_1
L'idée générale est de rester le plus longtemps
possible indépendant de la machine cible et de factoriser (notion
de compilateur multi-cibles). De plus en plus fréquemment, le langage
cible est aussi un langage source (par exemple C : Java vers C, ...). Ceci
est justifié par l'augmentation de performances des compilateurs
(mais attention aux différents niveaux d'optimisation et de traitement
des erreurs à la compilation et à l'exécution).
avec en parallèle : gestion de la table des symboles, gestion des erreurs.
Il existe des outils pour la construction des compilateurs (compilateur de compilateurs) :
COURS 2. Analyse lexicale. Automates.
Définition : un vocabulaire V est un ensemble fini de symboles.
Définition : un mot sur un vocabulaire V est une séquence finie d'éléments de V.
Il y a un mot particulier, la séquence vide, ou mot vide, que l'on note généralement e.
Etant donné un vocabulaire V, on note V* l'ensemble des mots sur V. On peut munir V* d'une loi de composition interne : la concaténation qui consiste à former un nouveau mot en mettant deux mots à la suite.
Définition : l'opérateur de concaténation
"." est définie par :
. : V*xV* -> V*
(a,b) -> a.b, noté
ab
Remarque : |ab| = |a|+|b|
On note an le mot composé de n occurrences de a.
a0 est le mot vide.
Cette opération de concaténation est associative et admet un élément neutre e. V* a donc une structure de monoïde. On l'appelle le monoïde libre (car la concaténation ne tient pas compte d'une quelconque signification des symboles).
Remarque : sur V = {chat, te, chatte}, chat.te est différent de chatte.
Définition : un langage formel L est une partie de V* (un langage est tout simplement un ensemble de mots).
Exemple : V={a,b}, L = {anbn | n>0} = {ab,aabb,aaabbb, ...}
Définition : L'union L1+L2 de deux langages L1
et L2 est l'union ensembliste classique :
L1+L2 = {m | m dans L1 ou m dans L2}
Définition : Le produit L1L2 de deux langages L1
et L2 est défini par :
L1L2 = {m1m2 | m1 dans L1 et m2 dans L2}
Définition : La fermeture L* d'un langage L est une itération : c'est l'union infinie des Li, avec Li = Li-1L et L0 = e
Exemples :
Exemples :
Sa puissance sera en pratique suffisante pour décrire le langage des unités lexicales.
Remarque : la représentation n'est pas canonique. Plusieurs expressions
peuvent représenter le même langage.
Exemple : a(b+c) = ab + ac
Ceci suggère la possibilité de manipulations algébriques.
Algorithme :
Initialisation flag = true pour les "premiers" symboles à
reconnaître dans l'expression. Les autres sont à false.
tant qu'il reste des caractères à lire faire
(1) mettre toutes les mark à false
lire un caractère sur l'entrée
(2) mettre à true les mark des symboles qui correspondent
au caractère lu. Si aucune ne peut être positionnée,
la reconnaissance échoue
(3) mettre à true les flag des symboles qui suivent
directement les symboles ayant mark à true. Les autres sont mis
à false
fait
Exemple : reconnaître cabcd dans (ab + c)*d
| a
Flag, Mark |
b
Flag, Mark |
c
Flag, Mark |
d
Flag,Mark |
| T,F | F,F | T,F | T,F |
| T,F | F,F | T,T | T,F |
| T,F | F,F | T,T | T,F |
| T,F | F,F | T,F | T,F |
| T,T | F,F | T,F | T,F |
| F,T | T,F | F,F | F,F |
| F,F | T,F | F,F | F,F |
| F,F | T,T | F,F | F,F |
| T,F | F,T | T,F | T,F |
| T,F | F,F | T,F | T,F |
| T,F | F,F | T,T | T,F |
| T,F | F,F | T,T | T,F |
| T,F | F,F | T,F | T,F |
| T,F | F,F | T,F | T,T |
Il semble donc que le problème de l'analyse lexicale soit résolu,
et ceci avec un algorithme simple qui ne nécessite pas de retour
arrière. Il n'en est rien en fait car cet algorithme naïf est
extrêmement inefficace pour des expressions rationnelles complexes.
La raison est qu'à chaque lecture de caractère, il faut examiner
et mettre à jour toutes les variables associées aux symboles
de l'expression. C'est pourquoi on va utiliser une forme compilée
des expressions (les automates) et des algorithmes plus sophistiqués.
Les automates vont "inverser" le procédé : le caractère
lu va indiquer directement l'état suivant du reconnaisseur. La mémoire
du reconnaisseur va être éclatée en états;
le changement d'état va directement être piloté par
le caractère lu : notion de transition étiquetée
par le caractère d'entrée.
peut être représenté par le graphe suivant (on donne ici la forme textuelle où une transition est représentée par un triplet (état départ, étiquette, état arrivée); dans le cours, on utilise la forme graphique) :
Initial : 1
Accepteurs : 3
(1, c, 1)
(1, a, 2)
(1, d, 3)
(2, b, 1)
Noter la notion d'état initial (habituellement, on considère que cet état est unique, sans perte de généralité) et la notion d'état terminal (ou accepteur).
L'intuition est qu'un automate est une machine. La machine démarre dans l'état initial. La lecture d'un symbole (caractère) active la transition correspondante et fait changer l'état de la machine. On considère que la chaîne d'entrée est reconnue lorsque la machine arrive dans un état accepteur. Si avant cela, aucune transition ne peut être activée, la chaîne est rejetée et n'est pas reconnue.
Autre exemple : donner l'automate qui reconnait les mots sur {a,b}*
qui comptent un nombre impair de a.
Exemple de complétude de notre exemple :
Initial : 1
Accepteurs : 3
(1, c, 1) (1, a, 2) (1, d, 3) (1, b, 4)
(2, b, 1) (2, a, 4) (2, c, 4) (2, d, 4)
(4, a, 4) (4, b, 4) (4, c, 4) (4, d, 4)
Pour une expression rationnelle E, on note d(E)
= {e} si le langage de E contient e,
d(E)
= {} sinon.
Remarque :
Les états de l'automate sont construits en calculant explicitement les dérivées de l'expression, puis les dérivées des dérivées et ainsi de suite... Il existe une transition étiquetée a dans l'automate entre l'état E et l'état a-1E.
La dérivation par rapport à un mot est définie classiquement par (a dans V, w dans V*) :
L'ensemble des dérivées d'une expression rationnelle est
fini, modulo associativité, commutativité, et idempotence
de +; c'est-à-dire que
{F | il existe w : F = w-1E} possède un nombre
fini de classes d'équivalence.
Algorithme :
Exemple : (ab+b)*ba
1: (ab+b)*ba
2: b(ab+b)*ba
3: (ab+b)*ba+a
4: b(ab+b)*ba + {e}
Etat initial : 1
Etat accepteur : 4
(1, a, 2)
(1, b, 3)
(2, b, 1)
(3, b, 3)
(3, a, 4)
(4, b, 1)
La récupération d'erreur dans cette phase d'analyse lexicale
est assez rudimentaire. En général, elle consiste à
ignorer le caractère fautif. Dans le cas d'une faute de frappe où
un caractère est remplacé par un autre, cela conduit souvent
à une cascade d'erreurs. Pour y pallier, l'analyseur syntaxique
peut tenir au courant l'analyseur lexical d'un ensemble possible de symboles
attendus, afin que celui-ci effectue la correction appropriée.
Etat initial : 1
Etat accepteur : 2
(1, a, 1) (1, b, 1) (1, a, 2)
Il a par contre une allure désagréable lorsque on veut s'en servir en reconnaisseur : dans quel état se trouve l'automate après avoir lu a ? La réponse est que les deux états 1 et 2 sont possibles. Le non-déterminisme est défini par le fait que plusieurs transitions portant la même étiquette sortent d'un état. Dans le contexte des automates finis, il se trouve que l'on peut toujours transformer un automate déterministe en un automate déterministe en utilisant un algorithme de déterminisation.
Voici la version déterministe de notre exemple (un peu moins "naturelle") :
Etat initial : 1
Etat accepteur : 1_2
(1, b, 1) (1, a, 1_2) (1_2, a, 1_2) (1_2, b, 1)
Il ne faut pas croire que cette équivalence déterministe/non-déterministe est naturelle. C'est un phénomène très particulier aux langages rationnels, ce qui en fait un paysage très "régulier". Ceci va permettre de définir une notion de représentation canonique d'un langage rationnel par un automate déterministe à nombre minimum d'états et de conduire au résultat théorique fondamental qui exprime que l'égalité de deux langages rationnels est décidable et un algorithme consiste à vérifier l'isomorphisme des automates canoniques associés.
Ce n'est en général plus vrai dès que l'on sort de cette classe. A titre d'exemple, considérons les langages infinitaires (formés de mots de longueur infinie) et définissables par des automates finis. Il suffit pour cela de changer l'interprétation des états accepteurs : pour qu'un mot infini soit reconnu, on demande que ce mot "passe" infiniment par un état accepteur (ou état répété). Ces automates ont été introduits par Buchi en 1968.
Exemple : les mots sur le vocabulaire {a,b} ayant un nombre infini de a.
Etat initial : 1
Etat répété : 2
(1, b, 1) (1, a, 2) (2, a, 2) (2, b, 1)
Exemple : les mots sur le vocabulaire {a,b} ayant un nombre fini de a.
Etat initial : 1
Etat répété : 2
(1, b, 1) (1, a, 1) (1, b, 2) (2, b, 2)
On peut se convaincre qu'il n'existe pas d'automate déterministe correspondant.
La définition formelle des automates finis éventuellement
non-déterministes reprend la définition du cas déterministe
mais avec une relation de transition qui peut rendre plusieurs états
:
d : QxV -> P(Q). La
relation de transition se généralise aux mots comme précédemment.
Mais cette fois-ci un mot est reconnu si il peut laisser l'automate dans
un état accepteur (dans le cas déterministe, l'état
dans lequel se trouve l'automate après avoir lu un mot était
unique).
M' est facilement défini par :
Reprendre l'exemple :
Etat initial : 1
Etat accepteur : 2
(1, a, 1) (1, b, 1) (1, a, 2)
--------------------------------
Etat initial : 1
Etat accepteur : 1_2
(1, b, 1) (1, a, 1_2) (1_2, a, 1_2) (1_2, b, 1)
Etat initial : 0
Etat accepteur : 2
(0, a, 0) (0, a, 1) (0, b, 0)
(1, a, 2)
(2, a, 2) (2, b, 2)
En appliquant l'algorithme précédent, on trouve :
Etat initial : 0
Etats accepteurs : 0_1_2, 0_2
(0, a, 0_1) (0, b, 0)
(0_1, a, 0_1_2) (0_1, b, 0)
(0_1_2, a, 0_1_2) (0_1_2, b, 0_2)
(0_2, a, 0_1_2) (0_2, b, 0_2)
alors l'automate suivant est plus petit en nombre d'états et reconnait le même langage :
Etat initial : 0
Etat accepteur : 2
(0, a, 1) (0, b, 0)
(1, a, 2) (1, b, 0)
(2, a, 2) (2, b, 2)
Il est possible de disposer d'un algorithme permettant de calculer le plus petit automate équivalent à un automate fini déterministe.
Etant donné un automate déterministe, on dit que 2 états p et q sont i-équivalents ssi pour tout mot m de longueur inférieure ou égale à i :
Etat initial : 0
Etats accepteurs : 3, 4
(0, a, 1) (0, b, 2)
(1, a, 1) (1, b, 3)
(2, a, 2) (2, b, 4)
(3, b, 3) (3, a, 4)
(4, b, 4) (4, a, 3)
Etat initial : 0
Etat accepteur : 3_4
(0, a, 1_2) (0, b, 1_2)
(1_2, a, 1_2) (1_2, b, 3_4)
(3_4, a, 3_4) (3_4, b, 3_4)
COURS 3. Analyse syntaxique. Grammaires.
<phrase> -> <sujet> <predicat> (<> définit l'unité syntaxique, -> est la décomposition : peut se dire "se compose de ", "se ré-ecrit en", ...).
On continue le raffinement :
<sujet> -> <nom> | <pronom> (retenir cette notion
d'alternative "|", équivalent à la juxtaposition de 2 règles
<sujet>
-> <nom> et
<sujet> -> <pronom>. Ceci sera générateur
d'ambiguités qu'il faudra pouvoir lever à l'analyse.)
<predicat> -> <verbe transitif> <objet> | <verbe intransitif>
<nom> -> le ( chat | chien | mouton) ("(" est un meta-symbole)
<pronom> -> je | tu | il
<verbe transitif> -> aime | déteste | mange
<objet> -> les biscuits | l'herbe | le soleil
<verbe intransitif> -> dort | parle | court
On voit ici la notion d'unité terminale. Ce sont des chaînes de caractères, ou pratiquement des unités lexicales en compilation.
A partir d'une grammaire complète, on peut générer des phrases du langage en ré-écrivant l'unité <phrase> et en effectuant, au hasard par exemple, les choix proposés.
Exemple de dérivation :
<phrase>
<sujet> <predicat>
<nom> <predicat>
le mouton <predicat>
le mouton <verbe transitif> <objet>
le mouton mange <objet>
le mouton mange les biscuits
D'autres phrases possibles sont : je parle, le chien déteste le soleil
mais aussi : je dort (qui n'est pas correct du point de vue de l'orthographe) ou le chat mange le soleil (ce qui n'a pas forcément de sens).
Considérons la grammaire suivante :
S -> S+T | T
T -> a | b
(S et T sont des symboles non-terminaux, +, a et b sont terminaux) Noter la définition récursive de S, permettant de définir les langages de cardinal infini à partir d'un nombre fini de règles.
Exemple : montrer que b+a+a est un "mot" du langage défini par cette grammaire.
Codage de la priorité des opérateurs :
Deuxième exemple :
<expression> -> <terme> | <expression> + <terme>
<terme> -> <primaire> | <terme> * <primaire>
<primaire> -> a | b | c
Trouver la génération de a+b*c
Montrer que la grammaire interprète la priorité à
l'opérateur * : a + (b*c)
Trouver la génération de a+b+c
Montrer que la grammaire interprète l'associativité à
gauche : (a+b)+c
En pratique, on utilise une notation étendue (itération
*, option []).
Formellement, une grammaire est un quadruplet G=(N,V,S,P) où :
Notation : soit U l'ensemble N union T, U+ est l'ensemble des chaînes formées par concaténation de membres de U. U*=U+ + {e}. e désigne la chaîne vide. On demande que a soit dans U+ et b dans U*.
Constater que nos exemples de BNF peuvent se formaliser ainsi.
On se restreint en général aux grammaires de type 1 (ou
contextuelles), en se restreignant aux règles de la forme
: a A b -> agb
avec a,
b et g
dans U*,
g non vide et A un symbole non terminal
simple. Une autre alternative à la définition est d'imposer
|a| <= |b| (mais
ne visualise pas la notion de "sensibilité" au contexte).
Il n'est pas difficile de trouver des langages qui ont besoin de cette puissance, même si en pratique les aspects contextuels sont souvent traités par un calcul extérieur à la grammaire. Ceci mène à la notion de grammaire sans contexte ("context-free").
Type 2 : les règles sont limitées à la forme A -> g où A est un non terminal simple. Cette classe est très importante en compilation et correspond exactement à ce que l'on peut exprimer dans la notation BNF.
La hiérarchie de Chomsky se complète avec les grammaires de type 3, en se restreignant aux règles de la forme : A -> a et A -> aB où A et B sont des non-terminaux, a est un symbole terminal. Ces grammaires sont aussi appelées "régulières" ou d'état fini. Elles décrivent en fait des langages que l'on peut aussi définir par des automates d'état fini. Très simples, elles sont généralement utilisées pour l'analyse lexicale, sous la forme d'automates comme on l'a vu au cours précédent.
La complexité des algorithmes de manipulation augmente bien sûr
en fonction de la position de la grammaire dans la hiérarchie.
On peut distinguer 3 niveaux d'abstraction différents :
Essayons de "parser" a*b+c :
on peut obtenir la suite de dérivations suivante :
a*b+c
<primaire> * b + c
<primaire> * <primaire> + c
<primaire> * <primaire> + <primaire>
<terme> * <primaire> + <primaire>
<terme> * <primaire> + <terme>
<terme> + <terme>
<expression> + <terme>
<expression>
Mais on aurait pu essayer une autre stratégie :
a*b+c
<primaire> * b + c
<primaire> * <primaire> + c
<primaire> * <primaire> + <primaire>
<primaire> * <terme> + <primaire>
<primaire> * <expression> + <primaire>
<primaire> * <expression> + <terme>
<primaire> * <expression>
<terme> * <expression>
<expression> * <expression>
ce qui conduit à un blocage, qui ne doit pourtant pas indiquer que l'expression est syntaxiquement incorrecte.
On distingue deux grandes familles de stratégies :
Dès que le sous-but commence avec un ou plusieurs symboles terminaux, on essaie de mettre ces symboles en correspondance avec la chaîne d'entrée. Si ce n'est pas possible, le sous-but n'est pas satisfait et il n'est pas nécessaire de continuer sur cette "branche". Si il y a correspondance, on continue la décomposition jusqu'à satisfaction de tous les symboles terminaux. Dans ce cas le sous-but est satisfait. Sinon, il n'est pas satisfait.
L'existence de l'alternative induit du back-tracking. Il est souvent mis en oeuvre par des procédures récursives.
On regardera les algorithmes plus tard. Il faut retenir ici les notions de dérivation droite et gauche ("rightmost derivation" et "leftmost derivation").
Considerons l'arbre syntaxique de l'expression a*b+c :
<expression> (<expression>+<terme>)(<terme> (<terme>*<primaire> (<primaire> a| b)) | <primaire> c)
Exemple de dérivation gauche (profondeur gauche d'abord) :
<expression>
<expression>+<terme>
<terme>+<terme>
<terme>*<primaire>+<terme>
<primaire>*<primaire>+<terme>
a*<primaire>+<terme>
a*b+<terme>
a*b+<primaire>
a*b+c
Exemple de dérivation droite (profondeur droite d'abord) :
<expression>
<expression>+<terme>
<expression>+<primaire>
<expression>+c
<terme>+c
<terme>*<primaire>+c
<terme>*b+c
<primaire>*b+c
a*b+c
Noter que de nombreux sous-buts infructueux risquent d'etre explores avant que les symboles de la chaine d'entree permettent d'en valider ou d'en invalider.
Exemple :
Chaine
Production inversee
a*b+c
<primaire> -> a
<primaire>*b+c
<terme> -> <primaire>
<terme>*b+c
<primaire> -> b
<terme>*<primaire>+c
<terme> -> <terme>*<primaire>
<terme>+c
<expression> -> <terme>
<expression>+c
<primaire> -> c
<expression>+<primaire>
<terme> -> <primaire>
<expression>+<terme>
<expression> -> <expression>+<terme>
<expression>
La propriete fondamentale de ces grammaires est que la re-ecriture est independante du contexte :
Theoreme :
Si ...A...B... ->* w alors w = ...u...v..., avec A,B dans N et A -> u, B -> v.
Se demontre aisement par recurrence sur la longueur des derivations.
On voit donc que l'ordre dans lequel va se faire les derivations va pouvoir
etre choisi arbitrairement.
Un arbre est un arbre syntaxique pour bune grammaire algebrique ssi :
S(a,S(a,S(vide),b),b)
Le "mot des feuilles" est obtenu en concatenant ses feuilles dans l'ordre
de leur decouverte par un parcours descendant de gauche a droite.
Un mot appartient au langage defini par la grammaire si et seulement
si il est un mot des feuilles pour un arbre syntaxique de la grammaire.
Exemple :
E -> E - E | 1
1-1-1 est le mot des feuilles des deux arbres suivants : E(E(E(1)-E(1))-E(1)) et E(E(1)-E(E(1)-E(1)))
Exemple de levee d'ambiguite pour le meme langage :
E -> E - T | T
T -> 1
ou encore :
E -> T - E
T -> 1
Noter alors qu'une grammaire non ambigue peut porter une information
importante, ici l'associativite a droite ou a gauche.
Une grammaire algebrique peut etre mise en forme normale de Chomsky
si ses regles s'ecrivent sous les seules formes suivantes :
COURS 4. Analyse syntaxique LL(1)
On rappelle que l'analyse syntaxique d'un mot m = a1...an c'est construire l'arbre syntaxique de m si m est dans le langage L(G) defini par la grammaire ; et produire des diagnostics d'erreur les plus precis possibles dans le cas contraire.
Pour construire l'arbre syntaxique de m on peut chercher a construire une derivation gauche en partant de l'axiome S ->+ m. Imaginons que l'on ait deja reconnu les j premiers symboles du mot m. Si la connaissance des k prochains symboles aj+1 .. aj+k suffit toujours a selectionner la regle de la grammaire qui doit etre appliquee a la prochaine derivation, on dit que la grammaire est LL(k). C'est une notion de "fenetre" de reconnaissance. En d'autres termes, une grammaire est dite LL(k) si une analyse top-down peut etre conduite dans laquelle la decision de la regle a appliquer ne depend que des k prochains symboles de l'entree. Le terme LL est derive du fait que l'entree est lue de gauche a droite et que l'analyseur conduit une derivation gauche ("from Left to right using Leftmost derivation)". Les grammaires LL(1) sont particulierement simples puisqu'il suffit de ne regarder qu'un seul symbole en avance.
Exemple :
S -> a S b | vide est LL(1)
En effet, si le prochain symbole a lire (symbole de pre-lecture) est a, on utilise la premiere regle, sinon on utilise la seconde.
S (a)aabbb : 1
aSb a(a)abbb : 1
aaSbb aa(a)bbb : 1
aaaSbbb aaa(b)bb : 2
aaabbb aaabbb : ok
Le non-determinisme comme (A -> aB | aC) pose evidemment des problemes pour une analyse LL(1). Des difficultes peuvent etre cachees comme la recursivite gauche que l'on verra plus tard. Heureusement, des transformations automatiques ont ete concues pour essayer de rendre une grammaire donnee LL(1). Lorsqu'on y arrive, l'analyse sera particulierement efficace, puisque le texte ne sera balaye qu'en une seule passe (pas de back-track).
L'analyse LR(k) est definie de la meme maniere, mais dans le contexte d'une analyse montante bottom-up. Les analyseurs LR(k) sont plus difficiles a ecrire a la main et sont plutot le resultat de l'application d'un compilateur de compilateur comme Yacc. La classe des grammaires LR(k) est plus grande que celle des LL(k). Il est a noter que toutes les grammaires LR(k) peuvent etre transformees en LR(1).
A toute grammaire LL(1), on peut associer un ensemble de procedures recursives. Une procedure recursive utilise une memoire a priori non bornee formee par la pile des appels de la procedure. La lecture de l'entree s'effectue symbole par symbole en utilisant par exemple une variable Lexlu. L'avancee de la tete de lecture sur le prochain symbole a lire est effectuee par la procedure AvTete : il s'agit de l'interface avec l'analyseur lexical realise par un automate. A chaque non terminal de la grammaire, on associe une procedure. La construction est systematique.
Sur notre exemple :
proc S
cas Lexlu :
"a" : AvTete; S; si Lexlu <> "b" alors
erreur; AvTete;
"b" : ;
autre : erreur
Regarder la trace des appels. Lors de l'execution du 4eme appel a S, la pile contient 3 appels de S en attente de retour correspondant a la detection d'un a sur la bande d'entree. Lors des retours on realise un appariement des a rencontres dans la premiere partie avec les b de la seconde partie du mot.
En pratique on parametre la procedure d'erreur pour donner des diagnostics pertinents (b attendu, ou a ou b attendus).
Avant execution de A : a1...aj, Lexlu pointe sur
aj+1
Apres execution de A : a1...aj...ai, Lexlu pointe
sur ai+1, le mot aj+1..ai a ete structure.
Pour les A-regles de la forme A -> g1 | ... | gn, on produit la procedure :
proc A
cas Lexlu :
selection 1 : traitement g1;
...
selection n : traitement gn;
autre : erreur;
Le traitement associe prend en compte les arbres syntaxiques des non-terminaux et verifie que les terminaux prennent leur place dans le mot des feuilles. Apres avoir execute A, on obtient la situation suivante : [...][a (A)][... (B)][b (A)][... (C)][c (A)][d (A)][... (D)][... (E)] ([] groupe les paquets, (B) veut dire structure par le non terminal B).
On en déduit la procédure suivante :
proc A
AvTete; -- La tête de lecture est
forcement positionnée sur un "a"
B;
si Lexlu <> b alors erreur; AvTete;
C;
si Lexlu <> c alors erreur; AvTete;
si Lexlu <> d alors erreur; AvTete;
D;
E;
La règle A -> vide produit une procédure qui ne fait rien.
- Lexlu dans Premiers(g) (cas où g ne se dérive jamais en vide) ou Lexlu dans Suivants(A) (cas où g peut se dériver en vide) : sélection de la règle A -> g
Définition :
Une grammaire est LL(1) si, pour chaque non-terminal A -> g1 | .. | gn, les 3 conditions suivantes sont vérifiées :
Exemples de grammaires non LL(1). Supposons que "a" est sous la tête de lecture.
Exemple :
A -> B C | D E
: violation de la condition 1
D -> a F | d
B -> a | b G
Exemple :
S -> A B
A -> F G | vide
: violation de la condition 2
B -> a D
F -> c X | vide
G -> b Z | vide
Exemple :
S -> A B
A -> a C | vide
: violation de la condition 3
B -> a D
Montrer qu'une grammaire comportant une règle récursive
à gauche n'est pas LL(1). [ Violation condition 1 ]
Ce cas est assez fréquent, mais peut être éliminé
systématiquement :
A -> A g | g'
se remplace en :
A -> g' A'
A' -> g A' | vide
Il est clair que la transformation de la grammaire vient modifier les arbres syntaxiques qui s'éloignent alors de la syntaxe naturelle que l'on voulait modéliser.
Exemple : considérons le langage des palindromes sur {a,b}, décrit par la grammaire :
S -> a S a | b S b | a | b | vide
Pour une valeur donnée de k, on ne peut évidemment pas savoir avec une pré-lecture de k symboles si on est arrivé ou pas au milieu du mot.
Malheureusement, décider si une grammaire algébrique peut être rendue LL(1) est un problème indécidable.
On peut néanmoins déterminer si une grammaire est dans une forme LL(1) ou non. Il s'agit de calculer la fonction Null qui décide si un mot g peut se réecrire en vide ou non. Il faut aussi calculer les ensembles Premiers et Suivants, afin de voir si les trois conditions de la définition sont satisfaites.
Exemple des expressions arithmétiques :
E -> E add T | T
T -> T mul F | F
F -> id | ( E )
add -> + | -
mul -> * | :
id -> a | b
non LL(1) et transformable en LL(1) suivante :
E -> T E'
E' -> add R E' | vide
T -> F T'
T' -> mul F T' | vide
add -> + | -
mul -> * | :
id -> a | b
Relation immédiate :
E -> T -> F -> [ ( , id -> [ a, b] ]
E' -> add -> [ +, - ]
T' -> mul -> [ *, : ]
qui donne :
Premiers(E) = {a,b,(}, Premiers(E') = {+,-}, Premiers(T) = {a,b,(},
Premiers(T') = {*,:}
Premiers(F) = {a,b,(}, Premiers(add) = {+,-}, Premiers(mul) = {*,:},
Premiers(id) = {a,b}
Heuristiques d'élimination des défauts :
Exemple : $p1 A $p2 -> $p3 a $p4 B $p5 C $p6 b $p7 | $p8 b $p9 A $p10
proc A
p1;
cas Lexlu :
a : p3; AvTete; p4; B; p5; C; si
Lexlu <> b alors erreur; p6; AvTete; p7;
b : p8; AvTete; p9; A; p10;
autre : erreur;
p2
SYNOPSIS
/usr/ccs/bin/yacc [ -dltVv ] [
-b file_prefix ] [ -Q [y | n ] ] [ -P parser ]
[ -p sym_prefix ] file
DESCRIPTION
The yacc command converts a context-free
grammar into a set of tables for a simple automaton that
executes an LALR(1) parsing algorithm. The grammar may be ambiguous;
specified precedence rules are used to break ambiguities. The output file,
y.tab.c, must be compiled by the C compiler to produce a function yyparse().
This program must be loaded with the lexical analyzer program,
yylex(), as well as main() and yyerror(), an error
handling routine. These routines must be supplied by the user; the
lex(1) command is useful for creating lexical analyzers usable
by yacc .
OPTIONS
The following options are supported:
-b file_prefix Use file_prefix instead of y
as the prefix for all output files. The code file y.tab.c,
the header file y.tab.h (created when -d is specified), and
the description file y.output (created when -v is specified), will
be changed to file_prefix.tab.c, file_prefix.tab.h, and file_prefix.output,
respectively.
-d
Generates the file y.tab.h with the #define statements that
associate the yacc user-assigned "token codes"
with the user-declared "token names." This
association allows source files other than y.tab.c to access the token
codes.
-l Specifies that the code produced in y.tab.c will not contain any #line constructs. This option should only be used after the grammar and the associated actions are fully debugged.
-P parser Allows you to specify the parser of your choice instead of /usr/ccs/bin/yaccpar. For example, you can specify: example% yacc -P ~/myparser parser.y
-p sym_prefix Use sym_prefix instead of yy as the prefix for all external names produced by yacc . The names affected include the functions yyparse(), yylex() and yyerror(), and the variables yylval, yychar and yydebug. (In the remainder of this section, the six symbols cited are referenced using their default names only as a notational convenience.) Local names may also be affected by the -p option; however, the -p option does not affect #define symbols generated by yacc .
-Q[y|n] The -Qy option puts the version stamping information in y.tab.c. This allows you to know what version of yacc built the file. The -Qn option (the default) writes no version information.
-t Compiles runtime debugging code by default. Runtime debugging code is always generated in y.tab.c under conditional compilation control. By default, this code is not included when y.tab.c is compiled. Whether or not the -t option is used, the runtime debugging code is under the control of YYDEBUG , a preprocessor symbol. If YYDEBUG has a non-zero value, then the debugging code is included. If its value is 0, then the code willl not be included. The size and execution time of program produced without the runtime debugging code will be smaller and slightly faster.
-V Prints on the standard error output the version information for yacc .
-v Prepares the file y.output, which contains a description of the parsing tables and a report on conflicts generated by ambiguities in the grammar.
OPERANDS
The following operand is required:
file A path name of a file containing instructions for which a parser is to be created.
EXAMPLES
Example 1: Using The yacc Command
Access to the yacc library is obtained with library search operands to cc. To use the yacc library main, example% cc y.tab.c -ly
Both the lex library and the yacc library contain main. The access the yacc maiin, example% cc y.tab.c lex.yy.c -ly -ll This ensures that the yacc library is searched first, so that its main is used.
The historical yacc libraries have contained two simple functions that are normally coded by the application programmer. These library functions are similar to the follow ing code:
#include <locale.h>
int main(void)
{
extern int yyparse();
setlocale(LC_ALL, "");
/* If the following parser is one created by lex, the
application must be careful to ensure that LC_CTYPE
and LC_COLLATE are set to the POSIX locale. */
(void) yyparse();
return (0);
}
#include <stdio.h>
int yyerror(const char *msg)
{
(void) fprintf(stderr, "%s\n", msg);
return (0);
}
ENVIRONMENT VARIABLES
See environ(5) for descriptions of the following
environment variables that affect the execution
of yacc : LC_CTYPE, LC_MESSAGES, and NLSPATH.
yacc can handle characters from EUC primary and supplementary codesets as one-token symbols. EUC codes may only be single character quoted terminal symbols. yacc expects yylex() to return a wide character (wchar_t) value for these one-token symbols.
EXIT STATUS
The following exit values are returned:
0 Successful completion.
>0 An error occurred.
FILES
y.output state transitions of the generated
parsery.tab.c source code of the generated parser
y.tab.h header file for the generated parser
yacc.acts temporary file
yacc.debug temporary file
yacc.tmp temporary file
yaccpar parser prototype for C programs
ATTRIBUTES
See attributes(5) for descriptions of the
following attributes:
____________________________________________________________
| ATTRIBUTE
TYPE |
ATTRIBUTE VALUE |
|_____________________________|_____________________________|
| Availability
| SUNWbtool
|
|_____________________________|_____________________________|
SEE ALSO
cc(1B), lex(1), attributes(5), environ(5)
Programming Utilities Guide
DIAGNOSTICS
The number of reduce-reduce and shift-reduce
conflicts is reported on the standard error
output; a more detailed report is found in the y.output file.
Similarly, if some rules are not reachable from the start symbol,
this instance is also reported.
NOTES
Because file names are fixed, at most one
yacc process can be active in a given directory at a given
time.
COURS 5. Analyse sémantique. Calcul de types
Le typage se définit à partir de :
Notation des expressions de type :
Noter que les bornes des tableaux ne sont pas notées dans le type. On pourrait bien sûr le faire en raffinant la définition, mais on ne pourra pas de toute façon calculer leurs valeurs statiquement : cf la question de la calculabilité. Noter aussi que le type tableau n'est pas très différent du type fonction.
Le type fonction peut être combiné récursivement
(fonction de fonction). Cela ne gêne pas le vérificateur de
type. Cela conduit à manipuler des objets d'ordre supérieur
( exemple des fonctions passées en paramètres et qui implique
un schéma d'exécution particulier). Cela est possible en
ML et interdit en C.
hypothèse1 ... hypothèse n
--------------------------- si condition
conclusion
Les hypothèses et la conclusion ont la forme construction : type, puisqu'il s'agit associer un type à une construction.
L'information de type est obtenue à partir des déclarations. On peut aussi l'obtenir au vu de la syntaxe des expressions. Le système utilise les unités lexicales remontées par l'analyseur lexical.
Exemples d'axiomes :
-----------------
--------------------------
------------ si decl X t
entier(X) : entier
bool(B) : booleen
X : t
Tableaux :
t : tableau(t,t') i : t'
---------------------- si decl T t[entier(X)]
--------------------
T : tableau (t, entier)
t[i] : t
Noter que les bornes du tableaux ne sont pas considérées dans le type. Le type est une abstraction calculable à la compilation.
Fonctions :
f : fonction (t, t') x : t
---------------------- si decl F t : t'
-------------------------
F : fonction (t, t')
f(x) : t'
A noter que le cas des fonctions n-aires peut être ramené
au cas des fonctions unaires, par l'opération de curryfication qui
fait correspondre
D1xD2x...xDn -> D0 à D1 -> (D2 -> ( ... (Dn -> D0) ...
))
Structures :
X : structure (a1 t1, ..., an tn)
--------------------------- --- si decl X struct{a1 t1, ... an tn}
---------------------------------
X : structure (a1 t1, ..., an tn)
X.ident(ai) : ti
Unions :
X : union (a1 t1, ..., an tn)
--------------------------- --- si decl X union{a1 t1, ... an tn}
---------------------------------
X : union (a1 t1, ..., an tn)
X.ident(ai) : ti
Pointeurs :
X : pointeur (t)
X : t
------------------ si decl X * t -----------------
-----------------
X : pointeur(t)
*X : t
&X : pointeur(t)
Une école de pensée actuelle consiste à transporter des vérifications faites classiquement à la compilation vers des vérifications dynamiques. Ceci permet d'aborder par exemple les problèmes du code mobile (les applets Java), de la vérification de sécurité, détection des virus, ...
On demande néanmoins que le typage soit de la bonne puissance, c'est-à-dire que aucun programme qui passe avec succès la vérification statique des types ne peut échouer à la vérification dynamique des types (c'est pourquoi le typage ne regarde pas en général le dépassement des bornes de tableau).
On peut souhaiter ne pas fournir toutes les déclarations dans le programme source, et laisser le compilateur les inférer. L'objectif est de garantir une certaine concision des programmes. On construit toujours une table des synboles, mais au lieu de la construire à partir des déclarations, on la construit à partir des occurrences d'utilisation. L'inférence de type proprement dite revient à faire remonter des feuilles de l'arbre syntaxique du programme des tables de symboles élémentaires qui sont progressivement unifiées pour ne former qu'une table de symboles.
Un bon exemple est ML et ses variantes comme CAML. CAML est doté
d'un système de type à la fois simple et puissant, notamment
parce qu'il offre à la fois des types polymorphes et leur inférence
automatique.
COURS 6. Génération de code
a*b - (c*(d+e) - f)
Mais l'arbre syntaxique peut être parcouru en profondeur d'abord, et traverser les noeuds dans l'ordre postfixe suivant :
a b * c d e + * f - -
L'intérêt de cette représentation est qu'elle peut
être directement interprétée par une machine à
pile.
Cette machine à pile peut être vue comme la machine virtuelle
cible du compilateur. Dans une telle machine, on empile les opérandes,
les opérateurs combinent les deux valeurs en sommet de pile et les
remplacent par le résultat.
Exemple d'exécution :
a
a b
a*b
a*b c
a*b c d
a*b c d e
a*b c d+e
a*b c*(d+e)
a*b c*(d+e) f
a*b c*(d+e)-f
a*b-(c*(d+e)-f)
et le code généré correspondant :
push a; push b; effectuer *; push c; push d; push e; effectuer +; effectuer *; push f; effectuer -; effectuer -;
Dans ce cours, nous donnons une présentation intuitive de ce que fait un compilateur de langage impératif. On définit la correspondance entre un programme en langage source, et le programme obtenu par compilation pour un calculateur cible. Le langage source choisi est un Pascal ou C légèrement appauvri. Le calculateur cible est une machine abstraite spécialement adaptée. La question plus précise de la mise en oeuvre d'une telle machine abstraite sera vue plus tard.
do
PC := PC +1;
exécuter l'instruction de la cellule CODE[PC-1]
od
Le registre PC est initialisé à 0, adresse du début de programme.
add : STORE[SP-1] := STORE[SP-1]
+ STORE[SP]; SP := SP - 1
sub : STORE[SP-1] := STORE[SP-1]
- STORE[SP]; SP := SP - 1
mul : STORE[SP-1] := STORE[SP-1]
* STORE[SP]; SP := SP - 1
div : STORE[SP-1] := STORE[SP-1]
/ STORE[SP]; SP := SP - 1
neg : STORE[SP] := - STORE[SP]
and : STORE[SP-1] := STORE[SP-1]
and STORE[SP]; SP := SP - 1
or : STORE[SP-1]
:= STORE[SP-1] or STORE[SP]; SP := SP - 1
not : STORE[SP]
:= not STORE[SP]
equ : STORE[SP-1] := STORE[SP-1]
= STORE[SP]; SP := SP - 1
geq : STORE[SP-1] := STORE[SP-1]
>= STORE[SP]; SP := SP - 1
leq : STORE[SP-1] := STORE[SP-1]
=< STORE[SP]; SP := SP - 1
les : STORE[SP-1] := STORE[SP-1]
< STORE[SP]; SP := SP - 1
grt : STORE[SP-1] := STORE[SP-1]
> STORE[SP]; SP := SP - 1
neq : STORE[SP-1] := STORE[SP-1]
<> STORE[SP]; SP := SP - 1
Il y a aussi les instructions de lecture et d'écriture en mémoire. ldo charge une donnée à partir d'une cellule donnée par son adresse absolue; ldc charge une constante donnée dans la P-instruction elle-même. ind charge par indirection, à partir de la cellule en sommet de pile; sro écrit dans une cellule dont l'adresse absolue est donnée; sto écrit dans la cellule dont l'adresse est obtenue indirectement à partir de la cellule immédiatement sous la sommet de pile.
ldo q : SP := SP + 1; STORE[SP] :=
STORE[q]
ldc q : SP := SP + 1; STORE[SP] :=
q
ind : STORE[SP]
:= STORE[STORE[SP]]
sro q : STORE[q] := STORE[SP]; SP
:= SP - 1
sto q : STORE[STORE[SP - 1]] := STORE[SP];
SP := SP - 2
En traduisant les affectations, il convient de prendre garde au fait qu'une désignation de variable dans la partie gauche d'une affectation sera traduite différemment d'une désignation de variable apparaissant en partie droite. En partie gauche, on a besoin de l'adresse de la variable pour en modifier le contenu; en partie droite, on a besoin de la valeur pour calculer celle de l'expression. La fonction de codage sera indexée par G ou D : codeG produit des P-instructions pour le calcul d'une valeur gauche, codeD pour le calcul d'une valeur droite.
La traduction d'une affectation x := y donne la séquence :
calculer la valeur gauche de x
calculer la valeur droite de y
sto
Nous considérons comme acquis que les vérifications de types ont déjà été effectuées.
Les fonctions de codage utilisent un deuxième paramètre : une fonction @, qui assigne à toutes les variables déclarées une adresse dans la mémoire STORE. En réalité, pour une variable déclarée dans une procédure, il s'agit d'une adresse relative. Pour l'instant, nous considérons @(x) comme étant l'adresse de x, realtive au début de STORE.
La traduction des instructions d'affectation est définie par :
codeD (e1 = e2) = codeD e1; codeD e2; equ
codeD (e1 + e2) = codeD e1; codeD e2; add
---
codeD x = codeG x; ind
(x désigne une variable)
codeG x = ldc @(x)
codeD c = ldc c
(c constante)
codeD(-e) = codeD e; neg
code(x:=e) = codeG x; codeD e; sto
Exemple :
Soit un programme contenant trois variables entières a,b,c, avec @(a)=5, @(b)=6 et @(c)=7. La traduction de l'affectation a:=(b+(b*c)) donne :
code(a:=(b+(b*c))) =
codeG a; codeD (b+(b*c)); sto =
ldc 5; codeD (b+(b*c)); sto =
ldc 5; codeD b; codeD (b*c); add; sto =
ldc 5; codeG b; ind; codeD b; codeD c; mul; add; sto =
ldc 5; ldc 6; ind; codeG b; ind; codeG c; ind; mul; add; sto =
ldc 5; ldc 6; ind; ldc 6; ind; ldc 7; ind; mul; add; sto
Regarder l'évolution de la pile.
On considères deux nouvelles instructions de la P-machine (ujp
pour le branchement inconditionnel, fjp pour le branchement conditionnel).
Avec le signification suivante :
ujp q : PC := q
fjp q : if STORE[SP] = false
then PC := q;
SP := SP - 1
On peut alors définir les fonctions de codage :
code (if e then st1 else st2) = codeD e; fjp l1; code st1; ujp l2; l1: code st2; l2:
(voir graphiquement dans la mémoire d'instruction)
code (if e then st) = codeD e; fjp l; code st; l:
code (while e do st) = l1: code D e; fjp l2; code st; ujp l1;
l2:
code (repeat st until e) = l: code st; codeD e; fjp l
Exemple :
Avec @(a)=5, @(b)=6 et @(c)=7
Générer le code pour les instructions :
if (a>b) then c:=a else c :=b
ldc 5; ind; ldc 6; ind; grt; fjp l1; ldc 7; ldc 5; ind; sto; ujp l2; l1: ldc 7; ldc 6; ind; sto; l2:
while (a>b) do c := c+1; a := a-b
l1: ldc 5; ind; ldc 6; ind; grt; fjp l2; ldc 7; ldc 7; ind; ldc 1; add; sto; ldc 5; ldc 5; ind; ldc 6; ind; sub; sto; ujp l1; l2:
sachant que lel schéma de traduction de la séquence est très simple :
code (st1;st2) = code st1; code st2
Considérons maintenant une sélection simplifiée de la forme :
case e of
0 : st0;
1 : st1;
...
k : stk
Une traduction fréquente consiste à utiliser un branchement indexé. La P-instruction ixj correspondante ajoute à l'adresse cible la valeur contenue dans la cellule en sommet de pile.
ixj q : PC := STORE[SP] + q; SP := SP - 1
La traduction est la suivante :
code (e, st0, ..., stk) = codeD e; neg; ixj q; l0: code st0; ujp q'; l1: code st1; ujp q'; ... lk: code stk; ujp q'; ujp lk; ...; ujp l1; q: ujp l0; q':
Noter que les dernières instructions forment la table des branchements.
Dans notre cas, le schéma d'affectation est simple. Pour chaque variable déclarée, on affecte les adresses au début de la pile, en séquence dans l'ordre de leur déclaration. En général, les adresses sont relatives (on verra plus loin l'utilité de cette notion). Par exemple, on peut considérer que les variables sont stockées à partir de l'adresse 5. Ce qui donne la fonction d'allocation suivante, pour les déclarations var x1 : t1; ... xn : tn;, @(xi) = i+5;
Combien de cellules mémoires ce tableau occupera-t-il ? 99, que l'on peut ranger par ligne (a[-5,1] ... a[-5,9], a[-4,1] ... a[-4,9], ...)
Pour un tableau array[l1..u1, ..., lk..uk] of integer, on a nbcell = X(i=1..k) (ui-li+1)
Pour chaque type t, on peut obtenir son nbcell(t) (nbcell(t)=1 pour les t simples).
Pour une déclaration de variable var x1 : t1; ... xn : tn; on a @(xi) = 5 + S(j=1..i-1) nbcell(tj)
Dans l'exemple des tableaux statiques, les grandeurs k, li, ... sont
connues dès la compilation, donc aussi les fonctions nbcell
et @. Ainsi si on veut ranger 0 dans la première cellule d'un tableau
a, on peut générer le code : ldc @(a); ldc 0; sto
Ceci ne marche pas pour générer du code pour l'affectation
a[i,j]
:= 0, dans laquelle i et j sont des variables qui ne recoivent des
valeurs qu'à l'exécution. Dans ce cas, il faut générer
auparavent le code qui calcule l'expression : (i-(-5))*(9-1+1)+j-1 =
(i+5)*9+j+1.
Dans le cas général, calculons l'adresse de l'élément
[i1,i2,...,ik]
relative
par rapport au début du tableau. Le tableau étant rangé
par ligne,
l'adresse de l'élément cherché est :
(i1-l1)*nbcell(array[l2..u2, ..., lk..uk]) +
(i2-l2)*nbcell(array[l3..u3, ..., lk..uk]) +
...
(ik-1 - lk-1)*nbcell(array[lk..uk]) +
(ik-lk)
soit en remplaçant par les valeurs de nbcell connues à
la compilation :
(i1-l1)*d2*d3* ...*dk +
(i2-l2)*d3*d4* ... *dk +
...
(ik-lk)
ou encore :
i1*d2*d3* ...*dk + i2*d3* ...*dk + ik -
(l1*d2*d3* ...*dk + l2*d3* ...*dk + lk) où la deuxième
partie est connue à la compilation.
Pour un type d'élément quelconque t, soit Dj = X(i=j+1..k)
di, et h = S(j=1..k) ij*Dj, alors
@([i1, ..., ik]) est de la forme h*nbcell(t) - d*nbcell(t).
On va considérer une P-instruction particulière pour faciliter les calculs : ixa q qui permettra d'obtenir successivement les adresses des sous-tableaux :
ixa q : STORE[SP-1] := STORE[SP-1]+STORE[SP]*q; SP := SP - 1
et aussi la décrémentation dec q :
dec q : STORE[SP] := STORE[SP] - q
@([i1, ..., ik]) va être calculé par le code généré ainsi :
codeG c[i1, ..., ik] = ldc @(c); codeI [i1, ..., ik] nbcell(t)
codeI [i1, ..., ik] n = codeD i1; ixa n*D1; codeD i2; ixa n*D2;
... codeD ik; ixa n*Dn; dec n*d;
Ce code ne vérifie que les indices appartiennent bien aux intervalles permis par la déclaration de tableau. Comme, ce n'est pas en général décidable à la compilation, il faut considérer une instruction de vérification chk p q :
chk p q : if (STORE[SP]<p) or (STORE[SP]>q) then error ("value out of range")
Exemple :
var i,j : integer;
a : array [-5..5,1..9] of integer;
et supposons que @(i)=5, @(j)=6, @(a)=7
d1=11, d2=9, n=1 et d=-44
La traduction de a[i+1,j] := 0 est :
code(a[i+1,j] := 0) = ldc 7;ldc 5; ind; ldc 1; add; chk -5 5; ixa 9; ldc 6; ind; chk 1 9; ixa 1; dec -44; ldc 0; sto
Cette méthode ne marche plus pour les tableaux dynamiques dont les bornes ne sont connues qu'à l'exécution. Le compilateur doit générer aussi le code pour l'allocation en mémoire. Ce cas complexe n'est pas traité dans ce cours.
La P-instruction new doit trouver en sommet de pile la taille de l'objet à créer, et en dessous l'adresse de la variable qui contiendra le pointeur vers le futur objet. Cette adresse permettra de trouver indirectement l'adresse du nouvel objet.
new : if NP - STORE[SP] <=
SP then erreur("memory overflow")
else NP := NP - STORE[SP]; STORE[STORE[SP-1]] := NP; SP := SP - 2
La traduction d'une instruction du langage source new(x) est donc :
code(new(x)) = codeG x; ldc nbcell(t); new (x est du type *t)
Pour déréférencer (adresser un objet à partir d'un pointeur) on utilise simplement la P-instruction ind.
Une procédure est appelée à l'exécution d'une instruction référençant son nom. Une fois appelée, une procédure peut à son tour appeler une autre procédure. Dès qu'une procédure a terminé de traiter ses instructions, on quitte la procédure, et la procédure qui l'avait appelée poursuit son exécution au delà de l'appel. Si on considère l'enchaînement des appels lors de l'exécution, on peut observer qu'il s'agit d'un arbre. La racine est étiquetée par le programme principal. Un noeud intérieur est étiqueté par un nom de procédure p, son noeud père par le nom de la procédure qui a exécuté l'appel de p. Les noeuds fils correspondent aux procédures appelées par le père successivement dans l'ordre de leur appel. Lorsqu'une procédure p est activée, les procédures traversées depuis la racine jusqu'à ce noeud sont dites vivantes (elles ne sont pas encore terminées).
Exemple :
program h;
var i : integer;
proc p
[
proc r
[]
if i>0 then i:= i-1; p
else r
]
i := 2;
p;
p
Arbre : h (p(p(p(r))),p(r))
A un programme donné peuvent correspondre plusieurs arbres d'appels (cela dépend de l'éxécution). Un arbre d'appels peut être infini.
Les noms de paramètres ou introduits par des déclarations locales sont des noms locaux pour lesquels il faudra réserver dynamiquement de la place lors de l'appel. La durée de vie de ces variables est exactement la durée de la procédure. Cette place peut être libérée en quittant la procédure. Ceci va être mis en oeuvrenpar une pile dans la mémoire. Le traitement des noms des variables globales est plus compliqué. Il faut utiliser des règles de visibilité pour retrouver la définition correspondant à une référence à une variable. Par exemple, la définition d'une variable sera cherchée dans les variables locales de la procédure. Si échec, il faudra chercher dans la procédure englobante et ainsi de suite. Il s'agit d'une relation DEF/USE qui peut être calculée sur la structure du programme.
Exemple :
proc p(a)[ var b; var c; proc q [ var a; var q; proc r [ var b; b;a;c ] a; b; q; ] proc s [ var a; a; q; ] a; q; ]
Trouver les DEF/USE
Ce mécanisme est une liaison statique. Dans certains langages, on préfère la liaison dynamique. Dans ce cas, un accès à un nom global fait intervenir la dernière instance de ce nom.
Exemple :
var s; proc p [ proc q [ var x; p ] x; q; ] p
A l'appel de p depuis l'extérieur, x se rapporte à la définition externe (statique comme dynamique). Par contre, l'appel de p depuis q, lie x à la déclaration dans q (statiquement la liaison serait la déclaration externe).
Dans le cas de liaison statique que l'on considère ici, on peut faire correspondre à chaque chemin d'instanciation, l'arbre des prédécesseurs statiques : un noeud de l'arbre est une instance de procédure, et son père est la dernière instance créée de la procédure englobante.
Dans notre exemple du programme h, l'arbre des prédécesseurs
statiques associé au chemin h-p-p-p-r est h(p,p,p(r)).
Exemple :
program h; [ var x; proc p [ ... proc q [ ... r ... ] proc r [ var y; proc s [ x+y; q ] s ] r ] p ]
Après le deuxième appel de s, montrer l'allure de la pile. Sachant que l'arbre des prédécesseurs statiques est
Exemple :
Dans le programme précédent :
définitions : p(1), q(2), r(2), s(3)
utilisations : p(1), q(4), r dans p (2), r dans q (3), s(3)
Considérons les accès aux variables non locales x et y depuis la procédure s. Supposons que la définition de x dans le programme principal soit visible dans s. La profondeur d'imbrication de cette définition est égale à 1. Les profondeurs des utilisations de x et y dans s sont 4. On voit qu'en suivant 3 fois le pointeur PrS, on atteint le bloc d'activation du programme principal, où se trouve x. La bonne instance de y accédée dans r est obtenue en suivant une fois ce pointeur PrS (la différence entre les profondeurs de l'utilisation et de la définition est de 1). On a en fait le résultat suivant : un accès depuis une profondeur n à une variable définie à un eprofondeur m (m<=n), nécessite de suivre (n-m) fois le pointeur PrS avant d'arriver au bloc d'activation contenant la définition cherchée. On doit ajouter à l'adresse de début de ce bloc l'adresse relative pour obtenir l'adresse absolue de la variable globale. On utilise les P-instructions suivantes (lod lit les valeurs, lda les adresses) :
lod p q : SP : = SP + 1; STORE[SP]
:= STORE[base(p,MP)+q)
lda p q : SP := SP + 1; STORE[SP]
:= base(p,MP)+q
str p q : STORE[base(p,MP)+q]
:= STORE[SP]; SP := SP - 1
p = différence des profondeurs d'imbrication; q = adresse
relative
base(p,a) = if p=0 then a else base(p-1,STORE[a+1])
mst p : STORE[SP+2] := base(p,MP);
STORE[SP+3] := MP; SP := SP + 4 (les paramètres peuvent être
évalués à partir de STORE[SP+1])
cup p q : MP := SP-(p+3); STORE[MP+3]
:= PC; PC := q (p donne la place requise pour les paramètres, q
est l'adresse de début de la procédure)
ssp p : SP := MP+p-1 (p est la
taille statique de la zone de données)
Une fois l'exécution du corps d'une procédure complètement terminée, on doit libérer la place qui a été allouée pour son bloc d'activation, et effectuer le branchement de retour vers l'appelant. La P-instruction retf se charge de cette tâche pour les fonctions et retp pour les procédures.
retf : SP := MP; PC := STORE[MP+3];
MP := STORE[MP+2]
retp : SP := MP - 1; PC := STORE[MP+3];
MP := STORE[MP+2]
Pour ce qui concerne la transmission des paramètres, il faut distinguer le passage par valeur du passage par référence. La traduction d'un paramètre effectif requiert des informations sur les paramètres formels correspondants. Ces informations sont fournies par l'analyse sémantique réalisée avant la génération de code. Le code généré pour ces paramètres formels s'exécute dans le contexte suivant : la procédure appelante a déjà exécuté la P-instruction mst ; le registre SP pointe sur la cellule immédiatement en dessous de la zone des paramètres. La transmission des paramètres occupe alors les cellules suivantes avec des adresses ou des valeurs. Ainsi SP est incrémenté, de façon à toujours pointer sur la dernière cellule libre. Si un paramètre formel x d'une procédure est spécifié comma var, alors le paramètre effectif correspondant doit être une variab à nouveau un paramètre var. Transmettre le paramètre consiste alors à calculer l'adresse, autrement dit la valeur gauche du paramètre effectif, et à la ranger en utilisant l'adresse relative qui a été affectée à x. Chaque accés au paramètre formel dans le corps de la procédure nécessite alors une indirection à travers son adresse relative.
COURS 7. Analyse de flot. Optimisation de code et architecture machine.
Du point de vue des machines réelles, la mémoire est essentiellement hiérarchisée en fonction de la rapidité des accès: on trouve les registres du processeur, un cache, une mémoire principale et une mémoire auxilliaire. Les registres se trouvent généralement sur la puce du processeur, et leur accès est très rapide. A l'inverse, un accès à la mémoire principale s'effectue en général à travers le bus système situé entre le processeur et la mémoire: c'est accès est nettement plus long. La tâche de génération de code est donc de maintenir autant que possible les objets dans des registres.
La mémoire principale est généralement une mémoire linéaire, qui devra accueillir le code généré, les piles et le tas. Sur les ordinateurs actuels, les octets sont souvent les plus petites unités adressables.
Il existe aussi plusieurs classes de registres. Il y a les registres universels pour les opérations arithmétiques et logiques sur les entiers et les adresses. On trouve aussi des registres flottants pour les opérations en virgule flottante (qui nécessitent un matériel ou du micro-code spécialisé). Quelquefois, les registres pour les données et les adresses sont séparés (du à leur longueyr différente). On trouve enfin le registre du compteur d'instruction (PC) et le registre du code condition (CC) qui contient le résultat des comparaisons et notamment les indicateurs de signe, de débordement, de retenue, ...
Le jeu d'instructions varie beaucoup d'un calculateur à l'autre. Cela peut varier de quelques dizaines à un millier. On distingue en général :
<operande> ::= Ri (contenu du registre Ri) | M[< Adr> ] (contenu de la cellule mémoire adressée) | c (valeur de la constante)
<resultat> ::= Ri (registre cible de l'opération) | M[<Adr> ] (cellule mémoire pour le résultat)
Sur la plupart des processeurs, les modes d'adressage possibles forment un sous ensemble du langage suivant :
<Adr> ::= c (valeur d'une constante) | Ri (contenu du registre)
| ++Ri (contenu du registre après pré-incrémentation)
|
--Ri (contenu du registre après pré-décrémentation)
| Ri++ (contenu du registre, post-incrémentation par effet de bord)
|
Ri-- (contenu du registre, post-décrémentation par effet
de bord) | M[<Adr>] (contenu de la cellule adressée) |
<Adr> + <Adr> (somme des adresses) | <Adr>*c |<Adr>.<Size>
(restriction à une partie d'un registre)
<Size> ::= L | W | B (mot long, mot, octet)
En plus de la génération de code proprement dite, on ajoute les tâches suivantes :
La réalisation de ces jeux d'instructions exige d'utiliser soit une grande quantité de matériel, soit de gros micro-programmes. Il reste peu de place en général sur la puce pour mettre des registres. La tâche d'allocation des registres est importante, mais difficile. L'essentiel de l'optimisation doit être conduit au niveau de la génération de code intermédiaire.
Le parallélisme peut être aussi exploité pour former des "pipelines". Dans un pipeline d'instructions peuvent se trouver à un instant donné plusieurs instructions, à diverses phases de leur exécution. Par exemple, le partage d'une instruction peut se faire en quatre phaes : (1) charger et décoder les instructions, (2) charger les opérandes, (3) exécuter l'instruction, (4) écrire le résultat dans un registre. A chaque phase correspond un étage du pipeline responsable de son exécution, et l'exécution d'un étage prend un cycle. Dans une situation idéale, lorsuqe le pipeline est régulièrement alimenté, il y a recouvrement, et une instruction est exécutée à chaque cycle (bien qu'elle dure en fait 4 cycles).
Exemple :
1 2
3 4 5 6
7
1 B1 B2 B3 B4
2 B1
B2 B3 B4
3
B1 B2 B3 B4
4
B1 B2 B3 B4
Une telle situation n'est possible que si les instructions successives ne requièrent pas simultanément les mêmes ressources matérielles, et aucune instruction n'a besoin d'un résultat d'une instruction précédente, et qui n'est pas encore disponible. Dans certainemachines, cette dernière situation était détectée dynamiquement et bloquait l'entrée du pipeline. Mais c'était très couteux. On préfère confier au compilateur le soin de réordonner les instructions de façon à intercaler entre deux instructions dépendantes un nombre suffisant d'instructions qui n'en dépendent pas, et éventuellement remplir les délais non utilisés par des instructions "NOP".
Ces tâches requièrent une représentation du flot de contrôle du programme.
cfg(while B do S) = 0 <B>-> 2
^ | 1
| v
cfg(S)
cfg(if B then S1 else S2) = -1<B>2-
|
|
cfg(S1) cfg(S2)
|_______|
|
v
cfg(S1;S2) = cfg(S1) -> cfg(S2)
Les arcs qui correspondent aux branchements explicites conduisent du noeud du branchement au noeud de la cible. s est l'unique noeud d'entrée du graphe de contrôle de la procédure, il correspond à la première instruction exécutée. Les noeuds possédant plus d'un prédécesseur sont appelés des jonctions, et ceux qui possèdent plusieurs successeurs sont des embranchements. Le graphe de contrôle est en général connexe (sinon, cela veut dire qu'il y a du code mort).
Exemple : construire le cfg du programme :
read a;
read b;
while a <> b do
if a < b
then t:=a; a:=b; b:=t
else a:=a-b
Les séquences d'instructions simples sont en général
rassemblées afin d'obtenir des blocs de base, contenant au plus
une jonction au début et un embranchement à la fin. On obtient
alors le graphe des blocs de base.
On va générer du code pour les arbres d'expressions,
intégrant l'allocation des registres et le choix des instructions
pour un modèle simple de machine. Il faut tenir compte du besoin
en registres, et produire les échanges nécessaires avec la
mémoire lorsque le besoin en registres dépasse le nombre
de registres disponibles.
Considérons par exemple l'arbre correposndant à l'affectation f := (a+b)-(c-(d+e)) : :=(f,-(+(a,b),-(c,+(d,e))))
Prenons une machine très simple dans laquelle il y a correspondance entre les opérations dans l'arbre et les instructions. La machine cible dispose de registres généraux. Les instructions sont à deux adresses, avec le format suivant :
Ri := M[V]
M[V] := Ri
Ri := Ri op M[V]
Ri := Ri op Rj
Supposons que notre machine ait 2 registres.
Un code généré possible est :
R0 := M[a]; R0 := R0 + M[b]; R1 := M[d]; R1 := R1 + M[e]; M[t1] := R1; R1 := M[c]; R1 := R1 - M[t1]; R0 := R0 - R1; M[f] := R0
Un échange avec la mémoire est utilisé car aucun registre n'est disponible pour la soustraction c-(d+e). On aurait pu par contre générer le code suivant :
R0 := M[c]; R1 := M[d]; R1 := R1 + M[e]; R0 := R0 - R1; R1 := M[a]; R1 := R1 - R0; M[f] := R1
Cette séquence ne nécessite pas d'échange avec la mémoire, et économise 2 instructions. La raison en est que le sous-arbre pour c-(d+e), dont l'évaluation nécessite deux registres, est évalué avant le sous-arbre de a+b, qui ne demande qu'un seul registre.
C'est le principe de l'algorithme. Soit t un arbre correspondant à une expression e1 op e2; soient t1 et t2 les sous-arbres pour e1 et e2. t1 utilise pour son évaluation r1 registres, et t2 r2 registres. Soit r le nombre de registres disponibles et r>=r1>r2. Après l'évaluation de t1, tous les registres qui ont servis sont libres, à l'exception du registre qui contient le résultat, et il y a un nombre suffisant de registres pour évaluer t2. Par conséquent, l'arbre entier peut être évalué en utilisant r1 registres. Si t1 et t2 requièrent le même nombre r1 de registres, il faut au total r1+1 registres pour évaluer t, si l'on maintient le résultat de l'un des sous-arbres dans un registre pendant que l'autre sous-arbre est évalué. Lorsuqe l'évaluation d'un arbre demande plus de r registres, il faut ranger en mémoire un ou plusieurs résultats intermédiaires. L'algorithme se déroule en 2 phases : une phase de marquage, pour noter les besoins en registres de sous-arbres, et une pahse de génération, où est produit le code, avec éventuellement des écritures en mémoire de résultats intermédiaires, sur la base des besoins en registres que l'on vient de calculer.
Marquage : on oublie pour l'instant quel 'on a qu'un nombre borné de registres. On utilise une visite ascendante. Les feuilles de gauche sont marquées par 1, puisqu'une telle feuille devra être envoyée dans un registre. Par contre, les feuilles de droite sont utilisées comme opérandes, et ont donc une consommation en registres égale à 0. Le raisonnement précédent donne les beoins en registres des noeuds intérieurs :
regnb(op(t1,t2)) = max(r1,r2) si r1<>r2, r1+1 sinon. Avec r1=regnb(t1), r2=regnb(t2)
Le marquage obtenu sur notre exemple est : := 2 (f,- 2 (+ 1 (a 1 ,b 0 ),- 2 (c,+ 1 (d 1 ,e 0 ))))
Génération : produit un code de taille optimale, à l'aide d'une visite de l'arbre. On produit l'instruction OP pour l'opération op à la racine de l'arbre op(t1,t2) après avoir produit le code pour t1 et t2. L'ordre dans lequel on évalue les deux sous-arbres t1 et t2 est déterminé par leurs besoins en registres. Les résultats intermédiaires des sous-arbres avec des besoins en mémoire trop élevés sont rangés en mémoire pour être relus ultérieurement. Les registres disponibles sont gérés dans une pile RSTACK, initialisée avec l'ensemble de tous les registres disponibles. Au début du traitement d'un sous-arbre t, le registre en sommet de pile est le registre du résultat de t. Après traitement d'un sous-arbre, tous les registres de la pile sont libérés, sauf le registre en sommet de pile. Une deuxième pile TSTACK permet de gérer des adresses des résultats intermédiaires rangés en mémoire. POur les deux piles, on dispose des opérations push, pop, top et exchange; exchange permute les deux éléments les plus haut dans la pile.
Algorithme :
var R: registre, T: adresse;
var RSTACK: pile de registre;
var TSTACK: pile de adresse;
proc gen_code (t:arbre);
cas t :
(feuille a,1) : emit(top(RSTACK) := a);
op((t1,r1),(feuille a,0)) : gen_code(t1); emit(top(RSTACK)
:= top(RSTACK) OP a);
op((t1,r1,(t2,r2)) : cas
r1 < min(r2,r)
: exchange(RSTACK); gen_code(t2); R := pop(RSTACK); gen_code(t1); emit(top(RSTACK)
:= top(RSTACK) OP R); push(RSTACK,R);
exchange(RSTACK)
r1 >= r2 ^ r2<r
: gen_code(t1); R := pop(RSTACK); gen_code(t2); emit(R := R OP top(RSTACK));
push(RSTACK,R)
r1>=r ^ r2>=r :
gen_code(t2); T := pop(TSTACK); emit(M[t] := top(RSTACK)); gen_code(t1);
emit(top(RSTACK) := top(RSTACK) OP M[T]); push(TSTACK,T)
Exemple :
a : X :=
b: X :=
c: := X
d: X :=
Un échange des instructions a et b changerait la valeur fournie à l'utilisation dans c, de même que l'échange de b et c, ou c et d.
Il existe plusieurs formes de dépendances :
Le graphe de dépendance d'un bloc de base est un graphe orienté, étiqueté et acyclique. Les noeuds sont étiquetés par les instructions du bloc. Un arc joint le noeud a au noeud b si a doit être exécuté avant b, c'est à dire si a se trouve avant b dans la séquence et si l'une des conditions suivantes est satisfaite :
Exemple :
1: D1 := M[A1+4];
2: D2 := M[A1+6];
3: A1 := A1+2
4: D1 := D1+A1
5: M[A1] := A1;
6: D2 := D2+1;
7: D3 := M[A1+12];
8: D3 := D3+D1;
9: M[A1+6] := D3
Graphe :
1 -> 4,3,5
2 -> 3,5,6
3 -> 4,7,5,9
4 -> 8
5 -> 7
7 -> 8,9
8 -> 9
Le graphe de dépendance représente les différents degrés de liberté laissé pour ré-ordonner les instructions : tout tri topologique du graphe doit donner un ordre admissible. L'écriture dans une cellule suivie d'une lecture donne une dépendance, même si on lit une autre cellule. Si une analyse d'alias permet de déterminer que dans toute exécution, les adresses effectives de ces cellules seront différentes, l'arc de dépendance disparaît (2,5), (1,5) et (5,7) peuvent disparaitre de cette façon.
Pour générer du code en pipeline, nous considérons maintenant pour simplifier que si une instruction b dépend d'une instructiona, b peut être exécutée au plus tôt après un retard d'un cyclen soit 2 cycles après a. Le problème de trouver le code pipeliné le plus court est NP-complet: on va utiliser une heuristique. L'heuristique consiste à effectuer un tri topologique en guidant les choix. On rappelle que le tri topologique consiste à partir des minimaux du graphe, puis à choisir parmi les successeurs qui n'ont pas été encore choisis. On retire le successeur choisi et on recommence. Lors du choix, l'heuristique ne va considérer que les canidats qui ne présentent aucune collision avec les instructions déjà ordonnées, et si il n'en existe pas, on insère une instruction NOP. Si il y a plusieurs candidats sans collision, on utilise les critères suivants dans l'ordre :
2: D2 := M[A1+6];
1: D1 := M[A1+4];
6: D2 := D2+1;
3: A1 := A1+2;
NOP
7: D3 := M[A1+12];
4: D1 := D1+A1
8: D3 := D3+D1;
5: M[A1] := A1;
9: M[A1+6] := D3
La réalité est malheureusement plus compliquée car il faut tenir compte des délais minimums imposés entre les instructions.
Le dernier problème est celui des mots d'instructions longs. Si l'on suppose n unités fonctionnelles travaillant en parallèle, le problème revient à réordonner une séquence d'instructions en n nouvelles séquences. Le parallélisme potentiel à l'intérieur des blocs de base est en général restreint. Il devient alors nécessaire de prendre en compte des ordonnacnements qui traversent les frontières des blocs de base. La technique consiste à diviser le graphe de flot de contrôle d'un eprocédure en sous-chemins disjoints. Après une évaluation de la fréquence d'utilisation des chemins (mesures préalables ou estimations), on refabrique des chemins plus longs en concaténant des sous-chemins de fréquence proche. On en traverse jamais une boucle. Le sous-chemin obtenu est alors réordonné, ce qui peut amener à déplacer des instructions des blocs de base au delà des points de fusion ou d'embranchement. Il faut alors insérer du code de compensation dans les blocs de bas qui débouchent dans ce chemin, ou qui en partent.
Exemples de déplacement de code :
x := ; if e then S1 else S2 -> if e then x := ; S1 else X := ; S2 correct dans le cas où il n'y a pas de dépendance entre X := et le if.
Peut être raffiné si X n'apparaît pas dans S1 ou S2. Dans ce cas, on peut considérer la transformation inverse qui remonte X := devant le test.
S1; X := ; S3 -> S1; X := ; S3
^
^
S2
S2; X :=
On peut concevoir des transformations plus complexes pour déplacer
un branchement ou faire des échanges de branchements. C'est
toujours une recherche très active de trouver des transformations
préservant la sémantique et calculables à la compilation.