Search for notes by fellow students, in your own course and all over the country.
Browse our notes for titles which look like what you need, you can preview any of the notes via a sample of the contents. After you're happy these are the notes you're after simply pop them into your shopping cart.
Title: Cours de compilation.
Description: École nationale supérieure d’informatique pour l’industrie et l’entrepris
Description: École nationale supérieure d’informatique pour l’industrie et l’entrepris
Document Preview
Extracts from the notes are below, to see the PDF you'll receive please use the links above
Universite de Bretagne Occidentale
IUP Ingenierie INFORMATIQUE
Deuxieme annee
COMPILATION
THEORIE DES LANGAGES
Derniere revision: 29 janvier 2003
Table des matieres
1 Introduction
1
...
2 Pourquoi ce cours? : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
1
...
1 Phases d'analyse : : : : : : : : : : : : :
2
...
1 Analyse lexicale : : : : : : : : : :
2
...
2 Analyse syntaxique : : : : : : : :
2
...
3 Analyse semantique : : : : : : :
2
...
2
...
2
...
3 Phases paralleles : : : : : : : : : : : : :
2
...
1 Gestion de la table des symboles
2
...
2 Gestion des erreurs : : : : : : : :
2
...
l : : : : : : : : : : : : : :
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
3 Analyse lexicale
3
...
1
...
2 Mise en uvre d'un analyseur lexical : :
3
...
1 Speci cation des unites lexicales
3
...
2 Attributs : : : : : : : : : : : : :
3
...
3 Analyseur lexical : : : : : : : : :
3
...
1
4
...
3
4
...
5
5 Analyse syntaxique
5
...
1
...
1
...
2 Mise en oeuvre d'un analyseur syntaxique
5
...
3
...
3
...
3
...
3
...
3
...
3
...
3
...
3
...
4 Analyse ascendante : : : : : : : : : : : : :
5
...
5
...
5
...
5
...
5
...
1
6
...
3
6
...
5
Structure du chier de speci cations bison : : : : : : :
Attributs : : : : : : : : : : : : : : : : : : : : : : : : : :
Communication avec l'analyseur lexical: yylval : : : :
Variables, fonctions et actions prede nies : : : : : : : :
Con its shift-reduce et reduce-reduce : : : : : : : : : : :
6
...
1 Associativite et priorite des symboles terminaux
6
...
7 Exemples de chier
...
1 Classi cation des grammaires : : : : : : : : : : : :
7
...
1 Les langages contextuels : : : : : : : : : : :
7
...
2 Les langages reguliers : : : : : : : : : : : :
7
...
3 Les reconnaisseurs : : : : : : : : : : : : : :
7
...
2
...
R
...
2
...
2
...
2
...
R
...
E
...
: :
7
...
1 Environnement d'execution : : : : : : : : : : : : : : : :
9
...
1 Organisation de la memoire a l'execution : : : :
9
...
2 Allocation dynamique: gestion du tas : : : : : :
9
...
2
...
2
...
2
...
3 Optimisation de code : : : : : : : : : : : : : : : : : : : :
9
...
1 Optimisations independantes de la machine cible
9
...
2 Optimisations dependantes de la machine cible :
9
...
3 Graphe de ot de contr^le : : : : : : : : : : : : :
o
9
...
4 Elimination des sous-expressions communes : : :
9
...
5 Propagation des copies : : : : : : : : : : : : : : :
9
...
6 Calculs invariants dans les boucles : : : : : : : :
9
...
7 Interpretation abstraite : : : : : : : : : : : : : :
9
...
1 De nition dirigee par la syntaxe : : : : : : : : : : :
8
...
1 Schema de traduction dirige par la syntaxe
8
...
2 Graphe de dependances : : : : : : : : : : :
8
...
3 Evaluation des attributs : : : : : : : : : : :
8
...
3 Contr^le de type : : : : : : : : : : : : : : : : : : :
o
8
...
1 Surcharge d'operateurs et de fonctions : : :
8
...
2 Fonctions polymorphes : : : : : : : : : : : :
8
...
1 Qu'est ce que la compilation?
Tout programmeur utilise jour apres jour un outil essentiel a la realisation de programmes informatiques: le
compilateur
...
C'est donc l'instrument
fondamental a la base de tout realisation informatique
...
1
...
Remarque : Une autre phase importante qui intervient apres la compilation pour obtenir un programme executable est la phase d'editions de liens
...
En general, un compilateur comprend une partie editeur
de lien
...
En outre, sur les systemes modernes, l'edition des liens est faite a l'execution du programme! (le programme
est plus petit, et les mises a jour sont plus faciles)
Autre remarque: on ne parlera pas non plus de la precompilation (cf preprocesseur C)
Attention, il ne faut pas confondre les compilateurs et les interpreteurs !
Un compilateur est un programme (de traduction automatique d'un programme ecrit dans un langage source
en un programme ecrit dans un langage cible)
...
1
...
Exemples de langages compiles: Pascal, C, C++, ADA, Fortran, Cobol
Au lieu de produire un programme cible comme dans le cas d'un compilateur, un interprete execute lui m^me
e
au fur et a mesure les operations speci ees par le programme source
...
A l'inverse d'un compilateur, il travaille simultanement sur le programme et sur les
donnees
...
Generalement les interpreteurs sont assez petits, mais le programme est plus lent
qu'avec un langage compile
...
Par
contre, les langages interpretes sont souvent plus simples a utiliser et tolerent plus d'erreurs de codage que les
langages compiles
...
On les appelle langages
P-code ou langages intermediaires
...
Lorsque l'on execute le programme, ce P-code
est interprete
...
class) "byte code" qui sera
interprete par une machine virtuelle
...
Les interpreteurs de p-code peuvent ^tre relativement petits et rapides, si bien que le p-code peut s'executer
e
presque aussi rapidement que du binaire compile 1
...
On ne garde que les avantages !!
1
...
De m^me, un informaticien a peu de chances d'^tre implique dans la realisation ou m^me la maintee
e
e
nance d'un compilateur pour un langage de programmation majeur
...
Par exemple une traduction de Pascal vers C, ou de Java vers C++, ou de : : :
Lorsque le langage cible est aussi un langage de haut niveau, on parle plut^t de traducteur
...
la traduction d'un langage de programmation de bas niveau vers un autre langage de programmation de haut
niveau
...
e
2) Le but de ce cours est de presenter les principes de base inherents a la realisation de compilateurs
...
Nous verrons
- les principes de base inherents a la realisation de compilateurs: analyse lexicale, analyse syntaxique,
analyse semantique, generation de code,
1 mais presque seulement
:
:::
4
- les outils fondamentaux utilises pour e ectuer ces analyses : fondements de base de la theorie des langages
(grammaires, automates, : : :), methodes algorithmiques d'analyse, : : :
3) En outre, comprendre comment est ecrit un compilateur permet de mieux comprendre les "contraintes"
imposees par les di erents langages lorsque l'on ecrit un programme dans un langage de haut niveau
...
3 Bibliographie succinte
Ce cours s'inspire des livres suivants
A
...
Sethi, J
...
N
...
R
...
Maurer, Les compilateurs: theorie, construction, generation, Masson 1994
...
Levine, T
...
Brown, lex & yacc, Editions O'Reilly International Thomson 1995
...
2
...
1
...
Pour cela, les caracteres sont regroupes en unites lexicales
(token)
...
Par exemple, a partir du morceau de C suivant :
if (i
x=2*x
l'analyseur lexical determinera la suite de token :
mot cle separateur ident op rel ident op arithm ident
separateur ident affectation cste op arithm
:::
2
...
2 Analyse syntaxique
(appelee aussi Analyse hierarchique ou Analyse grammaticale)
Il s'agit de veri er que les unites lexicales sont dans le bon ordre de ni par le langage ie : regrouper les unites lexicales en structures grammaticales, de decouvrir la structure du programme
...
En C, une selection simple doit se presenter sous la forme:
if (
expression ) instruction
Si l'analyseur syntaxique recoit la suite d'unites lexicales
MC IF IDENT OPREL ENTIER : : :
il doit signaler que ce n'est pas correct car il n'y a pas de ( juste apres le if
L'analyseur syntaxique produit un arbre syntaxique
2
...
3 Analyse semantique
(appelee aussi analyse contextuelle)
1 Certains separateurs (ou tous
:
:::
) peuvent faire partie des caracteres a ignorer
6
Dans cette phase, on opere certains contr^les (contr^les de type, par exemple) a n de veri er que l'assemblage
o
o
des constituants du programme a un sens
...
2 Phases de production
2
...
1 Generation de code
Il s'agit de produire les instructions en langage cible
...
Le langage cible est dans ce cas de ni par le type de processeur utilise
...
C'est pourquoi (entre autres raisons), on introduit des machines dites abstraites qui font abstraction des architectures reelles existantes
...
En general, on produira dans un premier temps des instructions pour une machine abstraite (virtuelle)
...
Ainsi, le portage du code compile sera facilite, car la traduction
en code cible virtuel sera faite une fois pour toutes, independamment de la machine cible reelle
...
2
...
2 Optimisation de code
Il s'agit d'ameliorer le code produit a n que le programme resultant soit plus rapide
...
3 Phases paralleles
2
...
1 Gestion de la table des symboles
La table des symboles est la structure de donnees utilisee servant a stocker les informations qui concernent les
identi cateurs du programme source (par exemple leur type, leur emplacement memoire, leur portee, visibilite,
nombre et type et mode de passage des parametres d'une fonction, : : :)
Le remplissage de cette table (la collecte des informations) a lieu lors des phases d'analyse
...
2
...
2 Gestion des erreurs
Chaque phase peut rencontrer des erreurs
...
Un compilateur qui se contente
d'a cher syntax error n'apporte pas beaucoup d'aide lors de la mise au point
...
Un compilateur qui s'arr^te a la premiere erreur n'est pas non
e
e
plus tres performant
...
e
2
...
Par exemple, la realisation du premier compilateur Fortran (1957) a necessite 18 hommes-annees
de travail
...
Di erentes phases de la compilation
Phases d'analyse
analyse lexicale
(scanner)
analyse syntaxique
(parser)
analyse semantique
Phases de production generation de code
optimisation de code
Gestions paralleles
table des symboles
traitement des erreurs
Outils theoriques utilises
expressions regulieres
automates a etats nis
grammaires
automates a pile
traduction dirigee par la syntaxe
traduction dirigee par la syntaxe
programme source
analyse lexicale
suite de lexemes
analyse syntaxique
arbre syntaxique
table des symboles
erreurs
analyse semantique
generation de code
code intermediaire
optimisation de code
programme cible
Fig
...
1 - Structure d'un compilateur
Contrairement a une idee souvent repandue, la plupart des compilateurs sont realises (ecrits) dans un langage
de haut niveau, et non en assembleur
...
Il est m^me possible d'ecrire un compilateur
e
pour un langage L dans ce langage L (gcc est ecrit en C) (bootstrap)
...
Sa t^che principale est de lire les caracteres
a
d'entree et de produire comme resultat une suite d'unites lexicales que l'analyseur syntaxique aura a traiter
...
Dans ce chapitre, nous abordons des techniques de speci cations et d'implantation d'analyseurs lexicaux
...
Le probleme qui nous interesse est la speci cation
e
et la conception de programmes qui executent des actions declenchees par des modeles dans des cha^nes
(traitement de donnees, moteurs de recherche, : : :)
...
1 Unites lexicales et lexemes
De nition 3
...
Exemples: les cha^nes
< > sont des operateurs relationnels
...
Les
cha^nes toto, ind, tab, ajouter sont des identi cateurs (de variables, ou de fonctions)
...
Les symboles : () sont des separateurs
...
2 Un modele est une regle associee a une unite lexicale qui decrit l'ensemble des cha^nes du
programme qui peuvent correspondre a cette unite lexicale
...
3 On appelle lexeme toute suite de caractere du programme source qui concorde avec le modele
d'une unite lexicale
...
Des exemples de lexemes pour cette
unite lexicale sont : truc, i,a1, ajouter valeur : : :
L'unite lexicale NOMBRE (entier signe) a pour modele: toute suite non vide de chi res precedee eventuellement d'un seul caractere parmi f+ ;g
...
Cela peut egalement ^tre un point suivi d'une suite
e
de chi res, et eventuellement du caractere E ou e et d'un lexeme correspondant a l'unite lexicale NOMBRE
...
4, 0
...
, -4e-1, -
...
3
...
1 Expressions regulieres
Dans cette partie, nous introduisons quelques notions de base de la theorie des langages
...
4
On appelle alphabet un ensemble ni non vide de symboles (lettres de 1 ou plusieurs caracteres)
...
On note " le mot vide
...
9
On note + l'ensemble des mots non vides que l'on peut former sur , c'est a dire + = ; f"g
On note jmj la longueur du mot m, c'est a dire le nombre de symboles de composant le mot
...
Remarque : =
n=0
Exemples
...
aaba, bbbacbb, c, ", ca sont des mots de , de longueurs respectives 4, 7, 1, 0 et
2
...
aba n'est pas un mot de
...
On note : l'operateur de concatenation de deux mots: si u = u1 : : :un (avec ui 2 ) et v = v1 : : :vp (avec
vi 2 ), alors la concatenation de u et v est le mot u:v = u1 : : :unv1 : : :vp
Remarque : un mot de n lettres est en fait la concatenation de n mots d'une seule lettre
...
5
ju:vj = juj + jvj
(u:v):w = u:(v:w) (associativite)
" est l'element neutre pour : : u:" = ":u = u
Remarque : nous ecrirons desormais uv pour u:v
De nition 3
...
Exemples
...
L1 est le langage in ni f" c ccc : : : ab ba : : : abccc
acbcc accbc : : : aabb abab abba baab : : : accbccbccccca : : : bbccccaccbcabcccacac :: :g
Soit L2 l'ensemble de tous les mots de ayant exactement 4 a
...
1), certains etant plus facile a decrire que
d'autres
...
De nition 3
...
De nition 3
...
R
...
R
...
R
...
R
...
R
...
R
...
R
...
R
...
R
...
R
...
R
...
Exemples:
(ajb) = (bja) denote l'ensemble de tous les mots formes de a et de b, ou le mot vide
...
C'est a dire
fa c bc bbc bbbc bbbbc : ::g
(a jb ) = (ajb) = (("ja)b )
(ajb) abb(ajb) denote l'ensemble des mots sur fa bg ayant le facteur abb
b ab ab ab denote l'ensemble des mots sur fa bg ayant exactement 3 a
(abbcjbaba)+ aa(ccjbb)
3
...
2
...
R
...
Par exemple, une
ER decrivant les identi cateurs en C pourrait ^tre :
e
ident = (ajbjcjdjejfjgjhjijjjkjljmjnjojpjqjrjsjtjujv jwjxjyjzjAjBjCjDjEjFjGjHjIjJjKjLjMjNjOjPjQ jRjSjTjU
jVjWjXjYjZj ) (ajbjcjdjejfjgjhjijjjkjljmjnjojpjqjrj sjtjujvjwjxjyjzjAjB jCjDjEjFjGjHjIjJjKjLjM jNj
OjPjQj RjSjTjUjVjWjXjYjZj0j1j2j3j4j5j6j7j8j9j )
C'est un peu chiant et illisible : : :
Alors on s'autorise des de nitions regulieres et le symbole ; sur des types ordonnes (lettres, chi res, : : : )
...
Exemple : l'unite lexicale IDENT (identi cateurs) en C devient
8 lettre = A ; Z ja ; z
>
< chi re = 0 ; 9
> sep =
: IDENT = (lettre j sep)( lettre j chi re j sep)
Remarque IMPORTANTE : toutes les unites lexicales ne peuvent pas ^tre exprimees par des de nitions
e
regulieres
...
Autre exemple : il n'est pas possible d'exprimer sous forme d'ER les systemes de parentheses bien formes, ie les
mots (), (())(), ()(()()(())) : : :
...
3
...
2 Attributs
Pour ce qui est des symboles <= >= < > <>, l'analyseur syntaxique a juste besoin de savoir que cela correspond a l'unite lexicale OPREL (operateur relationnel)
...
Pour ce qui est des identi cateurs, l'analyseur syntaxique a juste besoin de savoir que c'est l'unite lexicale IDENT
...
L'analyseur semantique aura aussi besoin du type de la variable pour veri er que les expressions sont semantiquement
correctes
...
3
...
3 Analyseur lexical
Recapitulons : le r^le d'un analyseur lexical est la reconnaissance des unites lexicales
...
e
11
Dans la theorie des langages, on de nit des automates qui sont des machines theoriques permettant la reconnaissance de mots (voir chapitre 7)
...
En
particulier :
Theoreme 3
...
Contentons nous pour l'instant de donner un exemple d'automate:
Le langage regulier decrit par l'ER (abbcjbacc)+c(cjbb) est reconnu par l'automate:
a
1
b
c
2
b
a
0
3
b
4
5
c
6
c
c
7
b
b
8
a
b
qui s'ecrit egalement
etat a
0 1
1
2
3
4 5
5
6 1
b c
4
2
3
6
3
4 7
7
8 7
8
7
Bon, un langage regulier (et donc une ER) peut ^tre reconnu par un automate
...
Lorsqu'une unite
lexicale est reconnue, elle envoyee a l'analyseur syntaxique, qui la traite, puis repasse la main a l'analyseur lexical
qui lit l'unite lexicale suivante dans le programme source
...
Exemple de morceau d'analyseur lexical pour le langage Pascal (en C) :
c = getchar()
switch (c) {
case ':' : c=getchar()
if (c== '=')
{
unite_lex = AFFECTATION
c= getchar()
}
else
unite_lex = DEUX_POINTS
break
case '<' : unite_lex := OPREL
c= getchar()
if (c=='=')
{
attribut = INFEG
c = getchar()
}
else
attribut := INF
break
case
...
default : ERREUR()
}
}
void Etat36524()
...
Par exemple : flex
Exemple de programme en flex :
chiffre 0-9]
lettre
a-zA-Z]
entier
+-]? 1-9]{chiffre}*
ident
{lettre}({lettre}|{chiffre})*
%%
":="
{ return AFF }
"<="
{
attribut = INFEG
return OPREL
}
if|IF|If|iF {return MC_IF }
{entier} {return NB }
{ident}
{return ID }
%%
main() {
yylex()
}
3
...
Les erreurs se produisent lorsque l'analyseur est confronte a une suite de caracteres qui ne
correspond a aucun des modeles d'unite lexicale qu'il a a sa disposition
...
S'il s'agit du mot clef mal orthographie, c'est l'analyseur syntaxique qui detectera alors une
erreur
...
L'analyseur lexical peut juste
signaler que la cha^ne 1i ne correspond a aucune unite lexicale de nie
...
On utilise des
1 attention, il faut tout de m^me signaler a l'utilisateur que l'on a ignore ces caracteres
e
:
13
techniques de calcul de distance minimale entre des mots
...
En outre, au niveau lexical, elle est peu e cace, car
elle entraine d'autres erreurs lors des phases d'analyse suivantes 2
...
En fait, en general, cette technique se contente de re ler le
probleme a l'analyseur syntaxique
...
2 par exemple, dans le cas du 1i, le calcul de la distance minimaleindiquera qu'il faut considerer i tout simplement
...
Soit lors de l'analyse semantique si i n'a pas ete declaree, soit
lors de l'execution si i sert a autre chose
...
lex est un utilitaire d'unix
...
(f)lex accepte en entree des speci cations
d'unites lexicales sous forme de de nitions regulieres et produit un programme ecrit dans un langage de haut
niveau (ici le langage C) qui, une fois compile, reconnait ces unites lexicales (ce programme est donc un analyseur
lexical)
...
l
lex
...
l
lex
...
c
gcc lex
...
c -ll
gcc lex
...
c -lfl
a
...
L'executable obtenu lit le texte d'entree caractere par caractere jusqu'a ce qu'il trouve le plus long pre xe
du texte d'entree qui corresponde a l'une des expressions regulieres
...
Il execute alors l'action correspondante
...
4
...
o
les regles de traduction sont des suites d'instructions de la forme
exp1
action1
exp2
action2
...
Les expi sont des expressions regulieres (f)lex et doivent commencer en colonne 0
...
e
...
e
la section du bloc principal et des fonctions auxiliaires est facultative (ainsi donc que la ligne %% qui la precede)
...
15
expression reconna^t, accepte
c
nc
"s"
r1r2
...
exemple
a
n+
"abc*+"
ab
a
...
1 - Expressions regulieres (f)lex
4
...
La gure 4
...
Attention, (f)lex fait la di erence entre les minuscules et les majuscules
...
Priorites:
est interprete comme (truc)|(machi(n*))
est interprete avec lex comme (abc)f1,3g et avec ex comme ab(cf1,3g)
est interprete avec lex comme (^truc)|machin et avec ex comme ^(truc|machin)
Avec lex, une reference a une de nition reguliere n'est pas consideree entre (), en ex si
...
4
...
int yyleng : longueur de cette cha^ne
...
int yywrap() : fonction toujours appelee en n de ot d'entree
...
yywrap() retourne 0
si l'analyse doit se poursuivre (sur un autre chier d'entree) et 1 sinon
...
L'utilisateur peut la
rede nir dans la section des fonctions auxiliaires
...
yyterminate() : fonction qui stoppe l'analyseur (ATTENTION : avec ex uniquement)
...
4 Options de compilation ex
-d
-i
-l
-s
pour un mode debug
pour ne pas di erencier les majuscules des minuscules
pour avoir un comportement lex
pour supprimer l'action par defaut (sortira alors en erreur lors de la rencontre d'un caractere qui ne
correspond a aucun motif)
4
...
l
Ce premier exemple reconnait les nombres binaires :
%%
(0|1)+
printf("oh un nombre binaire !\n")
Tout ce qui n'est pas reconnu comme nombre binaire est a che a l'ecran
...
printf("oh le beau
// RIEN !!!
nombre binaire %s !\n", yytext)
Ce deuxieme exemple supprime les lignes qui commencent par p ainsi que tous les entiers, remplace les o par des
* et retourne le reste inchange
...
)*\n
o
...
%{
int nbVoyelles, nbConsonnes, nbPonct
%}
consonne
b-df-hj-np-xz]
ponctuation
, :?!\
...
|\n
// ne rien faire
%%
main(){
nbVoyelles = nbConsonnes = nbPonct = 0
yylex()
printf("Il y a %d voyelles, %d consonnes et %d signes de ponctuations
...
Par exemple, en Pascal, un programme bien forme est compose de blocs, un bloc est forme d'instructions,
une instruction de : : :
La syntaxe d'un langage peut ^tre decrite par une grammaire
...
e
Le probleme est donc
etant donnee une grammaire G
etant donne un mot m (un programme)
=) est ce que m appartient au langage genere par G?
Le principe est d'essayer de construire un arbre de derivation
...
5
...
Mais la plupart du temps,
les langages ne sont pas reguliers et ne peuvent pas s'exprimer sous forme d'une ER
...
On a donc besoin d'un outil plus
puissant : les grammaires
...
1
...
Par exemple: L'etudiant subit un cours
On dira donc :
phrase = sujet verbe complement
Ensuite, il faut expliquer ce qu'est un sujet, un verbe, un complement
...
1 Une grammaire est la donnee de G = (VT VN S P) ou
VT est un ensemble non vide de symboles terminaux (alphabet terminal)
T
VN est un ensemble de symboles non-terminaux, avec VT VN =
S est un symbole initial 2 VN appele axiome
P est un ensemble de regles de productions (regles de reecritures)
De nition 5
...
e
est appellee partie gauche de la production, et partie droite de la production
...
Les lettres
minuscules du debut de l'alphabet sont utilisees pour representer des symboles terminaux
...
Les lettres
grecques denotent des cha^nes composees de symboles terminaux et non terminaux
...
1
...
On notera ! une derivation obtenue par application d'une seule regle de production, et ! une derivation obtenue par l'application de n regles de production, ou n 0
...
C'est
l'analyse semantique qui permettra d'eliminer ce probleme
...
3 Etant donnee une grammaire G, on note L(G) le langage genere par G et de ni par
fw 2 (VT ) tq S ! wg
(c'est a dire tous les mots composes uniquement de symboles terminaux (de lettres de l'alphabet) que l'on peut
former a partir de S )
...
4 On appelle arbre de derivation (ou arbre syntaxique) tout arbre tel que
la racine est l'axiome
19
les feuilles sont des unites lexicales ou "
les noeuds sont des symboles non-terminaux
les ls d'un noeud sont 0 : : : n si et seulement si
! 0::: n
est une production
Exemple : Soit la grammaire ayant S pour axiome et pour regles de production
P = S ! aTb jjcS
T ! cSS
Un arbre de derivation pour le mot accacbb est :
S
a
T
c
b
S
S
c
a
T
b
S
c
S ! aT b ! acSSb ! accSb ! accaTbb ! accaSbb ! accacbb (derivations gauches)
ou S ! aTb ! acSSb ! acSaT bb ! acSaSbb ! acSacbb ! accacbb (derivations droites)
Ces deux suites di erentes de derivations donnent le m^me arbre de derivation
...
5 Une grammaire est dite ambigue s'il existe un mot de L(G) ayant plusieurs arbres syntaxiques
...
8 instr !
>
< instr !
Exemple : Soit G donnee par > instr ! : : :
:
if (expr )
if (expr )
instr else instr
instr
expr ! : : :
Cette grammaire est ambigue car le mot m = if (x > 10 ) if (y < 0) a = 1 else a = 0
possede deux arbres syntaxiques di erents :
instr
if
(
expr
)
x>10
instr
if
instr
if (
expr ) instr
y<10
a=1
else instr
car il y a deux interpretations syntaxiques possibles :
if (x>10)
if (y<0)
a=1
else
a=0
// finsi
// finsi
(
expr )
x>10
if (
a=0
else
instr
expr ) instr
y<10
instr
a=0
a=1
if (x>10)
if (y<0)
a=1
// finsi
else
a=0
// finsi
5
...
Il doit dire si cette suite (ce mot) est syntaxiquement correct, c'est a dire si c'est un mot du langage
genere par la grammaire qu'il possede
...
S'il y
arrive, alors le mot est syntaxiquement correct, sinon il est incorrect
...
20
5
...
5
...
1 Exemples
Exemple 1:
S ! aSbT jcT jd avec le mot w = accbbadbc
T ! aT jbS jc
On part avec l'arbre contenant le seul sommet S
La lecture de la premiere lettre du mot (a) nous permet d'avancer la construction
S
w= accbbadbc
a
S
b
T
puis la deuxieme lettre nous amene a
S
w= accbbadbc
a
S
c
b
T
b
T
T
et ainsi de suite jusqu'a
S
w= accbbadbc
a
S
c
b
T
c
S
a
S
b
d
T
c
On a trouve un arbre de derivation, donc le mot appartient au langage
...
Exemple 2:
S ! aAb avec le mot w = acb
A ! cdjc
On se retrouve avec
S
w=acb
a
A
b
En lisant le c, on ne sait pas s'il faut prendre la regle A ! cd ou la regle A ! c
...
Ou alors, il faut se donner la possibilite de faire des retour en arriere: on essaye
la 1ere regle (A ! cd), on aboutit a un echec, alors on retourne en arriere et on essaye la deuxieme regle et la
ca marche
...
Exemple 4: grammaire des expressions arithmetiques
21
8 E ! TE
>
> E ! +T E j ; T E j"
<
> T ! F T j=FT j"
> T ! FT
: F ! (E)j nb
0
0
0
0
0
0
0
0
avec le mot w = 3 4 + 10 (5 + 11)=34 + 12
P f
...
Ca
existe, et ca s'appelle une table d'analyse
...
3
...
Exemple :
8
< S ! Ba
! cP
: B ! dS jbP jP j"
P
S ! a, donc a 2 PREMIER(S) S ! cPa, donc c 2 PREMIER(S)
S ! bPa, donc b 2 PREMIER(S) S ! dSa, donc d 2 PREMIER(S)
Il n'y a pas de derivation S ! "
Donc PREMIER(S)= fa b c dg
B ! dS, donc d 2 PREMIER(B)
aB ! a , donc PREMIER(aB)= fag
BSb ! ab, donc a 2 PREMIER(BS)
Algorithme de construction des ensembles PREMIER :
1
...
Si X est un non-terminal et X ! " est une production, ajouter " dans PREMIER(X)
3
...
Recommencer jusqu'a ce qu'on n'ajoute rien de nouveau dans les ensembles PREMIER
...
Ajouter un marqueur de n de cha^ne (symbole $ par exemple) a SUIVANT(S)
(ou S est l'axiome de depart de la grammaire)
2
...
Pour chaque production A ! B, alors ajouter SUIVANT(A) a SUIVANT(B)
4
...
Exemple 1 :
8 E ! T E0
> 0
> E ! +T E0j ; T E0j"
<
> T 0! F T 0 0j=FT 0j"
> T ! FT
: F ! (E)j nb
SUIVANT(E) = f $ )
SUIVANT(E 0 ) = f
$)
SUIVANT(T) = f + ;
)$
SUIVANT(T 0 ) = f
+; )$
SUIVANT(F) = f =
) +
Exemple 2 :
8 S ! aSbjcdjSAe
<
: A ! aAdBj"
B ! bb
PREMIER SUIVANT
S ac
$bae
A a"
ed
ed
B b
;
$
g
g
g
g
g
Construction de la table d'analyse LL
Une table d'analyse est un tableau M a deux dimensions qui indique pour chaque symbole non-terminal A et
chaque symbole terminal a ou symbole $ la regle de production a appliquer
...
pour tout a 2PREMIER( ) (et a 6= "), rajouter la production A ! dans la case M A a]
2
...
1
5
...
3 Analyseur syntaxique
Maintenant qu'on a la table, comment l'utiliser pour determiner si un mot m donne est tel que S ! m?
On utilise une pile
...
5
...
5
...
2
...
5
...
4 Grammaire LL(1)
L'algorithme precedent ne peut pas ^tre applique a toutes les grammaires
...
De nition 5
...
Le terme "LL(1)" signi e que l'on parcourt l'entree de gauche a droite (L pour Left to right scanning), que l'on
utilise les derivations gauches (L pour Leftmost derivation), et qu'un seul symbole de pre-vision est necessaire
a chaque etape necessitant la prise d'une decision d'action d'analyse (1)
...
On ne peut pas utiliser cette
methode d'analyse
...
Autre exemple :
S ! aT bbbb n'est pas LL(1)
T ! Tbj"
Theoreme 5
...
Voyons les autres termes
...
3
...
8 Une grammaire est immediatement recursive a gauche si elle contient un non-terminal A
tel qu'il existe une production A ! A ou
Exemple :
8
est une cha^ne quelconque
...
Eliminitation de la recursivite a gauche immediate:
Remplacer toute regle de la forme A ! A
A ! A0
A0 ! A0 j"
j
par
Theoreme 5
...
e
Sur l'exemple, on obtient :
8 S ! BS0
> 0
> S ! cAS0j"
> A ! A0
<
> A0 ! aA00j" 0
> B0! dB 0jeB
> B ! bB j"
:
Cette grammaire reconnait le m^me langage que la premiere
...
Il s'obtient a partir de la deuxieme grammaire par S ! BS 0 ! dB 0S 0 ! dbB 0S 0 ! dbbB 0 S 0 ! dbbS 0 !
dbbcAS 0 ! dbbcA0S 0 ! dbbcaA0S 0 ! dbbcaaA0S 0 ! dbbcaaS 0 ! dbbcaa
...
C'est a dire en fait que S ! S j" est equivalent a S
gauche, mais a droite, ce qui n'a rien a voir)
...
10 Une grammaire est recursive a gauche si elle contient un non-terminal A tel qu'il existe
+
une derivation A ! A ou
est une cha^ne quelconque
...
1 en fait, c'est une grammaire LL(2)
:
26
Eliminitation de la recursivite a gauche pour toute grammaire sans regle A ! ":
Ordonner les non-terminaux A1 A2 : : : An
Pour i=1 a n faire
pour j=1 a i-1 faire
remplacer chaque production de la forme Ai ! Aj ou Aj !
Ai ! 1 j : : : j p
n pour
eliminer les recursivites a gauche immediates des productions Ai
n pour
1j
: : : j p par
Theoreme 5
...
e
Sur l'exemple:
On ordonne S A
i = 1 pas de recursivite immediate dans S ! Aajb
i = 2 et j = 1 on obtient A ! AcjAadjbdj"
on elimine la rec
...
3
...
12 Une grammaire est dite propre si elle ne contient aucune production A ! "
Comment rendre une grammaire propre? En rajoutant une production dans laquelle le A est remplace par ",
ceci pour chaque A appara^ssant en partie droite d'une production, et pour chaque A d'un A ! "
...
3
...
8 S ! bacdAbdjbacdBcca
>
> A ! aD
<
Exemple : > B ! cE
> C ! :::
: E ! :::
Au depart, pour savoir s'il faut choisir S ! bacdAbd ou S ! bacdBcca, il faut avoir lu la 5ieme lettre du mot
(un a ou un c)
...
Ce qui est incompatible
avec une grammaire LL(1)
...
)
Factorisation a gauche :
27
Pour chaque non-terminal A
trouver le plus long pre xe commun a deux de ses alternatives ou plus
Si 6= , remplacer A ! 1 j : : : j nj 1 j : : : j p (ou les i ne commencent pas par ) par
A ! A0j 1 j : : : j p
A0 ! 1 j : : : j n
Recommencer jusqu'a ne plus en trouver
...
3
...
Mais
comment savoir que notre grammaire est LL(1)? 2
Etant donnee une grammaire
1
...
Il n'y a pas de methodes
...
2
...
la factoriser a gauche si necessaire
4
...
Sinon, il faut concevoir une autre methode pour l'analyse syntaxique 3
...
Pour lever l'ambigu te, on considere les priorites classiques des operateurs et on obtient
la grammaire non ambigue:
8 E ! E + T j E ; T jT
<
j
: T ! T jFnbT=F jF
F ! (E)
Apres 8
suppression de la recursivite a gauche, on obtient
< E0! T E0 0 0 T 0 ! FT 0j=FT 0j"
E !
: T ! F+T0 E j ; T E j" F ! (E)j nb
T
Inutile de factoriser a gauche
...
Autre exemple : la grammaire
S ! aT bj" n'est pas LL(1)
...
4 Analyse ascendante
Principe : construire un arbre de derivation du bas (les feuilles, ie les unites lexicales) vers le haut (la racine, ie
l'axiome de depart)
...
C'est a dire que l'on ne s'autorise que deux
operations :
{ decallage (shift) : decaller d'une lettre le pointeur sur le mot en entree
{ reduction (reduce) : reduire une cha^ne (suite consecutive de terminaux et non terminaux a gauche du
pointeur sur le mot en entree et nissant sur ce pointeur) par un non-terminal en utilisant une des regles
de production
2 Attention, le theoreme 5
...
3 si la grammaire est LL(k), on peut utiliser une methode descendante en modi ant legerement la de nition des ensembles
PREMIER et SUIVANT (cf exercices)
:
:
28
a a a c b a a c b c b c b c b a c b c
S
S
S
S
S
S
S
S
S
S
S
S
S
Fig
...
3 - Analyse ascendante
Exemple : S ! aSbS jc avec le mot u = aacbaacbcbcbacbc
a acbaacbcbcbacbc on ne peut rien reduire, donc on decalle
a a cbaacbcbcbacbc on ne peut rien reduire, donc on decalle
aa c baacbcbcbacbc ah ! On peut reduire par S ! c
aa S baacbcbcbacbc on ne peut rien reduire, donc on decalle
:::
aaSbaa c bcbcbacbc on peut utiliser S ! c
aaSbaa S bcbcbacbc on ne peut rien reduire, donc on decalle
aaSbaaS b cbcbacbc on ne peut rien reduire, donc on decalle
aaSbaaSb c bcbacbc On peut utiliser S ! c
aaSbaaSb S bcbacbc On peut utiliser S ! aSbS
aaSba S bcbacbc decallage
aaSbaS b cbacbc decallage
aaSbaSb c bacbc reduction par S ! c
aaSbaSb S bacbc reduction par S ! aSbS
aaSb S bacbc reduction par S ! aSbS
a S bacbc decallage
aS b acbc decallage
aSb a cbc decallage
aSba c bc reduction par S ! c
aSba S bc decallage
aSbaS b c decallage
aSbaSb c reduction par S ! c
aSbaSb S reduction par S ! aSbS
aSb S reduction par S ! aSbS
S termine!!!! On a gagne, le mot est bien dans le langage
...
3)
...
Table d'analyse SLR
(on l'appelle comme ca parce que, de m^me que la methode descendante vue precedemment ne permettait d'anae
lyser que les grammaires LL(1), cette methode va permettre d'analyser les grammaires dites LR)
...
Dans ce cas, on empile la lettre lue et on va dans un autre etat j
...
On note ca
rp
- soit on accepte le mot
...
Case vide
29
Construction de la table d'analyse : utilise aussi les ensembles SUIVANT ( et donc PREMIER), plus ce
qu'on appelle des fermetures de 0-items
...
" quelque part dans la partie droite
...
La fermeture de cet ensemble d'items est :
fT ! T :F E ! E: + T F ! :nb F ! :(E)g
Transition par X d'un ensemble d'items I :
(I X) =Fermeture(tous les items A ! X: ) ou A ! :X
2I
Sur l'exemple ETF :
Soit l'ensemble d'items I = fT ! T :F E ! E: + T F ! :nb F ! :(E)g, on aura
(I F ) = fT ! T F:g
(I +) = fE ! E + :T T ! :T F T ! :F F ! :nb F ! :(E)g
etc
...
Exemple : l'analyse du mot m = 3 + 4$ est donnee gure 5
...
La gure 5
...
On peut aussi dessiner l'arbre obtenu ( gure 5
...
action
d5
r6 : F ! nb
je suis en 0 avec F : je vais en 3
r4 : T ! F
je suis en 0 avec T : je vais en 2
r2 : E ! T
je suis en 0 avec E : je vais en 1
d6
ERREUR !! Ce mot n'appartient pas au langage
...
4 - Analyse LR du mot m = 3 + 4$
Remarques
Cette methode permet d'analyser plus de grammaires que la methode descendante (car il y a plus de grammaires
qui sont LR que de grammaires qui sont LL(1))
En TP on va utiliser un outil (bison) qui construit tout seul une table d'analyse LR (LALR en fait, mais c'est
presque pareil) a partir d'une grammaire donnee
...
e
31
pile
$0
$035
$0F
$0F 3
$0T
$0T 2
$0E
$0E1
$0E1+6
$0E1+645
$0E1+6F
$0E1+6F3
$0E1+6T
$0E1+6T9
$0E1+6T9
$0E1+6T9
$0E1+6T9
$0E1+6T9
$0E1+6T
$0E1+6T9
$0E
$0E1
7
725
7F
7 F 10
Fig
...
5 - Analyse LR du mot m = 3 + 4 2$
3 + 4 * 2
F
F
T
T
E
F
T
E
Fig
...
6 - arbre de derivation du mot 3 + 4 2
32
Les grammaires ambigues provoquent des con its
- con it decallage/reduction : on ne peut pas decider a la lecture du terminal a s'il faut reduire une
production S ! ou decaller le terminal
- con it reduction/reduction : on ne peut pas decider a la lecture du terminal a s'il faut reduire une
production S ! ou une production T !
On doit alors resoudre les con its en donnant des priorites aux actions (decaller ou reduire) et aux productions
...
Lorsqu'on lit le 2ieme + on a le choix entre
- reduire ce qu'on a deja lu par E ! E + E
...
Ici on s'en cague car c'est pareil
...
Soit a analyser 3+ 4 5
...
Si l'on reduit on calcule (3 + 4) 5,
si on decalle on calcule 3 + (4 5)! On ne peut plus s'en foutre ! Il faut decaller
...
On ne s'en fout pas non plus, il faut reduire !
Bref, il faut mettre qlqpart dans l'analyseur le fait que est prioritaire sur +
...
5
...
Le gestionnaire d'erreur doit
- indiquer la presence de l'erreur de facon claire et precise
- traiter l'erreur rapidement pour continuer l'analyse
- traiter l'erreur le plus e cacement possible de maniere a ne pas en creer de nouvelles
...
Cependant, une erreur peut se produire
longtemps avant d'^tre detectee (par exemple l'oubli d'un f ou g dans un programme C)
...
La plupart du temps, le gestionnaire d'erreurs doit deviner ce que le programmeur
avait en t^te
...
Il existe plusieurs strategies de recuperation sur erreur : mode panique, au niveau du syntagme 5, productions
d'erreur, correction globale
...
Ces erreurs illegitimes peuvent ^tre syntaxiques mais
e
egalement semantiques
...
Lors de l'utilisation de cette variable, l'analyseur semantique indiquera qu'elle n'a pas
ete declaree
...
5
...
Quand il decouvre une erreur, l'analyseur syntaxique elimine les
symboles d'entree les uns apres les autres jusqu'a en rencontrer un qui appartienne a un ensemble d'unites lexicales de synchronisation, c'est a dire (par exemple) les delimiteurs ( , end ou g), dont le r^le dans un programme
o
source est clair
...
5
...
2 Recuperation au niveau du syntagme
Quand une erreur est decouverte, l'analyseur syntaxique peut e ectuer des corrections locales
...
En outre, il faut faire attention a ne pas faire de modi cations
qui entrainerait une boucle in nie (par exemple decider d'inserer systematiquement un symbole juste avant le
symbole courant)
...
On implante cette recuperation sur erreur en remplissant les cases vides des tables d'analyse par des pointeurs
vers des routines d'erreur
...
Exemple : grammaire des expressions arithmetiques
(1) E ! E + E
(3) E ! (E)
(2) E ! E E
(4) E ! nb
La table d'analyse LR avec routines d'erreur est
( )
$
E
etat nb +
0 d3 e1 e1 d2 e2 e1 1
1 e3 d4 d5 e3 e2 ACC
2 d3 e1 e1 d2 e2 e1 6
3 r4 r4 r4 r4 r4 r4
4 d3 e1 e1 d2 e2 e1 7
5 d3 e1 e1 d2 e2 e1 8
6 e3 d4 d5 e3 d9 e4
7 r1 r1 d5 r1 r1 r1
8 r2 r2 r2 r2 r2 r2
9 r3 r3 r3 r3 r3 r3
Les routines d'erreur etant :
e1 : (routine appelee depuis les etats 0, 2, 4 et 5 lorsque l'on rencontre un operateur ou la n de cha^ne d'entree
alors qu'on attend un operande ou une parenthese ouvrante)
Emettre le diagnostic operande manquant
Empiler un nombre quelconque et aller dans l'etat 3
e2 : (routine appelee depuis les etats 0,1,2,4 et 5 a la vue d'une parenthese fermante)
Emettre le diagnostic parenthese fermante excedentaire
Ignorer cette parenthese fermante
e3 : (routine appelee depuis les etats 1 ou 6 lorsque l'on rencontre un nombre ou une parenthese fermante alors
que l'on attend un operateur)
Emettre le diagnostic operateur manquant
Empiler + (par exemple) et aller a l'etat 4
e4 : (routine appelee depuis l'etat 6 qui attend un operateur ou une parenthes fermante lorsque l'on rencontre
la n de cha^ne)
Emettre le diagnostic parenthese fermante oubliee
Empiler une parenthese fermante et aller a l'etat 9
34
5
...
3 Productions d'erreur
Si l'on a une idee assez precise des erreurs courantes qui peuvent ^tre rencontrees, il est possible d'augmenter la
e
grammaire du langage avec des productions qui engendrent les constructions erronees
...
5
...
Il existe des
algorithmes qui permettent de choisir une sequence minimale de changements correspondant globalement au
co^t de correction le plus faible
...
En outre, le programme correct le plus
e
e
proche n'est pas forcemment celui que le programmeur avait en t^te : : :
e
35
Chapitre 6
L'outil yacc/bison
De nombreux outils ont ete batis pour construire des analyseurs syntaxiques a partir de grammaires
...
yacc est un utilitaire d'unix, bison est un produit gnu
...
yacc est l'acronyme de Yet Another Compiler Compiler, c'est a dire encore un compilateur de compilateur
...
specifications bison
...
tab
...
y
compilateur C
cc
...
c -ly
a
...
Il utilise donc le
modele decallages-reductions
...
1 Structure du chier de speci cations bison
%f
declaration (en C) de variables, constantes, inclusions de chiers, : : :
%g
declarations des unites lexicales utilisees
declarations de priorites et de types
%%
regles de production et actions semantiques
%%
routines C et bloc principal
Les symboles terminaux utilisables dans la description du langage sont
; des unites lexicales que l'on doit imperativement declarer par %token nom
...
Par exemple: '+' 'a'
Les symboles non-terminaux sont les caracteres ou les cha^nes de caracteres non declarees comme unites
lexicales
...
SI et si ne designent pas le m^me objet
...
prodn
Les actions semantiques sont des instructions en C inserees dans les regles de production
...
Exemples:
G : S B 'X' fprintf("mot reconnu") g
S : A fprint("reduction par A") g T fprintf("reduction par T") g 'a'
La section du bloc principal doit contenir une fonction yylex() e ectuant l'analyse lexicale du texte, car
l'analyseur syntaxique l'appelle chaque fois qu'il a besoin du terminal suivant
...
l
...
y avec l'option -d qui produit un chier nom
...
h contenant
les de nitions (sous forme de #define) des unites lexicales (les token) rencontrees et du type YYSTYPE
s'il est rede ni,
; inclure le nom
...
h au debut du chier de speci cations (f)lex
; creer un
...
yy
...
tab
...
o et rajouter la bibliotheque
(f)lex lors de la compilation C du chier nom
...
c avec : gcc nom
...
c lex
...
o -ly -lfl
(attention a l'ordre de ces bibliotheques)
...
2 Attributs
A chaque symbole (terminal ou non) est associe une valeur (de type entier par defaut)
...
Le symbole $$ reference la valeur de l'attribut associe au non-terminal de la partie gauche, tandis que $i reference
la valeur associee au i-eme symbole (terminal ou non-terminal) ou action semantique de la partie droite
...
3 Communication avec l'analyseur lexical : yylval
L'analyseur syntaxique et l'analyseur lexical peuvent communiquer entre eux par l'intermediaire de la variable
int yylval
...
La valeur de cette unite lexicale peut ^tre rangee dans
e
yylval
...
La variable yylval est de type YYSTYPE (declare dans la bibliotheque yacc/bison) qui est un int par defaut
...
Par exemple
%union {
int entier
double reel
char * chaine
}
permet de stocker dans yylval a la fois des int, des double et des char *
...
entier=atoi(yytext)
return NOMBRE
}
Le type des lexemes doit alors ^tre precise en utilisant les noms des champs de l'union
e
%token
%token
On peut egalement typer des non-terminaux (pour pouvoir associer une valeur de type autre que
non-terminal) par
int
a un
%type
%type
6
...
: instruction qui permet de stopper l'analyseur syntaxique
...
e
main() : le main par defaut se contente d'appeler yyparse()
...
%start non-terminal : action pour signi er quel non-terminal est l'axiome
...
yyparse()
YYACCEPT
YYABORT
6
...
y
conflicts: 6 shift/reduce, 2 reduce/reduce
Il y a un con it reduce/reduce lorsque le compilateur a le choix entre (au moins) deux productions pour reduire
une cha^ne
...
yacc/bison resoud les con its de la maniere suivante :
con it reduce/reduce : la production choisie est celle apparaissant en premier dans la speci cation
...
Pour voir comment bison a resolu les con its, il est necessaire de consulter la table d'analyse qu'il a construit
...
Le chier contenant la table s'appelle nom
...
5
...
Les declarations suivantes (dans la section des de nitions)
%left term1 term2
%right term3
%left term4
%nonassoc term5
indiquent que les symboles terminaux term1, term2 et term4 sont associatifs a gauche, term3 est associatif a
droite, alors que term5 n'est pas associatif
...
Lorsque les symboles sont dans la m^me declaration d'associativite, ils ont
e
la m^me priorite
...
On peut forcer la priorite d'une production en faisant suivre la production de la declaration
%prec terminal-ou-unite-lexicale
ce qui a pour e et de donner comme priorite (et comme associativite) a la production celle du terminal-ou-unitelexicale (ce terminal-ou-unite-lexicale devant ^tre de ni, m^me de maniere factice, dans la partie Ib)
...
e
...
6
...
Cette fonction peut ^tre rede nie par l'utilisateur
...
On peut rajouter dans toute production de la forme A ! 1j 2j : : : une production
A ! error
Dans ce cas, une production d'erreur sera traitee comme une production classique
...
Des qu'une erreur est rencontree, tous les caracteres sont avales jusqu'a rencontrer le caractere correspondant a
...
e
La routine yyerrok replace l'analyseur dans le mode normal de fonctionnement c'est a dire que l'analyse syntaxique n'est pas interrompue
...
7 Exemples de chier
...
Le mot doit se terminer par le
symbole $
...
%%
mot : PI '$'
{printf("mot accepte\n") YYACCEPT }
PP : 'a' IP
| 'b' PI
| /* vide */
IP : 'a' PP
| 'b' II
| 'a'
PI : 'a' II
| 'b' PP
| 'b'
II :
|
|
|
'a'
'b'
'a'
'b'
PI
IP
'b'
'a'
%%
int yylex() {
char car=getchar()
if (car=='a' || car=='b' || car=='$') return(car)
else printf("ERREUR : caractere non reconnu : %c ",car)
}
Ce deuxieme exemple lit des listes d'entiers precedees soit du mot somme, soit du mot produit
...
Lorsque la liste debute par somme,
l'executable doit a cher la somme des entiers, lorsqu'elle debute par produit, il doit en a cher le produit
...
Cet exemple utilise la fonction yylex generee par le compilateur flex a partir du chier de speci cation
exemple2
...
h>
#include "exemple2
...
h"
// INCLUSION DES DEFS DES TOKEN
int nbligne=0
%}
chiffre
0-9]
entier
{chiffre}+
espace
\t]
%%
somme
return(SOMME)
produit
return(PRODUIT)
\n
nbligne++
...
printf("ERREUR ligne %d : %c inconnu\n",nbligne,yytext 0])
%%
Le chier de speci cations bison est alors le suivant
%token SOMME
%token PRODUIT
%token NOMBRE
%token FIN
%%
texte : liste texte
| FIN {printf("Merci et a bientot\n") YYACCEPT }
liste : SOMME sentiers '
...
' {printf("le produit est %d\n",$2) }
sentiers : sentiers ',' NOMBRE {$$=$1+yylval }
| NOMBRE {$$=yylval }
pentiers : pentiers ',' NOMBRE {$$=$1*yylval }
| NOMBRE {$$=yylval }
%%
Un Make le pour compiler tout ca est
exemple2 : lex
...
o exemple2
...
c
gcc exemple2
...
c lex
...
o -o exemple2 -ly -lfl
lex
...
o :
lex
...
c
gcc -c lex
...
c
lex
...
c : exemple2
...
tab
...
l
exemple2
...
h : exemple2
...
y
exemple2
...
c : exemple2
...
y
40
Chapitre 7
Theorie des langages : les automates
7
...
On distingue en fait quatres
types de langage, correspondant a quatres types de grammaires
...
Grammaire de type 3 (reguliere)
Les productions sont de la forme A ! wB ou A ! w avec A 2 VN (un seul symbole non terminal),
B 2 VN et8 2 VT (une cha^ne de symboles terminaux)
w
< S ! aSjT jabU jcc
Exemple: : T ! cT j"
U ! abS
Grammaire de type 2 (hors contexte) (algebrique)
S
Les productions sont de la forme A ! avec A 2 VN et 2 (VN VT )
Exemple (grammaire de Dyck): S ! ( S ) S j"
Grammaire de type 1 (contextuelle)
S
S
Les productions sont de la forme ! avec 2 (VN VT )+ et 2 (VN VT ) et j j j j
Les productions S ! " sont autorisees si S 2 VN n'apparait pas dans la partie droite d'une production de G
...
1 Les grammaires de type 0 englobent les grammaires de type 1 qui englobent les grammaires de
type 2 qui englobent les grammaires de type 3
...
1
...
Ce langage est une traduction abstraite du probleme consistant a controler
1 par la suite, on dira qu'un langage est de type s'il est de type et pas de type + 1
:
i
i
41
i
que, dans un programme, une variable doit ^tre declaree avant d'^tre utilisee
...
Nous on veut ensuite deplacer chaque lettre du w
...
Donnons alors un coup de baguette magique sur chaque symbole qui doit ^tre deplace :
e
8 DA ! DA0
<
! DB
: DB ! DC 00
DC
puis deplacons les :
8 A0A ! AA0 A0B ! BA0 A0C ! CA0
< 0
B A ! AB A B ! BB B C ! CB
: C 0A ! AC 00 A00B ! BC 00 C 00C ! CC 00
Sur notre mot, cela nous pousse a faire: abbacadDACABBAF ! abbcadDA0CBBAF ! abbcadDCBBAA0 F
(le A est arrive a sa bonne place), et les autres coups de baguettes magiques deplacent de m^me le C (
e
0 F ! abbcadDC 0BBAA0 F ! abbcadDBBAC 0 A0 F) puis les autres lettres (abbcadDBBAC 0 A0 F !
abbcadDCBBAA
abbcadDA0B 0 B 0 C 0A0 F )
Quand ils sont arrives a leur place, on les remet normaux (terminaux):
8 A0F ! Fa
< 0
F ! Fb
: B 0F ! F c
C
Sur le mot en exemple, ca nous permet donc d'avoir:
abbcadDA0B 0 B 0 C 0A0 F ! abbcadDA0B 0 B 0 C 0Fa ! abbcadDA0B 0 B 0 Fca ! abbcadDFabbca
Il ne reste plus qu'a virer les F et D quand tout est ni
...
Exemple 2 : L=fanbm cndm n 1 m 1g est contextuel
...
7
...
2 Les langages reguliers
Les langages reguliers peuvent ^tre generes par une grammaire reguliere
...
e
Exemples:
S ! aS jbS j" genere l'expression (ajb)
La grammaire S ! ajBc genere ajb c mais n'est pas reguliere
...
1
...
Un reconnaisseur pour un langage est un programme qui prend en entree une cha^ne x et repond oui si x est une phrase
(un mot) du langage et non sinon
...
2 Les automates a etats nis sont des reconnaisseurs pour les langages reguliers
...
3 Les automates a pile sont des reconnaisseurs pour les langages hors contexte
...
Malheureusement, la plupart des langages
de programmation usuels ne peuvent ^tre completement decrits par une grammaire hors contexte (et donc encore
e
moins par une grammaire reguliere)
...
Ainsi, lors de la
realisation d'un compilateur, ces deux aspects sont aussi separes : l'analyse syntaxique s'appuie sur la grammaire
(hors contexte) et les contraintes contextuelles sont rajoutees par la suite
...
2 Automates a etats nis
De nition 7
...
7
...
43
Representation par une table de transition :
etat a b
0 0,1 0
1
- 2
e0 = 0 et T = f3g
2
- 3
3
- Attention a toujours bien preciser l'etat initial et le ou les etats naux/terminaux
...
5 Le langage reconnu par un automate est l'ensemble des cha^nes qui permettent de passer
de l'etat initial a un etat terminal
...
1 accepte le langage (regulier) (l'expression reguliere) (ajb) abb
Un automate peut tres facilement ^tre simule par un algorithme (et donc on peut ecrire un programme simulant
e
un automate ni)
...
Ce que signi e donc le theoreme 7
...
Ainsi, si l'on veut faire l'analyse lexicale d'un langage regulier,
il su t d'ecrire un programme simulant l'automate qui lui est associe
...
2
...
R
...
{ automate acceptant la cha^ne vide
{ automate acceptant la lettre a
a
{ automate acceptant (r)(s)
s
r
1
...
les etats terminaux de A(r) ne sont plus terminaux
3
...
(l'ancien etat initial de A(s) n'est plus etat initial)
{ automate reconnaissant rjs
r
s
1
...
mettre une "-transition de q vers les etats initiaux de A(r) et A(s)
3
...
2
...
3
...
7
...
b
b
b
ε
b
a
ε
a
c
b
7
...
2
...
6 On appelle "-transition, une transition par le symbole " entre deux etats
...
7 Un automate ni est dit deterministe lorsqu'il ne possede pas de "-transition et lorsque pour
chaque etat e et pour chaque symbole a, il y a au plus un arc etiquete a qui quitte e
L'automate donne en exemple gure 7
...
Les AFD sont plus faciles a simuler (pas de choix dans les transitions, donc jamais de retours en arriere a faire)
...
L'AFD obtenu comporte en general plus d'etats
e
que l'AFN, donc le programme le simulant occupe plus de memoire
...
Determinisation d'un AFN qui ne contient pas d'"-transitions
Principe : considerer des ensembles d'etats plut^t que des etats
...
Partir de l'etat initial
2
...
Recommencer 2 jusqu'a ce qu'il n'y ait plus de nouvel "etat"
4
...
Renumeroter alors les etats
...
7
...
4
b
2
4
1
6
1
e0 = 0 et
2
T = f1 3 4 5 6 7 8 9 10 11 12g
10
(voir gure 7
...
7
...
8 On appelle "-fermeture de l'ensemble d'etats T = fe1 : : : eng l'ensemble des etats accessibles
depuis un etat ei de T par des "-transitions
46
Calcul de l'"-fermeture de T = fe1 : : : eng :
Mettre tous les etats de T dans une pile P
Initialiser "-fermeture(T ) a T
Tant que P est non vide faire
Soit p l'etat en sommet de P
depiler P
Pour chaque etat e tel qu'il y a une "-transition entre p et e faire
Si e n'est pas deja dans "-fermeture(T)
ajouter e a "-fermeture(T)
empiler e dans P
nsi
npour
n tantque
Exemple
...
Partir de l'"-fermeture de l'etat initial
2
...
Recommencer 2 jusqu'a ce qu'il n'y ait plus de nouvel "etat"
4
...
Renumeroter alors les etats
...
On a l'AFN donne gure 7
...
Appliquons l'algorithme de determinisation
...
a
a
a
5
c
7
...
7)
7
b
1
5
b
a
c
a
0
a
a
c
c
c
2
4
a
3
a
Fig
...
7 - Un AFD pour (a b) a (c(ac) (aa) a)+
7
...
3 Minimisation d'un AFD
But : obtenir un automate ayant le minimum d'etats possible
...
e
Par exemple on peut facilement remarquer que dans l'automate de la gure 7
...
On
a donc l'AFD minimal de la gure 7
...
C'est amusant car ca veut donc dire que (a b) a (c(ac) (aa) a)+ =
(ajb) ca(cajaa)
...
c
0,1
2,4
c
a
3,5
a
a
Fig
...
8 - l'AFD minimal pour (a b) a (c(ac) (aa) a)+
Principe de minimisation : on de nit des classes d'equivalence d'etats par ra nements successifs
...
e
1 - Faire deux classes : A contenant les etats terminaux et B contenant les etats non terminaux
...
e
3 - Recommencer 2 jusqu'a ce qu'il n'y ait plus de classes a separer
...
5:
(1) A = f0 2g et B = f1 3 4 5 6 7 8 9 10 11 12g
(2) (0 a) et (2 a) n'appartiennent pas a la m^me classe, alors A se casse en A = f0g et C = f2g
e
(5 b) et (1 b) n'appartiennent pas a la m^me classe, alors B se casse en D = f5g et
e
B = f1 3 4 6 7 8 9 10 11 12g
(3) Ca ne bouge plus
...
9
...
7
...
2
...
R
...
E
...
On a dit qu'un AEF et une ER c'etait pareil, on a vu comment passer d'une ER a une AEF, maintenant il reste
a passer d'un AEF a une ER
...
On peut alors ecrire un systeme
d'equations liant tous les Li :
toutes les transitions de l'etat ei ( (ei a1) = ej1 , : : : , (ei ap) = ejp ) permettent d'ecrire l'equation
Li = a1 Lj1 ja2Lj2 j : : : jap Ljp
pour chaque ei 2 T on rajoute Li = : : : j"
On resoud ensuite le systeme (on cherche a calculer L0 ) en remarquant juste que
Propriete 7
...
Ca indique juste qu'on est dans une
impasse (on boucle) et donc on a d^ se planter quelquepart
...
On pourrait faire aussi :
L = aLjbLjc = aLj(bLjc) ) L = a (bLjc) = (a bL)j(a c) ) L = (a b) a c ce qui exprime le m^me langage
e
mais en moins lisible 4
Exemple complet: soit l'automate
c
1
3
a
b
b
b
0
a
a
b
2
4
c
on obtient8le systeme
> L0 = bL0jaL1jbL2
> L1 = bL2jcL3
<
> L23 = aL0jcL2jaL4
> L ="
: L4 8 "jbL3
=
> L3 = "
> L4 = "jb
<
,
> L21 = aL20jjccL2jca("jb) = aL0j0cL2jajab = c (ajabjaL0)
> L = bL = jbc (ajabjaL )
: L0 = bL0jacjabc (ajabjaL0)jbc (ajabjaL0)
) L0 = acj(aj")bc (ajab)j(aj")bc aL0 jbL0
, L0 = (((aj")bc a)jb) (acj(aj")bc (ajab))
REMARQUE :
A une expression reguliere peut correspondre plusieurs AEF
...
Mais a chaque fois c'est en fait le(la) m^me AEF (expression) mais sous des ecritures di erentes
...
e
7
...
Par exemple, il n'existe pas d'AEF (ni
d'ER) reconnaissant fanbn n 0g
...
Une transition d'un AEF est de la forme (p a) = q, c'est a dire que si on est dans un etat p et qu'on lit la
lettre a, on passe dans l'etat q
...
Les transitions demandent donc en plus une condition sur l'etat
de la pile (sur la valeur qu'il y a en sommet de pile) et indiquent comment modi er la pile
...
De nition 7
...
5 noooon?
:
:
49
un ensemble ni d'etat E
un etat initial eo 2 E
un ensemble ni d'etats naux T
un alphabet des symboles d'entree
un alphabet ; des symboles de pile
un symbole 2 ; de fond de pile
une relation de transition : E
;
!E
;
De nition 7
...
e
e
50
Chapitre 8
Analyse semantique
Certaines proprietes fondamentales du langage source a traduire ne peuvent ^tre decrites a l'aide de la seule
e
grammaire hors contexte du langage, car justement elles dependent du contexte
...
-
...
o
Elle se fait en general en m^me temps que l'analyse syntaxique, a l'aide d'actions semantiques inserees dans les
e
regles de productions, c'est a dire a l'aide de de nitions dirigees par la syntaxe (DDS)
...
Dans ce chapitre, nous donnerons (apres avoir introduit ce qu'est une DDS) une
liste de problemes rencontres plutot que des solutions qui marchent a tous les coups
...
1 De nition dirigee par la syntaxe
Une de nition dirigee par la syntaxe (DDS) est un formalisme permettant d'associer des actions a une production
d'une regle de grammaire
...
e
...
Chaque regle de production de la grammaire possede un ensemble de regles semantiques qui permettent
de calculer la valeur des attributs associes aux symboles apparaissant dans la production
...
1 On appelle de nition dirigee par la syntaxe (DDS), la donnee d'une grammaire et de son
ensemble de regles semantiques
...
On notera X:a l'attribut a du symbole X
...
Un exemple:
Grammaire S ! aSbjaS jcSacS j"
attributs : nba (calcul du nombre de a), nbc (du nombre de c)
une DDS permettant de calculer ces attributs pourrait ^tre :
e
51
production Regle semantique
S ! aSb
S (0) :nba:=S (1) :nba+1
S (0) :nbc:=S (1) :nbc
S ! aS
S (0) :nba:=S (1) :nba+1
S (0) :nbc:=S (1) :nbc
S ! cSacS S (0) :nba:=S (1) :nba+S (2) :nba+1
S (0) :nbc:=S (1) :nbc+S (2) :nbc+2
S!"
S (0) :nba:=0
S (0) :nbc:=0
S0 ! S
// le resultat nal est dans S:nba et S:nbc
Dans cet exemple de DDS, les attributs des symboles en parties gauches dependent des attributs des symboles
de la partie droite
...
Par exemple pour le mot acaacabb :
4S 2
a
3 S2
c
1S0
a
Fig
...
1 - Calcul du nombre de a et b pour acaacabb
Sur cet arbre syntaxique (et donc pour cette DDS), on voit que l'on peut calculer les attributs d'un noeud des
que les attributs de tous ses ls ont ete calcules
...
2 On appelle arbre syntaxique decore un arbre syntaxique sur les noeuds duquel on rajoute la
valeur de chaque attribut
...
Tout ordre d'evaluation
qui calcule sur l'arbre syntaxique l'attribut a apres tous les attributs dont a depend est possible
...
Reprenons l'exemple et etudions une autre DDS pour ce probleme, une DDS qui ne ferait pas intervenir d'attributs, mais utiliserait de simples variables:
production Regle semantique
S ! aSb
nba++
S ! aS
nba++
S ! cSacS nba++
nbc+ = 2
S!"
Cette DDS pose un gros probleme : ou initialiser les variables? Si on le fait dans l'action semantique associee
a la regle S ! ", RIEN ne nous oblige a executer cette initialisation AVANT les actions d'incrementation des
variables
...
Conclusion: cette DDS ne marche pas, il faut utiliser des attributs
...
Ce qui les distingue c'est la facon dont ils
sont calcules
...
3 Un attribut est dit synthetise lorsqu'il est calcule pour le non terminal de la partie gauche en
fonction des attributs des non terminaux de la partie droite
...
C'est a
dire que le le calcul de l'attribut se fait des feuilles vers la racine
...
De nition 8
...
Mais pas du tout lors d'une analyse descendante
...
5 Un attribut est dit herite lorsqu'il est calcule a partir des attributs du non terminal de la partie
gauche, et eventuellement des attributs d'autres non terminaux de la partie droite
...
C'est a dire que le calcul de l'attribut se fait de la racine vers les feuilles
...
De nition 8
...
e
8
...
1 Schema de traduction dirige par la syntaxe
De nition 8
...
Exemple :
S 0 ! f nba := 0 g S
S ! a f nba ++ g S
Dans un STDS, si l'on a :
S ! X f une action g Y
l'action est executee apres que le sous-arbre syntaxique issu de X aura ete parcouru (par un parcours en profondeur) et avant que celui issu de Y ne le soit
...
8
...
2 Graphe de dependances
Une DDS peut utiliser a la fois des attributs synthetises et des attributs herites
...
L'attribut machin depend de l'attribut bidule qui lui-m^me
e
depend de l'attribut truc : : :Il faut etablir un ordre d'evaluation des regles semantiques
...
Exemple : Soit la DDS suivante (totalement stupide) qui fait intervenir deux attributs herites h et r et deux
attributs synthetises s et t
...
h:=2 E
...
r:=E
...
s:=E (1)
...
s
E (0)
...
t;E (2)
...
h:=E (0)
...
h:=E (0)
...
s:= nombre
E
...
h +1
La gure 8
...
De nition 8
...
Le graphe a pour sommet chaque attribut
...
53
On construit le graphe de dependances pour chaque regle de production, ou bien directement le graphe de dependances d'un arbre syntaxique donne
...
Mais il est toujours utile d'avoir le graphe de dependances pour chaque regle de production a n d'obtenir "facilement" le graphe pour n'importe quel arbre syntaxique
...
3 donne le graphe de dependances pour chaque regle de production, et la gure 8
...
Remarque : si le graphe de dependance contient un cycle, l'evaluation des attributs est alors impossible
...
a:=S
...
b:=S (1)
...
b+T
...
a:=S (0)
...
a:=S (0)
...
a:=S (0)
...
b+S (1)
...
b:=P
...
b
P
...
a+3
T (1)
...
...
5), le calcul est donc impossible
...
1
...
Cette methode est tres couteuse en memoire (stockage de l'arbre)
...
On peut egalement construire l'arbre en dur pour une sous-partie seulement du langage
...
Dans ce cas, on utilisera une
e
pile pour conserver les valeurs des attributs, cette pile pouvant ^tre la m^me que celle de l'analyseur syntaxique,
e
e
ou une autre
...
C'est a dire que l'on ne pourra traiter les grammaires S-attribuees
qu'avec une analyse ascendante, et les grammaires L-attribuees qu'avec une analyse descendante
...
Exemple avec un attribut synthetise : evaluation d'une expression arithmetique avec une analyse ascendante
(ce que fait yacc/bison)
...
val:=E (1)
...
val tmpT = depiler()
E !E +T E
tmpE = depiler()
empiler(tmpE+tmpT)
E ! E ; T E (0)
...
val;T
...
val:=T
...
val:=T (1)
...
val tmpF = depiler()
tmpT = depiler()
empiler(tmpT tmpF)
T !F
T
...
val
F ! (E)
F
...
val
F ! nb
F
...
Par exemple, pour le mot
2 (10 + 3) on obtiendra :
entree action
pile des attributs
pile
$ 0
2 (10 + 3)$ d5
$ 0 2 5
(10 + 3)$ r6 : F ! nb
2
(10 + 3)$ r4 : T ! F
2
$ 0 F 3
(10 + 3)$ d7
2
$ 0 T 2
(10 + 3)$ d4
2
$ 0 T 2 7
$ 0 T 2 7 ( 4
10 + 3)$ d5
2
+3)$ r6 : F ! nb
2 10
$ 0 T 2 7 ( 4 10 5
+3)$ r4 : T ! F
2 10
$ 0 T 2 7 ( 4 F 3
$ 0 T 2 7 ( 4 T 2
+3)$ r2 : E ! T
2 10
$ 0 T 2 7 ( 4 E 8
+3)$ d6
2 10
$ 0 T 2 7 ( 4 E 8 + 6
3)$ d5
2 10
)$ r6 : F ! nb
2 10 3
$ 0 T 2 7 ( 4 E 8 + 6 3 5
$ 0 T 2 7 ( 4 E 8 + 6 F 3
)$ r4 : T ! F
2 10 3
)$ r1 : E ! E + T 2 13
$ 0 T 2 7 ( 4 E 8 + 6 T 9
$ 0 T 2 7 ( 4 E 8
)$ d11
2 13
$ 0 T 2 7 ( 4 E 8 ) 11
$ r5 : F ! (E)
2 13
$ 0 T 2 7 F 10
$ r3 : T ! T F 26
$ r2 : E ! T
26
$ 0 T 2
$ ACCEPTE !!! 26
$ 0 E 1
Exemple avec un attribut herite : calcul du niveau d'imbrication des ) dans un systeme de parentheses bien
forme
...
nb:=0
empiler(0)
9
tmp=depiler() =
(1)
...
nb+1
S
S ! (S)S
empiler(tmp)
empiler(sommet()+1)
S (2)
...
nb
empiler(tmp+1)
S!"
ecrire S
...
e
Exemple : compter le nombre de bit a 1 dans un mot binaire
...
nb:=0
DDS avec attribut herite :
B ! 0B
B (1)
...
nb
B ! 1B
B (1)
...
nb+1
B!"
ecrire B
...
nb
DDS avec attribut synthetise :
B ! 0B
B (0)
...
nb
B ! 1B
B (0)
...
nb+1
B!"
B
...
6 donne les arbres decores pour le mot 10011
...
Par exemple, considerons une DDS de typage de variables
dans une declaration Pascal de variables (en Pascal, une declaration de variable consiste en une liste d'identi cateurs separes par des virgules, suivie du caractere ':', suivie du type
...
type:=T
...
type pour Id
L ! L, Id L(1)
...
type
mettre dans la table des symboles le type L(0)
...
type:=entier
T ! char
T
...
Pas possible de trouver un attribut synthetise faisant la m^me chose avec cette grame
maire
...
type pour Id
L(0)
...
type
mettre dans la table des symboles le type L(1)
...
type:=T
...
type:=entier
T
...
Heureusement, il existe des methodes
automatiques qui transforment une DDS avec des attributs herites et synthetises en une DDS equivalente n'ayant
que des attributs synthetises
...
Une autre idee peut ^tre de faire plusieurs passes d'analyses, suivant le graphe de dependances de la DDS
...
8
...
Cette notion de validite et visibilite depend bien s^r des langages
...
En Fortran, C, Pascal, : : :, les identi cateurs qui sont de nis dans un bloc ne sont visibles
qu'a l'interieur de ce bloc un identi cateur declare dans un sous-bloc masque un identi cateur de m^me nom
e
declare dans un bloc de niveau inferieur
...
Il faut donc memoriser tous les symboles
rencontres au fur et a mesure de l'avancee dans le texte source
...
La table des symboles contient toutes les informations necessaires sur les symboles (variables, fonctions, : : :) du
programme:
- identi cateur (le nom du symbole dans le programme)
- son type (entier, cha^ne, fonction qui retourne un reel,: : :)
- son emplacement memoire
- si c'est une fonction: la liste de ses parametres et leurs types
- :::
Lors de la declaration 3 d'une variable, elle est stockee dans cette table (avec les informations que l'on peut
deja connaitre)
...
Si c'est le
cas, c'est une erreur
...
Il faut donc munir la table des symboles de procedures d'ajout, suppression et recherche
...
Dans certains langages, on peut autoriser qu'un identi cateur ne soit pas declare dans son bloc B a condition
qu'il ait ete declare dans un bloc d'un niveau inferieur qui contient B
...
On peut alors utiliser une pile pour empiler la table des symboles et gerer ainsi la portee des identi cateurs
...
3 et encore, certains langages n'imposent pas de declarer les variables
...
3 Contr^le de type
o
Lorsque le langage source est un langage type, il faut veri er la pertinence des types des objets manipules dans
les phrases du langage
...
De nition 8
...
Le contr^le dynamique est a eviter car il est alors tres di cile pour le programmeur de voir d'ou vient l'erreur
o
(quand il y en a une)
...
Par
o
e
exemple, si l'on a
int tab 10]
int i
...
tab i]
...
Exemples de TDS de contr^le de type :
o
Regle de production action semantique
I ! Id = E
I
...
type=E
...
type,E
...
type := si E
...
type
sinon erreur type(ligne,: : :)
E ! Id
E
...
type := si E (1)
...
type=entier alors entier
sinon
si (E (1)
...
type6=entier)
ou (E (2)
...
type6=entier) alors
erreur type incompatible(ligne,E (1)
...
type)
sinon
reel
E ! E mod E
E (0)
...
type=entier et E (2)
...
...
f(p *i])-&j
Il faut alors trouver une representation pratique pour les expressions de type
...
On considere les constructions de types suivantes :
pointeur(t) : un pointeur vers le type t
fretourne(t) : une fonction (dont les arguments ne sont pas speci es) qui retourne un objet de type t
tableau(t) : un tableau (de taille indeterminee) d'objets de type t
Ces constructeurs etant unaires, les expressions de type formes en les appliquant a des types de base ont une
structure tres uniforme
...
Par exemple
e
constructeur codage
type de base codage
pointeur
01
entier
0000
tableau
10
booleen
0001
fretourne
11
caractere
0010
reel
0011
4 quoi qu'il existe des techniques d'analysede ot de donnees qui permettentde resoudre ce probleme dans certains cas particuliers
:
58
Les expressions de type peuvent maintenant ^tre encodee comme des sequences de bit
e
expression de type
codage
caractere 000000 0010
fretourne(caractere) 000011 0010
pointeur(fretourne(caractere)) 000111 0010
tableau(pointeur(fretourne(caractere))) 100111 0010
Cette methode a au moins deux avantages: economie de place et il y a une trace des di erents constructeurs
appliques
...
3
...
Par exemple, en C, la division est la division entiere si les deux operandes sont de type entier, et la
division reelle sinon
...
Maintenant, si l'on rencontre , doit-on considerer la multiplication standard qui retourne un
e
entier ou celle qui retourne un complexe? Pour repondre a cette question, il faut regarder comment est utilisee
l'expression
...
Bref, au lieu de remonter un seul type dans la TDS, il faudra remonter un ensemble de types possibles,
jusqu'a ce que l'on puisse conclure
...
3
...
Par exemple, l'operateur & en C est polymorphe puisqu'il s'applique aussi bien
a un entier qu'a un caractere, une structure de nie par le programmeur, : : :
...
Cette fois-ci, il ne s'agit plus seulement de veri er l'equivalence de deux types, mais il faut les uni er
...
Ces problemes ne sont pas simples et sont etudies dans le cadre des recherches en logique combinatoire et en
lambda-calcul
...
8
...
5 par exemple dans les langages objets
6 Et en plus personnellement je trouve ca tres chiant
:
:
59
S
14
9E 4
9 E3
14
st
r h
13 E 1 24
10
13 E 1 14
3
17 E 0
1
Fig
...
2 - Attributs herites et synthetises
h E s t
E s
h
t
r
S
hE s
nb
h E s t
h
E s
t
t
8
...
S
r
hE s
h Es t
3
t
h
E s t
h E s t
h
1
Fig
...
4 - Graphe de dependances de l'arbre syntaxique
S’
a S b
a S b
a Sb
aTb
a P b
Fig
...
5 - Cycle dans le graphe de dependance
60
3
S
S
B 0
B 3
B 1
1
B 1
0
0
B 2
1
B
1
1
B 2
0
B 2
1
B 2
0
B 1
1
B 3
1
B 0
3
(a)
Fig
...
6 - Arbre decore pour 10011 avec des attributs (a)herites (b) synthetises
P
entier i
caractere c
A
entier j
entier i
A1
entier c
A2
i entier
j entier
j entier
c car
i entier
Programme P
Fig
...
7 - Portee des identi cateurs : empilement de la table des symboles
61
Chapitre 9
Generation de code
Avant d'attaquer le probleme de la generation du code cible, il faut se poser des questions sur l'organisation de
la memoire (l'environnement d'execution) :
- gestion du ot de contr^le (appels et retour de fonctions, instructions de saut (du type break en C))
o
- stockage des variables
- allocation dynamique de memoire
- etc
Ensuite, il s'agit de produire le code cible
...
On produira donc dans un premier temps du code intermediaire,
que l'on pourra ensuite optimiser, puis en n a partir du code intermediaire on produira le code cible
...
1 Environnement d'execution
9
...
1 Organisation de la memoire a l'execution
Questions liees au langage source :
- les fonctions peuvent-elles ^tre recursives?
e
- une fonction peut-elle faire reference a des noms non locaux?
- comment sont passes les parametres lors d'un appel de fonction?
- peut-on allouer dynamiquement de la memoire?
- doit-on liberer explicitement l'espace memoire alloue dynamiquement?
- que deviennent les variables locales a une fonction lorsque l'on sort de la fonction?
- :::
Questions liees a la machine cible :
- quelle est la longueur d'un mot ou d'une adresse?
- quelles sont les entites directement adressables de la machine?
- existe-t-il des instructions pour acceder directement et e cacement a des parties d'entites directement
adressables?
- est-ce possible de rassembler plusieurs "petits" objets (booleen, caractere, : : :) dans des unites plus
grandes?
- y-a-t-il des restrictions d'adressage (conditions d'alignements)?
- :::
Les reponses a ces questions in uent sur la facon d'organiser la memoire
...
On les place alors dans une
zone determinee statiquement
...
pile de contr^le : elle permet de gerer les appels de fonctions
...
Lors d'un appel de fonction, un protocole d'appel alloue un enregistrement
d'activation, remplit ses champs et l'empile
...
tas : contient tout le reste, c'est a dire les variables allouees dynamiquement au cours de l'execution du programme
...
1
...
Les donnees allouees sont conservees jusqua
leur liberation explicite (instructions free en C, dispose en Pascal, : : :) ou implicite (appels implicites des
destructeurs en C++, garbage collector en Lisp, : : :)
...
Liberation implicite
Interet : evite les rebuts (ou miettes), c'est a dire les zones memoires allouees mais devenues innaccessibles,
et les references fant^mes, c'est a dire une reference a une zone qui a ete liberee
...
On incremente alors le compteur de reference a chaque nouvelle reference a ce bloc, et on le decremente a chaque "disparition" de reference (sortie de fonction dans laquelle la reference est locale par
exemple)
...
Exemple : si on a une instruction (C) p=q, le compteur du bloc reference par p est decremente, celui
de q est incremente
...
{ Marquage : L'autre approche consiste a suspendre temporairement l'execution du programme et faire
du ramasse-miettes
...
On commence par
marquer tout le tas en tant qu'inutilise
...
Compression
De temps a autres, on peut suspendre temporairement l'execution du programme pour faire de la compression, c'est a dire deplacer les blocs utilises vers une extremite du tas, a n de rassembler toute la memoire
63
libre en un seul grand bloc 1
...
9
...
e
Pourquoi passer par un langage intermediaire?
le "reciblage" est facilite
...
Utiliser un langage intermediaire permet de porter plus rapidement le compilateur,
puisque les 9/10 du boulot sont deja fait lorsqu'on est arrive a produire du code intermediaire
...
Il existe de nombreux algorithmes et methodes d'optimisation de
code pour les codes intermediaires les plus utilises
...
2
...
L'acces aux registres est plus rapide que l'acces a la memoire principale, donc un bon compilateur est un
compilateur qui utilise le plus possible les registres pour les resultats intermediaires, les calculs d'adresse,
la transmission des parametres d'une fonction, le retour des valeurs d'une fonction, : : :
Bien s^r, le nombre de registres est limite
...
{ jeu d'instructions :
- instructions de calcul (arithmetique, booleen, : : :), souvent di erenciees selon la longueur des
operandes
- instructions de transfert (entre et dans la memoire et les registres)
- instructions de branchements
- instructions de communication avec le syteme d'exploitation et les peripheriques (entrees/sorties)
9
...
2 Code a 3 adresses simpli e
Nous allons voir un code intermediaire souvent utilise: le code a 3 adresses
...
Le nombre de registres disponibles est illimite
Exemple 1 : le fragment de programme C a=b*c+b*(b-c)*(-c) devient
1 dans le cas d'une allocation de blocs de taille xe ca n'a pas grand inter^t
e
2 je vous laisse imaginer le bordel pour les listes de blocs
:
:
64
(1)
(2)
(3)
(4)
t1
t2
t3
t4
:=
:=
:=
:=
b*c
b-c
b*t2
-c
(5) t5 := t3*t4
(6) t6 := t1+t5
(7) a := t6
ou encore, en optimisant le nombre de registres utilises
(1)
(2)
(3)
(4)
t1
t2
t2
t3
:=
:=
:=
:=
b*c
b-c
b*t2
-c
(5) t2 := t3*t4
(6) t1 := t1+t5
(7) a := t1
Exemple 2 : soit le fragment de code C suivant
z=0
do {
x++
if (y<10)
{
z=z+2*x
h=5
}
else
h=-5
y+=h
} while (x<=50 && z<=5*y)
Le code a 3 adresses correspondant est
(1) t1 := 0
(2) z := t1
(3) t2 := x + 1
(4) x := t2
(5) t3 := y<10
(6) si t3=vrai aller a (8)
(7) aller a 14
(8) t4 := 2*x
(9) t5 := z+t4
(10) z := t5
(11) t6 := 5
(12)
(13)
(14)
(15)
(16)
(17)
(18)
(19)
(20)
(21)
(22)
h := t6
aller a (16)
t7 := -5
h := t7
t8 := y+h
y := t8
t9 := x<=50
t10 := 5*y
t11 := z<=t10
t12 := t9 et t11
si t12=vrai aller a (3)
(23)
...
2
...
Il est (assez) simple d'inserer des actions semantiques dans la grammaire du langage a n de produire ce code
...
65
Expressions arithmetiques
Exemple 1 : generation de code pour les expressions arithmetiques
...
1
Production Regle semantique
I ! Id = E I:code=
E:code
Id:place ":=" E:place
E ! Id
E:place=
Id:place
E:code=
" "
E ! (E)
E (0)
...
place
E (0)
...
code
E ! E + E E (0)
...
code= E (1)
...
code
E (0)
...
place "+" E (2)
...
...
Fig
...
1 - DDS de generation de code 3 adresses pour les expressions arithmetiques
Il faudrait aussi penser aux numeros des instructions, ce n'est pas fait dans cet exemple
...
Expressions booleennes
Soit la grammaire :
8 I ! si L alors I sinon I
>
< L ! Id oprel Id
L ! non L
L ! vrai
> L ! L ou L
: L ! L et L
L ! faux
De nition 9
...
2 On appelle evaluation court-circuit l'evaluation d'une expression booleenne qui n'evalue que
les termes necessaires
Pour une instruction, on considere un attribut suivant qui contient l'etiquette de l'instruction suivante a e ectuer
(ce n'est pas toujours celle qui suit dans le code car il peut y avoir des branchements)
...
2
...
sinon en (attention a construire l'arbre de derivation qui tient compte des priorites
des operateurs !) :
t1 := a
t4 := t2 et t4
t5 := t1 ou t4
si t5 aller a (Lvrai)
aller a (Lfaux)
(Lvrai)
...
(le code du bloc alors)
aller a (Isuiv)
(Lfaux)
...
(le code du bloc sinon)
(Isuiv)
...
...
L:code
"si" L:place"=vrai aller a" Vrai
"aller a" Faux
"(" Vrai ")" I (1) :code
"aller a" I (1) :suivant
"(" Faux ")" I (2) :code
(0) :place = NouvRegistre()
L
L(0) :code = L(1) :code
L(2) :code
L(0) :place ":=" L(1) :place "ou" L(2) :place
L:place = NouvRegistre()
L:code = L:place ":=" Id:place oprel:valeur Id:place
L(0) :place = NouvRegistre()
L(0) :code = L(0) :place ":= non" L(1):place
etc
...
2 - DDS de generation de code 3 adresses pour l'evaluation paresseuse des expressions booleennes
Un des problemes qui se pose est qu'on ne peut pas conna^tre toutes les etiquettes destination de toutes les instructions de branchement en une seule passe
...
On produit une serie de branchements dont les destinations
sont temporairement inde nies
...
La DDS pour un code court-circuit aura 2 attributs (herites) : vrai qui donne l'etiquette de l'instruction a
e ectuer si l'expression est vraie, et faux l'etiquette si l'expression est fausse
...
Donc :
si L alors
I1
sinon
I2
!
(L:vrai)
code de L
avec branchement soit a L
...
faux
code de I1
aller a I:suivant
(L:faux) code de I2
(I:suivant) : : :
La DDS pour un code court-circuit est donne gure 9
...
sera traduite par
(L1)
(l2)
(Lvrai)
(Lfaux)
(Lsuiv)
si aaller a L1
si c
si e
...
aller a Lsuiv
...
...
Pour corriger cela, il faudra
optimiser le code produit
...
9
...
3 Optimisation de code
Le terme "optimisation" est abusif parce qu'il est rarement garanti que le code resultat soit le meilleur possible
...
En e et, en general, dans la plupart
des programmes, 90% du temps d'execution est passe dans seulement 10% du code
...
9
...
1 Optimisations independantes de la machine cible
On e ectue une analyse des ux de donnees pour chercher
s'il existe un chemin d'execution le long duquel la valeur d'une variable serait utilisee sans avoir ete
prealablement initialisee
s'il existe du code "mort", c'est a dire une partie du programme qui n'est jamais atteinte
s'il existe des variables ayant toujours une m^me valeur tout le long d'une partie du programme
e
(propagation des constantes)
les invariants de boucle, c'est a dire les expressions a l'interieur d'une boucle qui ne dependent d'aucune
variable succeptible d'^tre modi ee dans la boucle, pour les deplacer devant la boucle
e
si une expression est calculee plusieurs fois sans qu'entre temps les composantes de l'expression se
trouvent modi ees (elimination des expressions communes)
etc : : :
Certaines de ces optimisations peuvent ^tre e ectuees avant la generation de code intermediaire
...
Il faut
toujours se demander si l'amelioration de la qualite du code justi e ou non le temps passe sur le probleme 5
...
3
...
: : :
9
...
3 Graphe de ot de contr^le
o
Pour realiser les optimisations de code, il nous faut une representation pratique du code intermediaire
...
o
De nition 9
...
Algorithme de partitionnement d'un programme en blocs de base :
1
...
1
...
2
...
3
...
chaque bloc de base debute avec son instruction de t^te et se poursuit jusqua la premiere instruction
e
qui precede une autre instruction de t^te
...
(1)
(2)
(3)
(4)
(5)
(6)
i:=3
t1:=4*i
t2:=a t1]
j:=2
j:=j+1
si j>100 aller a (12)
(7)
(8)
(9)
(10)
(11)
(12)
si t2t2:=t2+3
aller a (7)
b:=b-j
aller a (5)
a t1]:=t2
4 deja, on a inter^t a faire un e ort pour les corps de boucle
e
5 signalons aussi que certaines optimisations souhaitees sont en fait des problemes NP-complets
...
Les blocs sont B1 = f(1) (2) (3) (4)g, B2 = f(5) (6)g,
e
B3 = f(7)g, B4 = f(8) (9)g, B5 = f(10) (11)g et B6 = f(12)g
...
4 Le graphe de ot de contr^le est le graphe dont les noeuds sont les blocs de base et tel qu'il
o
y a un arc du bloc Bi au bloc Bj si et seulement si l'une des deux conditions suivante est realisee
la derniere instruction de Bi est un branchement (conditionnel ou inconditionnel) a la premiere
instruction de Bj
Bj suit immediatement Bi dans l'ordre du programme et Bi ne se termine pas par un branchement
inconditionnel
Sur l'exemple:
B1
B2
B3
B4
B5
B6
9
...
4 Elimination des sous-expressions communes
Exemple 1: soit le bloc de base
a:=b+c
b:=a-d
c:=b+c
d:=a-d
La deuxieme et la derniere expression calculent la m^me chose, par consequent on pourrait transformer ce bloc
e
en
a:=b+c
b:=a-d
c:=b+c
d:=b
Attention, la premiere et la troisieme expression ne calculent pas la m^me chose, car b est modife entre temps !
e
Exemple2: soit le bloc de base
t3:=4*i
x:=a t3]
t4:=4*i
a t4]:=y
La premiere et la troisieme expression sont identiques
...
t3:=4*i
x:=a t3]
a t3]:=y
70
Exemple3: soit le bloc de base
t4:=4*i
t5:=a t4]
t6:=4*i
t7:=a t6]
a t8]:=t7
On peut eliminer la troisieme instruction :
t4:=4*i
t5:=a t4]
t7:=a t4]
a t8]:=t7
On voit alors apara^tre de nouveau une expression commune, que l'on peut encore eliminer:
t4:=4*i
t5:=a t4]
a t8]:=t5
Exemple4: Attention aux tableaux !!
...
a t2]:=
...
y:=a t1]
Ici, on ne peut pas considerer que l'expression a t1] est commune, m^me si t1 n'est pas modi e entre les deux
e
expressions, car le tableau a, lui, est modi e et il n'est pas evident du tout (en general) de savoir si t2 peut ^tre
e
egal a t1 ou pas
...
au depart Prod(B)=
2
...
1
...
2
...
instruction Prod
a:=b+c
e:=a+d
b:=a-d
c:=b+c
d:=a-d
b+c
b+c a+d
a+d a-d
a+d a-d
Algorithme de calcul de Supp(B) : expressions supprimees par le bloc B
Soit U l'ensemble de toutes les expressions du programme
1
...
pour chaque instruction du bloc du type x:=y op z, mettre dans Supp(B) toutes les expressions
de U qui contiennent x a condition qu'elle ne soit pas recalculee plus loin dans le bloc
71
Exemple
...
(les numeros a la n des instructions correspondent a une numerotation des expressions)
B1
(1) t1:=m-1
(2) t2:=m+n
(3) k:=a+1
(4) a:=u1
(5) e:=2*c
(e1)
(e2)
(e3)
(e4)
(e5)
B2
(6) b:=2*c (e5)
(7) t1:=t1+1 (e6)
(8) t2:=t2-1 (e7)
(9) d:=a+1 (e3)
B4
B3
(13) t1:=m-1 (e1)
(14) b:=2*c (e5)
(15) c:=a+1 (e3)
(10) a:=u2 (e8)
(11) d:=2*c (e5)
(12) c:=m+n (e2)
U= fe1 e2 e3 e4 e5 e6 e7 e7g
Calcul des Prod et des Supp :
bloc Prod
Supp
B1 e1 e2 e4 e5 e6 e7 e3
B2 e5 e3
e6 e7
B3 e8 e2
e3 e5
B4 e1 e3
e6 e5
72
Calcul des In et Ex :
initialisations:
bloc In Ex
B1
e1 e2 e4 e5
B2
e1 e2 e3 e4 e5 e8
B3
e1 e2 e4 e6 e7 e8
B4
e1 e2 e3 e4 e7 e8
passe 1
In(B2)=Ex(B1)\Ex(B3)= fe1 e2 e4g
Ex(B2)=Prod(B2) (In(B2);Supp(B2))= fe3 e5g (fe1 e2 e4g ; fe6 e7g) = fe1 e2 e3 e4 e5g
In(B3)=Ex(B2)= fe1 e2 e3 e4 e5g
Ex(B3)=Prod(B3) (In(B3);Supp(B3))= fe2 e8g (fe1 e2 e3 e4 e5g ; fe3 e5g) = fe1 e2 e4 e8g
In(B4)=Ex(B2)= fe1 e2 e3 e4 e5g
Ex(B4)=Prod(B4) (In(B4);Supp(B4))= fe1 e3g (fe1 e2 e3 e4 e5g ; fe5 e6g) = fe1 e2 e3 e4g
passe 2
In(B2)=Ex(B1)\Ex(B3)= fe1 e2 e4g inchange, donc Ex aussi
In(B3)=Ex(B2)= fe1 e2 e3 e4 e5g inchange, donc Ex aussi
In(B4)=Ex(B2)= fe1 e2 e3 e4 e5g inchange, donc Ex aussi
termine, on a
bloc In
B1
B2 e1 e2 e4
B3 e1 e2 e3 e4 e5
B4 e1 e2 e3 e4 e5
Algorithme d'elimination des sous-expressions communes globales
Pour chaque instruction (i) x:=y op z du bloc B telle que y op z est disponible et ni y ni z ne sont
modi ees avant (i) dans B
1
...
creer une nouvelle variable u
3
...
remplacer l'instruction (i) par
(i) x:=u
Sur l'exemple: les expressions a etudier sont e1 e2 e3 et e5
e1 : appara^t dans l'instruction (13) du bloc B4
est-elle disponible? e1 2In(B4), oui
la derniere evaluation c'est l'instruction (1) qui devient donc
(1) t3:=m-1
(1') i:=t3
et l'instruction (13) devient : (13) i:=t3
e2 : appara^t dans l'instruction (12) du bloc B3
est-elle disponible? e2 2In(B3), oui
la derniere evaluation c'est l'instruction (2) qui devient donc
(2) t4:=m+n
(2') j:=t4
et l'instruction (12) devient : (12) c:=t4
e3 : appara^t dans (9) de B2 et (15) de B4
(9) de B2
est-elle disponible? e3 2In(B2)?, non
donc on ne peut pas l'eliminer
(15) de B4
est-elle disponible? e3 2In(B4), oui
la derniere evaluation c'est l'instruction (9) qui devient donc
(9) t5:=a+1
(9') d:=t5
et l'instruction (15) devient : (15) c:=t5
e5 : appara^t dans (6) de B2, (11) de B3 et (14) de B4
(6) de B2
est-elle disponible? e5 2In(B2)?, non
73
donc on ne peut pas l'eliminer
(11) de B3
est-elle disponible? e5 2In(B3), oui
la derniere evaluation c'est l'instruction (6) qui devient donc
(6) t6:=2*c
(6') b:=t6
et l'instruction (11) devient : (11) d:=t6
(14) de B4
est-elle disponible? e5 2In(B4), oui
la derniere evaluation c'est l'instruction (6) qui devient donc (attention il y a deja une instruction (6'))
(6) t7:=2*c
(6'') t6:=t7
et l'instruction (14) devient : (14) b:=t7
Bref, on obtient le graphe de la gure 9
...
(e5)
9
...
C'est l'algorithme de propagation des copies qui va se charger d'eliminer ce t7
...
3
...
9
...
6 Calculs invariants dans les boucles
On cherche a sortir des boucles les calculs qui sont e ectues a l'interieur d'une boucle alors qu'ils n'evoluent
jamais
...
Le graphe de la gure 9
...
5(b)
De nition 9
...
9
...
6 une boucle est une suite de blocs (ou un seul bloc) avec un en-t^te qui domine tous les autres
e
blocs de la boucle et telle qu'il existe au moins une maniere de revenir vers l'en-t^te a partir de n'importe quel
e
bloc de la boucle
Exemple 2 : dans la gure 9
...
B1
i:=1
B2
si u
B3
i:=2
u:=u+1
B4
v:=v-1
si v>20 aller a B2
B5
j:=i
Fig
...
6 - deplacement de code impossible
Mais on ne peut pas deplacer l'instruction i:=2 de B3 hors de la boucle, car on ne passe pas forcemment par B3
quand on passe dans la boucle
...
3
...
Elle s'appuit sur des methodes formelles de description de semantique des langages:
semantique denotationnelle ou semantique operationnelle
...
Nous n'en parlerons donc pas plus ici 6
...
4 Generation de code
Traduction du code intermediaire en code cible
...
Ce n'est pas
notre probleme
...
yy
Title: Cours de compilation.
Description: École nationale supérieure d’informatique pour l’industrie et l’entrepris
Description: École nationale supérieure d’informatique pour l’industrie et l’entrepris