Tables des matières

Tables des matières

Introduction à la compilation...........................................................................3
1.1. Définition d’un compilateur............................................................................................3
1.2. Compilation par analyse et synthèse...............................................................................4
1.2.1. Analyse du programme source.................................................................................4
1.2.2. Phases d'un compilateur............................................................................................5
1.2.3. Partie Frontale et finale.............................................................................................8

Expressions régulières et automates à états finis........................................10

2.1. Expressions Régulières..................................................................................................10
2.2. Automates à états finis..................................................................................................12
2.2.1. Automates à états finis non déterministes...............................................................12
2.2.2. Automates à états finis déterministes......................................................................14
2.2.3. Transformation d'un AFN en AFD.........................................................................15
2.3. Transformation d'une expression régulière en un AFD................................................18
2.3.1. Construction d'un AFN à partir d'une expression régulière....................................18
2.4. Simulation d'un AFN.....................................................................................................23

Analyse lexicale................................................................................................25
3.1. Le rôle de l'analyseur lexical.........................................................................................25
3.1.1. Pourquoi une analyse lexicale.................................................................................26
3.1.2. Unités lexicales, modèles et lexèmes......................................................................26
3.1.3. Attributs des unités lexicales...................................................................................27
3.2. Mémorisation du texte d'entrée: couple de tampons.....................................................28
3.3. Spécification des unités lexicales..................................................................................29
3.3.1. Chaînes et langage...................................................................................................29
3.3.2. Opération sur les langages.......................................................................................30
3.4. Reconnaissances des unités lexicales............................................................................30
3.4.1. Diagrammes de transition........................................................................................31
3.5. Un langage pour spécifier des analyseurs lexicaux (lex)..............................................35
3.6. Conception d'un générateur d'analyseurs lexicaux........................................................36
3.6.1. Reconnaissance fondée sur les Automates finis non déterministes.........................37
3.6.2. Reconnaissance fondée sur les Automates finis déterministes................................39

Analyse syntaxique...........................................................................................41
4.1. Grammaires non contextuelles......................................................................................41
4.1.1. Définition d'une grammaire non contextuelle.........................................................42
4.1.2. Définition d'une Dérivation....................................................................................42
4.2. Arbres d’analyse et dérivations.....................................................................................44
4.2.1. Ambiguïté................................................................................................................45
Associativité des opérateurs..............................................................................................45
4.2.2. Priorités des opérateurs...........................................................................................45

Sami KHALFOUI – Moez HAMMAMI – ENSI 1

2006/2007
 Tables des matières

4.3. Analyse descendante (TOP-DOWN)............................................................................46

4.3.1. Analyse par descente récursive...............................................................................46
4.3.2. Analyse prédictive non récursive............................................................................49
4.3.3. Diagrammes de transition pour analyseurs prédictifs.............................................55
4.3.4. Grammaires LL(1)..................................................................................................57
4.4. Analyse ascendante (décalage/réduction)......................................................................59
4.4.1. Définition d'un Manche...........................................................................................60
4.4.2. Elagage du manche..................................................................................................62
4.4.3. Implantation à l'aide d'une pile de l'analyse par décalage-réduction.......................62
4.4.4. Analyseurs LR.........................................................................................................63
4.4.5. Construction des tables d'analyse SLR à partir d'une grammaire...........................68

Traduction dirigée par la syntaxe...................................................................77

5.1. Définitions dirigées par la syntaxe................................................................................78
5.1.2. Attributs synthétisés................................................................................................78
5.1.3. Parcours en profondeur...........................................................................................79
5.2. Schéma de traduction....................................................................................................80
5.3. Arbre abstrait et arbre concret.......................................................................................82

Contrôle de type...............................................................................................84
6.1. Expression de type........................................................................................................84
6.2. Spécification d’un contrôleur de type simple................................................................85
6.2.1. Un langage simple...................................................................................................85
6.2.2. Contrôle de type des expressions............................................................................86
6.2.3. Contrôle de type des instructions............................................................................87
6.3. Conversion de type........................................................................................................88

Production de code intermédiaire..................................................................91

7.1. Code à trois adresses.....................................................................................................91
7.1.1. Traduction dirigée par la syntaxe pour la production du code à trois adresses.......91
7.1.2. Implantation d'instructions à trois adresses.............................................................93
7.2. Expressions booléennes (méthode numérique).............................................................94
7.3. Techniques de reprise Arrière (BackPatching)..............................................................96
7.3.1. Traduction des expressions booléennes..................................................................97
7.3.2. Traduction des instructions de flot de contrôle.......................................................98
7.3.3. Traduction des déclarations..................................................................................101

Bibliographie....................................................................................................101

Sami KHALFOUI – Moez HAMMAMI – ENSI 2

2006/2007
 Introduction à la compilation

Introduction à la compilation

Ce polycopié est le support de cours de « Techniques de compilation » présenté aux

classes de deuxième année des études d’ingénieurs en Informatique à l’ENSI. Ce
polycopié est inspiré de plusieurs cours et d’ouvrages de compilation, à savoir :
- « Le cours de techniques de compilations » du Professeur Adbelfatteh
BELGUITH, proposé aux étudiants de deuxième année à l’ENSI.
- « Le cours de langages et compilation » du Docteur Lamia ELABED, proposé
aux étudiants de troisième année à l’ISG de Tunis.
- A. Aho, R. Sethi, J. Ullman, « Compilateurs : principes, techniques et outils »,
2000.
- J. Voiron, « Comprendre la compilation », (disponible à la bibliothèque de
l’ENSI sous la référence : A-95)
- H. Glaire, « Technique de compilation », 1989. (disponible à la bibliothèque de
l’ENSI sous la référence : A-297)
Dans ce cours, nous allons essayer d’aborder les principaux aspects des compilateurs.
Pour approfondir les notions présentées dans ce cours, il est possible de consulter des
ouvrages plus approfondis (voir bibliographie).
Ce cours suppose que les étudiants ont des connaissances dans la matière « Théorie
des langages ».

1.1. Définition d’un compilateur

Un compilateur est un programme qui lit un programme écrit dans un premier
langage -le langage source- et le traduit en un programme équivalent écrit dans un
autre langage, le langage cible (voir figure 1.1). Au cours du processus de traduction,
l'un des rôles importants des compilateurs est de signaler à l'utilisateur la présence
d'erreurs dans le programme source.

Figure 1.1. Un compilateur

Il existe des milliers de langages source, allant des langages de programmation

traditionnels comme Fortran, Pascal, C, etc. aux langages spécialisés, qui sont

Sami KHALFOUI – Moez HAMMAMI – ENSI 3

2006/2007
 Introduction à la compilation

apparus dans quasiment tous les domaines d’applications de l’informatique. Les

langages cibles sont au moins aussi variés; un langage cible peut être un langage de
programmation ou bien le langage machine de n’importe quel ordinateur.

1.2. Compilation par analyse et synthèse

Il y'a deux parties dans la compilation:
- La partie analyse: partitionne le programme source en ses constituants et
en crée une représentation intermédiaire. (Elle vérifie avant si le programme
est bien écrit selon les spécifications du programme source).
- La partie synthèse: construit le programme cible désiré à partir de cette
représentation intermédiaire.

1.2.1. Analyse du programme source

Cette analyse comprend 3 phases:

1. L'analyse linéaire (analyse lexicale): le flot de caractères formant le
programme source est lu de gauche à droite et groupé en unités lexicales qui
sont des suites de caractères ayant une signification collective. Cette phase
aussi répond à la question: est-ce que les mots (jetons) qui existent dans ce
programme source sont corrects? On utilise alors les automates à états finis
déterministe et non déterministes.
2. L'analyse hiérarchique (analyse grammaticale ou syntaxique = Parsing):
Cette phase répond à la question: est ce que la séquence de ces mots (résultant
de l'analyse linéaire ) forme bien des phrases cohérentes, si oui, ces unités
lexicales seront groupées hiérarchiquement dans des collections imbriquées
ayant une signification collective (arbre syntaxique, Parse tree)
Exemple 1.1. Un arbre décrivant une instruction d'affectation E := m*c*c

:=

E *

m *

c c

3. L'analyse sémantique: au cours de laquelle on opère certains contrôles

pour s'assurer que l'assemblage des constituants d'un programme a un sens.
Elle répond aux questions: Est-ce que les opérandes de toutes les opérations
sont correctes (types), faut-il faire une conversion, est-ce que les indices d'un
tableau sont corrects. Si oui, extraire un programme écrit dans un autre
langage = Traduction.

Sami KHALFOUI – Moez HAMMAMI – ENSI 4

2006/2007
 Introduction à la compilation

1.2.2. Phases d'un compilateur

Un compilateur opère en phases, chacune d'elles transformant le programme source

d'une représentation en une autre comme le montre la figure 1.2:
Exemple 1.2. (Analyse lexicale)
Les caractères formant l'instruction d'affectation :
position := initiale + vitesse * 60
seraient groupées dans les unités lexicales suivantes:
1. L'identificateur position
2. Le symbole d'affectation :=
3. L'identificateur initiale
4. Le signe +
5. L'identificateur vitesse
6. Le signe de multiplication *
7. Le nombre 60
Les blancs séparent les caractères formant ces unités lexicales seront éliminées au
cours de l'analyse lexicale.
Remarques 1.
 Une fonction essentielle d'un compilateur est d'enregistrer les
identificateurs utilisés dans le programme source et de collecter de
l'information sur divers attributs de chaque identificateur. Ces attributs
fournissent de l'information concernant, par exemple, l'emplacement
mémoire assigné à un identificateur, son type, sa portée.
 Une table de symboles est une structure de données contenant un
enregistrement pour chaque identificateur, muni de champs pour chaque
identificateur. Cette structure de données permet de retrouver rapidement
l'enregistrement correspondant à un certain identificateur et d'accéder
rapidement aux données qu'il contient.
 Quand l'analyseur lexical détecte un identificateur, il le fait entrer dans la
table des symboles, cependant ses attributs ne peuvent normalement pas
être déterminés pendant l'analyse lexicale; par exemple, le type ne sera
déterminé que pendant l'analyse sémantique, il sera donc ajouté durant
cette phase.

Sami KHALFOUI – Moez HAMMAMI – ENSI 5

2006/2007
 Introduction à la compilation

Figure 1.2. Phases d'un compilateur

Remarque 2. Détection et compte rendu des erreurs

Chaque phase peut rencontrer des erreurs. La phase d'analyse lexicale peut détecter
des erreurs quand les caractères restant à lire ne peuvent former aucune unité
lexicale du langage. La phase d'analyse syntaxique détecte les erreurs dues au fait
que le flot d'unités lexicales n'est pas conforme aux règles structurelles (syntaxe) du
langage. Dans la phase d'analyse sémantique, le compilateur détecte les constructions
ayant une structure grammaticale correcte, mais telle que les opérations qu'elles

Sami KHALFOUI – Moez HAMMAMI – ENSI 6

2006/2007
 Introduction à la compilation

mettent en œuvre n'ont pas de sens. Par exemple lorsqu'on essaye d'additionner
deux identificateurs; l'un est le nom d'un tableau et l'autre celui d'une procédure.

Remarque 3. Analyse syntaxique

Cette phase consiste à regrouper les unités lexicales du programme source en
structures grammaticales qui seront employées par le compilateur pour synthétiser
son résultat. Ces phases sont en général représentées par un arbre syntaxique comme
celui de la figure 1.3.

Instruction
d'affectation

identificateur expression
:=
+
position
expression expression

identificateur expressio n * expression

initiale nombre
identificateur
60
vitesse

Figure 1.3. Arbre syntaxique pour : position := initiale + vitesse * 60

Les structures syntaxiques d'un langage sont généralement exprimées par des règles
récursives (grammaire)

G( V, , R, S)
(terminaux + non terminaux, alphabet, règles de production, axiome)

A  id := E
E E+E
E E
*E E
id
E nb

Remarque 4. Génération du code Intermédiaire

On peut considérer le code Intermédiaire comme un programme pour une machine
qui a une infinité de registres. Cette représentation doit avoir deux propriétés
importantes; Elle doit être facile à produire à partir de l'arbre syntaxique et facile à
traduire en langage cible.
Dans ce cours nous étudierons une forme intermédiaire appelée "code à 3 adresses"
qui est semblable au langage d'assemblage d'une machine dans laquelle chaque
Sami KHALFOUI – Moez HAMMAMI – ENSI 7
2006/2007
 Introduction à la compilation

emplacement peut jouer le rôle d'un registre. Un fragment de code à 3 adresses

consiste en une séquence d'instructions, dont chacune a au plus 3 opérandes.
Le programme source "position := initiale + vitesse * 60 pourrait être traduit en code
à trois adresses de la façon suivante:
temp1 := EntierVersRéel (60)
temp2 := id3 * temp1
temp3 := id2 + temp2
id1 := temp3

Remarque 5. Optimisation du code

Cette phase tente d'améliorer le code intermédiaire de façon que le code machine
résultant s'exécute plus rapidement.

Exemple 1.3.
temp1 := EntierVersRéel (60) la conversion de 60 peut être faite une fois
temp2 := id3 * temp1 pour toutes au moment de la compilation
(60.0)
temp3 := id2 + temp2 temp3 n'est utilisée qu'une seule fois pour
id1 := temp3 transmettre sa valeur à id1 on peut alors
substituer id1 à temp3

on obtient donc:

temp1 := id3 * 60.0

id1 := id2 + temp1

Remarque 6. Production du code

La phase finale d'un compilateur est la production du code cible. Un aspect crucial de
ce processus est l'assignation de variables aux registres.

Exemple 1.4. pour le code

intermédiaire temp1 := id3 * 60.0
id1 := id2 + temp1
on obtient le code objet suivant:
LOAD id3, R1 charge le contenu de id3 dans le register R1
MULF #60.0, R1 MULF: multiplication en virgule flottante, #: constante
LOAD id2,R2
ADD R1, R2 additionne le contenu de R1 et R2, le résultat est place dans R1
STORE R1, id1 copie le contenu de R1 dans l'emplacement id1

1.2.3. Partie Frontale et finale

La construction d'un compilateur se divise généralement en deux parties: une partie

frontale et une partie finale.

Sami KHALFOUI – Moez HAMMAMI – ENSI 8

2006/2007
 Introduction à la compilation

- La partie frontale est constituée des phases qui dépendent principalement du

langage source et qui sont en grande partie indépendantes de la machine cible.
Elle comprend normalement l'analyse lexicale, l'analyse syntaxique, la création
de la table des symboles, l'analyse sémantique et la production du code
intermédiaire.
La partie frontale peut aussi effectuer une certaine quantité d'optimisation du
code. Elle inclut aussi le traitement d'erreurs associé à chacune de ces phases.
- La partie finale comprend les portions du compilateur qui dépendent de la
machine cible; celles ci ne dépendent pas du langage source, mais seulement du
langage intermédiaire. On trouve dans la partie finale certains aspects de
l'optimisation du code ainsi que la production de code avec les opérations
nécessaires de traitement d'erreurs et de gestion de la table des symboles.

Sami KHALFOUI – Moez HAMMAMI – ENSI 9

2006/2007
 Expressions régulières et automates à états finis

Expressions régulières et
automates à états finis

2.1. Expressions Régulières

Le problème préliminaire qui se pose à propos des langages est : comment décrire un
langage ? L’étape suivante sera : étant donnée une phrase (un mot), est-ce qu’elle
appartient au langage ?
Dans cette partie, nous introduisons quelques notions de base de la théorie des
langages. En particuliers, nous décrivons les expressions régulières qui permettent
de décrire un certain type de langages, que l’on appelle langages réguliers.
En Pascal, un identificateur est une lettre suivie d'un nombre quelconque,
éventuellement nul, de lettres ou de chiffres. Une expression régulière est une
notation qui nous permettra de définir avec précision les ensembles de ce genre.
Avec cette notation, on peut définir les identificateurs de Pascal comme : lettre
(lettre|chiffre)*
La barre verticale signifie "ou", les parenthèses sont utilisées pour grouper des sous-
expressions, l'étoile signifie "un nombre quelconque, éventuellement nul, d'instances
de" l'expression entre parenthèses, et la juxtaposition de lettre au reste de
l'expression signifie la concaténation.
On construit une expression régulière à partir d'expressions régulières plus simples
en utilisant un ensemble de règles de définition. Chaque expression régulière r
dénote un langage L(r). Les règles de définition spécifient comment L(r) est formé
en combinant de manières variées les langages dénotées par les sous expressions de
r.
Voici les règles qui définissent les expressions régulières sur un alphabet . Associé à
chaque règle figure une spécification du langage dénoté par l'expression régulière
ainsi définie.
1.  est une expression régulière qui dénote {}, c'est à dire l'ensemble constitué
de la chaîne vide.
2. Si a est un symbole de , alors a est une expression régulière qui dénote {a},
c'est-à-dire l'ensemble constitué de la chaîne a. D'après le contexte on peut
parler de a comme expression régulière, comme chaîne ou comme symbole.
3. Supposons que r et s soient des expressions régulières dénotant les langages
L(s) et L(r), alors :
a - (r) | (s) est une expression régulière dénotant L(r)  L(s).
b - (r) (s) est une expression régulière dénotant L(r) L(s).

Sami KHALFOUI – Moez HAMMAMI – ENSI 10

2006/2007
 Expressions régulières et automates à états finis

c - (r)* est une expression régulière dénotant (L(r))*.

d - (r) est une expression régulière dénotant L(r), c'est-à-dire qu’on peut
placer des paires de parenthèses excédentaires autour d'expressions
régulières si on le désire.

Remarques
1. L'opérateur unaire « * » à la plus haute priorité et est associatif à droite.
2. La concaténation a la deuxième plus haute priorité et est associative à gauche.
3. L’opérateur « | » a la plus faible priorité et est associatif à gauche.
Selon les conventions, (a) | ((b)* (c)) est équivalente à a|b*c. Les deux expressions
dénotent l'ensemble des chaînes qui ont soit un seul a, soit un nombre quelconque
éventuellement nul, de b suivis par un c.

Exemple 2.1.
Soit  = {a, b}
1. L'expression régulière a|b dénote l'ensemble {a, b}
2. L'expression régulière (a|b) (a|b) dénote {aa, ab, ba, bb}, l'ensemble de
toutes les chaînes de a et de b de longueur deux. Une autre expression
régulière pour ce même ensemble est : aa | ab | ba | bb.
3. L'expression régulière a * dénote l'ensemble de toutes les chaînes formées d'un
nombre quelconque (éventuellement nul) de a, c'est à dire {, a, aa, aaa, …}.
4. L'expression régulière (a|b)* dénote l'ensemble de toutes les chaînes constituées
d'un nombre quelconque (éventuellement nul) de a ou de b. Une autre
expression régulière pour cet ensemble est (a*b* ) *.
5. L'expression régulière a|a*b dénote l'ensemble contenant la chaîne a et toute les
chaînes constituées d'un nombre quelconque (éventuellement nul) de a suivi
d'un b.
Si deux expressions régulières r et s dénotent le même langage, on dit que r et s sont
équivalentes et on écrit r = s. Par exemple, (a | b) = (b | a). Les expressions
régulières obéissent à un certain nombre de lois algébriques qui peuvent être utilisées
pour manipuler les expressions régulières sous des formes équivalentes, le tableau 2.1
montre quelques lois algébriques qui s'appliquent aux expressions régulières r, s, t.

Axiome Description
r|s = s|r « | » est commutatif
r | (s|t) = (r|s) | t « | » est associatif
(rs)t = r(st) La concaténation est associative
r(s|t) = rs | rt La concaténation est distributive par rapport à
(s|t)r = sr|tr «| »
r = r  est l'élément neutre pour la concaténation

Sami KHALFOUI – Moez HAMMAMI – ENSI 11

2006/2007
 Expressions régulières et automates à états finis

r = r
r* = (r|)* Relation entre * et 

r**= r* * est idempotent

Tableau 2.1. Propriétés algébriques des expressions régulières

2.2. Automates à états finis

Le problème qui se pose est de pouvoir reconnaître si un mot donné appartient à un

langage donné. Un reconnaisseur pour un langage est un programme qui prend en
entrée une chaîne x et répond oui si x est une phrase (mot) du langage et non sinon.
Les automates à états finis (A.E.F.) sont des reconnaisseurs pour les langages
réguliers.
Un automate fini peut être déterministe ou non déterministe, ce dernier terme
signifiant qu'on peut trouver plus d'une transition sortant d'un état sur le même
symbole d'entrée.
 Il y a conflit temps/place :
- Les automates finis déterministes produisent des connaisseurs plus rapides
que les automates finis non déterministes.
- Un automate fini déterministe peut être beaucoup plus volumineux qu'un
automate fini non déterministe.

2.2.1. Automates à états finis non déterministes

Un automate fini non déterministe (AFN en abrégé) est un modèle mathématique qui
consiste en :
1. Un ensemble d'états E ;
2. Un ensemble de symboles d'entrées  (l'alphabet des symboles d'entrée);
3. Une fonction Transiter, qui fait correspondre des couples état-symbole à des
ensembles d'états.
4. Un état e0 qui est distingué comme état de départ ou état initial
5. Un ensemble d'états F distingués comme états d'acceptation ou états
d'acceptation ou états finals.
Un AFN peut être représentée graphiquement comme un graphe orienté étiqueté,
appelé graphe de transition, dans lequel les nœuds sont les états et les arcs étiquetés
représentent la fonction de transition.

Remarque.
Ce graphe ressemble à un diagramme de transition, mais le même caractère peut
étiqueter deux transitions au plus en sortie d'un même nœud et les arcs peuvent être
étiquetés par le symbole spécifique au même titre que les symboles d'entrées.

Sami KHALFOUI – Moez HAMMAMI – ENSI 12

2006/2007
 Expressions régulières et automates à états finis

Exemple 2.2.
Soit le langage dénoté par l'expression régulière (a | b)* abb, consistant en
l'ensemble des chaînes de a et de b se terminant par abb.
La figure 2.1 représente le graphe de transition par un AFN qui reconnaît ce langage.
L'ensemble des états de l'AFN est {0, 1, 2, 3} et l'alphabet d'entrée est {a, b}. L'état 0
est distingué comme étant l'état de départ et l'état d'acceptation 3 est indiqué par un
double cercle.

a
a b b
début 0 1 2 3

Figure 2.1. Un automate fini non déterministe

Implémentation d’un AFN

En machine la fonction de transition d'un AFN peut être implantée à l'aide d'une
table de transition dans laquelle il y a une ligne pour chaque état et une colonne pour
chaque symbole d'entrées et , si nécessaire.
L'entrée pour la ligne i et le symbole a dans la table, donne l'ensemble des états qui
peuvent être atteints par une transition depuis l'état i sur le symbole a. (voir tableau
2.2)
SYMBOLE D'ENTREE
Etats a b
0 {0, 1} {0}
1 - {2}
2 - {3}
3 - -
Tableau 2.2. Table de transition pour l'automate fini non déterministe de la figure 2.1

Un AFN accepte une chaîne d'entrée x si et seulement si il existe un certain chemin

dans le graphe de transition entre l'état de départ et un état d'acceptation, tel que les
étiquettes d'arcs le long de ce chemin épellent le mot x.
L'AFN de la figure 2.1 accepte les chaînes d'entrées abb, aabb, babb, aaabb, … Par
exemple, aabb est acceptée par le chemin depuis 0, en suivant de nouveau l'arc
étiqueté a vers l'état 0, puis vers les états 1, 2 et 3 via les arcs étiquetés a;b et b
respectivement.
Un chemin peut être représenté par une suite de transitions d'état appelée
déplacements. Ce diagramme montre les déplacements réalisés en acceptant la
chaîne d'entrée aabb.

a a b b En général, il existe plus d'une suite

0 0 1 2 3 de déplacements pouvant mener à
l'état d'acceptation

Sami KHALFOUI – Moez HAMMAMI – ENSI 13

2006/2007
 Expressions régulières et automates à états finis

Bien d'autres suites de déplacements pourraient être faites sur la chaîne d'entrée
aabb, mais aucune des autres n'arrive à terminer dans un état d'acceptation.

a a b b Cette suite stationne dans l'état de

0 0 0 0 0 non acceptation 0.

 Le langage défini par un AFN est l'ensemble des chaînes d'entrées qu'il accepte.

Exemple 2.3.
Soit l’expression régulière aa*|bb*. Cette expression est acceptée par l’automate de la
figure 2.4.
a
a
 1
2
0 b
 b
3 4

Figure 2.4. Automate fini non déterministe acceptant aa*|bb*

La chaîne aaa est acceptée en se déplaçant via les états 0, 1, 2, 2, et 2. Les étiquettes
de ces arcs sont : , a, a, et a dont la concaténation est aaa. Notons que  disparaît
dans la concaténation.

2.2.2. Automates à états finis déterministes

Un automate fini déterministe (AFD en abrégé) est un cas particulier d'automate fini
non déterministe dans lequel :
1. Aucun état n'a de  transitions, c'est à dire de transition sur l'entrée  et
2. Pour chaque état e et chaque symbole d'entrée a, il y a au plus un arc étiqueté a
qui quitte e.
Un automate fini déterministe a au plus une transition à partir de chaque état sur
n'importe quel symbole. Chaque entrée de sa table de transition est un état unique. Il
est très facile de déterminer si un automate fini déterministe accepte une chaîne
d'entrée, puisqu'il existe au plus un chemin depuis l'état de départ étiqueté par cette
chaîne.
L'algorithme 2.1 montre comment simuler le comportement d'un AFD sur une chaîne
d'entrée.

Algorithme 2.1. Simulation d'un AFD

Données :

Sami KHALFOUI – Moez HAMMAMI – ENSI 14

2006/2007
 Expressions régulières et automates à états finis

- Une chaîne d'entrée x terminée par un caractère de fin de fichier « fdf ».

- Un AFD D avec un état de départ e0 et un ensemble d'états d'acceptation F.
Résultat :
La réponse "oui" si D accepte x; "non" dans le cas contraire.
Méthode :
La fonction transiter(e, c) donne l'état vers lequel il y a une transition depuis
l'état e sur le caractère d'entrée c. La fonction CarSuiv retourne le prochain
caractère de la chaîne d'entrée x.
e := e0
C:=CarSuiv();
Tanque c  fdf faire
e:= Transiter(e,
c); c:= CarSuiv();
fin
si e  F alors
retourner "oui"
sinon
retourner "non"

Exemple 2.4.
La figure 2.5 présente le graphe de transition d'un automate fini déterministe qui
accepte la langage (a|b)* abb (le même que celui accepté par l'AFN de la figure 2.1).
Avec cet AFD et la chaîne d'entrée ababb, l'algorithme 1 passe par la suite les états 0,
1, 2, 1, 2 et 3 et retourne oui.

Figure 2.5. DFA acceptant (a|b)*abb

2.2.3. Transformation d'un AFN en AFD

Si on utilise un AFN pour vérifier si une chaîne x  langage, on trouvera plusieurs

chemins qui épellent la même chaîne x, on doit les avoir tous pris en compte avant
d'en trouver un qui mène à l'acceptation ou de découvrir qu'aucun d'entre eux ne
mène à un état d'acceptation.

Remarque.
Dans la table de transition d'un AFN, chaque entrée est un ensemble d'états. Dans la
table de transition d'un AFD chaque entrée est un état unique.

Sami KHALFOUI – Moez HAMMAMI – ENSI 15

2006/2007
 Expressions régulières et automates à états finis

L'idée  chaque état de l'AFD correspond à un ensemble d'états de l'AFN.

Algorithme 2.2. Construction d'un AFD à partir d'un AFN

Données : Un AFN N
Résultat : Un AFD D qui accepte le même langage.
Méthode : Notre algorithme construit une table de transition Dtran pour D.
Chaque état de l'AFD est un ensemble d'états de l'AFN et on construit
Dtran de telle manière que D simulera "en parallèle" tous les
déplacements possibles que N peut effectuer sur une chaîne d'entrée
donnée.
On utilise les opérations suivantes (voir tableau 2.3) pour garder trace des ensembles
d'états de l'AFN (e représente un état de l'AFN et T représente un ensemble d'états
de l'AFN).

opération Description
Ensemble des états de l'AFN accessibles depuis un état
-fermeture(e)
e de l'AFN par de -transitions uniquement
Ensemble des états de l'AFN accessibles de puis un état
-fermeture(T)
e appartenant à T par des -transitions uniquement
Ensemble des états de l'AFN vers lesquels il existe une
Transiter(T, a) transition sur le symbole à partir d'un état e
appartenant à T
Tableau 2.3. Opérations sur les états d'un AFN

Avant de voir le premier symbole d'entrée, N peut appartenir à n'importe lesquels

des états de l'ensemble ε-fermeture (e0) ou e0 est l'état de départ de N. Supposons que
seules les états de l’ensemble T soient accessibles à partir de e0 sur une suite donnée
de symboles d’entrée, et soit a le prochain symbole d’entrée. Quand il voit a, N peut
passer dans un des états de l’ensemble Transiter (T, a). Quand on autorise des -
transitions, N peut être dans un des états de ε-fermeture (Transiter (T, a)), après avoir
lu le a.
On construit Détats, l'ensemble des états de D et Dtran, la table de transition de D, de
la manière suivante. Chaque état de D correspond à un ensemble d'états de l'AFN
dans lesquels N pourrait se trouver après avoir lu une suite de symboles d'entrée, en
incluant toutes les -transitions possibles avant ou après la lecture des symboles.
L'état de départ D est ε-fermeture(e0). On ajoute des états et des transitions à D en
utilisant l'algorithme 2.3.

Algorithme 2.3. Construction des sous-ensembles

Au départ ε-fermeture(e0) est l'unique état de Détats et il est non marqué;
Tant que il existe un état non marqué T dans Détats faire début
Marquer T;
Pour chaque symbole d'entrée a faire début
U : = -fermeture(Transiter(T, a));

Sami KHALFOUI – Moez HAMMAMI – ENSI 16

2006/2007
 Expressions régulières et automates à états finis

Si U n'appartient pas à Détats alors

Ajouter U comme nœud non marqué de Détats;
Dtran[T,a] : = U
Fin
Fin

Un état D est un état d'acceptation si c'est un ensemble d'états de l'AFN qui contient
au moins un état d'acceptation.

Exemple 2.5.
La figure 2.6 illustre un AFN qui accepte le langage (a|b)*abb. Appliquons
l'algorithme 2.2 à cet AFN. L'état de départ de l'AFD équivalent est -fermeture(0),
qui est A = {0,1,2,4,7}, étant donné que ce sont précisément les états accessibles
depuis l'état 0 via un chemin dans lequel chaque arc est étiqueté .


a
2 3


  a b b
0 1 6 7 8 9 10

b 
4 5


Figure 2.6. Un NFA pour le langage (a|b)*abb

L'alphabet des symboles d'entrée est ici {a,b}. L'algorithme 2.3 nous dit de marquer A
et de calculer -fermeture(Transiter(A, a)). Nous calculons d'abord Transiter (A,a),
l'ensemble des états de N qui ont des transitions sur a depuis les éléments de A.
Parmi les états 0, 1, 2, 4 et 7, seuls 2 et 7 ont de telles transitions vers 3 et 8, aussi :
-fermeture(Transiter({0,1,2,4,7},a) = -fermeture({3,8}) = {1,2,3,4,6,7,8}
Appelons cet ensemble B. Nous avons alors Dtran[A,a]= B.
Parmi les états de A, seul 4 a une transition sur b vers 5 aussi l'AFD a une transition
sur b depuis A vers :
C = -fermeture({5}) = {1,2,4,5,6,7}.
Donc Dtran[A,b] = C
Si nous continuons ce processus avec les ensembles actuellement non marqués B et
C, on atteint finalement le point où tous les ensembles qui sont des états de l'AFD
sont marqués.
Les cinq différents ensembles que nous construisons réellement sont
: A = { 0,1,2,4,7} D = {1,2,4,5,6,7,9}

Sami KHALFOUI – Moez HAMMAMI – ENSI 17

2006/2007
 Expressions régulières et automates à états finis

B = {1,2,3,4,6,7,8} E = {1,2,4,5,6,7,10}
C = {1,2,4,5,6,7}

L'état A est l'état de départ et l'état E est l'unique état d’acceptation (le tableau 2.4
donne la table du transition complète).

Symbole
Etat d'entrée
a b
A B C
B B D
C B C
D B E
E B C
Tableau 2.4. Table de transition Dtran pour le DFA

Voici le graphe de transition correspondant à l'AFD (voir figure 2.7)

Figure 2.7. DFA pour (a|b)*abb

2.3. Transformation d'une expression régulière en un AFD

Une façon de construire un reconnaisseur à partir d'une expression régulière consiste
à construire un NFA à partir d'une expression régulière ensuite simuler le
comportement de l'NFA sur une chaîne d'entrée en utilisant les algorithmes que nous
allons voir. Si la vitesse d'exécution est essentielle, on peut convertir le AFN en AFD.

2.3.1. Construction d'un AFN à partir d'une expression régulière

L’algorithme est dirigé par la syntaxe en ce sens qu'il utilise la structure syntaxique
de l'expression régulière pour guider le processus de construction. On va voir
d'abord comment construire les automates pour les opérations qui contiennent un
opérateur d'alternance, de concaténation ou de fermeture de Kleene. Par exemple,
pour l'expression r|s, on construit un AFN à partir des AFN reconnaissant r et s.

Sami KHALFOUI – Moez HAMMAMI – ENSI 18

2006/2007
 Expressions régulières et automates à états finis

Algorithme 2.4. Construction d'un AFN à partir d'une expression régulière,

ou construction de Thompson.
Donnée : Une expression régulière r sur un alphabet .
Résultat : un AFN N qui reconnaît L(r).
Méthode : On décompose d'abord r en ses sous expressions. Puis en utilisant les
règles (1) et (2) ci dessous, on construit des NFA pour chacun des symboles de
base de r, c'est à dire doit  soit les symboles de l'alphabet. Les symboles de base
correspondent aux parties (1) et (2) dans la définition d'une expression régulière
(il est important de comprendre que si un symbole a apparaît plusieurs fois
dans r, un AFN séparé est construit pour chaque occurrence).
Ensuite, en se guidant sur la structure syntaxique de l'expression régulière r, on
combine régulièrement ces AFN en utilisant la règle (3) ci dessous, jusqu'à
obtenir le AFN pour l'expression régulière complète.
Chaque AFN intermédiaire produit au cours de la construction correspond à
une sous- expression de r et a plusieurs propriétés importantes: il a exactement
un état final, aucun arc ne rentre dans l'état de départ et aucun arc ne quitte
l'état final.

1. Pour , construire l'AFN:

déb 
i f

Ici i est un nouvel état de départ et f un nouvel état d'acceptation. Il est clair que cet
AFN reconnaît {}

2. Pour un a appartenant à , construire l'AFN :

déb a
i f

Ici encore, i est un nouvel état de départ et f un nouvel état d'acceptation. Cet
automate reconnaît {a}.

3. Supposons que N(s) et N(t) soient les AFN pour les expressions régulières s et t.

(a) Pour l'expression régulière s|t, construire l'AFN composé suivant N(s|t):

N(s


déb i f



Sami KHALFOUI – Moez HAMMAMI – ENSI 19

2006/2007
 Expressions régulières et automates à états finis

Ici, i est un nouvel état de départ et f un nouvel état d'acceptation. Il y a une

transition sur  depuis i vers les états de départ de N(s). Il y a une transition sur
 depuis les états d'acceptation de N(s) et N(t) vers le nouvel état d'acceptation f.
Les états de départ et d'acceptation N(s) et N(t) ne sont pas les états de départ et
d'acceptation de N(s|t). Il est à noter que tout chemin depuis i vers f doit
traverser soit N(s), soit N(t) exclusivement on voit donc que l'automate composé
reconnaît L(s)  L (t).

(b) Pour l'expression régulière st, construire l'AFN composé N(st) :

i N(s N(t f

L'état de départ de N(s) devient l'état de départ de l'AFN composé et l'état

d'acceptation de N(s) est fusionné avec l'état de départ de N(t).
 Toutes les transitions depuis l'état de départ de N(t) deviennent des
transitions depuis l'état d'acceptation de N(s). Le nouvel état fusionné perd son
statut d'état de départ ou d'acceptation dans l'AFN composé.

(c) Pour l'expression régulière S*, construire l'AFN composé N(S*) :

 
i N(s f


Ici, i est un nouvel état de départ et f un nouvel état d'acceptation. Dans l'AFN
composé, on peut aller de i à f directement en suivant un arc étiqueté  qui
représente que  appartient à (L(s))*, ou bien on peut aller de i à f en traversant
N(s) une ou plusieurs fois. Il est clair que l'automate composé reconnaît (L(s))*.

(d) Pour l'expression régulière parenthèse (s), utiliser N(s) lui même comme
AFN.
Chaque fois qu'on construit un nouvel état, on lui donne un nom distinct. Ainsi, il ne
peut y avoir deux états dans deux sous-automates qui aient le même nom. Même si le
même symbole apparaît plusieurs fois dans r, on crée, pour chaque instance de ce
symbole, un AFN séparé avec ses propres états.

Sami KHALFOUI – Moez HAMMAMI – ENSI 20

2006/2007
 Expressions régulières et automates à états finis

La construction produit un AFN N(r) qui a les propriétés suivantes :

1. N(r) a au plus deux fois d'états qu'il y a de symboles et d'opérateurs dans r.
Ce ci revient du fait que chaque étape de la construction crée au plus deux
nouveaux états
2. N(r) a également un état de départ et un état d'acceptation. L'état
d'acceptation n'a pas de transition sortante. Cette propriété s'applique de la
même manière à chacun des sous automates le constituant.
3. Chaque état de N(r) a soit une transition sortante sur un symbole de , soit au
plus deux transitions sortantes sur .

Exemple 2.6.
Soit l'expression régulière r = (a|b)* abb. La figure 2.8 présente un arbre syntaxique
pour r.

Figure 2.8. Décomposition de (a|b)*abb

- Pour le composant r1, le premier a, on construit l'AFN

- Pour r2, on construit

- On peut maintenant combiner N(r1) et N(r2) en utilisant la règle d'union pour

obtenir l'AFN pour r3 = r1|r2 :

Sami KHALFOUI – Moez HAMMAMI – ENSI 21

2006/2007
 Expressions régulières et automates à états finis

- L'AFN pour r4 est le même que celui pour r3. L'AFN pour (r4)* est alors :

- L'AFN pour r6= a est :

- Pour obtenir l'automate pour r7 =r5r6, on fusionne les états 7 et 7' en appelant
l'état résultant 7 pour obtenir

- En continuant ainsi on obtient l'AFN pour r11 = (a|b)*abb

Sami KHALFOUI – Moez HAMMAMI – ENSI 22

2006/2007
 Expressions régulières et automates à états finis

Figure 2.9. AFN obtenu par la construction de Thompson pour r11=(a|b)*abb

2.4. Simulation d'un AFN

Nous présentons maintenant un algorithme qui, si on lui donne un AFN N construit
par l'algorithme 2.4 (construction de Thompson) et une chaîne d'entrée x, détermine
si N accepte x. L'algorithme fonctionne en lisant le texte d'entrée, caractère par
caractère, et en calculant l'ensemble complet des états dans lesquels N peut se
trouver après avoir lu chaque préfixe de la chaîne d'entrée.

Algorithme 2.5 : Simulation d'un AFN

Données : Un AFN N construit par l'algorithme 4 et une chaîne d'entrée x, On
suppose que x est terminée par un caractère de fin de fichier « fdf ». N a un état
de départ e0 et un ensemble d'états d'acceptation F.
Résultat : La réponse « oui » si N accepte x; « non » dans le cas contraire.
Méthode : Appliquer l'algorithme suivant à la chaîne d'entrée
x E := -fermeture({e0});
a:= Carsuiv();
Tant que a  fdf faire début
E:=-fermeture (transiter(E,a));
A:= CarSuiv()
Fin

Si EF  Ø alors
Retourner "oui
Sinon
Retourner "non"
L'algorithme en réalité réalise la construction des sous-ensembles à l'exécution. Il
calcule une transition depuis l'ensemble courant d'états E vers le prochain ensemble
d'états en deux étapes. Tout d'abord, il détermine l'ensemble transiter(E, a)de tous les
états qui peuvent être atteints depuis un état de E par une transition sur a, le
caractère d'entrée courant. Ensuite, il calcule ε-fermeture de transiter(E, a), c'est à dire
tous les états qui peuvent être atteints depuis transiter (E, a) par zéro ou plusieurs ε-
fermeture. L'algorithme utilise la fonction CarSuiv pour lire les caractères de x, un par
un.

Sami KHALFOUI – Moez HAMMAMI – ENSI 23

2006/2007
 Expressions régulières et automates à états finis

Quand tous les caractères de la chaîne d'entrée x ont été traités, l'algorithme retourne
« oui » si l'ensemble des états courants contient un état d'acceptation, « non » dans le
cas contraire.

Implantation à l'aide de deux piles

Cet algorithme peut être efficacement implanté en utilisant deux piles et un vecteur
indicé par les états de l'AFN :
- On utilise une pile pour garder trace de l'ensemble courant des états non
déterministe, et l'autre pile pour calculer l'ensemble suivant d'états non
déterministes.
- On peut utiliser le vecteur de bits pour déterminer rapidement si un état non
déterministe est déjà dans la pile, de manière à ne pas l'ajouter une deuxième
fois.
- Une fois qu'on a calculé l'état suivant sur la deuxième pile, on peut échanger le
rôle de deux piles.

Sami KHALFOUI – Moez HAMMAMI – ENSI 24

2006/2007
 Analyse lexicale

Analyse lexicale

Ici, on traite des techniques de spécification et d'implémentation d'analyseurs

lexicaux. Une manière simple de construire un analyseur lexical consiste à bâtir un
diagramme qui illustre la structure des unités lexicales du langage source, puis de
traduire à la main le diagramme en programme qui reconnaît les unités lexicales.
Un outil logiciel qui automatise la construction d'analyseurs lexicaux permet à des
utilisateurs de cultures différentes d'employer des comparaisons de modèles, ou
filtrage dans leurs propre domaines d'application. Par exemple, Javis a utilisé un
constructeur d'analyseurs lexicaux pour créer un programme qui reconnaît des
imperfections dans les circuits imprimés.
Un avantage majeur d'un constructeur d'analyseurs lexicaux est qu'il peut utiliser les
algorithmes de filtrage les plus connus et en conséquence, créer des analyseurs
lexicaux efficaces pour des utilisateurs qui ne sont pas des experts en matière de
technique de filtrage par modèle.

3.1. Le rôle de l'analyseur lexical

L’analyseur lexical constitue la première phase d'un compilateur, sa tache principale
est de lire les caractères d'entrée et de produire comme résultat, une suite d'unité
lexicales que l'analyseur syntaxique va utiliser (voir figure 3.1).

Figure 3.1. Interaction entre un analyseur lexical et un analyseur syntaxique

A la réception d'une commande "prochaine unité lexicale" de l'analyseur syntaxique,

l'analyseur lexical lit les caractères d'entrée jusqu'à ce qu'il puisse obtenir la
prochaine unité lexicale. Cette interaction est couramment implantée en faisant de
l'analyseur lexical un sous programme de l'analyseur syntaxique. L’analyseur lexical
peut aussi réaliser certaines tâches secondaires comme l'élimination des
commentaires et des espaces (caractère blanc, tabulation, fin de ligne). Une autre
tâche consiste à relier les messages d'erreurs issus du compilateur, au programme
source (garder la trace du nombre de caractère fin de ligne rencontrée pour pouvoir
associer un numéro de ligne à un message d'erreur).

Sami KHALFOUI – Moez HAMMAMI – ENSI 25

2006/2007
 Analyse lexicale

On divise souvent les analyseurs lexicaux en deux phases successives, la première

appelée « lecture » et la seconde « analyse lexicale ». La lecture est responsables de
tâches simples (exemple, éliminer les blancs), tandis que l’analyse lexicale
proprement dit réalise les opérations les plus complexes.

3.1.1. Pourquoi une analyse lexicale

De nombreuse raisons justifient de découper la phase d'analyse de la compilation en

analyse lexicale et analyse syntaxique.
1. Une conception plus simple (simplifier l'une ou l'autre des phases).
Exemple : un analyseur syntaxique contiendrait les traitements relatifs aux
commentaires et aux espaces serait nettement plus complexe que celui qui les
considère déjà éliminés par un analyseur lexical.
2. L'efficacité du compilateur est améliorée.
Un analyseur lexical séparé permet de construire un module spécialisé et
potentiellement plus efficace pour cette tache (utilisation de technique
spécialisées de gestion des tampons au cours de la lecture des caractères d'entrée
et du traitement des unités lexicales.
3. La portabilité du compilateur est accrue.
Les particularités de l'alphabet d'entrées et d'autres anomalies spécifiques au
matériel peuvent être confiées à l'analyseur lexical (la représentation des
symboles spéciaux ou non standard, comme la  en Pascal, peut être restreinte à
l'analyseur lexical).
Des outils spécialisés ont été conçus pour aider à automatiser la construction
d'analyseurs lexicaux et syntaxiques (on va les étudier ultérieurement)

3.1.2. Unités lexicales, modèles et lexèmes

Quand on parle d'analyse lexicale, on utilise les termes « unité lexicale » « modèle »
et « lexème » avec des spécifications bien spécifiques. Le tableau 3.1 donne des
exemples de leur utilisation. En général, il y a un ensemble de chaînes en entrée pour
lesquelles la même unité lexicale est produite en sortie. Cet ensemble de chaînes est
décrit par une règle appelée modèle associé à l'unité lexicale. On dit que le modèle
filtre chaque chaîne de l'ensemble.
Un lexème est une suite de caractères du programme source qui concorde avec le
modèle de l'unité lexicale. Par exemple, dans la déclaration Pascal : const pi=3.1416.
La sous-chaîne pi est un lexème de l'unité lexicale « identificateur ».
Les lexèmes reconnus par le modèle décrivant l'unité lexicale représentent les chaînes
de caractères du langage source qui peuvent être traitées en bloc comme une unité
lexicale.

Sami KHALFOUI – Moez HAMMAMI – ENSI 26

2006/2007
 Analyse lexicale

Description informelle
Unité lexicale Lexèmes
des modèles
const const const
if if if
oprel (opérateur de
< <= = <> > >= < <= = <> > >=
relation)
lettre suivie de lettres ou
id pi compte D2
chiffres
Toute constante
nb 3.1416 0 6.02E23
numérique
Tous caractère entre"et"
littéral "cours compilation"
sauf "
Tableau 3.1. Exemples d'unités lexicales

Dans la plupart des langages de programmation, les constructions suivantes sont

traitées comme des unités lexicales : mots clés, opérateurs, identificateurs,
constantes, chaînes littérales et symbole de ponctuation (parenthèses, virgules, :).
Dans l'exemple précédent, quand la suite de caractères pi apparaît dans le
programme source, une unité lexicale représentant un identificateur est retournée à
l'analyseur syntaxique (souvent en passant un entier correspondant à l'unité lexicale,
c'est cet entier qui est référencé par l'unité lexicale id).
Un modèle est une règle qui décrit l'ensemble des lexèmes pouvant représenter une
unité lexicale particulière dans les programmes sources. Le modèle de l'unité lexicale
const est limité à la simple chaîne const qui orthographie le mot clé. Le modèle de
l'unité lexicale oprel est l'ensemble des six opérateurs de relation de pascal. Pour
décrire précisément les modèles d'unités lexicales plus complexes, comme id et nb
nous utiliserons la notation des expressions régulières que nous allons voir.

3.1.3. Attributs des unités lexicales

L'analyseur lexical réunit les informations sur les unités lexicales dans les attributs
qui leur sont associés. Par exemple le modèle nb correspond à la fois à la chaîne 0 et
1, mais il est essentiel pour le générateur de code de savoir quelle chaîne a
effectivement été reconnue. Les unités lexicales influent sur les décisions de l'analyse
syntaxique les attributs influent sur la traduction des unités lexicales. En pratique,
une unité lexicale a en général un seul attribut un pointeur vers l'entrée de la table
des symboles dans laquelle l'information sur l'unité lexicale est conservée.

Exemple 3.1.
Les unités lexicales et les valeurs d'attributs associées pour l'instruction Fortran E =
M*C**2 sont données ici sous la forme de couples :

Sami KHALFOUI – Moez HAMMAMI – ENSI 27

2006/2007
 Analyse lexicale

<id, pointeur vers l'entrée de la table des symboles associés à E>

<op-affectation, > /* aucune valeur d'attribut n'est nécessaire, le premier composant suffit
pour identifier le lexème*/.
<id, pointeur vers l'entrée de la table des symboles associés à M>
<op-multiplication,>
<id, pointeur vers l'entrée de la table des symboles associés à C>
<op-exponentiation, >
<nb, valeur entière 2> /* Nous avons associé à cette unité un attribut à valeur entière. Le
compilateur peut ranger la chaîne de caractères composant le nombre dans
la table des symboles et faire en sorte que l'attribut de l'unité lexicale nb soit
un pointeur vers la table des symboles.*/

3.2. Mémorisation du texte d'entrée: couple de tampons

On utilise un tampon divisé en deux moitiés de N caractères, comme à la figure 3.2
(N pourra être le nombre de caractères dans un bloc disque, par exemple 1024 ou
4096

Figure 3.2. Un tampon d'entrée en deux moitiés

On lit N caractères d'entrées dans chacune des entrées du tampon en une seule
commande système de lecture, plutôt que d'invoquer une commande de lecture pour
chaque caractère d'entrée. S'il reste moins que N caractères en entrée, un caractère
spécial fdf est placé dans le tampon après les caractères d'entrée.
On gère deux pointeurs vers le tampon d'entrées. La chaîne de caractères entre les
deux pointeurs constitue le lexème courant. Au départ les deux pointeurs désignent
le premier caractère du prochain lexème à trouver. L'un appelé le pointeur
« Avant », lit en avant jusqu'à trouver un modèle. Une fois que le prochain lexème est
reconnu, le pointeur « Avant » est positionné sur le caractère à sa droite. Après
traitement de ce lexème, les deux pointeurs sont positionnés sur le caractère qui suit
immédiatement le lexème.
Si le pointeur « Avant » est sur le point de dépasser la marque de moitié, la moitié
droite est remplie avec N nouveaux caractères d'entrée. Si le pointeur « Avant » est
sur le point de dépasser l'extrémité droite du tampon, la partie gauche est remplie
avec N nouveaux caractères d'entrées, et le pointeur « Avant » poursuit
circulairement au début du tampon.

Sami KHALFOUI – Moez HAMMAMI – ENSI 28

2006/2007
 Analyse lexicale

3.3. Spécification des unités lexicales

Les expressions régulière sont une notation importante pour spécifier (donner une
expression formelle) des modèle. Chaque modèle reconnaît un ensemble de chaînes.

3.3.1. Chaînes et langage

Le terme alphabet ou classe de caractère dénote tout ensemble fini de symboles. Des
exemples typiques de symboles sont les lettres et les caractères. L'ensemble {0,1} est
l'alphabet binaire. L' ASCII est un exemple de l'alphabet informatique.
Une chaîne sur un alphabet est une séquence finie de symboles extraits de cet
ensemble. La longueur d'une chaîne s, habituellement notée |s| est le nombre
d'occurrences de symboles dans s. La chaînes vide notée , est une chaîne spéciale de
longueur zéro. Voici la terminologie courante concernant des portions de chaînes
(tableau 3.2).

Terme Définition
Une chaîne obtenue en supprimant un nombre
Préfixe de s quelconque, éventuellement nul, de symboles en fin
de s; par exemple, ban est un préfixe de banane
Une chaîne obtenue en supprimant un nombre
Suffixe de S quelconque, éventuellement nul, de symboles début
de S; par exemple, nane est un suffixe de banane
Une chaîne obtenue en supprimant un préfixe et un
suffixe de S. Par exemple nan de banane. Tout suffixe
Sous-chaîne de S ou préfixe et une sous-chaîne. Pour toute chaîne de S,
S et  sont toutes deux préfixe, suffixes et sous chaîne
de S.
Suffixe, préfixe ou sous- Toute chaîne non vide se qui est, respectivement,
chaîne propre de S préfixe, suffixe ou sous chaîne de s telle que s  x
Toute chaîne obtenue en supprimant un nombre
quelconque, éventuellement nul, de symbole non
Sous suite de S
nécessairement consécutifs de S; par exemple, baan
est une sous suite de banane
Tableau 3.2. Vocabulaire pour les portions de chaînes

Le terme langage dénote un ensemble quelconque de chaînes construites sur un

alphabet fixé.
Si x et y sont deux chaînes, alors la concaténation de x et de y, qui s'écrit xy, est la
chaîne formées en joignant x et y. Par exemple si x = porte et y = mine alors
xy=portemine. La chaîne vide est l'élément neutre pour la concaténation; cela signifie
que S = S = S.
Si l'on considère la concaténation comme un produit, on peut définir l'exponentiation
de chaîne comme suit : on définit S0 comme  et pour i > 0, on définit Si comme Si-1 S.
Comme S est S elle même, S1 = S. Donc S2 = SS ainsi de suite.

Sami KHALFOUI – Moez HAMMAMI – ENSI 29

2006/2007
 Analyse lexicale

3.3.2. Opération sur les langages

Plusieurs opérations importantes peuvent s'appliquer aux langages. Pour l'analyse

lexicale, On s'intéresse principalement à l'union, la concaténation et la fermeture
définis dans le tableau 3.3. On peut aussi généraliser l'opérateur d'exponentiation aux
langages en définissant L0 comme {}, et Li comme Li-1 L. Ainsi, Li et L concaténé i-1
fois avec lu i même.

Opération Définition
Union de L et M notée LCM LM = { S | SL ou S  M }
Concaténation de L et M notée LM LM = { St | SL et t  M }
L* =   Li
i0

Fermeture de kleene de L notée L* L* dénote un nombre quelconque

éventuellement nul, de concaténation
de L.
L+ =  Li
i1

Fermeture positive de L notée L+ L+ dénote un nombre quelconque non

nul, de concaténation de L.

Tableau 3.3. Opérations sur les langages

Exemple 3.2.
Soit L l'ensemble {A, B, …, Z, ab,…, Z} et C {0, 1, …,9}. Etant donnée qu'un symbole
peut être considéré comme une chaîne de longueur 1, les ensembles L et C sont des
langages finis. Voici quelques exemples de nouveaux langages crées à partir de L et
C en appliquant les opérateurs définis dans le tableau 3.3 :
1. L  C est l'ensemble des lettres et des chiffres.
2. LC est l'ensemble des chaînes formées d'une lettre suivie d'un chiffre.
3. L4 est l'ensemble des chaînes de quatre lettres.
4. L* est l'ensemble de toutes les chaînes de lettre y compris , la chaîne vide.
5. L(LC) est l'ensemble de toutes les chaînes de lettre et de chiffres commençant
par une lettre

3.4. Reconnaissances des unités lexicales

Tout au long de cette section nous utiliserons le langage engendré par la grammaire
suivante comme exemple type.

Exemple 3.3.
instr  si expr alors instr
| si expr alors instr sinon instr
|

Sami KHALFOUI – Moez HAMMAMI – ENSI 30

2006/2007
 Analyse lexicale

exp  terme oprel terme

| terme

terme  id
| nb

Où les terminaux si, alors, sinon, oprel, id et nb engendrent les ensembles de

chaînes données par les définitions régulières suivantes :
si  si
alors  alors
sinon  sinon
oprel  < |<= | = | <>| > |
>= id  lettre (lettre |
chiffre)*
nb  chiffre+(.Chiffre+)? (E(+|-)? Chiffre+)?
Lettre et chiffre sont définis comme suit :
lettre  A | B | … | Z | a | b | … |
z chiffre  0 | 1 | … |9

Remarque.
Pour ce fragment de langage l'analyseur lexical reconnaîtra les mots clé si, alors sinon
au même titre que les lexèmes dénotés par oprel, id, nb. (Pour simplifier on suppose
que les mots clé sont réservés).
On suppose que les lexèmes sont séparés par un espace consistant en une suite non
vide de blancs, tabulations et fin de ligne. Notre analyseur lexical éliminera ces
espaces en comparant une chaîne avec la définition régulière bl suivante.
délim  blanc | tabulation | fin de ligne
bl  délim +
Notre objectif est de construire un analyseur lexical qui isole le lexème associé à la
prochaine unité lexicale du tampon d'entrée et qui produise en sortie un couple
composé de l'unité lexicale appropriée et d'une valeur d'attribut. Les attributs pour
les opérateurs de relation (oprel) sont donnés par les constantes symboliques PPQ,
PPE, EGA, DIF, PGQ, PGE.

3.4.1. Diagrammes de transition

Supposons que le tampon d'entrée soit le même que dans la figure 3.2 et que le
pointeur vers le début du tampon pointe sur le caractère qui suit la dernière unité
lexicale trouvée. On utilise un diagramme de transition pour garder trace des
informations sur les caractères rencontrés quand le pointeur « avant » parcourt le
texte d'entrée. On procède par des déplacements de position en position dans le
diagramme au fur et à mesure de la lecture des caractères.

Sami KHALFOUI – Moez HAMMAMI – ENSI 31

2006/2007
 Analyse lexicale

Exemple 3.4.
- Diagramme de transition pour « si » (figure 3.3)

s i
0 1 2 Retourne Si

autre
L'étiquette autre désigne tous les caractères autres que
autre ceux qui sont indiqués explicitement sur les arcs
quittant e.

Figure 3.3. Diagramme de transition pour « si »

- Diagramme de transition pour « >= » (figure 3.4)

Figure 3.4. Diagramme de transition pour « >= »

Ce diagramme fonctionne comme suit : Dans l'état de départ 0, on lit le prochain

caractère d'entrée. On suit l'arc « > » depuis 0 vers 6 si le caractère d'entrée est
« > ». Sinon, on n'a réussi à reconnaître ni « > » ni « > = ». En atteignant l'état 6,
on lit le prochain caractère d'entrée, l'arc étiqueté « = « entre l'état 6 et l'état 7
doit être suivi si le caractère d'entrée est « = ». Autrement, l'arc étiqueté autre
conduit à l'état 8. Le double cercle sur l'état 7 indique que c'est un état
d'acceptation, état dans lequel l'unité lexicale « >= » a été reconnue.
Noter que le caractère « > » et un autre caractère sont lus quand on progresse
dans la suite d'arcs depuis l'état initial jusqu'à l'état d'acceptation 8. Etant donné
que le caractère supplémentaire ne fait pas partie de l'opérateur de relation « >= »
on doit reculer le pointeur avant d'un caractère. On utilise une * pour signaler les
états dans lesquels ce recul dans l'entrée doit être fait.
En général, il peut y avoir plusieurs diagrammes de transition, chacun d'entre-eux
spécifiant un groupe d'unités lexicales. Si un échec se produit quand on parcoure un
diagramme de transition, alors on recule le pointeur avant là ou il était à l'état initial
de ce diagramme et on active le diagramme de transition suivant (le pointeur avant
est reculé à la position du pointeur début). Si un échec intervient dans tous les
diagrammes de transition, alors une erreur lexicale a été détectée et on appelle une
routine de récupération sur erreur.

Exemple 3.5.
La figure 3.5 représente un diagramme de transition pour l'unité lexicale oprel
(opérateur de relation).

Sami KHALFOUI – Moez HAMMAMI – ENSI 32

2006/2007
 Analyse lexicale

Figure 3.5. Diagramme de transition pour les opérateurs de relation

Remarque.
Comme les mots clés sont des suites de lettres, il y a des exceptions à la règle selon
laquelle une suite de lettres ou de chiffres débutant par une lettre est un
identificateur. Plutôt que de coder les exceptions dans un diagramme de transition,
une astuce consiste à traiter les mots clés comme des identificateurs spéciaux. Quand
on atteint l'état d'acceptation de la figure 3.6, on exécute un certain code pour
déterminer si le lexème amenant à cet état d'acceptation est un mot clé ou un
identificateur.

Figure 3.6. Diagramme de transition pour les identificateurs et les mots clés

Une technique simple pour séparer les mots clé des identificateurs consiste à diviser
la table de symboles en deux parties : une partie statique au début de la table de
symboles dans laquelle on place les mots clé (si, alors, sinon, etc.) avant qu'aucun
caractère n'ait été lu et une partie dynamique en bas pour les identificateurs.
L'instruction de retour qui suit l'état d'acceptation utilise UnilexId () et RangerId()
pour obtenir l'unité lexicale et la valeur d'attribut respectivement. RangerId() a accès
au tampon ou l'unité lexicale identificateur a été trouvée.
On examine la table des symboles et :
- Si on trouve le lexème avec l'indication mot clé, RangerId () rend 0.
- Si on trouve le lexème comme variable du programme, RangerId() rend un
pointeur vers l'entrée dans la table des symboles.
- Si on ne trouve pas le lexème dans la table des symboles, il y est placé en tant
que variable et un pointeur vers cette nouvelle entrée est retourné.
La procédure UnilexId(), de manière similaire, recherche le lexème dans la table des
symboles. Si le lexème est un mot clé, l'unité lexicale correspondante est retournée ;
autrement, l'unité lexicale « id » est retournée.

Exemple 3.6. Nombre sans signe

Soit la définition régulière suivante dénotant des nombres sans signe :

Sami KHALFOUI – Moez HAMMAMI – ENSI 33

2006/2007
 Analyse lexicale

nb  chiffre+ (.chiffre+)? (E(+/-)? Chiffre+)

? chiffres fractions ? exposant ?

Dans cette définition, fraction et exposant sont optionnels.

 Le lexème pour une unité lexicale possible doit être le plus long possible.
Quand l'entrée est 12.3E4 l'analyseur ne doit pas s'arrêter après avoir vu 12 ou 12.3.
Partant des états 25, 20 et 12 de la figure 3.7 on atteint les états d'acceptation après
avoir vu 12, 12.3 et 12.3E4, respectivement (on suppose que 12.3E4 n'est pas suivi
d'un chiffre).

Figure 3.7. Diagrammes de transition pour les nombres sans signe

Les diagrammes de transition avec les états de départ 25, 20 et 12 correspondent à

chiffres, chiffres fraction et chiffres fraction ? exposant respectivement, on
doit donc essayer les états de départ dans l'ordre inverse 12, 20, 25.
Une autre solution consiste à les rassembler en un seul diagramme (figure 3.8).

Figure 3.8. Diagramme de transition pour les nombres sans signe

RangerNb() entre le lexème dans la table des symboles et rend l'unité lexicale « nb »
avec ce pointeur comme valeur lexicale.

Sami KHALFOUI – Moez HAMMAMI – ENSI 34

2006/2007
 Analyse lexicale

Remarque.
On peut obtenir une suite de diagrammes de transitions pour toutes les unités
lexicales de l'exemple 3.3 si on réunit les diagrammes de transition étudiés. On doit
essayer les états de départ de plus petit numéro avant ceux de numéros plus élevés.
Le traitement de « bl » est différent : Rien n'est retrouvé quand l'état d'acceptation
est atteint ; on revient simplement à l'état de départ du premier diagramme de
transition pour rechercher un autre modèle. Voici un diagramme de transition qui
reconnaît
« bl » (figure3.9).

Figure 3.9. Diagramme de transition pour « bl »

Remarque.
Il est préférable de rechercher d'abord les unités lexicales qui apparaissent le plus
fréquemment avant celles qui apparaissent le moins fréquemment, car on atteint un
diagramme de transition qu'après l'échec des diagrammes précédents.
Comme des espaces peuvent apparaître fréquemment, placer le diagramme de
transitions des espaces près du début peut être une amélioration par rapport au
placement à la fin.

3.5. Un langage pour spécifier des analyseurs lexicaux (lex)

Les analyseurs lexicaux basés sur des tables de transitions sont les plus efficaces...une
fois la table de transition construite. Or, la construction de cette table est une
opération longue et délicate. Le langage lex fait cette construction automatiquement :
il prend en entrée un ensemble d'expressions régulières et produit en sortie le texte
source d'un programme C qui, une fois compilé, est l'analyseur lexical correspondant
au langage défini par les expressions régulières en question (voir figure 3.10).

Figure 3.10. Utilisation de lex

Sami KHALFOUI – Moez HAMMAMI – ENSI 35

2006/2007
 Analyse lexicale

En lisant cette section, souvenez-vous de ceci : lex écrit un fichier source C. Ce fichier
est fait de trois sortes d'ingrédients :
- des tables garnies de valeurs calculées à partir des expressions régulières
fournies,
- des morceaux de code C invariable, et notamment le « moteur » de l'automate,
c'est-à-dire la boucle qui répète inlassablement etat  transit (etat; caractere),
- des morceaux de code C, trouvés dans le fichier source lex et recopiés tels quels,
à l'endroit voulu, dans le fichier produit.
Un fichier source pour lex doit avoir un nom qui se termine par « .l ». Il est fait de
trois sections, délimitées par deux lignes réduites au symbole %% :
%{
Déclarations pour le compilateur C
%}
Définitions régulières
%%
Règles
%%
Fonctions C supplémentaires

La partie « déclarations pour le compilateur C » et les symboles %{ et %} qui l'encadrent

peuvent être omis. Quand elle est présente, cette partie se compose de déclarations
qui seront simplement recopiées au début du fichier produit. En plus d'autres choses,
on trouve souvent ici une directive #include qui produit l'inclusion du fichier « .h »
contenant les définitions des codes conventionnels des unités lexicales (INFEG, INF,
EGAL, etc.).
La troisième section « fonctions C supplémentaires » peut être absente également (le
symbole %% qui la sépare de la deuxième section peut alors être omis). Cette section
se compose de fonctions C qui seront simplement recopiées à la fin du fichier
produit.

3.6. Conception d'un générateur d'analyseurs lexicaux

Dans cette section, nous étudions la conception d'un outil logiciel qui construit
automatiquement un analyseur lexical à partir d'un programme dans le langage Lex.

Spécification du
langage source L Générateur automatique Analyseur
(définition régulière d'analyseurs lexicaux lexical de L
lex)

Nous supposons que nous disposons d'une spécification d'analyseur lexical de la

forme :

Un fragment à exécuter à chaque fois qu'on rencontre dans le texte d'entrée

m1 {action1} un lexème qui concorde avec l'expression régulière mi.

Sami KHALFOUI – Moez HAMMAMI – ENSI 36

2006/2007
 Analyse lexicale

m2 {action2}
…
mn {actionn}

Le but est de construire un reconnaisseur qui recherche des lexèmes dans le tampon
d'entrée. Si plus d'un modèle convient, le reconnaisseur doit choisir le lexème le plus
long. S'il y a au moins deux modèles qui reconnaissent le lexème le plus long, le
modèle listé en premier est choisi.
Un automate fini est un modèle naturel sur lequel on peut bâtir un analyseur lexical.
Le compilateur lex converti les modèles d’expressions régulières de la spécification
lex en une table de transition pour un automate fini. L'analyseur lexical lui-même
utilise un tampon d'entrée avec deux pointeurs (début, avant). Il consiste en un
simulateur d'AF qui utilise une table de transitions pour rechercher les modèles dans
le tampon d'entrée (voir figure 3.11).

Figure 3.11. Schéma du compilateur lex

3.6.1. Reconnaissance fondée sur les Automates finis non déterministes

On commence par construire une table de transition pour un AFN N pour le modèle
m1m2..mn. On construit un AFN pour chaque mi, on ajoute un nouvel état de
départ e0, et enfin on relie e0 aux états de départ de chaque N(mi) par des -
transitions.
 On doit reconnaître le préfixe le plus long de la chaîne d'entrée qui correspond à
un modèle.
Nous apportons donc les modifications suivantes à l'algorithme 2.5 (simulation d'un
AFN)
- Chaque fois qu'on ajoute un état d'acceptation à l'ensemble d'états courant, on
enregistre la position courante dans le texte d'entrée et le modèle mi
correspondant à cet état d'acceptation.
- Si l'ensemble d'états courant contient déjà un état d'acceptation, alors seul le
modèle qui apparaît le premier dans la spécification lex est noté.

Sami KHALFOUI – Moez HAMMAMI – ENSI 37

2006/2007
 Analyse lexicale

- On continue à effectuer des transitions jusqu'à atteindre la terminaison (un

ensemble d'états n'ayant pas de transition sortante sur le symbole d'entrée
courant.
 On recule le pointeur avant jusqu'à la position à laquelle a eu lieu la dernière
concordance
 - Le modèle correspondant identifie l'unité lexicale.
- Le lexème est la chaîne entre le pointeur début et avant.
Si aucun modèle ne marche  transfert du contrôle à une fonction de récupération
sur erreur.

Exemple 3.7.
Supposons qu'on a le programme lex suivant :
m1 a   /* Les actions sont
m2 abb   omises */
m3 a*b+  
Les trois unités lexicales sont reconnues par les automates de la figure 3.12

Figure 3.12. AFN reconnaissant trois modèles différents

Soit la chaîne d'entrée aaba

Sami KHALFOUI – Moez HAMMAMI – ENSI 38

2006/2007
 Analyse lexicale

Suite d'ensembles d'états traversés et de modèles reconnus au cours du traitement de

la chaîne d'entrée aaba.
Supposons que la chaîne d'entrée est la suivante : aab/ab/abbb
On continue le schéma précédant en revenant à l'état de départ de l'AFN avec le
quatrième caractère.

3.6.2. Reconnaissance fondée sur les Automates finis déterministes

Si on convertit l'AFN de la figure 3.12 en AFD, on obtient la table de transition

suivante (voir tableau 3.4):

Symbole d'entrée
Etat Modèle annoncé (à l'entrée de l'état)
a b
0137 247 8 aucun
247 7 58 a
8 - 8 a*b+
7 7 8 aucun
58 - 68 a*b+
68 - 8 abb
Tableau 3.4. Table de transition d'un AFD

Remarque.
La chaîne abb correspond aux deux modèles abb et a*b+, reconnus aux états 6 et 8 de
l'AFN.  l'état 68 dans l'AFD inclut donc deux états d'acceptation de l'AFN puisque

Sami KHALFOUI – Moez HAMMAMI – ENSI 39

2006/2007
 Analyse lexicale

abb apparaît avant a*b+ dans la spécification de l'AFN donc seul le modèle abb est
reconnu à l'état 68.

Sur la chaîne d'entrée aaba :

m1 m3
a b a néant
0137 247 7 8

Jeton 1: aab, lexème a*b+

Considérons le second exemple : aba

m1 m3
a b a
0137 247 58 néant

Cet état comprend l'état d'acceptation 8 du NFA donc

a*b+ est reconnu et le lexème est ab

Ensuite il reconnaît a :
m1
0137 a 247

Sami KHALFOUI – Moez HAMMAMI – ENSI 40

2006/2007
 Analyse syntaxique

Analyse syntaxique
Dans notre modèle de compilateur, l'analyseur syntaxique obtient une chaîne
d'unités lexicales de l'analyseur lexical, comme illustre à la figure 4.1, et vérifie que la
chaîne peut-être engendrée par la grammaire du langage source.
On suppose que l'analyseur syntaxique signale chaque erreur de syntaxe, il doit
également supporter les erreurs les plus communes de façon à pouvoir continuer le
traitement du texte restant.

Figure 4.1. Emplacement d'un analyseur syntaxique dans un modèle de compilateur

Les méthodes utilisées (par l'analyse syntaxique) communément sont soit

descendantes soit ascendantes. Comme leurs nom l'indique, les analyseurs
descendants construisent des arbres d'analyse de haut en bas, alors que les
analyseurs ascendants partent des feuilles et remontent vers le racine.
Dans les deux cas, l'entrée de l'analyseur est parcourue de la gauche vers la droite, un
symbole à la fois.
Les méthodes descendantes ou ascendantes les plus efficaces travaillent uniquement
sur des sous classes de grammaires hors contexte, mais certaines de ces sous classes
sont suffisamment expressives pour décrire la plupart des constructions syntaxiques
des langages de programmation.

4.1. Grammaires non contextuelles

Beaucoup de constructions de langages de programmation, ont une structure
récursive; ces constructions peuvent être définies par des grammaires non
contextuelles.

Exemple 4.1.
si S1 et S2 sont des instructions et E une expression
"si E alors S1 sinon S2" est une instruction (1)

Sami KHALFOUI – Moez HAMMAMI – ENSI 41

2006/2007
 Analyse syntaxique

Remarque.
Cette forme d'instruction ne peut être spécifiée en utilisant la notation des
expressions régulières.
En utilisant les variables syntaxiques inst pour dénoter la classe des instructions et
expr pour dénoter la classe des expressions, on peut exprimer (1) de façon lisible en
utilisant la production:
"instr si expr alors instr sinon instr" (2)

4.1.1. Définition d'une grammaire non contextuelle

Soit une grammaire G (VT, VN, S, P)

VT : ensemble des symboles terminaux de la grammaire (unités lexicales)
VN : ensemble des symboles non terminaux de la grammaire (variables syntaxiques
qui dénotent un ensemble de chaînes)
S : l’axiome est un non terminal particulier, tel que l'ensemble des chaînes qu'il
dénote est le langage défini par la grammaire.
P : ensemble de règles de production de la grammaire; spécifient la manière dont les
terminaux et les non terminaux peuvent être combinés pour former les chaînes.

Exemple 4.2.
La grammaire constituée des productions suivantes définit des expressions
arithmétiques simples:

expr  exp op expr Dans cette grammaire les symboles

expr  (expr) terminaux sont : id + - * / ( )
expr  – expr les symboles non terminaux sont expr
et op et l'axiome est expr
expr  id
op  +
en abrégé:
op  –
op  *
expr  exp op expr|(expr)|– expr|
op  / id
op  op  +| – | * | / | 

4.1.2. Définition d'une Dérivation

Nous disons que A   si A   est une production et  et  sont des chaînes
arbitraires de symboles grammaticaux.
si 1  2  …. n, on dit que 1 se dérive en n.

Sami KHALFOUI – Moez HAMMAMI – ENSI 42

2006/2007
 Analyse syntaxique

le symbole  signifie "se dérive en une étape"

*

pour dire "se dérive en zéro, une ou plusieurs étapes" on peut utiliser le symbole 
donc
*
   pour une chaîne quelconque  et
* *
si    et   , alors   

 signifie "se dérive en une ou plusieurs étapes"

soit une grammaire G et S son axiome; on peut utiliser la  pour définir
relation
L(G), le langage engendré par G. On dit qu'une chaîne de terminaux w appartient à

L(G) ssi S  w. La chaîne w est appelée phrase de G.
un langage qui peut être engendré par une grammaire est dit langage non
contextuel.
*
si S  , où  peut contenir certains non terminaux, on dit que  est une proto-
phrase de G.

Exemple 4.3.
Soit la grammaire G(VT,VN,S,P)
E  E+E|E*E|(E)|-E|id (3)
la chaîne –(id+id) est une phrase de la grammaire (3) car on a la
dérivation: E –E –(E) –(E+E)  –(id+E)  –(id+id) (4)
Les chaînes E, -E, -(E),…,-(id+id) sont toutes des proto-phrases de cette grammaire.
*
On écrit E  -(id+id) pour indiquer que E se dérive en –(id+id)
A chaque étape d'une dérivation, on doit faire deux choix :
 Il faut choisir le non terminal à remplacer
 Quelle alternative utiliser pour ce non terminal

Dérivation gauche : Seul le non terminal le plus à gauche est remplacé à chaque
étape. On écrit    on peut alors réécrire (4)
g

E  –E  –(E)  –(E+E)  –(id+E)  –(id+id) (4)

g g g g g

Chaque étape d'une dérivation gauche peut s'écrire:

A   ou  est formé uniquement de terminaux A   est la production
g

utilisée et  est une chaîne de symboles grammaticaux.

Sami KHALFOUI – Moez HAMMAMI – ENSI 43
2006/2007
 Analyse syntaxique

 se dérive en  par une dérivation gauche est notée   

g

si *
  on dit que  est une proto-phrase gauche de la grammaire considérée.
S g

Dérivation droite : le terminal la plus à droite est remplacé à chaque étape.

4.2. Arbres d’analyse et dérivations

Définition Arbre syntaxique: un arbre syntaxique illustre visuellement la manière
dont l'axiome d'une grammaire se dérive en une chaîne du langage. Si le non
terminal A est défini par la production A  XYZ, alors un arbre syntaxique peut
posséder un nœud intérieur étiqueté A et avoir trois fils étiquetés X,Y et Z, de gauche
à droite.

X Y Z

Formellement, étant donné une grammaire non contextuelle, un arbre syntaxique

est un arbre possédant les propriétés suivantes:
- La racine est étiquetée par l'axiome
- chaque feuille est étiquetée par une unité lexicale ou par 
- chaque nœud intérieur est étiqueté par un non terminal.
Si A est le non-terminal étiquetant un nœud intérieur et si les étiquettes des fils de ce
nœud sont, de gauche à droite, X1,X2,..,Xn, alors A X1X2…Xn est une production,
ici X1,X2, …,Xn représentant soit un non terminal, soit un terminal. Un cas
particulier A   qui signifie qu'un nœud étiqueté A a un seul fils étiqueté .

Exemple 4.4.
liste  liste +
chiffre liste  liste
– chiffre liste 
chiffre
chiffre  0|1|2|3|4|5|6|7|8|9

liste

liste chiffre

liste - chiffre
+

chiffre 5
2
Sami KHALFOUI – Moez HAMMAMI – ENSI 44
2006/2007
 Analyse syntaxique

Sami KHALFOUI – Moez HAMMAMI – ENSI 45

2006/2007
 Analyse syntaxique

Des feuilles d'un arbre syntaxique, lues de gauche à droite, constituent le mot des
feuilles de l'arbre, qui est la chaîne engendrée ou dérivée à partir du non terminal
situé à la racine de l'arbre syntaxique. (Dans l'exemple la chaîne engendrée est 9-
5+2).

4.2.1. Ambiguïté

Une grammaire peut avoir plus d'un arbre syntaxique qui engendre une chaîne
donnée d'unités lexicales. Une telle grammaire est dite ambiguë. Comme une telle
chaîne a habituellement plus d'une signification, on a besoin de travailler avec des
grammaires non ambiguës.

Exemple 4.5.
chaîne  chaîne + chaîne| chaîne - chaîne|0|1|2|3|4|5-6|7|8|9
La figure 4.2 montre qu'une expression comme 9-5+2 a plus d'un arbre syntaxique.
Les deux arbres pour 9-5+2 correspondent aux deux manières de parenthèser
l'expression (9-5)+2 et 9-(5+2). Le deuxième parenthèsage donne à l'expression la
valeur 2 plutôt que la valeur habituelle 6.

chaîne chaîne

chaîne chaîne chaîne chaîne

+ _

chaîne _ chaîne 2 9 chaîne chaîne

+

9 5 5 2
Figure 4.2. Deux arbres syntaxiques pour 9-5+2

Associativité des opérateurs

Par convention 9+5+2 est équivalent à (9+5)+2 et 9-5 est équivalent à (9-5)-2. On dit
que l'opérateur + est associatif à gauche car un opérande avec des signes + de chaque
coté est traité par l'opérateur qui est à sa gauche.
+,-,*,/ sont associatifs à gauche.
 L’exponentiation est associative à droite.
:= l'affectation est associative à droite.

4.2.2. Priorités des opérateurs

L’expression 9+5*2 a deux interprétations (9+5)*2 ou 9+(5*2)

On a besoin de connaître la priorité relative des opérateurs dès qu'il y'a plus d'un
type d'opérateurs en présence. On dira que * a une priorité supérieure à celle de + si *
agit sur ses opérandes avant +.
Dans l'arithmétique usuelle *, / ont une priorité supérieure à +,-

Sami KHALFOUI – Moez HAMMAMI – ENSI 46

2006/2007
 Analyse syntaxique

En conséquence 5 est traitée par * dans 9+5*2 et 9*5+2 ce qui est équivalent
respectivement à 9+(5*2) et (9*5)+2.

4.3. Analyse descendante (TOP-DOWN)

Dans cette section, nous introduisons les idées de base de l'analyse descendante qui
comprend plusieurs formes (voir figure 4.3).

analyse descendante

avec rebroussement sans rebroussement

(analyse descendante récursive) (Analyse prédictive)

récursive non récursive

(à la main) (génération automatique)

Figure 4.3. Arborescence des méthodes d'analyse descendantes

Nous définissons la classe des grammaires LL(1) à partir desquelles on peut

construire automatiquement des analyseurs prédictifs.

4.3.1. Analyse par descente récursive

L'analyse descendante peut-être considérée comme une tentative pour déterminer

une dérivation gauche associée à une chaîne d'entrée.
Elle peut-être aussi vue comme une tentative pour construire un arbre d'analyse de la
chaîne d'entrée, en partant de la racine et en créant les nœuds de l'arbre suivant un
ordre prédéfini.
Nous présentons ici une analyse qui peut impliquer des retours arrière (nécessité de
passages répétés sur la chaîne d'entrée.

Exemple 4.6.
Considérons la grammaire
S  cAd
A  ab|a
et la chaîne d'entrée w = cad.
On commence par construire initialement un arbre qui contient un seul nœud
étiqueté S. Un pointeur d'entrée repère c, le premier symbole de w, nous utilisons la
première production de S pour développer l'arbre et obtenir

Sami KHALFOUI – Moez HAMMAMI – ENSI 47

2006/2007
 Analyse syntaxique

Figure 4.4.a

La feuille la plus à gauche, étiquetée c, correspond au premier symbole de w. Nous

avançons maintenant le pointeur d'entrée sur a, second symbole de w, et nous
considérons la feuille suivante étiquetée A. Nous pouvons alors développer A en
utilisant la première alternative pour A et nous obtenons l'arbre suivant:

Figure 4.4.b

Nous avons alors une concordance avec le second symbole d'entrée; nous avançons
donc le pointeur à d (troisième symbole en entrée), et comparons d avec la feuille
suivante étiquetée b.
Comme b et d sont différents, nous signalons un échec et retournons à A pour voir
s'il n'existe pas une autre alternative de A, non encore essayé et qui serait susceptible
de produire une concordance.
En retournant à A, nous devons remettre le pointeur d'entrée en position 2, la
position qu'il avait quand nous sommes arrivés sur A la première fois.
Nous essayons maintenant la seconde alternative de A et obtenons l'arbre de la figure
suivante:

Figure 4.4.c

La feuille a correspond au second symbole de w et la feuille d au troisième symbole.

Comme nous avons produit un arbre d'analyse pour w, nous nous arrêtons et
annonçons le succès final de l'analyse.

Remarque.
Une grammaire récursive à gauche peut faire boucler un analyseur par descente
récursive même s'il possède un mécanisme de retour arrière.
En effet dans le cas de A  A|ab|a, en essayant de développer A, on peut
éventuellement se retrouver en train de développer A de nouveau, et cela sans avoir
consommé de symbole en entrée.

Sami KHALFOUI – Moez HAMMAMI – ENSI 48

2006/2007
 Analyse syntaxique

 Nous devons éliminer la récursivité à gauche.

(Notons que le terminal d'entrée ne change que quand un terminal de la partie
droite est accepté).

Suppression de la récursivité gauche

Définition.
Une grammaire est récursive à gauche si elle contient un non-terminal A tel qu'il

existe une dérivation A  A, où  est une chaîne quelconque.
Considérons tout d'abord le non terminal A dans les deux productions:
A  A|  où  et  sont des suites de terminaux et de non terminaux qui ne
commencent pas par A. Par exemple expr  expr + terme|terme A = expr,
=+terme et  =terme.
Une application répétée de cette production fabrique une suite de  à droite de A
comme la figure 3.a. Quand A est finalement remplacé par , on obtient un  et une
suite éventuellement vide de .

Figure 4.5.a

On peut obtenir le même effet, en réécrivant la production définissant A de la

manière suivante:
A  R
R  R|
Ici R est un nouveau terminal. La production R R est récursive à droite.

Figure 4.5.b

Sami KHALFOUI – Moez HAMMAMI – ENSI 49

2006/2007
 Analyse syntaxique

Exemple 4.7.
expr  expr + terme |terme
devient :
expr  terme R
R  + terme R | 
Quelque soit le nombre de A-productions, il est possible d'éliminer les récursivités à
gauche immédiates par la technique suivante:
Dans un premier temps, on groupe les A-productions comme suit:
A  A1| A2| …| Am|1|2|….|n
où aucune i ne commence par un A. Ensuite on remplace les A-productions par:
A  1A'|2A'|….| nA'
A'  1A'| 2A'| …| m A'| (on suppose que i  )

4.3.2. Analyse prédictive non récursive

On peut construire un analyseur prédictif non récursif en tenant à jour une pile. Le
problème clé de l'analyse prédictive est la détermination de la production à
appliquer pour développer un non terminal. L'analyseur non récursif de la figure 4.6
suivante recherche la production à appliquer dans une table d'analyse (qu'on va voir
la méthode de construction ultérieurement).

Figure 4.6. Modèle d'analyseur prédictif non récursif

Cet analyseur possède un tampon d'entrée, une pile, une table d'analyse et un flot de
sortie.
 Le tampon d'entrée contient la chaîne à analyser, suivie de $ (marqueur fin)
 La pile contient une séquence de symboles grammaticaux, avec $ marquant le
fond de pile. Initialement la pile contient l'axiome de la grammaire au dessus de $
 La table d'analyse est un tableau à deux dimensions M [A,a], où A est un non
terminal et a est un terminal ou le symbole $.
L’analyseur syntaxique est contrôlé par un programme qui a le comportement
suivant. Ce programme considère X, le symbole en sommet de pile et a, le symbole

Sami KHALFOUI – Moez HAMMAMI – ENSI 50

2006/2007
 Analyse syntaxique

d'entrée courant, ces deux symboles déterminent l'action de l'analyseur. Il y a trois

possibilités:
1. si X = a = $, l'analyseur s'arrête et annonce la réussite finale de l'analyse.
2. Si X = a  $ , l'analyseur enlève X de la pile et avance son pointeur d'entrée sur
le symbole suivant.
3. Si X est un non terminal, le programme consulte l'entrée M[X, a] de la table
d'analyse M. Cette entrée sera soit une X-production de la grammaire, soit une
erreur. Si par exemple, M[X, a] = {X UVW}, l'analyseur remplace X en
sommet de pile par WVU (avec U au sommet).(Nous supposerons que
l'analyseur se contente, pour tout résultat d'imprimer la production utilisée). si
M[X, a] = erreur, l'analyseur appelle une procédure de récupération sur
erreur. Le comportement de l'analyseur peut décrire en termes de ses
configurations qui décrivent le contenu de sa pile et le texte d'entrée restant.

Algorithme 4.1. Analyse prédictive non récursive

Donnée: une chaîne w et une table d'analyse M pour une grammaire G.
Résultat: Si w est dans L(G), une dérivation gauche de w, sinon une indication
d'erreur.
Méthode: Initialement, l'analyseur est dans une configuration dans laquelle il a $S
dans sa pile avec S, l'axiome de G au sommet et w$ dans son tampon d'entrée.
Le programme est le suivant:
Positionner le pointeur source ps sur le premier symbole de w$
Répéter
soit X le symbole en sommet de pile et a le symbole repéré par ps
si X est un terminal ou $ alors
si x = a alors
enlever X de la pile et avancer ps
sinon erreur()
sinon /* X est un non terminal */
si M[X,a] = X Y1Y2…Yk alors
début
enlever X de la pile
Mettre Yk,Yk-1,…,Y1 sur la pile, avec Y1 au sommet;
émettre en sortie la production X Y1Y2…Yk
fin
sinon
erreur()
jusqu'à X = $ /* la pile est vide*/

Exemple 4.8.
Considérons la grammaire suivante :
E TE'
E' +TE'|

Sami KHALFOUI – Moez HAMMAMI – ENSI 51

2006/2007
 Analyse syntaxique

T FT'
T' *FT'|
F (E)|id
Voici une table d'analyse prédictive (voir tableau 4.1) pour cette grammaire. (Jusque
là on n'a pas vu comment la construire)
Symbole d'entrée
id + * ( ) $
E E TE' E TE'
E' E' +TE' E'  E' 
T T FT' T FT'
T' T'  T' *FT' T'  T' 
F F id F (E)
Tableau 4.1. Table d’analyse

Les entrées vides représentent des erreurs

Les entrées non vides indiquent les productions qu'il faut utiliser pour développer le
non terminal en sommet de pile.
Sur la chaîne id+id*id, l'analyseur prédictif effectue la séquence d'actions de la figure
4.7. Dans la colonne symbole d'entrée, le pointeur d'entrée repère le symbole le plus à
gauche de la chaîne.
Pile Entrée Sortie
$E id+id*id$
$E'T id+id*id$ E TE'
$E'T'F id+id*id$ T FT'
$E'T'id id+id*id$ F id
$E'T' +id*id$
$E' +id*id$ T' 
$E'T+ +id*id$ E' +TE'
$E'T id*id$
$E'T'F id*id$ T FT'
$E'T'id id*id$ F id
$E'T' *id$
$E'T'F* *id$ T' *FT'
$E'T'F id$
$E'T'id id$ F id
$E'T' $
$E' $ T' 
$ $ E' 
Figure 4.7. Transitions effectuées par un analyseur prédictif sur la chaîne source id+id*id

On voit que les actions de l'analyseur décrivent une dérivation gauche de la chaîne
source, c'est à dire que les productions utilisées sont celles d'une dérivation gauche.

Sami KHALFOUI – Moez HAMMAMI – ENSI 52

2006/2007
 Analyse syntaxique

Premier et Suivant
Ces fonctions nous permettent, quand c'est possible, de remplir la table d'analyse
prédictive pour G.

Premier ().
Si  est une chaîne de symboles grammaticaux, Premier() désigne l'ensemble des
*

terminaux qui commencent les chaînes qui se dérivent de . si   , alors  est aussi
dans premier().
Pour calculer Premier(X), pour tout symbole de la grammaire X, appliquer les règles
suivantes jusqu'à ce qu'aucun terminal ni  ne puisse être ajouté aux ensembles
Premier
1. si X est un terminal, Premier (X) est {X}
2. si X  est une production, ajouter  à premier(X)
3. si X est un non terminal et X  Y1Y2…Yk une production
Premier (X) = Premier (Y1) sauf 
*
Premier (Y2) sauf  si Y1   ( est dans premier())
*
Premier(Y3) sauf  si Y1Y2  
…
Premier(Yk-1) sauf  si   (Premier(Y1)  Premier(Y2)  ..  Premier(Yk-2)
*
Premier(Yk) si Y1Y2..Yk-1  
(autrement si   Premier (Yj) pour tout j  1,2,..k ajouter  à Premier (X))

Maintenant, nous pouvons calculer Premier pour une chaîne X1X2..Xn de la façon
suivante: Ajouter à Premier (X1X2…Xn) tous les symboles de Premier (X1) différents
de . Si  est dans Premier(X1), ajouter également les symboles de premier(X2)
différents de . Si  est dans Premier (X1) et dans Premier(X2) ajouter également les
symboles de Premier(X3) différents de  etc. Finalement, si quel que soit i, premier
(Xi) contient , ajouter  à premier(X1,X2…Xn)

Exemple 4.9.
Soit la grammaire :
E TE'
E' +TE'|
T FT'
T' *FT'|
F (E)|id
Alors :
Premier (E) = Premier(T) = Premier(F) = {(,id}
Premier(E') = {+,}
Premier(T') = {*,}
Cela s'explique par

Sami KHALFOUI – Moez HAMMAMI – ENSI 53

2006/2007
 Analyse syntaxique

Premier(E) = Premier(T) sauf  [Premier(E') si 

Premier(T)] Premier(T) = Premier(F) sauf  [Premier(T') si
 Premier(F)] Premier(F) = Premier(( )  Premier(id)
={(,id}
donc Premier(T) = Premier(F) = {(,id} car   Premier(F)
et Premier(E) = Premier(T) = {(,id} car  
Premier(T)
Premier (E') = Premier(+){} = {+,}
Premier(T') = Premier(*){} = {*,}

Suivant (A).
Pour chaque non-terminal A, Suivant(A) définit l'ensemble des terminaux a qui
peuvent apparaître immédiatement à droite de A dans une proto-phrase, c'est à dire
*
l'ensemble des terminaux a tels qu'il existe une dérivation de la forme S  Aa où 
et  sont des chaînes de symboles grammaticaux.

Remarque.
Il a pu exister au cours de la dérivation, des symboles entre A et a, mais, dans ce cas
ils se sont dérivés en  et ont disparu.
Si A peut-être le symbole le plus à droite dans une proto-phrase, alors $ est dans
Suivant (A).
Pour calculer Suivant(A) pour tous les non terminaux A, appliquer les règles
suivantes jusqu'à ce que aucun terminal ne puisse être ajouté aux ensembles
SUIVANT.
1. Mettre $ dans Suivant(S), où S est l'axiome et $ est le marqueur droit
indiquant la fin du texte source.
2. S'il y a une production A B, le contenu de Premier(), excepté , est ajouté
à Suivant (B)
3. S'il existe une production A B ou une production A B telle que
*

Premier() contient  (  ), les éléments de SUIVANT(A) sont ajoutés à

SUIVANT(B).
Exemple 4.10.
Sur la même grammaire
E TE'
E' +TE'|
T FT'
T' *FT'|
F (E)|id

Suivant (E) = Suivant(E') = {),$}

Suivant(T) = Suivant(T') = {+,),$}
Suivant(F) = {+,*,),$}

Sami KHALFOUI – Moez HAMMAMI – ENSI 54

2006/2007
 Analyse syntaxique

Explication.
Suivant(E) = {$}  Premier( ))
(règle 1) (car on a F → (E) règle 2)
= {$,)}

Suivant(E') = Suivant(E) car la règle 3 s'applique sur E → TE'

= {$,)}

Suivant(T) = Premier(E') sauf   Suivant(E')

règle 2 sur E' →+TE' règle 3 appliquée sur E' → +TE'|ε
= {+} {$,)}
={+,$,)}

Suivant (T') = Suivant(T) règle 3 sur T→FT'

= {+,$, )}

Suivant(F) = Premier(T') sauf   suivant (T)

*
règle 2 appliquée à T →FT' règle 3 sur T→*FT' et T'  ε
={*}  {+,$,)}
={*,+,$,)}

Construction des tables d'un analyseur prédictif

L’idée est la suivante: soit A  une production et a dans Premier() alors,
l'analyseur développe A en  chaque fois que le symbole d'entrée courant est a. Une
*

complication se produit quand  =  ou   . Dans ce cas, nous devons égalemet

developper A en  si le symbole d'entrée courant est dans suivant(A) ou si le $
d'entrée a été atteint et si $ est dans Suivant de A.
Algorithme 4.2. Construction d'une table d'analyse prédictive
Donnée: une grammaire G
Résultat: une table d'analyse M pour G
Méthode:
1. Pour chaque production A  de la grammaire, procéder aux étapes 2 et 3.
2. Pour chaque terminal a dans Premier(), ajouter A à M[A,a].
3. Si  est dans Premier (), ajouter A à M[A,b]. pour chaque terminal b dans
suivant (A).
4. si  est dans Premier () et $ est dans suivant(A) ajouter A  à M[A, $].
5. Faire de chaque entrée non définie de L une erreur

Exemple 4.11.
Appliquons l'algorithme 4.2 à la grammaire
E TE'
E' +TE'|

Sami KHALFOUI – Moez HAMMAMI – ENSI 55

2006/2007
 Analyse syntaxique

T FT'
T' *FT'|
F (E)|id
 Puisque Premier(TE') = Premier(T) = {(,id}, la production E TE' implique que
les entrées M[E,(] et M[E,id] prennent toutes les deux la valeur E TE'
 La production E' +TE' implique que l'entrée M[E',+] prend la valeur E'  +TE'.
 La production E'   implique M[E',)] et M[E',$] prennent toutes les deux valeurs
E'  car suivant(E') = {),$}
Voici donc la table d'analyse prédictive pour la grammaire (voir tableau 4.2)
Symbole d'entrée
id + * ( ) $
E E TE' E TE'
E' E' +TE' E'  E' 
T T FT' T FT'
T' T'  T' *FT' T'  T' 
F F id F (E)
Tableau 4.2. Table d’analyse

4.3.3. Diagrammes de transition pour analyseurs prédictifs

Pour construire, à partir d'une grammaire, le diagramme de transition d'un

analyseur syntaxique prédictif, il faut d'abord éliminer les récursivités gauches de la
grammaire puis la factoriser à gauche. Ensuite, pour chaque non-terminal A il faut:
1. Créer un état initial et un état final (retour);
2. Pour chaque production A  X1X2...Xn, créer un chemin de l'état initial à l'état
final, dont les arcs sont étiquetés Xl, X2,..., Xn.
L'analyseur syntaxique prédictif travaille à partir des diagrammes de transition
comme suit. Il commence dans l'état initial avec l'axiome. Si, après un certain
nombre d'actions, il est dans l'état s avec un arc menant à l'état t étiqueté par le
terminal a, et si le prochain symbole en entrée est a, alors l'analyseur avance le
curseur d'entrée d'une position sur la droite et va dans l'état t. Inversement, si l'arc
est étiqueté par un non-terminal A, l'analyseur se positionne dans l'état de départ du
diagramme associé à A, sans bouger le curseur d'entrée. S'il atteint l'état final de A, il
va immédiatement dans l'état t, avec pour effet d'avoir « reconnu» A dans la chaîne
d'entrée pendant le temps où il transitait de l'état s à l'état t. Finalement, s'il y a un
arc de s à t étiqueté e, alors, depuis l'état s, l'analyseur va immédiatement dans l'état
t, sans avancer son curseur d'entrée.
Un programme d'analyse prédictive reposant sur un diagramme de transition essaie
de faire correspondre les transitions terminales du diagramme avec les symboles de
l'entrée et simule un appel récursif de procédure chaque fois qu'il doit suivre un arc
étiqueté par un non-terminal. On peut obtenir une implantation non récursive en
empilant l’état s chaque fois qu'il y a une transition sur un non-terminal issue de s, et

Sami KHALFOUI – Moez HAMMAMI – ENSI 56

2006/2007
 Analyse syntaxique

en dépilant chaque fois que l'état final d'un non-terminal est atteint. L'implantation
des diagrammes de transition sera détaillée plus loin.
L'approche décrite ci-dessus est correcte à la condition que le diagramme de
transition considéré ne comporte pas de non-déterminisme, c'est-à-dire s'il n'existe
pas d'état ayant des transitions différentes sur le même symbole. Si une ambiguïté se
produit, nous devons être capables de la résoudre d'une façon ad hoc, comme dans
l'exemple suivant. Si le non-déterminisme ne peut pas être éliminé, nous ne pouvons
pas construire d'analyseur syntaxique prédictif, mais, si nous pensons que c'est la
meilleure stratégie d'analyse possible, nous pouvons construire un analyseur par
descente récursive utilisant le rebroussement pour essayer systématiquement toutes
les possibilités.

Exemple 4.12.
Soit la grammaire :
E TE'
E' +TE'|
T FT'
T' *FT'|
F (E)|id

La figure 4.8 contient une collection de diagrammes de transition pour cette

grammaire. Les seules ambiguïtés se produisent sur les transitions sur la chaîne vide.
Si nous interprétons les arcs sortants de l'état initial pour E' comme signifiant de
suivre la transition sur + chaque fois que c'est le prochain symbole en entrée, sinon
de suivre la transition sur f, et si nous faisons une supposition analogue sur T', alors
l'ambiguïté disparaît et nous pouvons écrire un programme d'analyse prédictif pour
cette grammaire.

Figure 4.8. Diagrammes de transition

On peut simplifier les diagrammes de transition en substituant les diagrammes les

uns aux autres. La figure 4.9(b) montre un diagramme de transition équivalent pour
E'. Nous pouvons alors substituer le diagramme de la figure 4.9(b) pour la transition
sur E' dans le diagramme pour E de la figure 4.8, ce qui produit le diagramme de la

Sami KHALFOUI – Moez HAMMAMI – ENSI 57

2006/2007
 Analyse syntaxique

figure 4.9(c). Nous observons alors que le premier et le troisième nœuds de la figure
4.9(c) sont équivalents et nous les fusionnons. Le résultat obtenu à la figure 4.9( d)
est illustré à nouveau comme premier diagramme de la figure 4.10. Les mêmes
techniques s'appliquent aux diagrammes pour T et T'. L'ensemble complet des
diagrammes résultants est montré à la figure 4.10. Une implantation en C de cet
analyseur syntaxique prédictif s'exécute de 20 à 25% plus vite que l'implantation en C
de la figure 4.8.

Figure 4.9. Digrammes de transition simplifiés

Figure 4.10. Digrammes de transition simplifiés des expressions arithmétiques

4.3.4.Grammaires LL(1)

Pour certaines grammaires, la table d'analyse peut avoir des entrées qui sont définies
de façon multiple. Par exemple, si G est récursive à gauche ou ambiguë, la table
d'analyse aura alors au moins une de ses entrées défini de façon multiple.

Sami KHALFOUI – Moez HAMMAMI – ENSI 58

2006/2007
 Analyse syntaxique

Exemple 4..13.
Soit la grammaire G
S  iEtSS'|a
S'  eS|
Eb

Voici la table d'analyse pour cette grammaire.

Symbole d'entrée
a b e i t $
S S a S iEtSS'
S' S'   S'
S'  eS
E Eb
 L'entrée M[S',e] contient à la fois S'  eS et S'  , car Suivant(S') = {e,$} (donc
la règle 3, si  est dans Premier(), ajouter A  à M[A,b] pour chaque terminal b
dans Suivant((A))
 D'autre part, premier() = {e} donc mettre S'  eS dans M[S',e]
 La grammaire est ambiguë (choix de la production à utiliser quand on voit e
(sinon). Nous pouvons résoudre cette ambiguïté en choisissant S' eS
Une grammaire dont la table d'analyse n'a aucune entrée définie de façon multiple
est appelée LL(1). Le premier "L" de LL(1) signifie "Parcours de l'entrée de la gauche
vers la droite" (left to right scanning of the input), le second "L" signifie "Dérivation
gauche" (Leftmost Dérivation) et le "1" indique qu'on utilise un seul symbole d'entrée
de prévision à chaque étape nécessitant la prise d'une décision d'action d'analyse.
Les grammaire LL(1) ont un certain nombre de propriétés distinctives.
 Aucune grammaire ambiguë ou récursive à gauche ne peut être LL(1).
 Une grammaire est LL(1) si et seulement si, chaque fois que A  | sont deux
productions distinctes de G, les conditions suivantes s'appliquent:
1. Pour aucun terminal a,  et  ne se dérivent toutes les deux en des
chaînes commençant par a.
2. Une des chaînes au plus  et  peut se dériver en la chaîne vide.
*

3. Si   ,  ne se dérive pas en une chaîne commençant par un terminal

de Suivant(A). Cela causerait une entrée multiple (voir exemple
précédent) car l'un des premiers de  serait égale à un suivant de A.
On peut alors vérifier que la grammaire
E TE'
E' +TE'|
T FT'
T' *FT'|

Sami KHALFOUI – Moez HAMMAMI – ENSI 59

2006/2007
 Analyse syntaxique

F (E)|id est LL(1)

Les grammaires
S  iEtS|iEtSeS|a (1) S  iEtSS'|a (2)
E b S'  eS| 
Eb

ne sont pas LL(1)

La grammaire (1) n'est pas LL(1) à cause de la règle (1)
La grammaire (2) n'est pas LL(1) à cause des productions S'  eS|  qui est sous la
*
forme A  |, avec    mais =eS se dérive en une chaîne commençant par e 
Suivant S' = {e,$}.

Remarque. Qu'est ce qu'on doit faire lorsque la table d'analyse a des entrées à
valeurs multiples?
Réponse: Transformer la grammaire afin d'éliminer les récursivités à gauche puis
factoriser à gauche, Mais c'est pas encore sur d'obtenir une table d'analyse dans
entrées multiples.
La grammaire
S iEtSS'|a
S' eS|
E b
est un exemple de grammaires n'ayant pas de transformations la rendant LL(1). On
peut cependant l'analyser en supposant que M[S',e] = {S'eS}.
De manière générale, il n'existe pas de règles universelles par lesquelles une entrée à
valeur multiple peut être transformée en une entrée à valeur simple sans affecter le
langage reconnu par l'analyseur.

4.4. Analyse ascendante (décalage/réduction)

Dans cette section, nous introduisons un modèle général d'analyse syntaxique
ascendante, connu sous le nom d'analyse par décalage-réduction. On va consacrer
la section suivante à une forme d'analyse par décalage-réduction facile à
implémenter, appelée analyse par précédence d'opérateurs. Une méthode
beaucoup plus générale, appelée analyse LR, est présentée à la section qui suit. Elle est
utilisée dans un grand nombre de constructeurs automatiques d'analyseurs
syntaxiques.
L'analyse par décalage-réduction a pour but de construire un arbre d'analyse pour
une chaîne source en commençant par les feuilles (le bas) et en remontant vers la
racine (le haut). Ce processus peut-être considéré comme la "réduction" d'une chaîne
w vers l'axiome de la grammaire. A chaque étape de réduction, une sous-chaîne
particulière correspondant à la partie droite d'une production est remplacée par le

Sami KHALFOUI – Moez HAMMAMI – ENSI 60

2006/2007
 Analyse syntaxique

symbole de la partie gauche de cette production. Si la sous chaîne est choisie

correctement à chaque étape, une dérivation droite est ainsi élaborée en sens inverse.

Exemple 4.14.
Soit la grammaire:
S  aABe
A Abc|b (1)
B d
La phrase abbcde peut être réduite vers S par les étapes suivantes:
abbcde
aAbcde production utilisée A b
aAde production utilisée A Abc
aABe production utilisée B d
S production utilisée S  aABe
On parcourt abbcde à la recherche d'une sous-chaîne qui corresponde à la partie
droite d'une production. Les sous-chaînes b et d conviennent. choisissons la sous
chaîne b la plus à gauche (c'est pas une règle) et remplaçons la par A.
Maintenant les sous-chaînes Abc,b et d correspondent aux parties droites de
production. On va choisir la production A  Abc malgré que b est la sous chaîne la
plus à gauche qui corresponde à une partie droite de production (on va voir
ultérieurement les règles de choix entre les chaînes). Nous obtenons aAde.
Remplaçons d par d par B (Bd) nous obtenons aABe.
Nous pouvons maintenant remplacer cette chaîne tout toute entière par S.
Nous avons donc par une séquence de quatre réductions été capables de réduire
abbcde vers S. Ces réductions, élaborent en sens inverse la dérivation droite suivante:
S  aABe  aAde  aAbcde  abbcde
d d d d

4.4.1. Définition d'un Manche

De façon informelle, un "manche" de chaîne est une sous chaîne qui correspond à la
partie droite d'une production et dont la réduction vers le non terminal de la partie
gauche de cette production représente une étape le long de la dérivation droite
inverse.
Formellement: un manche de proto-phrase droite  est:
- Une production A
- Une position dans  où  peut être trouvée et remplacée par A pour produire la
proto-phrase droite précédente dans une dérivation droite de .
*
C'est à dire que si S  A , A dans la position suivant () est une manche
d d

de , la chaîne  à droite du manche, ne contient que des terminaux.

Sami KHALFOUI – Moez HAMMAMI – ENSI 61

2006/2007
 Analyse syntaxique

Remarque. Dans l'exemple 1. Si nous remplaçons b par A dans la seconde chaîne

aAbcde nous obtenons la chaîne aAAcde qui par la suite ne peut être réduite vers S
donc Ab dans la position 3 n'est pas un manche.
Dans l'exemple 1, abbcde est une proto-phrase droite dont le manche est A b en
position 2.

De même aAbcde est une proto-phrase droite dont le manche est AAbc en
position2.

Exemple 4.15.
Soit G:
et la dérivation droite:
(1) E E+E
(2) E E *E (2) E  E+E
d
(3) E (E)
 E+E*E
(4) E id d

 E+E*id3
d

 E+id2*id3
d

 id1+id2*id3
d

On a indicé les id pour faciliter la discussion; nous avons aussi souligné un manche
de chaque proto-phrase droite. Par exemple id1 est un manche de la proto-phrase
droite id1+id2*id3 car id est la partie droite de la production E  id et le
remplacement de id1 par E produit la proto-phrase droite précédente E +id2*id3.

Remarque. La chaîne apparaissant à droite d'un manche contient uniquement des

symboles terminaux.
Puisque il existe une autre dérivation droite pour la même chaîne.

E  E*E
d

 E*id3
d

 E+E * id3
d

E + id2*id3
d

 id1+id2*id3 La grammaire 2 est ambiguë

d

Considérons la proto-phrase droite E+E*id3. Dans cette dernière dérivation, E+E

est un manche de E+E*id3 alors que, selon la première dérivation id3 est un
manche de cette même proto-phrase droite.

Sami KHALFOUI – Moez HAMMAMI – ENSI 62

2006/2007
 Analyse syntaxique

4.4.2.Elagage du manche

La réduction d'un manche par la partie gauche de la production correspondante est

« l'élagage du manche ».
Une dérivation droite inverse peut être obtenue par « élagage du manche ».
Plus précisément, nous commençons avec une chaîne de terminaux  que nous
désirons analyser. Si  est une phrase de la grammaire considérée alors  = n où n
est la nième proto-phrase droite d'une dérivation droite encore inconnue.

S = 0  1  2  ..…  n-1  n = 
d d d d d

Pour reconstruire cette dérivation en ordre inverse, on repère le manche n dans n et

on remplace n par la partie gauche d'une production Ann pour obtenir la (n-1)ème
proto-phrase droite n-1. Nous poursuivons le même travail pour obtenir n-2 ensuite
après un nombre d'étapes on obtient une proto-phrase droite formée uniquement
par
S. Nous arrêtons et annonçons la réussite finale de l'analyse.
L'inverse de la séquence des productions utilisées dans les réductions est une
dérivation droite de la chaîne d'entrée.

Exemple 4.16.
E E+E
E E*E et la chaîne d'entrée: id1+id2*id3

(2) E (E)
E id
Le tableau 4.3 présente une séquence de réductions qui réduit id1+id2*id3 vers
l'axiome E.
Remarque. On observe que la séquence de proto-phrases droites est exactement
l'inverse de la première dérivation droite de la grammaire 2.
Proto-phrase Droite Manche Production de réduction
id1+id2*id3 id1 Eid
E+id2*id3 id2 E id
E+E*id3 id3 Eid
E+E*E E*E EE*E
E+E E+E EE+E
E
Tableau 4.3. Réductions effectuées par un analyseur par décalage-réduction

4.4.3.Implantation à l'aide d'une pile de l'analyse par décalage-réduction

Une bonne façon est d'utiliser une pile pour conserver les symboles grammaticaux et
un Tampon d'entrée pour contenir la chaîne  à analyser.
Nous utilisons le symbole $ pour marquer à la fois le fond de pile et l'extrémité droite
du tampon d'entrée.
Sami KHALFOUI – Moez HAMMAMI – ENSI 63
2006/2007
 Analyse syntaxique

Initialement la pile est vide et la chaîne  est dans le tampon d'entrée.

PILE ENTREE
$ $
L'analyseur opère en décalant zéro, un ou plusieurs symboles d'entrée du tampon
vers la pile jusqu'à ce qu'un manche  se trouve en sommet de pile.
L'analyseur réduit alors  vers la partie gauche de la production appropriée.
L'analyseur recommence ce cycle jusqu'à ce qu'il détecte une erreur ou jusqu'à ce que
la pile contienne l'axiome et que le tampon d'entrée soit vide
PILE ENTREE
$S $
S'il atteint cette configuration, l'analyseur s'arrête et annonce la réussite finale de
l'analyse.

Exemple 4.17.
La table suivante montre les actions que doit effectuer un analyseur par décalage-
réduction sur la chaîne id+id2*id3 sur la grammaire: E E+E |E*E| (E) | id en
utilisant la première dérivation: E  E+E  E+E*E  E+E*id3E+id2*id3  id1 +
d d d d
id2 * id3
Pile Entrée Action
(1) $ id1+id2*id3 $ décaler
(2) $id1 +id2*id3 $ réduire par E id
(3) $E +id2*id3 $ décaler
(4) $E+ *id3 $ décaler
(5) $E+id2 *id3 $ réduire par Eid
(6) $E+E id3 $ décaler
(7) $E+E* $ décaler
(8) $E+E*id3 $ réduire par E id
(9) $E+E*E $ réduire par E E*E
(10) $ E+E $ réduire par E E+E
(11) $E $ accepter

Remarque. Du fait que la grammaire permet deux dérivations droites pour cette
entrée. Il existe une autre séquence d'actions qu'un analyseur par décalage-réduction
pourrait effectuer

Préfixes viables. Les préfixes d'une proto-phrase droite qui peuvent apparaître sur la
pile d'un analyseur par décalage réduction sont appelés préfixes viables.

4.4.4.Analyseurs LR

Cette section présente une technique efficace d'analyse syntaxique ascendante qui
peut être utilisée pour analyser une large classe de grammaires non contextuelles.
Cette technique est appelée analyse LR(K); "L" signifie parcours de l'entrée de gauche

Sami KHALFOUI – Moez HAMMAMI – ENSI 64

2006/2007
 Analyse syntaxique

vers la droite" (left to right scanning of the input), "R" signifie "en construisant une
dérivation droite inverse) et K indique le nombre de symboles de prévision utilisés
pour prendre les décision s d'analyse. Quand (K) est omis, K est supposé être égal à
un.
Après avoir présenté le fonctionnement d'un analyseur LR, nous présenterons trois
techniques pour construire les tables d'analyse LR pour une grammaire.
- La première méthode appelée "simple LR" (SLR en abrégé), est la plus facile à
implémenter, mais la moins puissante des trois. Pour certaines grammaires, la
production des tables d'analyse peut échouer alors qu'elle réussirait avec
d'autres méthodes.
- La seconde méthode, appelée LR canonique, est la plus puissante, mais elle est
la plus coûteuse.
- la troisième méthode appelée "LookAheadLR" (LALR en abrégé) ou LR à
prévision, a une puissance et un coût intermédiaires entre les deux autres.

Algorithme d'analyse LR

Figure 4.11. Modèle d'un analyseur LR

La figure 4.11 montre qu'un modèle d'analyseur LR consiste en : un tampon d'entrée,

un flot de sortie, une pile, un programme pilote et des tables d'analyse subdivisées en
deux parties (Action et Successeur).
Le programme moteur est le même pour tous les analyseurs LR; seules les tables
d'analyse changent d'un analyseur à l'autre. Le programme d'analyse lit les unités
lexicales l'une après l'autre dans le tampon d'entrée, il utilise une pile pour y ranger
les chaînes de la forme S0X1S1X2S2…XmSm, où Sm est au sommet. chaque Xi est un
symbole de la grammaire et chaque Si est un symbole appelé état. La combinaison du
numéro de l'état en sommet de pile et du symbole d'entrée courant est utilisée pour
indicer les tables et déterminer l'action d'analyse "décaler ou réduire" à effectuer.
Les tables d'analyse contiennent deux parties, une fonction d'actions d'analyse;
Action et une fonction de transfert; Successeur.
Le programme dirigeant l'analyseur LR se comporte de la façon suivante:
- Il détermine Sm, l'état en sommet de la pile, et ai, le symbole terminal d'entrée
courant.

Sami KHALFOUI – Moez HAMMAMI – ENSI 65

2006/2007
 Analyse syntaxique

- Il consulte Action [Sm,ai] ( l'entrée de la table des actions pour l'état Sm et le

terminal ai) qui peut avoir l'une des quatre valeurs:
1. décaler S, où S est un état.
2. réduire par une production de la grammaire A 
3. accepter et
4. erreur.
- La fonction successeur prend comme argument un état et un symbole non
terminal et retourne un état.
Une configuration d'un analyseur LR est un couple dont le premier composant est
le contenu de la pile et le second est la chaîne d'entrée restant à analyser.
(S0X1S1 X2 S2.................XmSm, ai ai+1… an $)
Cette configuration représente la proto-phrase
droite: X1 X2…Xm ai ai+1…an
L'action suivante de l'analyseur est déterminée par la lecture de ai , le symbole
d'entrée courant, Sm, l'état en sommet de pile, et la consultation de l'entrée
Action[Sm,ai] de la table des actions d'analyse.
Les configurations résultantes, après chacun des quatres types d'actions sont les
suivantes:
1. si Action [Sm,ai] = décaler S, l'analyseur exécute une action décaler,
atteignant la configuration: (S0X1S1X2S2….XmSm ai S, ai+1…an$) Ici
l'analyseur a à la fois epilé le symbole d'entrée courant ai et le prochain état
S, qui est donné par Action[Sm,ai], ai+1 devient le symbole d'entée
courant.
2. si Action [Sm, ai] = réduire par A  , alors l'analyseur exécute une action
réduire, atteignant la configuration:
(S0X1S1X2S2….Xm-rSm-r A S, ai ai+1…an$)
où S = Successeur[Sm-r,A], r = la longeur de , partie droite de la
production..
Ici l'analyseur commence par dépiler 2r symboles ( r symboles d'états et r
symboles grammaticaux), exposant ainsi l'état Sm-r au sommet. L'analyseur
empile alors à la fois A, partie gauche de la production et S, l'entrée pour
successeur [Sm-r,A].
Nous supposerons que la sortie est formée de la liste des productions par
lesquelles on réduit.
3. si Action[Sm, ai] = accepter, l'analyse est terminée.
4. si Action [Sm, ai] = erreur, l'analyseur a découvert une erreur et appelle
une routine de récupération sur erreur.

Sami KHALFOUI – Moez HAMMAMI – ENSI 66

2006/2007
 Analyse syntaxique

Algorithme 4.3. Analyse LR

Donnée : Une chaîne d'entrée w et des tables d'analyse LR (les fonctions
Action et successeur) pour une grammaire G.
Résultat : Si w est dans L(G), une analyse ascendante de w, sinon une indication
d'erreur.
Méthode : Initialement, l'analyseur a S0 en pile, où S0 est l'état initial et w$ dans
son tampon d'entrée.

Initialiser le pointeur ps sur le premier symbole de w$

répéter indéfiniment début
soit S l'état en sommet de pile et
a le symbole pointé par ps;
si Action [s,a] = décaler S' alors début
empiler a puis S'
avancer ps sur le prochain symbole d'entrée
fin
sinon si Action[s,a] = réduire par A  alors début
dépiler 2*|| symboles;
soit S' le nouvel état sommet de pile;
empiler A puis successeur [S',A];
emettre en sortie une identification de production A 
fin
sinon si Action [S,a] = accepter alors
retourner
sinon Erreur ()
Fin

Exemple 4.18.
La table 4.4 présente les fonctions Action et Successeur des tables d'analyse LR
pour la grammaire des expressions arithmétiques restreintes aux opérateurs
binaires + et *.
(1) E E+T
(2) E T
(3) T T * F (5)
(4) T F
(5) F  (E)
(6) F id
Le codage des actions est :
1. di signifie décaler et empiler l'état i
2. rj signifie réduire par la production (j)
3. acc signifie accepter et
4. une case vide signifie une erreur

Sami KHALFOUI – Moez HAMMAMI – ENSI 67

2006/2007
 Analyse syntaxique

Action Successeur
id + * ( ) $ E T F
0 d5 d4 1 2 3
1 d6 Acc
2 r2 d7 r2 r2
3 r4 r4 r4 r4
4 d5 d4 8 2 3
5 r6 r6 r6 r6
6 d5 d4 9 3
7 d5 d4 10
8 d6 d11
9 r1 d7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
Tableau 4.4. Table d'analyse pour la grammaire des expressions

Notons que l'état atteint par transition sur le symbole a depuis l'état s est identifié
dans le champs Action[S,a] en même temps que l'action décaler, et que l'état atteint
par transition sur le non terminal A depuis l'état S se trouve en successeur [S,A].
Sur le texte d'entrée id*id+id, la séquence des contenus de la pile et du tampon
d'entrée est présenté à la figure 4.12:
PILE ENTREE ACTION
(1) 0 id * id + id $ décaler d5
(2) 0 id 5 * id + id $ réduire par F  id (r6)
(3) 0 F 3 * id + id $ réduire par T F (r4)
(4) 0 T 2 * id + id $ décaler 7
(5) 0 T 2 * 7 id + id $ décaler 5
(6) 0 T 2 * 7 id 5 + id $ réduire par F  id (r6)
(7) 0 T 2 * 7 F 10 + id $ réduire par F  id
(8) 0 T 2 + id $ réduire par E  T
(9) 0 E 1 + id $ décaler 6
(10) 0 E 1 + 6 id $ décaler 5
(11) 0 E 1 + 6 id 5 $ réduire par F  id (r6)
(12) 0 E 1 + 6 F 3 $ réduire par T  F (r4)
(13) 0 E 1 + 6 T 9 $ réduire par E  E+T
(14) 0 E 1 $ accepter

Figure 4.12. Transitions d’un analyseur LR sur id*id+id

Sami KHALFOUI – Moez HAMMAMI – ENSI 68

2006/2007
 Analyse syntaxique

A la ligne (1) l'analyseur LR est dans l'état 0 avec id comme premier symbole en
entrée. L'entrée ligne 0 colonne id de la table Action de la figure 4 est d5 qui signifie
décaler et empiler l'état 5. C'est ce qui a été fait à la ligne (2).
A ce moment, * devient le symbole d'entrée courant et l'action dans l'état 5 sur
l'entrée * est réduire par F  id. Deux symboles sont dépilés, (un symbole d'état et
un symbole de la grammaire). L’état 0 est donc au sommet de la pile. Comme la
valeur du champ successeur pour l'état 0 sur F est 3, F et 3 sont empilés.

Grammaires LR
Une grammaire pour laquelle nous pouvons construire des tables d'analyse est
appelée grammaire LR.
Intuitivement, pour qu'une grammaire soit LR, il suffit qu'un analyseur par décalage-
réduction gauche-droite soit capable de reconnaître les manches quand ils
apparaissent en sommet de pile.
Il existe une différence significative entre les grammaires LL et LR. Pour qu'une
grammaire soit LR(k), on doit être capable de reconnaître l'occurrence de la partie
droite d'une production en ayant vu tout ce qui est dérivé de cette partie droite et
une prévision de k symboles en entrée. Cette condition est beaucoup moins
contraignante que pour les grammaires LL(k), pour lesquelles on doit être capable de
reconnaître l'usage d'une production à la vue des k premiers symboles de dérivés de
sa partie droite.

Remarques.
1. Le symbole d'état en sommet de pile contient toutes les informations dont
l'analyseur LR a besoin pour savoir quand un manche apparaît au sommet.
2. S'il est possible de reconnaître un manche en connaissant uniquement les
symboles grammaticaux en pile, il existe un automate à états fini qui peut, en
lisant les symboles grammaticaux de la pile depuis le fond vers le sommet,
déterminer quel manche, s'il y'en a, est en sommet de pile. Les Fonctions
Action et Successeur des tables d'analyse LR représentent essentiellement la
fonction de transition d'un automate fini.
3. L'automate fini n'a cependant pas besoin de lire la pile à chaque transition. Le
symbole d'état stocké en sommet de pile est l'état dans lequel l'automate fini
reconnaissant les manches serait s'il avait lu depuis le fond vers le sommet ,
les symboles grammaticaux de la pile . L'analyseur LR peut donc déterminer à
partie de l'état en sommet de pile, toutes les informations de la pile qu'il a
besoin de connaître.

4.4.5. Construction des tables d'analyse SLR à partir d'une grammaire

Nous donnerons trois méthodes qui diffèrent par leur puissance et leur facilité
d'implémentation. La première appelée "Simple LR" ou SLR en abrégé, est la moins
puissante des trois en termes du nombre de grammaires pour lesquelles elle réussit
mais elle est la plus simple à implémenter.

Sami KHALFOUI – Moez HAMMAMI – ENSI 69

2006/2007
 Analyse syntaxique

Des tables d'analyse Construites par cette méthode sont appelées Tables SLR et
l'analyseur est appelé analyseur SLR. Une grammaire pour laquelle il est possible de
construire un analyseur SLR est appelée grammaire SLR.

Définition. Un item LR(0) (item en abrégé) d'une grammaire G est une production
de G avec un point repérant une position de sa partie droite.

Exemple 4..19.
A  XYZ 
A  XYZ
A  XYZ
A  XYZ
A  XYZ

La production A   fournit uniquement l'item A  

Intuitivement, un item indique la « quantité » de partie droite qui a été reconnue, à
un moment donné, au cours du processus d'analyse.

Exemple 4.20.
A  XYZ indique qu'on espère avoir en entrée une chaîne dérivable depuis XYZ
A  XYZ indique que nous venons de voir en entrée une chaîne dérivée de X et que
nous espérons maintenant voir une chaîne dérivée de YZ.

Exemple 4.21.
(1) E  E+T  E  E+T, E  E+T, E  E+T, E  E+T (manche reconnu)
(2) E  T  E  T , E  T (manche reconnu)
(3) T T * F  T T * F, T T * F, T T * F, T T * F (manche reconnu)
(4)T  F  T  F , T  F (manche reconnu)
(5) F  (E)  F   (E) , F  (E) , F  (E) , F  (E)  (manche reconnu)
(6)F  id  F   id , F  id (manche reconnu)

L'idée centrale de la méthode SLR est de construire, tout d'abord, à partir de la

grammaire, un automate fini déterministe pour reconnaître les préfixes viables.
- Les items sont regroupés en ensembles qui constituent les états de l'analyseur
SLR
- Les items peuvent être vus comme les états d'un NFA reconnaissant les
préfixes viables, et le "regroupement" est exactement la construction des sous
ensembles présentée lors de la conversion NFA  DFA.
- une collection d'ensembles d'items LR(0), que nous appellerons collection
LR(0) canonique fournit la base de la construction des analyseurs SLR.
- Pour construire la collection LR(0) canonique pour une grammaire, nous
définissons une grammaire augmentée et deux fonctions Fermeture et
Transition.

Sami KHALFOUI – Moez HAMMAMI – ENSI 70

2006/2007
 Analyse syntaxique

Définition: Si G est une grammaire d'axiome S, alors G', la grammaire augmentée de

G, est G avec un nouvel axiome S' et une nouvelle production S' S.
But: indiquer à l'analyseur quand il doit arrêter l'analyse et annoncer que la chaîne
d'entrée a été acceptée.
L'opération fermeture.
Si I est un ensemble d'items pour une grammaire G, Fermeture de I est l'ensemble
d'items construit à partir de I par les deux règles:
1. Initialement, placer chaque item de I dans Fermeture (I)
2. Si A  B est dans fermeture (I), et B   est une production, ajouter l'item
B à Fermeture (I), s'il ne s'y trouve pas déjà. Nous appliquons cette règle
jusqu'à ce qu'aucun nouvel item ne puisse plus être ajouté à Fermeture de I.
Intuitivement, si A  B est dans Fermeture (I) cela indique que à un certain
point du processus d'analyse, nous pourrions voir se présenter dans l'entrée, une
sous-chaîne dérivable depuis B comme entrée. Si B   est une production, nous
supposons que nous pourrions également voir, à ce moment là une chaîne dérivable
depuis .
Autrement : soit A  B avec B un non terminal, espérer avoir une chaîne
dérivable depuis B c'est espérer avoir toute chaîne dérivable à partir de toute partie
droite B  .

Exemple 4.22.
Considérons la grammaire augmentée des expressions:
E'  E
E  E+T |T
T  T*F|F (5)
F  (E) |id
Si I est l'ensemble formé de l'unique item {[E'  E]}, alors Fermeture (I) contient les
items:

 E+T

E' → 
 T*F
T  (E)

F
 id
on a donc
E'  E ici E'  E est placé dans
E Fermeture (I) par la règle (1).
E+T E Comme il y'a un E
 T immédiatement à droite d'un
T  T*F

Sami KHALFOUI – Moez HAMMAMI – ENSI 71

2006/2007
 Analyse syntaxique

T  F point, par la règle (2) nous

F ajoutons les E-productions avec
(E) F  des points aux extrémités gauches.
 id C'est –à dire EE+T et E  T,
nous avons maintenant un T
immédiatement à droite d'un
point, nous ajoutons donc T 
 T*F et T  F puis le F à droite
d'un point implique l'ajout de
F(E) et F  id. On ne peut
plus alors ajouter aucun autre
item à Fermeture (I) par la règle
(2).

L'opération Transition.
Transition (I,X) où I est un ensemble d'items et X est un symbole de la grammaire.
Transition(I,X) est définie comme la fermeture de l'ensemble de tous les items
[AX] tel que [[AX] appartienne I. Intuitivement, si I est l'ensemble
d'items qui sont valides pour un préfixe viable donné , alors Transition(I,X) est
l'ensemble des items qui sont valides pour le préfixe viable X.

Exemple 4.23.
Si I est l'ensemble des deux items {[E'E], [E E+T], alors Transition(I,+)
consiste en:

E → E+•T Nous calculons Transition(I,+) en recherchant dans I,

T → •T*F
T → •F les items ayant + immédiatement à droite du point, E'
F → •
(E) F → E ne convient pas, mais E E+T répond au critère.
• id Nous faisons franchir au point + afin d'obtenir {[E
E+T]}, puis nous calculons Fermeture sur cet
ensemble.
Algorithme 4.4. Construction des ensembles d'items
Voici l'algorithme pour construire C, la collection canonique d'ensembles d'items
LR(0) pour la grammaire augmentée G'.
Procedure Items (G');
début
C := {fermeture ({[S'  S]})}
répéter
pour chaque ensemble d'items I de C et pour chaque symbole de la
grammaire X tel que Transition(I,X) soit non vide et non encore dans C
ajouter Transition (I,X) à C
fin pour
jusqu'à ce qu'aucun nouvel ensemble d'items ne puisse être plus ajouté à C

Sami KHALFOUI – Moez HAMMAMI – ENSI 72

2006/2007
 Analyse syntaxique

fin

Exemple 4.24.
La collection canonique d'ensembles d'items LR(0) pour la grammaire augmentée :
G' (V, , R, S), avec V = {E', E, T, F, +,*,(,), id}, = {+,*,(,),id}, S = E' et R définit par
les règles de production suivantes:
E'  E
E  E+T |T (5)
T  T*F|F
F  (E) |id
est présentée ci dessous:
I0 : {fermeture ({[E' E]})}
I7 := Transition (I2, *)
E' → •E T →
E → •E+T T*•F F
E → •T → • (E) F
T→ → • id
•T*F T
→ •F
F→• I8 := Transition (I4, E)
(E) F → F → (E•)
• id E → E•+T

I1 := transition(I0,E)
I9 := transition (I6,T)
E' → E•
E  E+T
E → E•+T
T → T•*F

I2 := transition(I0,T)
Transition (I4,F) =
E → T•
I3 Transition (I4, ( )
T → T•*F
= I5

I3 := Transition (I0,F ) I10 = Transition (I7, F)

T  F T → T*F•

I4 := Transition (I0, ( )
F → (•E)
I11 = Transition (I8, ) )
E → F  (E)
•E+T E →
•T
T →
•T*F T
→ •F
F → •
(E) F →
• id

Transition (I0,+) = 
Transition (I0,*) =
Transition (I0, ) ) = 

I5 := Transition (I0, id )
F → id•
I6 := transition (I1,+)

Sami KHALFOUI – Moez HAMMAMI – ENSI 73

2006/2007
 Analyse syntaxique

E → E+•T
T → •T*F
T → •F
F → •
(E) F →
• id

La fonction de Transition pour cet ensemble est donnée sous la forme d'un
diagramme de transition d'un automate fini déterministe D (voir figure 4.13).

Figure 4.13. Diagramme de transition de l'automate fini déterministe D reconnaissant les préfixes
viables.

Remarque 1. Si chaque état D de la figure 6 est un état final et I0 est l'état initial,
alors D reconnaît exactement les préfixes viables de la grammaire G' de l'exemple 10.
Remarque 2 : On peut imaginer un NFA N dont les états sont les items eux-mêmes
avec une transition de [AX] vers [AX] étiquetée X, et il y'a une transition
de [AB] vers B étiquetée . Alors Fermeture(I) pour l'ensemble d'items
(états de N) I est exactement la -fermeture de l'ensemble des états du NFA déjà vue
dans le cours. Donc Transition (I,X) donne la transition depuis I sur le symbole X
dans le DFA produit à partir de N par la construction des sous ensembles.

Items Valides.
Nous disons que l'item [A 12] est valide pour un préfixe viable 1 s'il existe une
*
dérivation S ' αAω αβ1β 2ω(w  *)
d d

Sami KHALFOUI – Moez HAMMAMI – ENSI 74

2006/2007
 Analyse syntaxique

En général, un item sera valide pour plusieurs préfixes viables.

Exemple 4.25.
Soit le préfixe viable E+T* (1); Cherchons les items valides pour ce préfixe.
Cherchons alors toutes les possibilités de dérivation qui font apparaître ce préfixe.
E E+T
E E+T*F
donc TT*  F est un item valide pour E+T*

suffixe du 1 2
préfixe viable

Continuons
E E+T aussi E E+T
 E+T*F  E+T*F
 E+T*(E)  E+T*id
donc donc F id
F (E)
2
2

1 vide

Nous pouvons facilement calculer l'ensemble des items valides pour chaque préfixe
viable qui peut apparaître sur la pile d'un analyseur LR, en utilisant le théorème
suivant:

Théorème: L'ensemble des items valides pour le préfixe viable  est exactement
l'ensemble des items atteints depuis l'état initial, le long d'un chemin étiqueté 
dans le DFA construit à partir de la collection canonique d'ensembles d'items dont les
transitions sont données par transition.

Remarque.
le fait que A 12 soit valide pour 1 nous en dit beaucoup sur l'action décaler
ou réduire que l'on doit effectuer quand on trouve 1 sur la pile d'analyse.
 si 2  , il suggère que nous n'avons pas encore décalé le manche sur la pile donc
on doit décaler
 si 2 = , il semblerait que A 1 soit le manche et que nous devions réduire par
cette production.

Sami KHALFOUI – Moez HAMMAMI – ENSI 75

2006/2007
 Analyse syntaxique

Tables d'analyse SLR

On va voir comment construire les fonctions Action et Successeur à partir du DFA
qui reconnaît les préfixes viables.

Algorithme 4.5. Construction des Tables d'analyse

SLR Donnée : Une grammaire augmentée G'
Résultat : Les tables d'analyse SLR des fonctions Action et Successeur pour G'
Méthode :
1. Construire C = {I0,I1,…,In}, la collection des ensembles d'items LR(0)
2. L'état i est construit à partir de Ii. Les actions d'analyse pour l'état i sont
déterminés comme suit:
a) si [A a ] est dans Ii et Transition (Ii,a) = Ij, remplir Action[i,a]
avec "décaler j". Ici a doit être un terminal.
b) si [A ] est dans Ii, remplir Action [i,a] avec "réduire par A "
pour tous les a de suivant (A); ici A ne doit pas être S'.
c) si [S' S] est dans Ii, remplir Action[i,$] avec "accepter"
si les règles précédentes engendrent des actions conflictuelles, nous disons
que la grammaire n'est pas SLR(1). Dans ce cas, l'algorithme échoue et ne
produit pas d'analyseur.
3. On construit les transitions successeur pour l'état i pour tout non terminal A
en utilisant la règle: si Transition (Ii,A) = Ij, alors Successeur [i,A] = j
4. Toutes les entrées non définies par les règles (2) et (3) sont positionnées à
"erreur"
5. L'état initial de l'analyseur est celui qui est construit à partir de l'ensemble
d'items contenant [S' S].
Les tables d'analyse formées des fonctions Action et successeur déterminées par
l'algorithme 3 sont appelées tables SLR(1) pour G. Un analyseur LR utilisant les
tables SLR(1) pour G est appelé analyseur SLR(1) pour G et une grammaire ayant des
tables d'analyse SLR(1) est SLR(1). Nous omettons en general le (1) apres SLR, car
nous ne considérerons pas ici d'analyseurs utilisant plus d'un symbole de prévision.

Exemple 4.26.
Construisons les tables SLR pour la grammaire G' de l'exemple 4.22.
La collection canonique des ensembles d'items LR(0) pour G' est représentée dans
l'exemple 4.24.
Considérons tout d'abord l'ensemble d'items I0:
I0 :E'  E l'item F   (E) produit l'entée
E → •E+T Action[0,(] = décaler 4 et l'item
E → •T
T → •T*F Fid produit l'action[0,id] =

Sami KHALFOUI – Moez HAMMAMI – ENSI 76

2006/2007
 Analyse syntaxique

T → •F décaler5 les autres items de I0 ne

F → • (E) produisent aucune action.
F   id

Considérons I1
E' → E• Le premier Item produit Action [1,$]
E  E+T = accepter et le second item produit
Action[1,+] = décaler 6.

Considérons maintenant I2
E → T• comme Suivant(E) = {$,+,)}, le
T → T•*F premier item produit Action[2,$] =
Action[2,+] = Action[2,)] = réduire
par E  T
Le second item produit Action [2,*] =
décaler 7 (car transition (I1,*) = I7
dans le DFA)
En continuant ainsi, nous obtenons les tables Action et successeur suivantes:
Action Successeur
id + * ( ) $ E T F
0 d5 d4 1 2 3
1 d6 Acc
2 r2 d7 r2 r2
3 r4 r4 r4 r4
4 d5 d4 8 2 3
5 r6 r6 r6 r6
6 d5 d4 9 3
7 d5 d4 10
8 d6 d11
9 r1 d7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5

Sami KHALFOUI – Moez HAMMAMI – ENSI 77

2006/2007
 Traduction dirigée par la syntaxe

Traduction dirigée par la syntaxe

Il s'agit d'associer de l'information à une construction d'un langage de

programmation en attachant des attributs aux symboles de la grammaire
représentant cette construction. Les valeurs de ces attributs sont calculées par des
règles sémantiques" associés aux productions de la grammaire. Il existe deux
notations pour associer des règles sémantiques aux productions : les définitions
dirigées par la syntaxe et les schémas de traduction. Les premiers ne spécifient pas
l'ordre dans lequel la traduction s'effectue, les schémas de traduction indiquent
l'ordre dans lequel les règles sémantiques doivent être évaluées. Ces deux notations
sont employées pour :
- des vérifications sémantiques (détermination des types)
- engendrer du code intermédiaire
Dans les deux notations, on effectue l'analyse syntaxique du flot des terminaux
d'entrée, on construit l'ordre syntaxique, puis ce dernier est parcouru autant de fois
qu'il est nécessaire pour évaluer les règles sémantiques à ses nœuds l'évolution des
règles sémantiques peut produire du code, sauvegarder de l'information dans une
table de symboles, émettre des messages d'erreurs ou autres.

Notation postfixée :
La notation postfixée pour une expression E peut être définie récursivement comme
suit :
1. Si E est une variable ou une constante, la notation postfixée de E est E elle-
même.
2. Si E est une expression de la forme E1 op E2, où op est un opérateur binaire, la
notation postfixée de E est '
E' 'op, où E 'et E sont les notations postfixées
E1 2 1 2
de E1 et E2 respectivement.
3. Si E est une expression de la forme (E1), la notation postfixée de E est la
notation postfixée de E1.
Remarque. Aucune parenthèse n'est nécessaire en notation postfixée, car la
position et l'arité (nombre d'arguments) des opérateurs ni permettent qu'un seul
décodage de l'expression postfixée. Par exemple, la notation postfixée (9 - 5) + 2 est
95 -2+ et celle de 9 – (5+2) est 952+-.

Sami KHALFOUI – Moez HAMMAMI – ENSI 78

2006/2007
 Traduction dirigée par la syntaxe

5.1. Définitions dirigées par la syntaxe

Une définition dirigée par la syntaxe utilise une grammaire non contextuelle pour
spécifier la structure syntaxique du texte d'entrée. A chaque symbole de la
grammaire, on associe un ensemble d'attributs et, à chaque production, un ensemble
de règles sémantiques pour calculer la valeur des attributs associés aux symboles
apparaissant dans cette production. La grammaire et l'ensemble des règles
sémantiques constituent la définition dirigée par la syntaxe.

5.1.1. Attributs synthétisés

Les attributs synthétisés sont utilisés intensivement en pratique. Une définition

dirigée par la syntaxe qui utilise uniquement des attributs synthétisés est appelée
définition S-attribuée.
Un attribut est synthétisé si sa valeur, à un nœud d'un arbre syntaxique, est
déterminée à partir de valeurs d'attributs des fils de ce nœud. Les attributs
synthétisés ont la propriété de pouvoir être évolués au cours d'un simple parcours
ascendant de l'arbre syntaxique.

Exemple 5.1.
La figure 5.1 représente une définition dirigée par la syntaxe pour traduire des
expressions formées de chiffres séparés par des signes + ou – en une notation
postfixée. Est associé à chaque non terminal un attribut t dont la valeur est une
chaîne qui représente la notation postfixée de l'expression engendrée par ce terminal
dans un arbre syntaxique.

Production Règle sémantique

expr  expr1 + terme expr.t : = expr1.t
expr  expr1 – terme terme.t'+' expr.t : =
expr  terme expr1.t terme.t'-' expr. t :
terme  0 = terme.t
terme  1 eerme.t : = '0'
--- terme.t : = '1'
terme  9 ---
terme.t : = '9'
Figure 5.1. Définition dirigée par la syntaxe de la traduction infixée, postfixée

(L'opérateur  dans les règles sémantiques représente la concaténation de chaînes.)

- La notation postfixée d'un chiffre est lui-même, la règle sémantique associée à la
production « terme  9 » définit terme.t comme étant 9, à chaque fois que
cette production est utilisée à un nœud d'un arbre syntaxique.

Sami KHALFOUI – Moez HAMMAMI – ENSI 79

2006/2007
 Traduction dirigée par la syntaxe

- Quand la production « exp  terme » s'applique, la valeur de terme.t devient

la valeur de expr.t.
- La production « expr  expr1 + terme » dérive une expression formée d'un
opérateur + ; l'indice de expr1 distingue l'instance de expr de droite de celle en
partie gauche.
- La règle sémantique : « expr.t : = expr1.t terme.t'+' » associée à la
production définit la valeur de l'attribut expr.t en concaténant les formes
postfixées expr1.t et le terme.t et en y ajoutant le signe plus.
La figure 5.2 donne l'arbre décoré pour l'expression 9-5+2.
La valeur de l'attribut t associé à chaque nœud a été calculée en utilisant la règle
sémantique de la production utilisée au nœud. La valeur de l'attribut à la racine est la
notation postfixée de la chaîne produite par l'arbre syntaxique.

expr.t = 95 – 2 +

expr.t = 95 – terme.t = 2

expr.t = 9 terme.t = 5

terme.t = 9

9 - 5 + 2

Figure 5.2 : Valeurs des attributs aux nœuds d'un arbre syntaxique

5.1.2. Parcours en profondeur

Une définition dirigée par la syntaxe n'impose aucun ordre spécifique pour
l'évaluation des attributs sur l'ordre syntaxique ; tout ordre d'évolution qui calcule
l'attribut a après tous les attributs dont a dépend est acceptable.
On peut utiliser le parcours en profondeur. Le parcours d'un arbre débute à la racine
et récursivement, visite les fils de chaque nœud dans un ordre gauche-droite, comme
le montre la figure 5.3.
On évalue les règles sémantiques à un nœud donné après que tous les descendants
de ce nœud ont été visités.

Sami KHALFOUI – Moez HAMMAMI – ENSI 80

2006/2007
 Traduction dirigée par la syntaxe

Procédure visiter (n : nœud) ;

début
pour chaque fils m de n, de gauche à droite faire
visiter (m) ;
évaluer les règles sémantiques au nœud n
fin

Figure 5.3. Parcours en profondeur d'un arbre

5.2. Schéma de traduction

Un schéma de traduction est une grammaire non contextuelle dans laquelle on insère
des fragments de programmes appelés actions sémantiques à l'intérieur même des
parties droites des productions.
Un schéma de traduction ressemble à une définition dirigée par la syntaxe, excepté
que l'ordre d'évaluation des règles sémantiques est explicitement donné.
On indique la position à laquelle une action doit être exécutée en englobant cette
action entre accolades à laquelle une action doit être exécute en englobant cette
action entre accolades et en l'écrivant à l'intérieur de la partie droite d'une production
comme dans :
reste  +terme Imprimer ('+') reste 1
Les actions sémantiques seront alors exécutés dans l'ordre où elles apparaissent au
cours d'un parcours en profondeur de l'arbre syntaxique.
Quand on construit un arbre syntaxique pour un schéma de traduction, on indique
une action en construisant pour elle une feuille additionnelle, reliée par un trait
pointille au nœud de la partie gauche de cette production.
La figure 5.4 représente la portion de l'arbre syntaxique pour
reste  +terme Imprimer ('+') reste 1 et son action

Sami KHALFOUI – Moez HAMMAMI – ENSI 81

2006/2007
 Traduction dirigée par la syntaxe

reste

+ terme Imprimer ('+') reste 1

Figure 5.4. Portion d’un arbre syntaxique

Le nœud pour une action sémantique n'a pas de fils, l'action est exécutée quand ce
nœud est visité pour la première fois.

Remarque.
Les définitions dirigées par la syntaxe mentionnées jusqu'à maintenant ont la
propriété suivante : la chaîne représentant la traduction du non-terminal en partie
gauche de chaque production est la concaténation des traduction des non terminaux
en partie droite dans le même ordre que dans la production, avec éventuellement des
chaînes venues s'insérer entre ces traductions. Une définition dirigée par la syntaxe
qui a cette propriété est simple.

Exemple 5.2.
Production Règle sémantique
Expr  expr 1 + terme expr.t : = expr1.t terme.t'+'
Reste  + terme reste 1 reste.t : = terme.t '+' reste1.t

chaîne additionnelle
apparaît avant

Les définitions dirigées par la syntaxe simple peuvent être implantées par des
schémas de traduction dans lesquelles les actions impriment les draines
additionnelles dans l'ordre dans lesquels ils apparaissent dans la définition.

Exemples 5.3.
La figure 5.5 représente un schéma de traduction dérivé de la définition de la figure
5.1.
expr  expr + terme Imprimer ('+')
expr  expr - terme Imprimer '-'
expr  terme
terme  0 Imprimer ('0')
terme  1 Imprimer ('1')
---
terme  9 Imprimer ('9')
Figure 5.5. Actions traduisant des expressions en notation postfixée

Sami KHALFOUI – Moez HAMMAMI – ENSI 82

2006/2007
 Traduction dirigée par la syntaxe

La figure 5.6 représente un arbre syntaxique avec des actions pour 9 – 5 + 2.

expr

expr + terme {Imprimer ('+')}

expr - terme {Imprimer ('-')} 2 {Imprimer ('2')}

terme 5 {Imprimer ('5')}

9 {Imprimer ('9')}
Figure 5.6. Actions traduisant 9 – 5 + 2 en 95 – 2 +

Quand elles sont exécutées au cours d'un parcours en profondeur de l'arbre

syntaxique, les actions de la figure 5.6 impriment 95 – 2 +.

5.3. Arbre abstrait et arbre concret

Dans un arbre syntaxique abstrait, chaque nœud représente un opérateur et les fils
de ce nœud représentent des opérandes.
Par opposition, un arbre syntaxique est appelé arbre syntaxique concret et la
grammaire sous jacents est appelée syntaxe concrète du langage.
Par exemple les figures 5.7 et 5.8 donnent les arbres abstraits et syntaxiques pour 9
– 5 + 2.

+ liste
_ 2 liste
chiffre

9 5 liste chiffre

chiffre

9 _ 5 + 2

Figure 5. 7. Arbre abstrait pour 9 – 5 + 2 Figure 5.8. Arbre syntaxique pour 9 – 5 + 2

Remarque.
Il est souhaitable qu'un schéma de traduction s'appuie sur une grammaire dont les
arbres syntaxiques sont aussi près que possible des arbres abstraits.

Sami KHALFOUI – Moez HAMMAMI – ENSI 83

2006/2007
 Traduction dirigée par la syntaxe

Remarque.
On peut désigner une définition dirigée par la syntaxe par SDTS abstraite pour
syntax Directed Translation schéma abstrait et le schéma de traduction tel qu'il a été
présenté SDTS concret.

Sami KHALFOUI – Moez HAMMAMI – ENSI 84

2006/2007
 Contrôle de type

Contrôle de type
De nombreux compilateurs Pascal combinent les contrôles statiques et la production
de code intermédiaire avec l'analyse syntaxique. Pour des constructions plus
complexes comme celles d'Ada, on peut faire intervenir une passe séparée pour le
contrôle de type, placée entre l'analyse syntaxique et la production de code
Intermédiaire, comme indiqué dans la figure 6.1.

Figure 6.1. Position du contrôleur de type

Un contrôleur de type vérifie que le type d'une construction correspond au type

attendu par son contexte. Ainsi, par exemple, l'opérateur arithmétique « mod » de
Pascal nécessite des opérandes entiers j un contrôleur de type doit donc vérifier que
les opérandes de « mod » sont bien de type entier. De façon similaire, le contrôleur
de type doit vérifier que le déréférençage n'est appliqué qu'à des pointeurs, que seuls
des tableaux sont indicés, que toute fonction définie par l'utilisateur est utilisée avec
le bon nombre d'arguments de types corrects, ainsi de suite.

6.1. Expression de type

Le type de toute construction d'un langage est dénoté par une « expression de type ».
De façon informelle, ou bien une expression de type est un type de base, ou bien elle
est formée en appliquant un opérateur appelé « constructeur de type» à d'autres
types de base. L'ensemble des types de base et des constructeurs dépend du langage
sur lequel s'effectue le contrôle.
Nous utilisons dans ce chapitre la définition suivante d'expression de type:
1. Un type de base est une expression de type. Parmi les types de base, on trouve
booléen, caractère, entier et réel. Un type de base spécial, erreur_de_type, signale
les erreurs détectées lors du contrôle de type. Enfin, un type de base vide,
dénotant « l'absence de valeur », permet le contrôle des instructions.
2. Puisque les expressions de type peuvent être nommées, un nom de type est une
expression de type.
3. Un constructeur de type appliqué à des expressions de type est une expression de
type. On trouve parmi les constructeurs:
(a) Les tableaux. Si T est une expression de type, tableau (I, T) est une expression
de type, qui dénote le type d'un tableau dont les éléments sont du type T et
dont l'ensemble des indices est I. Ce dernier est souvent un intervalle d'entiers.

Sami KHALFOUI – Moez HAMMAMI – ENSI 85

2006/2007
 Contrôle de type

(b) Les produits. Si Tl et T2 sont des expressions de type, leur produit cartésien Tl
X T2 est une expression de type. Nous supposons que X est associatif à
gauche.
(c) Les structures. En un certain sens, le type d'une structure est le produit des
types de ses champs. La différence entre une structure et un produit est que
les champs d'une structure ont des noms.
(d) Les pointeurs. Si T est une expression de type, pointeur(T) est une expression
de type dénotant le type «pointeur vers un objet de type T ».
(e) Les fonctions. En termes mathématiques, une fonction fait correspondre à des
éléments d'un ensemble de départ, le domaine, des éléments d'un ensemble
d'arrivée, le co-domaine. Nous pouvons considérer que les fonctions des
langages de programmation font correspondre au type domaine D le type co-
domaine A. Le type d'une telle fonction sera dénoté par l'expression de type
DA. Par exemple, la fonction intrinsèque « mod » de Pascal a pour type
domaine entier X entier, c'est-à-dire un couple d'entiers, et pour type co-
domaine entier. Nous disons donc que « mod » a pour type :
entier X entier  entier.

6.2. Spécification d’un contrôleur de type simple

Nous spécifions dans cette section un contrôleur de type pour un langage simple,
dans lequel le type de tout identificateur doit être déclaré avant que cet identificateur
soit utilisé. Ce contrôleur de type est un schéma de traduction qui synthétise le type
de toute expression à partir des types de ses sous-expressions. Le contrôleur de type
peut manipuler tableaux, pointeurs, instructions et fonctions.

6.2.1. Un langage simple

Soit la grammaire G suivante :

P D ; E
D  D ; D | id : T
T  caractère |entier |tableau [nb] de T |
↑T E  littéral |nb |id|E mod E|E [ E ]|E↑
Cette grammaire engendre des programmes, représentés par le non-terminal P, qui
consistent en une séquence de déclarations D suivie d'une seule expression E.
Voici un exemple de programme engendré par la grammaire G :
x : entier ;
x mod 1999
Avant de nous intéresser aux expressions, considérons les types dans ce langage. Le
langage lui-même a deux types de base, caractère et entier; nous utilisons un
troisième type de base, erreur_de_type, pour signaler les erreurs.

Sami KHALFOUI – Moez HAMMAMI – ENSI 86

2006/2007
 Contrôle de type

Dans le schéma de traduction de la figure 6.2, l'action associée à la production

Did:T stocke un type dans l'entrée d'un identificateur dans une table de symboles.
L'action AjouterType(id.entrée, T.type) est appliquée à l'attribut synthétisé entrée, qui
pointe vers l'entrée de id dans la table des symboles, et à une expression de type
représentée par l'attribut synthétisé type du non-terminal T.

Figure 6.2. La partie d’un schéma de traduction qui stocke le type d’un identificateur

Si T engendre caractère ou entier, T.type est défini comme caractère ou entier,

respectivement. La borne supérieure d'un tableau est obtenue à partir de l'attribut val
de l'unité lexicale nb qui donne l'entier représenté par nb. Les tableaux sont censés
commencer à 1, donc le constructeur de type tableau est appliqué à l'intervalle
l..nb.val et au type des éléments.
Puisque D apparaît avant E en partie droite de P  D ; E, nous sommes sûrs que le
type de tous les identificateurs déclarés sera stocké avant que commence le contrôle
de l'expression engendrée par E. En fait, en modifiant la grammaire G de façon
adéquate, nous pouvons mettre en œuvre les schémas de traduction de cette section
lors d'une analyse syntaxique ascendante ou descendante, au choix.

6.2.2. Contrôle de type des expressions

Dans les règles qui suivent, l'attribut synthétisé type associé à E donne l'expression
de type affectée par le système de typage à l'expression engendrée par E. Les règles
sémantiques ci-dessous spécifient que les constantes représentées par les unités
lexicales littéral et nb sont de types caractère et entier respectivement:

Nous utilisons une fonction Rechercher(e) pour retrouver le type stocké dans l'entrée
référencée par e dans la table des symboles. Lorsqu'un identificateur apparaît dans
une expression, nous allons chercher son type déclaré et l'affectons à l'attribut type:

Une expression formée par application de l'opérateur « mod » à deux sous-

expressions de type entier a pour type entier; dans les autres cas son type est
erreur_de_type. La règle est la suivante:

Sami KHALFOUI – Moez HAMMAMI – ENSI 87

2006/2007
 Contrôle de type

Dans un accès à un élément de tableau E1[E2], l'expression E2 doit être de type entier,
auquel cas le résultat est le type t des éléments obtenu à partir du type tableau(s,t) de
E1; nous n'utilisons pas l'ensemble s des indices du tableau.

Dans les expressions, l'opérateur postfixe ↑ retourne l'objet référencé par son
opérande. Le type de E↑ est le type t de l'objet référencé par le pointeur E:

6.2.3. Contrôle de type des instructions

Puisque les constructions des langages telles les instructions n'ont en général pas de
valeur associée, le type de base spécial vide peut leur être affecté. Lorsqu'une erreur
est détectée dans une instruction, le type qui est affecté à cette instruction est
erreur_de_type.
Les instructions que nous prenons en compte sont l'affectation, la conditionnelle et la
boucle «tant que». Les séquences d'instructions sont séparées par des points-
virgules. Les productions de la figure 6.3 peuvent être combinées avec celles de la
grammaire G, en changeant simplement la production pour un programme complet
en PD;I. Un programme consiste alors en des déclarations suivies d'instructions ;
nous avons toujours besoin des règles précédentes pour le contrôle des expressions,
car les instructions peuvent contenir des expressions.
Les règles pour le contrôle des instructions sont données à la figure 6.3. La première
règle contrôle que les parties gauche et droite d'une instruction d'affectation sont du
même type. Les deuxième et troisième règles spécifient que, dans l'instruction
conditionnelle et la boucle « tant que », l'expression doit être de type booléen. Les
erreurs sont propagées par la dernière règle de la figure 6.3, parce qu'une séquence
d'instructions n'est de type vide que si chaque sous-instruction est de type vide. Dans
ces règles, une discordance de types produit le type erreur_de_type ; bien entendu,
un contrôleur de type convivial signalerait en outre la nature et l'emplacement de la
discordance de types.

Figure 6.3. Schéma de traduction pour le contrôle de type des instructions

Sami KHALFOUI – Moez HAMMAMI – ENSI 88

2006/2007
 Contrôle de type

6.3. Conversion de type

Considérons une expression comme x+i où x est de type réel et i de type entier.
Puisque les représentations des entiers et des réels ne sont pas les mêmes dans un
calculateur et que l'on utilise des instructions machine différentes pour les opérations
sur les entiers et sur les réels, le compilateur peut avoir à convertir un des opérandes
de + pour assurer que les deux opérandes sont du même type lorsque l'addition est
effectuée.
La définition du langage spécifie quelles sont les conversions nécessaires.
Lorsqu'un entier est affecté à un réel, ou vice versa, la conversion se fait vers le type
de la partie gauche de l'affectation. Dans les expressions, la transformation consiste
habituellement à convertir l'entier en un nombre réel, puis à effectuer une opération
réelle sur le couple d'opérandes réels ainsi obtenu. Dans un compilateur, le
contrôleur de type peut être utilisé pour insérer ces opérations de conversion dans la
représentation intermédiaire du programme source. Par exemple, la notation
postfixée de x+i pourrait être:
x i EntierVersRéel +réel
Ici, l'opérateur EntierVersRéel convertit i d'entier vers réel, puis +réel effectue une
addition réelle sur ses opérandes.
Coercitions
La conversion d'un type vers un autre est dite implicite si elle est censée être réalisée
automatiquement par le compilateur. Les conversions de type implicites, que l'on
appelle aussi coercitions, sont dans de nombreux langages limitées aux situations où
elles ne donnent en principe lieu à aucune perte d'information j par exemple, un
entier peut être converti en un réel mais pas le contraire. En pratique toutefois, une
perte d'information est possible si un nombre réel occupe le même nombre de bits
qu'un nombre entier.
La conversion est dite explicite si le programmeur a quelque chose à écrire pour que
la conversion ait lieu. En Ada, toutes les conversions nécessaires en pratique sont
explicites. Du point de vue du contrôleur de type, les conversions explicites sont
exactement semblables aux applications de fonctions et ne présentent donc aucun
problème nouveau.
En Pascal, par exemple, la fonction intrinsèque ord fait correspondre à un caractère
un entier et chr effectue la correspondance inverse d'entier vers caractère j ces
conversions sont donc explicites. En revanche, C contraint (c'est-à-dire convertit
implicitement) les caractères ASCII en des entiers compris entre 0 et 127 dans les
expressions arithmétiques.

Exemple 6.1.
Considérions les expressions formées en appliquant un opérateur arithmétique op à
des constantes et des identificateurs, comme dans la grammaire de la figure 6.4.
Supposons que nous ayons deux types réel et entier, les entiers étant convertis en des
réels lorsque cela est nécessaire. L'attribut type du non-terminal E peut avoir pour
valeur soit entier soit réel; les règles de contrôle de type sont données à la figure 6.4.

Sami KHALFOUI – Moez HAMMAMI – ENSI 89

2006/2007
 Contrôle de type

La fonction Rechercher(e) retourne le type stocké dans l'entrée référencée par e dans
la table des symboles.

Figure 6.4. Règles de contrôle de type pour la coercition d’entier vers réel

Affectation de type mixte

x : real code 3 Q voulu
y : real T1 : = I * J
I : integer T2 : = intoreal T1
J : integer T3 : = y + T2
X:=Y+I*J X : = T3

E  E1 op E2

E.place : = New Temp ( ) ;

if E1.type = E2.type = integer then

begin
E.type : = integer
GEN (E.place : = E1.place "intop" E2.place)
end
else
if (E1.type = real) and (E2.type = real) then

begin
E.type : = real
GEN (E.place : = E1.place "real op" E2place)
end
else
if F2.type = real then
begin
U : = NewTemp ( ) ;
GEN (U : = "intoreal" E1.place)
GEN (E.place : = U "realop" E2.place
E.type : = real
end
else // E2.type = integer
begin
U : = NewTemp ( ) ;
GEN (U : = intoreal E2.place)

Sami KHALFOUI – Moez HAMMAMI – ENSI 90

2006/2007
 Contrôle de type

GEN (E.place : = E1.place "realop" U)

E.type : = real
end
end if
end if
end if

E  (E1) E.type : = E1.type

E.place : = E1.place

E   E1 E.type : = E1.type
E.place : = NewTemp ( )

GEN (E.place : = "  " E1.place)

E  id E.type : = Rechercher (id.entrée)

E.place : = id.place

A  id : = E
if rechercher (id.entrée) = real then

if E.type = real then

GEN (id.place : = E.place)
else // E.type = integer
begin
U : = NewTemp ( )
GEN (U : = intoreal (E.place))
GEN (id.place : = U)
end

else // id son type est entier

if E.type ) integer then
GEN (id.place : = E.place)
else
erreur ( )
end if
end if

Sami KHALFOUI – Moez HAMMAMI – ENSI 91

2006/2007
 Production de code intermédiaire

Production de code
intermédiaire
A l'issue de l'analyse syntaxique et de l'analyse sémantique, certains compilateurs
construisent explicitement une représentation intermédiaire du programme source.
On peut considérer celle ci comme un programme pour une machine abstraite (pas
de limites quand au nombre de registres). Cette représentation intermédiaire doit
avoir deux propriétés importantes: Elle doit être facile à produire et facile à traduire
en langage cible.
L'une des formes de ce code intermédiaire est le code à 3 adresses

7.1. Code à trois adresses

Un code à trois adresses est une séquence d'instructions de la forme: x := y op z où
x,y et z sont des noms, des constantes ou des variables temporaires produites par le
compilateur. « op » dénote n'importe quel opérateur, tel qu'un opérateur
arithmétique, entier ou réel, ou bien un opérateur logique sur des valeurs
booléennes. Ainsi l'expression du langage source x +y*z pourra être traduite par
séquence suivante:
t1 := y *z
t2 := x +
t1
où t1 et t2 sont des variables temporaires produites par le compilateur.

Remarque.
Le code intermédiaire est une représentation linéarisée d'un arbre abstrait, dans
laquelle les noms explicites correspondent aux nœuds internes de l'arbre.
La terminologie "code à trois adresses" peut se justifier par le fait que chaque
instruction contient en général trois adresses, deux pour les opérandes et une pour le
résultat.
Dans les implantations de code à trois adresses plus loin dans ce chapitre, un nom
définit par le programmeur est représenté par un pointeur référençant une entrée
dans la table des symboles.

7.1.1. Traduction dirigée par la syntaxe pour la production du code à trois

adresses

Quand on produit du code à trois adresses, on crée des variables temporaires pour
les nœuds internes d'un arbre abstrait. La valeur du non terminal E partie gauche de
la production E  E1 + E2 est calculée dans un nouveau temporaire t.

Sami KHALFOUI – Moez HAMMAMI – ENSI 92

2006/2007
 Production de code intermédiaire

En général, le code à trois adresses pour id := E est constitué par la séquence de

l'évaluation de E dans un temporaire t, suivis par l'affectation id.place := t.
Si une expression est un identificateur simple, par exemple y, alors y lui même
contient la valeur de l'expression.
La définition S-attribuée (qui utilise uniquement des attributs synthétisés) de la
figure 7.1 produit du code à trois adresses pour les instructions d'affectation. Etant
donné l'instruction d'entrée a := b*-c+b*-c, elle produit la séquence:
t1 := -C
t2 :=
b*t1 t3
:= -C
t4 := b + t3
t5 := t2 +
t4 a := 5
Production Règle Sémantique
I  id := E I.code := E.code ||Gen(id.place ':= ' E.place)
E  E1 + E2 E.place := NewTemp;
E.code := E1.code||E2.code|| Gen (E.place ':=' E1.place '+' E2.place)
E  E1 * E2 E;place := NewTemp;
E.code := E1.code||E2.code||Gen(E.place ':=' E1.place '*' E2.place)
E  -E1 E.place := Newtemp;
E.code := E1.code||Gen(E.place ':=' 'MoinsU' E1.place)
E  (E1) E.place := E1.place
E.code := E1.code;
E  id E.place := id.place;
E.code := ' '
Figure 7.1. Une définition S-attribuée produisant du code à trois adresses pour les instructions
d'affectation.

L'attribut synthétisé I.code représente le code 3@ pour l'instruction d'affectation

définie par le non terminal I.
Le non terminal E possède deux attributs:
- E.place : le nom qui contient la valeur de E et
- E.code : la séquence de code à trois adresses permettant d'évaluer E.
La fonction NewTemp retourne un nouveau nom à chaque appel. Chaque nom est de
la forme tn.
Nous utilisons Gen(x ':=' y '+' z) pour représenter l'instruction à trois adresses
x':='y'+'z. Les expressions apparaissant à la place de variables comme x,y et z sont
évaluées quand-elles sont passées en paramètre à Gen.

Sami KHALFOUI – Moez HAMMAMI – ENSI 93

2006/2007
 Production de code intermédiaire

7.1.2. Implantation d'instructions à trois adresses

Dans un compilateur, les instructions à 3 adresses peuvent être implémentées par des
structures dont les champs contiennent l'opérateur et les opérandes. Parmi ces
représentations on trouve les quadruplets et les triplets.
Quadruplets. Un quadruplet est une structure possédant quatre champs appelés
respectivement op, arg1, arg2 et résultat. Le champ op contient un code interne pour
l'opérateur.
L'instruction à trois adresses x := y op z est représentée en plaçant y dans arg1, z
dans arg2 et x dans résultat.
Les instructions utilisant les opérateurs unaires tels que x := -y ou x := y n'utilisent
pas arg2.
Les instructions de branchement conditionnel (if A relop B Goto L) et inconditionnel
(Goto L) rangent leurs étiquettes dans résultat.

Exemple 7.1.
Les quadruplets de la figure 7.2 (a) représentant l'instruction d'affectation a:= b*-
c+b*-c. Elles correspondent au code à trois adresses.
t1 := -c
t2 := b *t1
t3 := -c
t4:= b*t3
t5 := t2
+t4 a := t5

op arg1 arg2 résultat op arg1 arg2

(0) MoinsU c t1 (0) MoinsU c
(1) * b t1 t2 (1) * b (0)
(2) MoinsU c t3 (2) MoinsU c
(3) * b t3 t4 (3) * b (2)
(4) + t2 t4 t5 (4) + (1) (3)
(5) := t5 a (5) := a (4)
(a) Quadruplets (b) triplets
Figure 7.2. Représentation de code à trios adresses en quadruplets et triplets

Les contenus des champs arg1, arg2 et résultat sont des pointeurs vers les entrées de
la table des symboles des noms représentées par ces champs. Les variables
temporaires doivent donc être rangées dans la table des symboles lorsqu'elles sont
crée.
Triplets. On peut éviter de ranger des variables temporaires dans la table des
symboles en référençant une valeur temporaire par la position de l'instruction qui la
calcule. Dans ce cas, les instructions à 3 adresses sont représentées par les structures
à 3 champs: op arg1, arg2 comme dans la figure 7.2 (b). Les arguments arg1 et arg2

Sami KHALFOUI – Moez HAMMAMI – ENSI 94

2006/2007
 Production de code intermédiaire

sont soit des pointeurs vers la table des symboles, soit des pointeurs vers la structure
des triplets (pour les valeurs temporaires).

Voici maintenant deux techniques équivalentes pour traduire l'instruction

d'affectation et les expressions arithmétiques en code à 3 adresses.

Définition dirigée par la syntaxe pour l'affectation et les expressions

arithmétiques. (SDTS abstraite)

AF  id := E A.code := E.code || id.place ':=' E.place

E  E1 op E2 E.place := newTemp
E.code := E1.code|E2.code|E.place ':=' E1.place 'op' E2.place

E  -E1 E.place := newtemp();

E.code := E1.code||E.place ':=' '-' E1.place

E  (E1) E.place := E1.place

E.code := E1.code

E  id E.place := id.place
E.code := Null

Figure 7.3. SDTS abstraite pour traduire l'instruction d'affectation et les expressions arithmétiques

Schéma de traduction pour l'affectation et les expressions arithmétiques (SDTS

concrète)

AF  id := E {Gen(id.place ':= ' E.place)}

E  E1 op E2 {E.place := newTemp();
Gen(E.place ':=' E1.place 'op' E2.place)}
E  -E1 {E.place := NewTemp();
Gen(E.place ':=' '-' E1.place)}
E  (E1) {E.place ':=' E1.place}

E  id {E.place ':=' id.place}

Figure 7.4. SDTS concrète pour traduire l'instruction d'affectation et les expressions arithmétiques

7.2. Expressions booléennes (méthode numérique)

Une méthode de représentation des expressions booléennes consiste à coder
numériquement vrai et faux et à évaluer une expression booléenne comme une

Sami KHALFOUI – Moez HAMMAMI – ENSI 95

2006/2007
 Production de code intermédiaire

expression arithmétique. On utilise souvent la valeur 1 pour représenter vrai et 0

pour représenter faux.
Voici un exemple de traduction:

a ou b et non C ("ou "et "et" associatifs à gauche, "ou"

a une priorité inférieur à "et" et à
"non")
Devient :
t1 := non C
t2 := b et t1
t3 := a ou
t2
Une expression de relation telle que a < b est équivalente à l'expression
conditionnelle si a <b alors 1 sinon 0 qui peut être traduite par la séquence à trois
adresses suivante:
100: si a < b aller à
103 101: t:= 0
102: aller à 104
103: t:= 1
104:
Le schéma de traduction permettant de produire du code à trois adresses pour les
expressions booléennes est présenté à la figure 7.5.
Dans ce schéma, on suppose que la procédure "Gen" écrit les instructions à trois
adresses sur un fichier de sortie, InstSuiv fournit l'indice de la prochaine instruction
à trois adresses dans la séquence de sortie et que "Gen" incrémente InstSuiv après
avoir produit les instructions à 3 adresses.
E  E1 ou E2 {E.place := NewTemp;
Gen( E.place ':=' E1.place 'ou' E2.place)}
E  E1 et E2 E.place := NewTemp;
Gen(E.place ':=' E1.place 'et' E2.place)}
E  non E1 {E.place := NewTemp;
Gen(E.place ':=' 'non' E1.place)}
E (E1) {E.place := E1.place)}
E  id1 oprel id2 {E.place := NewTemp;
Gen('Si' id1.place oprel.op id2.place 'aller à' InstSuiv +3);
Gen(E.place ':=' '0');
Gen('aller à' InstSuiv +2);
Gen(E.place ':=' '1')}
E  vrai {E.place := NewTemp;
Gen(E.place ':=' '0')}
EFaux {E.place := NewTemp
Figure 7.5. Schéma de Traduction utilisant la représentation numérique des booléens

Sami KHALFOUI – Moez HAMMAMI – ENSI 96

2006/2007
 Production de code intermédiaire

7.3. Techniques de reprise Arrière (BackPatching)

Dans cette section, nous montrons comment la technique de reprise arrière peut être
utilisée pour engendrer le code des expressions booléennes et des instructions de flot
de contrôle en une seule passe.
Principe de base.
Le principe consiste à produire une série de branchements dont les destinations sont
temporairement indéfinies. Ces instructions sont conservées dans une liste
d'instructions de branchements dont les champs "étiquettes" sont remplis quand les
valeurs des étiquettes seront déterminées
Exemple 7.2.
vrai

si A < B alors A := B+C

Faux
Nous produirons les quadruplets dans un tableau. Les étiquettes seront les indices de
ce tableau.
La production des quadruplets pour A :=
1 si A <B aller à Vrai B+C nous a permis de connaître le
2 Aller à faux numéro du quadruplet avec lequel
3 T1 := B+C commence cette instruction qui est 3.
4 A := T1  Le branchement indéfini de la ligne 1
5 devrait alors brancher vers le quadruplet
3

Aussi on a pu savoir que l'adresse du premier quadruplet qui suit le code pour A :=
B+C est 5. Le branchement indéfini de la ligne 2 devrait brancher vers 5.
Le code devient alors:

1 si A <B aller à 3
2 Aller à 5
3 T1:= B+C
4 A := T1
5
 C'est le principe de reprise arrière.
Nous allons utiliser trois fonctions pour manipuler les listes d'instructions:
1. MakeList(i) crée une nouvelle liste contenant seulement i, indice dans le
tableau des quadruplets; makelist retourne un pointeur vers la liste ainsi crée.
2. Merge (p1,p2) concatène les listes pointées par p1 et p2 et retourne un
pointeur vers la liste résultat.
3. BackPatch (p,i) insère i comme étiquette cible dans chacune des instructions
de la liste pointée par p.

Sami KHALFOUI – Moez HAMMAMI – ENSI 97

2006/2007
 Production de code intermédiaire

7.3.1. Traduction des expressions booléennes

Nous présentons un schéma de traduction destiné à la production de code pour les

expressions booléennes pendant une analyse ascendante.
Nous insérons le non terminal marqueur M dans la grammaire afin que l'action
sémantique associée puisse collecter la valeur de l'indice du prochain quadruplet à
produire. La grammaire que nous utilisons est la suivante:
C C1 ou C2
|C1 et MC2
|non C1
|(C1)
|id1 oprel id2
|bid

M 
On utilise les attributs synthétisés True et False attachés au non terminal C pour
produire le code des expressions booléennes. Quand on produit le code pour C, on
ne produit pas complètement les instructions de branchement correspondant aux
sorties vrai et faux car leurs champs étiquette n'est pas rempli. On range ces
instructions de branchement incomplètes dans les listes pointées par C.true et
C.false.
Les actions sémantiques sont expliquées comme suit:
True True

False
C  C1 et C2
False

Etudions la production C C1 et MC. Si C1 est faux, C est faux aussi; Les instructions
de C1.False appartiennent donc aux instructions de C.False.
Si C1 est vrai, il faut tester C2, donc l'instruction destination de C1.true doit débuter
le code produit par C2. On obtient cette instruction destination en utilisant le
Marqueur M.
L'attribut M.quad mémorise le numéro de la première instruction de C2.code. A la
production M on associe l'action sémantique {M.quad = nextQuad.
La variable globale nextQuad contient la valeur de l'indice du prochain quadruplet
qui sera produit. Cette valeur sera affectée à C1.True quand le reste de la production
C C1et M C2 aura été traité. Le schéma de Traduction complet est le suivant:

(1) C C1 ou C2 { BackPartch(C1.False, M.quad);

C.True := Merge(C1.True, C2.True);
C.False}

(2) C C1 et MC2 { BackPatch(C1.True, M.quad);

Sami KHALFOUI – Moez HAMMAMI – ENSI 98

2006/2007
 Production de code intermédiaire

C.True := C2.true
C.False := Merge(C1.false, C2.False)}

(3) C non C1 { C.True := C1.false;

C.false := C1.True}

(4) C (C1) { C.True := C1.True

C.False := C1.False}

(5) C  id1 oprel id2 { C.True := MakeList(nextQuad);

C.False := MakeList (nextQuad+1);
GEN('Si' id1.place oprel.op id2.place 'aller à ')
GEN('aller à ')}

(6) C  bid { C.true := makeList (nextQuad);

C.false := makeList (nextQuad +1);
GEN('Si' bid.place 'aller à ');}

Remarque.
L’action sémantique (5) produit deux instructions, un branchement conditionnel et
un branchement inconditionnel. Aucun des champs étiquette n'est rempli dans ces
deux instructions. On range l'indice de la première instruction produite dans une
liste et on donne à C.True la valeur du pointeur vers cette liste. On range la seconde
instruction produite ' aller à ' dans une liste et on donne à C.Faux la valeur du
pointeur vers cette liste.

7.3.2. Traduction des instructions de flot de contrôle

Nous allons développer un schéma de traduction pour les instructions engendrées

par la grammaire suivante:
PI P: programme
I  si C alors I C: Condition
|si C alors I sinon I I: Instruction
|tantque C faire I L:Liste d'instructions
|début L fin A: Affectation
E: expression
L  L;I
|I

C C1 ou C2
|C1 et MC2
|non C1
|(C1)
|id1 oprel id2
|bid

A  bid := C
|id := E

Sami KHALFOUI – Moez HAMMAMI – ENSI 99

2006/2007
 Production de code intermédiaire

E E+E|E*E| -E| (E) |id

Approche générale consiste à remplir les champs des instructions de branchement

quand les instructions destination sont connues.
Outre les expressions booléennes, les instructions ont besoin de listes de
branchements données par l'attribut I.next vers le code qui suit dans la séquence.

True
I  si C alors M1 I1 N sinon M2 I2

False instruction qui suit I en

ordre d'exécution

I.next = une liste contenant des numéros de quadruplets déjà générés qui sont des
branchements conditionnels et non conditionnels dont l'étiquette est manquante et
qui devraient aller à l'instruction qui suit I en ordre d'exécution.
si le contrôle passe à la fin de I1, on doit inclure à la fin de I1 une instruction de
branchement vers la fin de I. Nous utilisons le marqueur N pour produire ce saut.
N   { N.nest :=
makelist(nextSuad) GEN
('aller à ') }
N a un attribut N.next qui pointe vers la liste contenant l'unique quadruplet 'aller à '
qui a un branchement non défini
Voici maintenant les règles sémantiques:
I  si C alors M1I1N sinon M2I2 { Backpatch (C.True, M1.quad);
BackPatch (C.False, M2.quad);
I. next := Merge (I1.next, N.next, I2.next)}
M  {M.quad := nextquad)}
Nous reportons les destinations des branchements quand C est vrai dans le
quadruplet M1.quad(début I1) de la même façon, nous reportons les destinations des
branchements quand C est faux dans le debut de I2. La liste I.next englobe tous les
sauts dont la destination est située à l'extérieur de I1 et I2 ainsi que celui produit par
N.
de façon analogue false
True

I  si C alors M I
1

Sami KHALFOUI – Moez HAMMAMI – ENSI 100

2006/2007
 Production de code intermédiaire

next

Sami KHALFOUI – Moez HAMMAMI – ENSI 101

2006/2007
 Production de code intermédiaire

I  si C alors M I1 {Backpatch(C.true, M.quad);

I. next := Merge (C.False, I1.next)}

Les Boucles
True

I  Tant que M1 C faire M2 I1 

aller à
explicite false

Figure 7.6 (a)

I. début
vers C.vrai
C.code
C.vrai vers C.Faux

I1.code

aller à I.début
C.Faux

Figure 7.6 (b)

Dans l'implémentation de la figure 6 (b), les étiquettes I.début et C.vrai marquent le

début du code associé à I et le début du code associé à I1. Les deux occurrences du
marqueur M enregistrent les numéros de ces quadruplets.
Lorsque le corps de la boucle I1 a été exécuté, le contrôle retourne au début de la
boucle. Lorsque nous réduisons par la production I  Tantque M1C faire M2 I1 nous
devons effectuer la reprise arrière (Backpatch) des éléments de la liste I1.next afin de
remplir le champs destination par M1.quad.
Un branchement explicite vers le début du code de C est ajouté à la suite du code de
I1. C.true est repris en arrière afin d'atteindre le début de I1. Les branchements
depuis C.True permettent alors d'atteindre M2.quad.
I  Tant que M1 C faire M2 I1 { Backpatch (I1.next, M1.quad);
Backpatch(c.true, M2.qua);
I.next := C.false
GEN('aller à ' M1.quad)}

Sami KHALFOUI – Moez HAMMAMI – ENSI 102

2006/2007
 Production de code intermédiaire

de même pour la boucle répéter

next True

I  Repeter M1I1 Jusqu'à M2C

false

Action sémantique pour le marqueur M

M  {M.quad := nextquad)}

Action sémantique pour répéter

{ Backpatch (I1.next, M2.quad)
Backpatch (C.false, M1.quad)
I.next := C.true }

I  début L fin {I.next :=

L.next} I A {I.next := Makelist()}
L'affectation I.next := nil initialize I.next à la liste
vide. L  L1;MI {Backpatch (L1.next, M.quad);
L.next := I.next}

L'instruction qui suit L1 dans l'ordre d'exécution est le début de l'instruction I. Ainsi
la liste L1.next est reprise en arrière au début du code de I, indiqué par M.quad.
L  I {L.next := I.next}.

7.3.3. Traduction des déclarations

Dans cette sections deux grammaires différentes concernant les déclaration

1 ère Grammaire de déclaration :

D  integer NameList {Backpatch (Nalemist.next, int)}
D  real NameList {Backpatch (Namelist.next, real)
NameList  id, NameList1 { NameList.next := ADD(NameList1.next, id.place)}
| id {NameList.next := makeList (id.place)}

NameList est un non terminal qui désigne une liste d'identificateurs.

L'attribut NameList.next désigne les identificateurs déjà rencontrés et dont le type
est encore inconnu et qu'il faut backpatcher pour qu'on le trouve.
ADD(p,i) est une fonction qui ajoute i à la liste pointée par p et retourne un pointeur
sur la liste p mise à jour.

Sami KHALFOUI – Moez HAMMAMI – ENSI 103

2006/2007
 Production de code intermédiaire

2ème Grammaire de déclaration :

D integer id { Entrer (id.place, integer); D.attr :=
int} D  real id {Entrer (id.place, real); D.attr := real }
D  D1, id {D.attr := D1.attr; Entrer (id.place, D1.attr)}
(Entrer (id.place, T): recherche l'emplacement de id.place dans la table des symboles
et insère le T dans le champ type)

Sami KHALFOUI – Moez HAMMAMI – ENSI 104

2006/2007
 Bibliographie

Bibliographie
D. Thalman, « Conception et implantation de langage de programmation: une
introduction à la compilation », isbn : 0-88612-020-9, 1979.

J. Voiron, « Comprendre la compilation ».

A. Aho, « Compilers principles techniques and tools », isbn : 0-201-10194-7,

Addison- Wesley, 1986.

A. Aho, « Compilateurs:Principes, Techniques et outils », isbn : 2-10-005126-1,

Dunod, 2000.

Y. Noelle, « Traitements des langages évolués: compilateur interprétation support

d'exécution », isbn : 2-225-81368-X, Masson, 1988.

H. Glaire, « Technique de compilation », isbn : 2-85428-119-5, CEPAD, 1989.

R. Wilher, « Compilateurs (Les): théorie, construction génération », isbn : 2-225-

84615-4, Masson, 1984.

Sami KHALFOUI – Moez HAMMAMI – ENSI 105

2006/2007