UM5R - EMI – G.

Info

Compilation et théorie des langages

Support préparé par
D. Chiadmi - O. Diouri

Cours dispensé par D. Chiadmi

2024-2025
 Bibliographie
1- Compilers principles, Techniques and Tools.
A. V . AHO, R. Sethi, J.D. Ullman; Addison-Wesley

2- Syntax of Programming languages:Theory & Practice

R.C Backhouse. Prentice Hall International

3- Espace du cours Moodle :

[Link]

4- Livres sur [Link]

[Link] - [Link] 2 Théorie des langages et compilation

 Webographie

5- [Link]
engineering-and-computer-science/6-035-computer-
language-engineering-spring-2010/[Link]

6- Plusieurs documents existent sur le Net. En

vérifier la qualité avant de les utiliser

[Link] - [Link] 3 Théorie des langages et compilation

 Déroulement des séances de cours

À faire obligatoirement avant chaque séance:

1. Lire la partie du polycopié relative à chaque séance du cours et
prendre des notes.
2. Voir la capsule du cours relative à cette séance.

Toute participation au cours sera prise en considération dans votre

évaluation

Un quiz de 5mns à faire sur la plateforme Moodle peut être demandé

pendant quelques séances du cours
 Planning TL/Compil.
Contenu
Février 17 Introduction
Introduction
24 Besoins théoriques : Langages, expressions
régulières et Automates d’états finis
Manipulation des Automates (déterminisme)

Mars 3 Manipulation des Automates (Minimalisation)

Analyse lexicale
10 Analyse lexicale
TP
17 Analyse lexicale
TP
24 Analyse lexicale
TP
[Link] - [Link] 5 Théorie des langages et compilation
 Objectifs et compétences à acquérir
Compétences cruciales pour tout développeur ou ingénieur qui travaille sur la
conception de langages de programmation ou d'outils de traitement du langage.
1. Connaître le rôle et les phases d’un compilateur
2. Acquérir une compréhension des langages formels et des automates qui
sous-tendent les mécanismes de l'analyse lexicale
3. Maîtrise des automates et des expressions régulières
4. Comprendre les concepts fondamentaux de l'analyse lexicale
4.1 Définition des unités lexicales (UL)
4.2 comprendre les différents types d’UL dans un langage donné (mots-
clés, commentaires, chaînes de caractères, etc.).
4.3 Apprendre à écrire un analyseur lexical qui parcourt un flux de
caractères et les divise en tokens
4.4 Apprendre à gérer la table des symboles comme table de hachage
[Link] - [Link] 6 Théorie des langages et compilation
 Motivation et Intérêt de ce cours1/2
1- Fait partie des fondamentaux de l’informatique : l’architecture des
ordinateurs, les systèmes d’exploitation, etc.
2- Permet de comprendre les mécanismes internes des langages utilisés
quotidiennement. Ces mécanismes sont bien maitrisés et réutilisés dans
différents domaines de l’informatique.
3- Permet de comprendre en profondeur le processus de transformation
d’un langage de programmation en instructions exécutables
4- Développer une vision systémique de la programmation :
L'enseignement de la compilation mêle à la fois des concepts
théoriques (automates, grammaires formelles, théorie des langages)
et des compétences pratiques (implémentation d’un compilateur,
gestion de la mémoire, optimisation du code). Ce qui permet
d'aborder des problèmes complexes de manière systémique et de
comprendre comment les différents composants d'un programme
interagissent.
[Link] - [Link] 7 Théorie des langages et compilation
 Motivation et Intérêt de ce cours2/2
Avec les progrès de l'informatique et l'évolution des technologies, les
compilateurs sont devenus un outil polyvalent pour les applications,
notamment
• Optimisation de code source améliorant les performances des
applications.
• Développement de langages spécifiques au domaine, DSL tq le
traitement du langage naturel, apprentissage automatique, Green Marl
(Traitement de graphe).
• Programmation multiplateforme pour créer des programmes compatibles
avec différentes plateformes matérielles et logicielles.
• Analyse de code source et identification d’erreurs potentielles ou de
vulnérabilités de sécurité.
• Intelligence Artificielle : fondée sur les prédictions (reconnaissance)
• Optimisations (calcul des expressions, variable liveness, parallélisme, .. )

[Link] - [Link] 8 Théorie des langages et compilation

 Introduction

[Link] - [Link] 9 Théorie des langages et compilation

 Discussion ouverte

• Connaissez-vous un compilateur ?

• Dans quel contexte l’avez-vous utilisé ?

• Quelles fonctionnalités ?

D’autres questions
Les•compilateurs sont un que vous auriez
élément aimé poser ? de
clé du développement
logiciels, utilisés pour traduire le code source écrit dans
un langage de programmation en code exécutable par une
machine
[Link] - [Link] 10 Théorie des langages et compilation
 Compilateurs

code source compilateur code cible

messages d’erreurs

Elément clé du développement de logiciels,

- permet une programmation en langages de haut niveau

- traduit le code source écrit dans un langage de

programmation évolué (langage source) en code
exécutable (langage cible) par une machine

[Link] - [Link] 11 Théorie des langages et compilation

 Outil de traduction du pg source vers le pg cible

Pg source Pg cible
(C, DSL) Compilateur (Code Pentium,
java, C,..)

Messages d’erreurs

A cet effet, il doit :

– lire et comprendre le programme source
– déterminer avec précision les actions exigées
– déterminer comment les réaliser
– ordonner leur exécution

[Link] - [Link] 12 Théorie des langages et compilation

Programme en entrée Vs Programme en sortie

Pg source Pg cible
(C) Compilateur (Code Pentium)

Messages d’erreurs

Sortie : ASM
• Données : Registres, Mémoire avec un espace
d’adressage
• Code Machine : instructions Load/store; Arithmétique,
opérations sur les registres, instructions de
branchement (boucle)

[Link] - [Link] 13 Théorie des langages et compilation

 De la compilation à l’exécution ?

Le code en langage machine produit n’est pas exécutable.

Il faut encore 3 étapes supplémentaires :
• édition de liens,
• chargement
• résolution des bibliothèques

[Link] - [Link] 14 Théorie des langages et compilation

 Edition de lien (linking) en bref 1/2

Le compilateur génère des fichiers objets (FO) qui contiennent du

code machine, des données et des symboles nécessaires au programme.

L’EL crée un programme exécutable à partir de FOs :

• Combinaison : les FOs sont combinés pour créer un fichier
exécutable
• Résolution des symboles externes : les références à id (fn, var,
etc.) définie dans un FO X et utilisées dans un FO Y sont résolues
en associant chaque id à son adresse dans l'exécutable final.
 Edition de lien (linking) en bref 2/2
Gestion des adresses et décalages

Lorsqu’un FO est compilé, les adresses des variables, des fonctions et

des instructions de branchements ne sont pas définies.

➔ L’EL doit attribue des adresses et ajuste le code en conséquence

➔ Lors de la compilation, les instructions sont placées à partir de

l'adresse 0 et une table (des symboles) est utilisée pour enregistrer
les noms des variables, fonctions, et objets externes utilisés par le

programme (Ex : Printf)

[Link] - [Link] 16 Théorie des langages et compilation

 Vue d’ensemble d’un programme en C

Code source Libraires et

avec des macros fichiers objets

Préprocesseur code machine Chargeur / éditeurs de liens

cpp

Programme source Assembleur Exécutable

compilateur Programme
cc ou gcc assembleur cible

[Link] - [Link] 17 Théorie des langages et compilation

Vue d’ensemble d’un programme en Java,
XML

Code source
(ex.: .java, .xml)

Compilateur / Processeur de langage

(e.x.: javac, xml2html)

Le compilateur javac lit le fichier

Code cible
source .java et génère un ou
(ex.: .class, .html)
plusieurs fichiers .class contenant du
bytecode.

[Link] - [Link] 18 Théorie des langages et compilation

 Compilateur Vs Interpréteur
2 outils qui fonctionnent de manière très différente.

Pg source Le compilateur traduit le code source. Il

(C) Pg cible
Compilateur génère un fichier objet qui permet à l’EL
pré-traitement (Code Pentium)
de générer un exécutable (exécuté
Messages d’erreurs directement par la machine cible)

Pg source
L'interpréteur traduit le code source en
+ Interpréteur Résultat
temps réel pendant l'exécution du
Données
programme. Il parcourt le code source

machine indépendante car ne ligne par ligne et traduit chaque ligne en

génère pas de code. instructions machine avant de l'exécuter.

[Link] - [Link] 19 Théorie des langages et compilation

 Compilateur Vs Interpréteur (I)
Exécution immédiate du code
➔ développement interactif et exécution rapide de portions de
code (utile pour tests rapides, prototypage, etc.)

Portabilité des programmes écrit dans le langage cible entre

différentes plateformes

Processus de débogage simplifié

➔ l’exécution ligne par ligne facilite l'identification/la
correction des erreurs au fur et à mesure de l'exécution.

Moins de consommation d’espace disque

[Link] - [Link] 20 Théorie des langages et compilation

 Compilateur Vs Interpréteur (I)
Performance : consommation de temps processeur
➔ exécution plus lente due à l’analyse ligne par ligne à chaque
exécution

Dépendance supplémentaire par rapport aux pgs compilés

➔ exécution n’est possible que si l’I est installé sur le système.

Pas d'optimisation avant l'exécution :

➔Aucune optimisation statique n'est effectuée sur le code
avant son exécution (Pas de prétraitement)
➔Performance moindre sur les longues durées d'exécution.
[Link] - [Link] 21 Théorie des langages et compilation
 Compilateur Vs Interpréteur
Critère Interpréteur Compilateur
Vitesse
Plus lent Plus rapide (optimisation possible)
d'exécution
Très portable (si Moins portable (dépend de la
Portabilité
l'interpréteur est installé) plateforme cible)
Dépendances Dépend de l'interpréteur Prog autonome après compilation
Temps de Plus rapide pour les tests Plus long à cause de la
développement et prototypage compilation préalable
Optimisation Pas d'optimisation optimisations avant exécution
Erreurs visibles pendant Erreurs détectées lors de la
Erreurs
l'exécution compilation
Exemples Python, JavaScript, Ruby C, C++, Rust, Go, Java (bytecode)

Certains langages font recours à un compilateur puis à un interpréteur (

langages P_code) ➔ le code source est compilé générant du p_code,
lequel est ensuite interprété à l’exécution
 Qualités d’un compilateur 1/2
Plusieurs qualités sont requises pour garantir performances
optimales, compatibilité avec le langage de programmation, et une
expérience de développement fluide.

Précision : traduire du code source de manière précise et sans erreur

Rapidité : traduire le code source rapidement surtout pour les projets de taille.

Efficacité : générer un code optimisé qui maximise la performance (tps

d'exécution et empreinte mémoire).

Portabilité : générer du code porté sur plusieurs plateformes

[Link] - [Link] 23 Théorie des langages et compilation

 Qualités d’un compilateur 2/2
Convivialité : fournir des messages d'erreur clairs pour aider le programmeur.

Flexibilité : prendre en charge différentes fonctionnalités du langage de

programmation et s'adapter aux évolutions du langage.

Sécurité : détecter et éviter les erreurs de sécurité dans le code source, telles
que les dépassements de tampon et les attaques par injection de code.

Maintenance : être extensible et compatible avec des évolutions du langage.

[Link] - [Link] 24 Théorie des langages et compilation

 Vue sur le processus de « traduction »

a := i + r * 60

movf id_r, R2
???
mulf #60.0, R2
movf id_i, R1
addf R2, R1
movf R1, id_a

The book is available

???
Le livre est disponible
[Link] - [Link] 25 Théorie des langages et compilation
 Structure d’un compilateur
Analyse lexicale/Scaner
Séquence de lexèmes

Analyse Syntaxique / Parser

Structure en arbre

Analyse sémantique
Structure en arbre avec attributs

Génération de code Intermédiaire

Séquence de code intermédiaire

Optimisation du code
Séquence de code intermédiaire optimisée

Génération de code
Séquence de code objet

[Link] - [Link] 26 Théorie des langages et compilation

 Exemple
Pour présenter la structuration d’un compilateur, nous empruntons
l’exemple proposé dans Le Dragon. Voir un 2e exemple
[Link]
engineering-spring-2010/[Link]

Considérons le fragment de programme source

position = initial + rate * 60

avec position, initial et rate sont des variables de type

suivons les étapes de traitements.

[Link] - [Link] 27 Théorie des langages et compilation

 Modèle analyse-synthèse de la compilation(1)

code source
position = initial + rate * 60 table de symboles

Analyse lexicale (scanner) position id1

initial id2
unités lexicales id1 = id2 + id3 * num60 rate id3
(token)

Analyse syntaxique (parser)

arbre

[Link] - [Link] 28 Théorie des langages et compilation

Modèle analyse-synthèse de la compilation(2)
Exemple (suite)

Analyse sémantique

Génération de code intermédiaire

temp1 = int2real(60);
temp2 = id3 *temp1;
temp3 = id2 + temp2;
id1 = temp3

[Link] - [Link] 29 Théorie des langages et compilation

 Modèle analyse-synthèse de la compilation(3)
Exemple (suite)

Génération du code

Optimisation du code MOVF id3 , R2

MULF #60.0 , R2
MOVF id2 , R1
temp1 = id3 *60.0 ADD R2 , R1
id1 = id2 + temp1 MOVF R1 , id1

− Certaines de ces phases sont parfois combinées

− Ce cours se limitera à l’analyse lexicale et à l’analyse syntaxique avec génération
de code par une méthode simple (actions sémantiques).

[Link] - [Link] 30 Théorie des langages et compilation

 Commentaires

Pour répondre aux qualités requises

− Les informations ne doivent pas circuler dans un seul sens

− Les phases ne sont pas toujours exécutées l’une après l’autre

− Les structures de données (arbres …) ne sont pas toujours

construites dans leur intégralité

[Link] - [Link] 31 Théorie des langages et compilation

Besoins théoriques
Théorie des langages
 Plan
1. Langages et relations
vocabulaire, chaînes, concaténation, langages,
expressions régulières, relations
2. Automates finis
automates sans e-transitions, Automates
déterministes, Automates minimaux (principe)
3. Langages réguliers et langages d’état fini
construire un automate à partir d’une expression
régulière, retrouver le langage (ER) à partir d’un
automate

[Link] - [Link] 33 Théorie des langages et compilation

 Langages et relations

Langage ?
− Que dites vous ?
− Que dit Larousse ?
Le langage est un système qui a pour finalité de réaliser un message
d'un émetteur vers un récepteur. Cela permet d'englober plusieurs
modes de communication formalisés : langue naturelle, langages
artificiels (de programmation informatique, par exemple), ou tout
autre code : Code de la route, langage des fleurs, etc.
Chaque langue naturelle est un code original propre à l'espèce
humaine ; les langages artificiels proviennent de simplifications et de
conventions à partir des langues naturelles.

[Link]
[Link] - [Link] 34 Théorie des langages et compilation
 Langages et relations

[Link]

• Capacité, observée chez tous les hommes, d'exprimer leur pensée

et de communiquer au moyen d'un système de signes vocaux et
éventuellement graphiques (la langue, hiéroglyphe d’ancien Egypte).
• Tout système structuré de signes non verbaux remplissant une
fonction de communication : Langage gestuel. Langage animal.
• …
• Ensemble des procédés utilisés par un artiste dans l'expression de
ses sentiments et de sa conception du monde.
• Ensemble de caractères, de symboles et de règles qui permettent
de les assembler, utilisé pour donner des instructions à un
ordinateur.

[Link] - [Link] 35 Théorie des langages et compilation

 Langages et relations

I. Vocabulaire, chaînes et langages

Vocabulaire ou alphabet : un ensemble fini d’éléments

Éléments : lettres, caractères ou symboles // x , ‫ت‬, ۩, ▲, ■

# V : Cardinal du vocabulaire V // V = {۩, ▲, ■} ; # V = 3

Chaîne est une suite éventuellement vide d’éléments d’un vocabulaire

// mot ou phrase

Ex : aba est une chaîne de V = {a, b}

۩▲ ۩■ est une chaîne de V = {۩, ▲, ■}
début x:=1 fin est une chaine du vocabulaire

v= {début, x, :=, 0,..,9, fin}

[Link] - [Link] 36 Théorie des langages et compilation

Remarque :

Ambiguïté entre chaînes du vocabulaire

Ex: V= {a, aa} aaa provient de a aa ou aa a
Notations
V0 = {} où  est la chaîne vide
V1 = V // Si V = {a} alors V1 = {a }
Vn : ensemble des chaînes sur V de longueur n
V* =  Vi i 0 // Si V = {a} alors V* = {, a, aa, aaa, …}
V+=  Vi i >0 // Si V = {a} alors V+ = {a, aa, aaa, …}

[Link] - [Link] 37 Théorie des langages et compilation

Chaînes
1. |x| : longueur d’une chaîne x // | ۩▲ ۩■ | = 4

2. Sous chaîne
u sous chaîne de w si  x, y  V* tel que w = x u y
u préfixe de w si x = 
u suffixe de w si y = 

3. Opérations sur les chaînes

Concaténation de x et y notée . donne x.y ou y.x
Propriétés : associative -  x, y, z  V* x.(y.z) = (x.y).z
admet un élément neutre  -  x  V* x. = .x = x
[Link] - [Link] 38 Théorie des langages et compilation
Langages
• Un langage sur un vocabulaire V est tout sous ensemble de V *

• Ex: V={0,1}et Lg={ tous les mots de V* se terminant par 1}

• Propriétés :
Un Langage L est infini ssi  n  N,  x  L | |x| > n

• Lg est-il infini?
Répondre sur le forum sur l’espace réservé

[Link] - [Link] 39 Théorie des langages et compilation

Opérations sur les langages : Soient L, L1, L2 langages sur V
ensemblistes - L1  L2 : union
L1  L2 : intersection
L1 \ L2 : différence
L = V* \ L : complémentaire

Concaténation - L1.L2 = {x.y / x  L1 et y  L2} //Associative

Puissance - L0 = {} // langage Ø  langage {}

n>0 Ln =L. Ln-1 = L.L…L n fois

Concaténation itérée ou opérateur de Kleene

L*=  Ln n  0 et L+ =  Ln n > 0
{a }*  a* et   {} // abus de langage

[Link] - [Link] 40 Théorie des langages et compilation

II. Expression de langage ?

• Comment exprimer un langage ?

− Si petite taille : donner le vocabulaire et les
chaînes le constituant
− Si grande taille :
1) donner le vocabulaire ,
2) impossible de donner l’ensemble des chaînes

formalisme ou système de réécriture :

expressions régulières, grammaires

[Link] - [Link] 41 Théorie des langages et compilation

 Expression de langage ?

Comment reconnaître qu’une chaîne appartient au

langage ?
Comment distinguer entre les chaînes du langage et les
autres chaînes du vocabulaire V ?

Construction d’un algorithme de

reconnaissance du langage

[Link] - [Link] 42 Théorie des langages et compilation

 Expressions régulières

Les identificateurs utilisés dans les langages de programmation

recourent aux expressions régulières.

Que sait-on sur les identificateurs ?

Quelles opérations utilise-t-on ?

le langage des identificateurs C est défini par l’expression régulière

suivante : (A+B+…+Z+a+b+…+z).(A+B+…+Z+a+b+…+z+0+1+…+9)*

[Link] - [Link] 43 Théorie des langages et compilation

 Expressions régulières

Ø Est une ER décrivant le langage Ø // V : vocabulaire

 Est une ER décrivant le langage {}
Tout a  V est une ER décrivant le langage {a}
Soient r et s 2 ER décrivant les langage R et S alors:
- r + s est une ER décrivant le langage R  S
- r.s est une ER décrivant le langage RS
- r* est une ER décrivant le langage R*=  Rn n0

[Link] - [Link] 44 Théorie des langages et compilation

Exercices
Donner intuitivement une ER pour
• L1= {l’ensemble des mots sur l’alphabet {a, b, c} telle que
« jamais de ‘b’ avant la première occurrence de ‘a’ »}.
Notons que un mot sans ‘a’ ou un mot sans ‘b’ fait partie de
L1.

• L2= {l’ensemble des mots sur l’alphabet ASCI commençant

par /* et se terminant par */, et sans */ entre les deux}

[Link] - [Link] 45 Théorie des langages et compilation

Exercices suite
Écrire une expression régulière pour reconnaître chacun des cas
suivants :
1. tous les mots sur l’alphabet latin qui commencent par une voyelle et
se terminent par une consonne.
2. les adresses e-mail valides.
3. les dates au format JJ/MM/AAAA.
4. les mots sur l’alphabet latin qui contiennent exactement deux
occurrences de la sous-chaîne "abc".
5. les mots sur {a, b} dans lesquels le nombre de sous-chaînes "aba" est
impair.
 Automates
Que sait-on sur les automates ?

Que dit Larousse ?

• Machine qui, par le moyen de dispositifs mécaniques,
pneumatiques, hydrauliques, électriques ou électroniques,
est capable d'actes imitant ceux des corps animés.
• Machine et mécanisme automatiques, utilisés par exemple
pour la peinture et le soudage dans l'industrie automobile.
• …, distributeur automatique
[Link]

[Link] - [Link] 47 Théorie des langages et compilation

 Automates
Que dit ChatGPT ?
Un automate est un modèle mathématique abstrait utilisé pour décrire le
comportement d'un système. Plus précisément, un automate est une machine
qui prend en entrée une séquence de symboles, les traite selon des règles
prédéfinies, et produit une sortie.
Les automates peuvent être de différents types, en fonction de leurs
caractéristiques et de leurs fonctionnalités. Les automates finis, par exemple,
sont des machines à états finis qui sont largement utilisées pour la
reconnaissance de motifs dans les langages formels. …..
Les automates sont couramment utilisés dans les domaines de l'informatique,
des télécommunications, etc. Ils constituent un outil puissant pour la
modélisation, l'analyse ….

[Link] - [Link] 48 Théorie des langages et compilation

 Automates finis

I. Définition:
C’est un quintuplet (Q, V,  , I, F) où

Q ensemble fini d’états

V ensemble fini de symboles = vocabulaire de
l’automate
 sous ensemble de Q x V  {} x Q = ens de
transitions
I  Q sous ensemble d ’états initiaux
F  Q

[Link] - [Link] 49 Théorie des langages et compilation

transition

(p,a,q) transition où p,q Q

a
et a  V = a-transition
p q
p : origine
q : extrémité

[Link] - [Link] 50 Théorie des langages et compilation

Quelques définitions
Tout automate peut être dessiné comme suit :

a Signifie que (p,a,q)  

p q

a,b
Signifie que (p,a,q) et (p,b,q)  
p q

Marque un état initial

p

p ou p Marque un état final

p
[Link] - [Link] 51 Théorie des langages et compilation
 Exemple 1:

[0-9]

[0- 9]
• [0-9]
2

1
3
•

4
[0-9]

L’automate suivant reconnaît quel langage?

[Link] - [Link] 52 Théorie des langages et compilation
 Exemple 2
Représentation graphique
Autres notations

Représentation par une

table de transitions

[Link] - [Link] 53 Théorie des langages et compilation

Quelques définitions

• Chemin
Un chemin de A de longueur n = suite de
transitions de  / (ri , ai+1 , r i+1) pour 0 i  n a1 …an
a1 …an = trace du chemin r0 rn

Par convention, un chemin de longueur 0 est 

la transition (p,,p) p

[Link] - [Link] 54 Théorie des langages et compilation

 Quelques définitions (suite)

• Mot : un mot x est reconnu par un automate s’il existe une

trace x menant d’un état initial à un état final

• Langage : Soit A un automate,

L(A) ={ des mots reconnus par l’automate A }
L(A) = le langage reconnu par A

Un langage reconnu par un automate fini de

vocabulaire V est appelé langage d’états fini sur V

[Link] - [Link] 55 Théorie des langages et compilation

Propriétés
1. 2 automates A et B sont équivalents s’ils ont le même
vocabulaire et reconnaissent le même langage.
2. Soient A = (Q, V,  , I, F) un automate fini ; x, y  V* et
p, q deux états de A
Un chemin mène de p à q avec la trace xy   un état r
x y
p r et r q
a
Soit a  V, a est un chemin de p à q p q
chemin

 a 
  r, s Q / p r s q
chemin transition chemin
[Link] - [Link] 56 Théorie des langages et compilation
• Entrée : ER r sur V
• Sortie : AFND
• Méthode: Décomposer r en sous
expressions
1- r q r f

2- r+s q
s
f
r

q r s f
q1
3- r.s
r
 
4- r* q q1 f

[Link] - [Link] 57 Théorie des langages et compilation

2024-2025
Pour tout e  V
e
1 2

1 r 2
r+s
ε 1 r ε
2
1 3
1 s 2
ε ε
r.s

1 2 1 2

r*

1’ r
1 2 1’’
ε ε
 Exemple
• Soit 1 AFND reconnaissant des nombres réels
xx..xExx ou xx…[Link]…x
•  = {0, ... , 9, ., E}

ch ch
ch
ch
E
.
ch . ch ε

ch ch
[Link] - [Link] 59 Théorie des langages et compilation
 Autres définitions
• Un automate est complet si pour tout état q, et pour toute
lettre a, il existe au moins une transition partant de q et
portant l'étiquette a.
• q est accessible s'il existe un chemin d'un état initial à q.
• q est coaccessible s'il existe un chemin de q à un état final
• Un automate est accessible (coaccessible) si tous ses
états sont accessibles (coaccessibles).
• Un état est utile s’il est accessible et coaccessible.
• Un automate est émondé si tous ses états sont utiles

[Link] - [Link] 60 Théorie des langages et compilation

 Exercices

Donnez un automate reconnaissant chacun des langages:

1. Le langage des identificateurs

2. Le langage dont les mots contiennent au moins deux ‘a’

consécutifs sur l’alphabet {a,..,z}

3. ((a+b) a)* sur le vocabulaire {a,b}

4. (0+1)*0 sur le vocabulaire {0,1}

[Link] - [Link] 61 Théorie des langages et compilation

 Automates déterministes
Un AFD est un cas particulier d'un AFND où :
− Il y a un unique état initial
− Aucune -transition
− (q,a), qQ & aV,  au + un état successeur

On note (p,a)  l’unique état q / (p,a,q)  

Q x V → Q fonction de transition

Exemple

0 0
1 État initial
pair impair = état final
1
[Link] - [Link] 62 Théorie des langages et compilation
Propriétés

Soit A= (Q,V,  ,q0, F) automate fini déterministe

1. Pour tout état p et toute chaîne x,
x
(p,x) = q ssi  un chemin p → q
trace
2. L(A) = {x V* / (q0,x)  F}
Preuve: utiliser la propriété 1

3. Pour tout état p et toutes chaînes x,y

 (p,xy) =  ( (p,x) ,y)
Preuve: par récurrence sur la lg de y

[Link] - [Link] 63 Théorie des langages et compilation

Propriétés (suite)
Définition : L’état p est accessible pour A ssi il y a une
chaîne x sur V/ p = (q0,x)

Un automate déterministe dont tous les états sont

accessibles = initialement connecté

4. Soit R l’ensemble des états accessibles de l’AFD

A= (Q,V,  ,q0, F)

B = (R,V,  , q0, RF) est l’automate obtenu en

supprimant les états inaccessibles avec
=   (R x V x R)
Automate déterministe  A et B est initialement
connecté
[Link] - [Link] 64 Théorie des langages et compilation
 Automate déterministe: construction

Théorème 1:
Un langage reconnu par un AFND est aussi reconnu
par un AFD

Pb :
AFND ? AFD

[Link] - [Link] 65 Théorie des langages et compilation

 Principe par l’exemple

[Link] - [Link] 66 Théorie des langages et compilation

 Cas 1:
automate fini sans -transitions

Un langage reconnu par un automate fini avec

-transitions est aussi reconnu par un automate
déterministe

[Link] - [Link] 67 Théorie des langages et compilation

 Cas2: cas général
automate fini avec -transitions

Soit A = (Q, V, , q0, F) AFND,

Définition1 : { -fermeture} de

− q  Q : -fermeture(q) = { p | (q,,p) }

− S  Q : -fermeture(S) = qS -fermeture(q)

[Link] - [Link] 68 Théorie des langages et compilation

AFD Construction (suite)

Définition2 :
L’AFD B=(Q', V, , q’0 ,F'), équivalent à A, est
défini par :
− Q'  P(Q) , l'ensemble des parties de Q
− q'0 = -femeture (q0)
− F' = {S  Q| S  F   }
−  (S,a) = - fermeture{p |(q,a,p) , qS} ,  a V

[Link] - [Link] 69 Théorie des langages et compilation

 Exple : d’un AFND à un AFD
1. Partir de -fermeture de l’état initial
2. Rajouter dans la relation de transition toutes les fermetures des
nouveaux états produits avec leurs transitions
3. Recommencer jusqu’à ce qu’il n’y ait plus de nouvel état
4. Tous les états contenant au moins un état terminal deviennent
terminaux
5. Renuméroter alors les états

état a b c 

0 2 - 0 1
1 3 4 - -
2 - - 1,4 0
3 - 1 - -
4 - - 3 2

[Link] - [Link] 70 Théorie des langages et compilation

Exple : d’un AFND à un AFD
état a b c  état a b c
0,1 2,3,0,1 2,4,0,1 0,1
0 2 - 0 1
2,3,0,1 2,3,0,1 2,4,0,1 0,1,4,2
1 3 4 - -
2,4,0,1 2,3,0,1 2,4,0,1 0,1,2,3,4
2 - - 1,4 0
0,1,2,3, 2,3,0,1 2,4,0,1 0,1,2,3,4
3 - 1 - - 4
4 - - 3 2

-fermeture(0) = {0,1}
g({0,1},a) = -fermeture{2,3} = {2,3,0,1} état a b c
g({0,1},b) = -fermeture{4} = {2,4,0,1}
0’ 1’ 2’ 0’
g({0,1},c) = -fermeture {0} = {0,1}
1’ 1’ 2’ 2’
g({2,3,0,1},a) = -fermeture{2,3} ={2,3,0,1}
2’ 1’ 2’ 3’
g({2,3,0,1},b) = -fermeture{4,1} ={4,1,2,0}
3’ 1’ 2’ 3’
g({2,3,0,1},c) = -fermeture{0,1,4} ={0,1,4,2} Etc.
[Link] - [Link] 71 Théorie des langages et compilation
 Algorithme : De l’AFND à l’AFD
q'0 := -fermeture(q0) ; Q' := {q'0} ; marque(q'0) := faux ;  := ;

Tantque ( S  Q') & ( non marque (S)) faire

marque(S) := vrai ;
pour tout a  V faire
T := -fermeture({pQ | (q,a,p)   & q  S});
si T  Q' alors
Q' := Q' U {T} ; /* nouvel état*/
marque(T) := faux ;
fsi
 :=   {(S,a) → T} /*nouv. trans.*/
fpour
ftq
fin.

[Link] - [Link] 72 Théorie des langages et compilation

Exercices

Rendre déterminisme les automates de

l’exercice précédent

1. Les mots contenant au moins deux ‘a’

consécutifs sur l’alphabet {a,..,z}
2. ((a+b) a)* sur le vocabulaire {a,b}
3. (0+1)*0 sur le vocabulaire {0,1}

[Link] - [Link] 73 Théorie des langages et compilation

 Devoir à rendre :
( formez les groupes)
Le système d’immatriculation marocain est
composé de 3 champs consécutifs :
Compteur Série région
Ex : 125 ‫أ‬ 25
Avec
- Compteur entre 1 et 999999
- Série  { ‫أ‬, ‫ب‬, ‫}س‬
- Région entre 1 et 76

Ecrire un automate qui décrit un tel langage.

[Link] - [Link] 74 Théorie des langages et compilation

 Automates minimaux
Un automate déterministe A est minimal si tout
automate déterministe équivalent à A comporte au
moins autant d’états que A

Soit A= (Q,V,  ,q0,F) automate fini déterministe

• Deux états p, q de A sont équivalents (p A q)
si xV* ,  (p, x)  F  (q, x)  F

• x  V* p  q   (p,x)  (q,x)

[Link] - [Link] 75 Théorie des langages et compilation

Automate déterministe: 13 états avec
q0={0} et F={1,3,4,5,6,7,8,9,10,11,12}

[Link] - [Link] 76 Théorie des langages et compilation

 Automate minimal correspondant: 4 états
avec [q0]=A et G={C,D}

[Link] - [Link] 77 Théorie des langages et compilation

Soit (A)= (R, V, , [q0], G) Où

• R : ens des classes d’équivalence de la relation ‘’

• G : ens des classes d’équivalence des états de F

• [q] : classe d’ de q pour la relation ‘’

• ([p],a) = [(p,a)] pour a V , pQ

Si A automate déterministe minimal alors A est initialement

connecté et ses états sont 2 à 2 non équivalents

Unicité de l’automate minimal

[Link] - [Link] 78 Théorie des langages et compilation

Construction d’un automate minimal équivalent à un
automate donné (1)

Soit A= (Q,V,  ,q0 ,F)

1. Enlever les états inaccessibles de A

 B = (R, V, , q0, G)
2. Calculer la congruence ‘’ pour B : p, q  Q

Rappel : p  q ssi xV*, (p,x)  G  (q,x)  G

[Link] - [Link] 79 Théorie des langages et compilation

 Construction d’un automate minimal équivalent à un
automate donné (2)

3. Construire l’automate minimal noté

 (B)= (S, V, , [q0], H)
Où
 S ens des classes de la relation ‘’
 H ens des classes des états de G
 ([p],a) = [(p,a)] a V , p R

[Link] - [Link] 80 Théorie des langages et compilation

Nous avons les propriétés suivantes: (3)

1.  k  0 ‘k’ est une relation d’équivalence

p k q   x  V* / |x|  k et (p, x)  G  (q,x)  G
1. p 0 q ssi p  G  q G
2.  k0, p k+1 q ssi p k q et a  V / (p,a) k
(q,a)
3.  k  0 k+1  k
4.  = k0 k

1. Si n est le nb d’états de l’automate B alors

 K  n  ‘k’ = ‘k+1’ = ‘

[Link] - [Link] 81 Théorie des langages et compilation

A = ({S0,..S9}, {a,b},  , S0, {S2, S4, S5, S8}) ; la relation de transition  :

s0 s1 s2 s3 s4 s5 s6 s7 s8 s9
a s9 s6 s1 s0 s2 s7 s7 s7 s5 S3
b s8 s1 s9 s4 s9 s3 s7 s1 s3 s4

s0 s1 s2 s3 s4 s5 s6 s7 s8 s9

a s9 s6 s1 s0 s2 s7 s7 s7 s5 s3
b s8 s1 s9 s4 s9 s3 s7 s1 s3 s4
s0 s1 s2 s3 s4 s5 s6 s7 s8 s9
a s9 s6 s1 s0 s2 s7 s7 s7 s5 s3
b s8 s1 s9 s4 s9 s3 s7 s1 s3 s4
[Link] - [Link] 82 Théorie des langages et compilation
A = ({S0,..S9}, {a,b},  , S0, {S2, S4, S5, S8}) ; la relation de transition  :

s0 s1 s2 s3 s4 s5 s6 s7 s8 s9
a s9 s6 s1 s0 s2 s7 s7 s7 s5 S3
b s8 s1 s9 s4 s9 s3 s7 s1 s3 s4
Etape 1 - 2 classes d’  : les états finaux et les états non finaux
{ S2, S4, S5, S8} et {S0, S1, S3, S6, S7, S9}
Etape 2 – on traite la classe { S2, S4, S5, S8}

a
S4 S2, S4, S5, S8
a
S8 b
b la classe {S2, S4, S5, S8}
S2
a,b est divisée en 2 : {S4, S8}
S0, S1, S3, S6, S7, S9 et {S2, S5}
S5
a,b

[Link] - [Link] 83 Théorie des langages et compilation

A = ({S0,..S9}, {a,b},  , s0, {s2, s4, s5, s8}) ; la relation de transition  :

s0 s1 s2 s3 s4 s5 s6 s7 s8 s9
a s9 s6 s1 s0 s2 s7 s7 s7 s5 S3
b s8 s1 s9 s4 s9 s3 s7 s1 s3 s4

Etape 3 – on traite la classe {s0, s1, s3, s6, s7, s9}

b
s0
b
s2, s4, s5, s8
s3 b
a
s9 a a la classe {s0, s1, s3,
s1 a,b s0, s1, s3, s6, s7, s9
s6, s7, s9} est divisée
s6 a,b en 2 : {s0, s3, s9} et
s7 a,b {s1, s6,s7}

[Link] - [Link] 84 Théorie des langages et compilation

A = ({S0,..S9}, {a,b},  , s0, {s2, s4, s5, s8}) ; la relation de transition  :

s0 s1 s2 s3 s4 s5 s6 s7 s8 s9
a s9 s6 s1 s0 s2 s7 s7 s7 s5 S3
b s8 s1 s9 s4 s9 s3 s7 s1 s3 s4

Etape 4, 5, etc. on traite les classes restantes une à une

s4, s8 a s2, s5
S’0 S’1 S’2 S’3
b a S’0 S’1 S’1 S’2
b b a
b S’3 S’1 S’0 S’0
a,b
a s0, s3, s9 s1, s6, s7

[Link] - [Link] 85 Théorie des langages et compilation

Exemple minimisation:

𝞭 1 2 3 4 5 6 7 8
a 2 3 6 3 8 3 8 8
b 4 5 1 7 6 6 6 7

≡0 [1,2,3,4,5,6,7] ; [8] ([1,. . .,7] et [8] sont séparés par ε).

≡1 [1,2,3,4,6] ; [5,7] ; [8] ([1,2,3,4,6] et [5,7] sont séparés par a).
≡2 [1,3,6] ; [2,4] ; [5,7] ; [8] ([1,3,6] et [2,4] sont séparés par b).
≡3 [1] ; [3,6] ; [2,4] ; [5,7] ; [8] ([1] et [3,6] sont séparés par a).
≡4 [1] ; [3] ; [6] ; [2,4] ; [5,7] ; [8] ([3] et [6] sont séparés par b).

≡4= ≡5 d’où ≡ = ≡4.

 Langages d’états finis et langages réguliers

Tout langage régulier sur V est un langage d’états finis

sur V

Un automate fini est simple s’il n’admet qu’un état initial

et qu’un état final et aucune transition n’a comme
extrémité l’état initial ni comme origine l’état final

Tout langage régulier sur V admet un automate fini

simple

[Link] - [Link] 87 Théorie des langages et compilation

 Tout langage d’états fini sur V est un langage régulier sur V

Définition : système d’équation associé à un automate fini

• A = (Q,V, , I, F) automate fini

• q1, .. , qn liste sans répétition des états de A

• i,j = { a  V  {} / (qi, a, qj )   1  i,j  n }

• x1, .. , xn : n variables non éléments de V

Le système d’équations sur V pour 1  i  n

n
xi =  +  i,j xj si qi  F
j=1

n
xi =  i,j xj si qi  F
j=1

[Link] - [Link] 88 Théorie des langages et compilation

Ce système a pour plus petite solution :
x1= L(A1), .. , xn= L(An) pour 1  i  n
Ai = (Q,V, , qi, F)
Théorème :
Si ,  deux langages sur V et x  V alors :

x = .x + admet comme plus petite solution x=*

Ex: si x = L  *  L

Un langage d’états fini sur V SSI un langage régulier sur V

L = L(A) =  L(Ai) =  langages réguliers = régulier

iI. iI

[Link] - [Link] 89 Théorie des langages et compilation

Exemple: Soit l’automate A

[Link] - [Link] 90 Théorie des langages et compilation

Solution du système d’équations: Langage reconnu
par l’automate A

Notation: | = +

[Link] - [Link] 91 Théorie des langages et compilation

 Exercice (5 min)

• Ecrire ER et automate reconnaissant le langage sur

a et b : tous les mots qui n’ont pas plus de 4a
consécutifs.

• Dire si l’automate obtenu est déterministe et s’il

est minimal

[Link] - [Link] 92 Théorie des langages et compilation

• Ecrire ER et automate reconnaissant le langage sur a et b : tous les mots
qui n’ont pas plus de 4a consécutifs.

• Dire si l’automate obtenu est déterministe et s’il est minimal

[Link] - [Link] 93 Théorie des langages et compilation

Analyse lexicale
 Analyse lexicale

• Rôle et Fonctions
• Unité lexicale
• Implémentation
• Algorithme

[Link] - [Link] 95 Théorie des langages et compilation

 Rôle de l’analyseur lexical(1)

− L’analyseur lexical lit une séquence de caractères et produit

une séquence de tokens ou unités lexicales

token Analyseur
Code Analyseur
source lexical syntaxique
next
token

Table de Analyseur
symboles sémantique

Code cible
−

[Link] - [Link] 96 Théorie des langages et compilation

 Rôle de l’analyseur lexical (2)
Terminologie
• lexème : mot du pg source (abc a1 if 125 )
• UL (token) : classe de lexème (id id id num )
• Patron : règle associée à chaque UL

Afin d’optimiser le
L'analyseur lexical doit tps d’exécution, il
est préférable de
faire du 2 en 1 !
• Isoler un lexème (Scanner) Isoler et
• Le reconnaitre reconnaître avec
le même
traitement grâce
au patron

[Link] - [Link] 97 Théorie des langages et compilation

 Rôle de l’analyseur lexical (3)
- Dans le cas des id et des cstes numériques, nous devons transmettre
Un compilateur commence par transformer le flux de
à l’analyseur syntaxique l’UL plus une info supplémentaire appelée
caractères d'entrée en une suite d'entités plus
attribut.
abstraites.
- Attribut : permet de sauvegarder une info disponible à ce stade de
l’analyse. IlProg source
est utilisé lorsque l’UL ne peutunités
décomposer lexicales
pas se décrire de manière
complète. Ex : l’UL + ou ) ne nécessite pas une description
supplémentaire alors que l’UL opérateur n’est pas suffisante, il faut
direEntrée : opérateur
de quel a = a*(b+1)
il sa’git : opérateurSortie
(+) : id (a)
=
id (a)
*
(
id (b)
+
num (1)

[Link] - [Link] 98 Théorie des langages et compilation

 C’est quoi une unité lexicale ?

• Une unité lexicale (token) est une séquence de caractères

pouvant être traitée comme une « classe » de la grammaire d’un
langage de programmation.

Type de token Séquence de caractères

ID x, rate, position
NUM 60, 10
REAL 60.0
IF if
WHILE while
SEMI ;
LPAREN (
RPAREN )

[Link] - [Link] 99 Théorie des langages et compilation

 C’est quoi une UL ?
− Mots clés : les UL comme IF, WHILE. Ils sont souvent
réservés.

− UL incluent identificateurs, mots-clés, nombres et

séparateurs ou terminaisons d’instructions (Ex : /*). Ils
s’agit des symboles terminaux d’une grammaire d’un
langage de programmation.

− Analyseur lexical ignore (en général) les espaces entre les

UL et les commentaires
[Link] - [Link] 100 Théorie des langages et compilation
 Comment identifier une UL ?

− UL sont décrites en utilisant la notation formelle des

expressions régulières.

− analyseur lexical identifie les UL en utilisant -les

outils formels- les automates (à états) finis.

analyseur lexical

[Link] - [Link] 101 Théorie des langages et compilation

 Analyseur lexical : fonctions

Structures de données utilisées :

− unités lexicales
− table des symboles
− table des mots clefs (si reconnu comme identificateur)

Fonctions d'accès à la TS :
– permet la recherche ou l'ajout d'un identificateur

[Link] - [Link] 102 Théorie des langages et compilation

 Analyse lexicale : Fonctions (2)

• F1 : Fournir des messages d'erreurs

• F2 : Fournir des attributs quand c’est nécessaire (UL, attribut)

• F3: Éliminer les séparateurs et les commentaires

• F4: Reconnaître les (groupes) caractères spéciaux tel que ++, ==

• F5: Reconnaître les constantes (entiers, réels, chaînes)

• F6: Reconnaître les identificateurs1

• F7: Reconnaître les mots clés

[Link] - [Link] 103 Théorie des langages et compilation

 Analyse lexicale : F1

Lorsque aucune ER ne peut être associée à une suite de

caractères en entrée, aucune UL n’est reconnue et par
conséquent, un message d'erreur doit être retourné.

[Link] - [Link] 104 Théorie des langages et compilation

 Analyse lexicale : F2

Lorsque l’information véhiculée par une UL est

incomplète, on a recours aux attributs pour
véhiculer cette information aux phases ultérieures
du compilateur (analyse syntaxique, …)

[Link] - [Link] 106 Théorie des langages et compilation

 Attributs - Explication :
• Dans le cas des symboles <=, >=, <, >, <>, l'analyseur syntaxique
a juste besoin de savoir qu’il s’agit de l’UL OPREL (opérateur
relationnel). C'est lors de la phase de génération de code
qu’il est nécessaire de distinguer < de <= par exemple.

• Dans le cas des identificateurs de variable, l'analyseur

syntaxique a juste besoin de savoir qu’il s’agit de l’UL IDENT.
Les phases ultérieures auront besoin de plus d’informations :
l'adresse mémoire pour le générateur de code, le type pour
l'analyseur sémantique, etc.

Une information supplémentaire est donc requise : Attribut.

[Link] - [Link] 107 Théorie des langages et compilation

 Analyse lexicale : F3
- Séparateurs et commentaires inclus dans le texte du pg n’ont d’intérêt que
pour le développeur (lisibilité, description, etc.). Dans le cas du compilateur
C, un pré-processeur les élimine avant de commencer la compilation. Une
optimisation du tps de compilation consiste à faire cette élimination par
l’analyse lexicale. Dans ce cas, une ER leur est associée et permet de
reconnaître et isoler un commentaire ou un séparateur qu’il ne transmet pas
au syntaxique. Ce n’est donc pas une UL.

Un espace blanc peut être :

- Un caractère blanc, une tabulation, un retour à la ligne
- Des commentaires: une séquence quelconque de caractères entre /*…*/.

[Link] - [Link] 108 Théorie des langages et compilation

 Analyse lexicale : F4
Pb : comment distinguer entre

l’UL <= et les 2 UL < et =

l’UL ++ et les 2 UL + et +

Réponse : Isolation du préfixe le plus long.

Lors du traitement, on trouve < on ne décide que si le caractère qui

suit ne donne pas une UL connue

[Link] - [Link] 109 Théorie des langages et compilation

 Analyse lexicale : F5

Pb : une constante a une valeur. Si au niveau du syntaxique il suffit

de savoir que c’est une constante, lors de la génération du code, on
aura besoin de sa valeur. Besoin d’attribut

-F5.1 - entières ou réelles

- Un attribut valeur est transmis avec l’UL. Exple num (10)

-F5.2 - chaînes de caractères

- Vue la taille d’une chaîne de caractères, on a souvent recours

à une table appelée table des constantes

[Link] - [Link] 110 Théorie des langages et compilation

 Analyse lexicale : F5
- F5.2 - chaînes de caractères : Vue la taille d’une chaîne de
caractères, on a recours à une table des constantes
- Entrée : « bonjour »
− L’ER associée à la chaîne permet d’isoler/de reconnaître une
chaîne.
− La valeur est mise dans une table de type caractère

.. b o n j o u r a v e c

Attributs possibles :
− Indice de début et indice de fin
− Indice de début et longueur
− Indice de début avec sentinelle entre les chaînes

[Link] - [Link] 111 Théorie des langages et compilation

 Analyse lexicale : F6

Pb : +sieurs informations sont associées à un id.

- Identifie quoi : une variable, un type, une fonction, …

- si variable : simple ou composée ?

- si simple : quel type ? Quelle adresse mémoire ? …

- si tableau : nb d’éléments ? Indice du 1e élément ? Indice du

dernier élément ? Type des éléments ? …
La table des symboles stocke toutes ces infos au
moment où elles sont disponibles (pas ttes au niveau
lexical)

[Link] - [Link] 112 Théorie des langages et compilation

 Analyseur lexical : F6
(récapitulation)

Les identificateurs :
peuvent avoir différentes utilisations :
− variable
− procédure / fonction
− nom de type (pb des types prédéfinis à initialiser)
− constante
peuvent avoir des attributs :
− type
de base (entier, réel, booléen...)
construit ( pointeur, tableau, structure, ....)
− taille (tableau, structure)
− 'adresse' (relative au début d'une zone de donnée)

[Link] - [Link] 113 Théorie des langages et compilation

 Analyse lexicale : F6
Table des symboles :

Une table qui stocke toutes les infos relatives aux id.

Vu le nb d’id dans un pg, le nb d’accès à cette table est élevé. Aussi,

pour des raisons d’optimisation, utilise-t-on le hash-code.

- Une fonction est appliquée sur le lexème pour trouver un indice

-Traitement des collisions

Travail à rendre :

1. algorithme de gestion de la table des symboles (dans 7 jours)

2. Implémentation en TP
[Link] - [Link] 114 Théorie des langages et compilation
 Table h-code
2 règles :
− taille de la table ~ 2* nb d’UL (nb premier)
− fonction qui calcule la clé
Exemple : Σ des codes ASCii pondérés mod taille
Ajouter id dans TS :
1. Calcul de la clé
2. Accès à T[clé] : ( soit libre, soit pleine)
• Si vide : ajouter lexème et attribut(clé)
• Sinon recherche de la 1e case vide après clé (soit clé1),
ajouter lexème au niveau de clé1 et attribut (clé1)
Chercher id dans TS :
Calculer clé
si vide : n’existe pas
si pleine : soit ‘=‘ donc trouvé, soit ‘≠’ donc recherche jusqu’à
la 1e case vide ou trouvé

[Link] - [Link] 115 Théorie des langages et compilation

 Exemple de fonction de hachage

int F(char lexeme[]){

int i,cle=0;
for(i=0;lexeme[i]!='\0';i++)
cle=cle+lexeme[i]*(i+1);
return cle;

[Link] - [Link] 116 Théorie des langages et compilation

 Analyse lexicale : F7

Pb : l’ER associée à un identificateur, ne peut distinguer

entre un mot clé (si, sinon, alors, …) et un identificateur
(alpha, x, a156, … )

Solution : initialiser la table des symboles par les

mots clés

[Link] - [Link] 117 Théorie des langages et compilation

 Analyse lexicale : F6+F7
Entrée : si alpha = alpha …
si Mot clé

- Si est d’abord reconnu comme un id

- recherche dans la TS retourne mot clé alors Mot clé

- alpha est reconnu comme un id alpha id

- Recherche dans la TS négative

- Ajout dans la TS

[Link] - [Link] 118 Théorie des langages et compilation

 Analyse lexicale : F6+F7
Entrée : si alpha = alpha …
si Mot clé

- = est reconnu comme un signe d’affectation

(non concerné par la TS) alors Mot clé

- alpha est reconnu comme un id

alpha id
- Recherche dans la TS positive

- Pas d’ajout dans la TS

[Link] - [Link] 119 Théorie des langages et compilation

 Table symboles

code source
Entier position table de symboles
Si position == initial alors initial = rate * 60
Traitement de entier
entier Mc
Traitement de position Mc
si Mc
Traitement de si position Id
Mc
Traitement de position

Etc.

[Link] - [Link] 120 Théorie des langages et compilation

 Table symboles : gain
La manipulation de la TS à ce niveau permet de traiter la déclaration
des id sans « effort » supplémentaire :

Id ?

Existe dans TS N’existe pas dans TS

Mc Id Zone Déclaration

Zone Déclaration Zone Instruction

Zone Instruction
Erreur : db Erreur : non
déclaration Ok Ok déclaré

[Link] - [Link] 121 Théorie des langages et compilation

 Analyse lexicale : Implémentation
UL
analyseur analyseur
Pg source syntaxique
lexical
obtenir UL
svte

table des symboles

Id/MC

• Basé sur les AEF ou les expressions régulières

• Plus simple qu'un analyseur syntaxique
• "esclave" de l' analyseur syntaxique
• scanner / parser

• { UL} reconnues par un Scanner est un langage régulier

• Machines qui reconnaissent des LR sont des AFND (AFD)
• Matrice de transition : Tableau bidimensionnel indexé par
l’état courant & le car. en entrée (pb : matrice creuse)

[Link] - [Link] 122 Théorie des langages et compilation

 Exemple: calculette
• Id: suite de caractères alphanumériques dont le
1er est alph.
• Num: suite de chiffres
• Res: =
• Opérateurs arithmétiques: +, -, *, /, mod
• Commentaire: /* … */
Travail à faire:
1. ER Règle: 2UL peuvent être
2. Automate Séparées par 0, 1 ou plusieurs
blancs Ou commentaires
3. Automate global
4. Matrice de transition
5. Écriture du programme

[Link] - [Link] 123 Théorie des langages et compilation

 Analyse lexicale : Noyau de l’alg.
Extraction du plus long préfixe

Q = Q0;
car = carsuiv; trans = vrai ;
TQ (trans & non fin de Entrée) Qu’est ce qui manque à
Qp = Q; ce noyau ?
Q = M(Q,car);
car = carsuiv;
trans = (Q <> -1)
…...
FTQ
si Q/Qp est un état final alors return “ OK….. ”
sinon return “ erreur ”

[Link] - [Link] 124 Théorie des langages et compilation

 Analyse lexicale : Sorties
sortie = UL (entier+valeur associée) :

– mot clef : if, then, else, while, for, main ...

rend le mot clef (ou un n° correspondant)
– opérateur : +,-,*,<,<=,=,==,& ...
rend l’UL ou le n° correspondant
– identificateur :
rend l’UL "ident" ou le n° correspondant et l'indice d'entrée
dans la table des symboles comme attribut
– constante :
rend l’UL « cste » ou le n° correspondant avec comme
attribut la valeur de la constante ou un indice d'entrée dans
une table de constantes

[Link] - [Link] 125 Théorie des langages et compilation

 Générateur automatique d’analyseur lexical

• Il y a un procédé systématique pour faire

correspondre un analyseur lexical à n’importe quel
expression régulière.
• Trois étapes:
− Expression régulière → AFND
− AFND → AFD
− AFD → programme généré du scanner
• Cela peut être automatisé dans un générateur de
scanner

[Link] - [Link] 126 Théorie des langages et compilation