Cours : Compilation
Chapitre2 : Analyse lexicale
1
Enseignante : Fehima Achour
[email protected] L’analyse lexicale
Objectifs de ce module
En suivant ce chapitre vous allez:
Comprendre l'analyse lexicale. Être
capable de créer un petit interpréteur.
Apprendre à réaliser des automates.
Une représentation des enchaînements.
Découvrir LEX. Et savoir l'interfacer
avec un autre compilateur.
3 Plan Du Cours
I. Introduction
II. Les expressions régulières
III. Les automates
IV. Les analyses
V. LEX : outil de compilation
4 Plan Du Cours
I. Introduction
II. Les expressions régulières
III. Les automates
IV. Les analyses
V. LEX : outil de compilation
5 I. Introduction
Présentation de l’analyseur lexical
Les terminaux
Les séparateurs
L’analyseur lexical vs syntaxique
6 I. Introduction
Présentation de l’analyseur lexical
La première phase d’un compilateur est : L’Analyse lexicale : Elle consiste à lire les
caractères du programme source afin de les regrouper en terminaux (unités
lexicales), en ignorant les séparateurs.
Le résultat de cette analyse est un flot de terminaux (une suite d’unités lexicales)
qui sera ensuite transmis à l’analyseur syntaxique.
L ’analyseur lexical gère les numéros de ligne dans le programme source
pour pouvoir associer à chaque erreur rencontrée par la suite la ligne dans
laquelle elle intervient.
L ’analyseur lexical élimine les blancs et les commentaires.
7 I. Introduction
Les terminaux
Les terminaux sont les symboles de base (ensemble de caractères) produits par
l’analyse lexicale. Dans nos programmes, nous les retrouvons sous la forme :
Variables : nombre_de_clients, nom_prenom
Numériques et constantes : 1,2,3,….
Opérateurs : +, -, *, MOD, DIV,…
Marqueurs du langage : ; , != , {, }, (, ),…
Chaînes de caractères :«salut les copains»
Identificateurs (IDF, mots-clés du langage) : if, while, break, return, …
8 I. Introduction
Les terminaux
Bien que les variables et les identificateurs représentent des chaînes de caractères,
nous faisons en compilation une différence.
Variables : désigne un emplacement particulier en mémoire. Ceci s’explique que
nous pouvons retrouver plusieurs fois des variables de noms identiques, mais dans
des fonctions ou des procédures différentes.
Chaînes de caractères : sont représentées sous un contexte particulier entre les "".
Identificateurs (IDF): sont dans les langages des noms réservés ne pouvant pas
être réutilisés en variables (sauf dans certain langage exemple de Fortran). Tous les
IDF sont des noms, mais tous les noms ne sont pas des IDF.
9 I. Introduction
Les terminaux : Exemple
Exemple de terminaux contenus dans l’instruction (en Langage C)
suivante :
printf(« la valeur est %d », var);
Les terminaux sont :
Variables : var
Marqueurs du langage : ( ) , ;
Chaînes de caractères : "la valeur est"
Identificateurs : printf %d
10 I. Introduction
Les terminaux : Exemple
11 I. Introduction
Les séparateurs
Les séparateurs sont en général :
Des espaces
Des tabulations : ‘\t’
Des fins de ligne : ‘\r’ , ‘\n’
Des commentaires : // , /* */,
12 I. Introduction
L’analyseur lexical vs syntaxique
Programme source
Analyseur lexical
table des symboles
Analyseur syntaxique
La plupart du temps, c’est l’analyseur syntaxique (présenté dans le Module 3) qui sollicite
les terminaux produits par l’analyseur lexical par un simple appel .
C’est en réponse à cet appel que l’analyseur lexical lit les caractères en entrée (programme
source) pour reconnaître un terminal qu’il retourne à l’analyseur syntaxique.
Pendant toute la phase de transfert, la table des symboles est complétée.
13 I. Introduction
L’analyseur lexical vs syntaxique
Avec l’analyseur syntaxique, l’analyseur lexical a une relation du
type producteur-consommateur.
L’analyseur syntaxique appelle la procédure (coroutine) de
l’analyseur lexical lorsqu’il a besoin du terminal suivant.
Une première passe d’analyse lexicale produit une séquence de
terminaux, soit en mémoire vive, soit en fichier.
L’analyse lexicale et l’analyse syntaxique se synchronisent lorsque
le compilateur a besoin d’un terminal.
14 Plan Du Cours
I. Introduction
II. Les expressions régulières
III. Les automates
IV. Les analyses
V. LEX : outil de compilation
15 II. Expressions régulières
Définition
Exemples
Exercices
16 II. Expressions régulières
Définition
Supposons que nous voulons construire tous les IDF valides d’un
langage à partir d’un alphabet donné ?
Ce processus utilise la notation : Expression Régulière (ER) appelée
ainsi car elle correspond à des règles de constructions (méthodes par
applications).
Une ER : est un motif permettant de décrire des chaînes de caractères
ou des portions complètes de texte.
Une ER : décrit tous les langages qui peuvent être construits par
l’application des opérations sur les symboles du vocabulaire donné.
17 II. Expressions régulières
Définition
L’utilisation des ER peut comprendre
1. La recherche d’éléments dans un texte (ou un flux de données) : il s’agit de
reconnaître des éléments particuliers.
2. L’extraction d’information : il s’agit d’isoler des parties d’une chaîne de
caractères.
3. La validation de données : il s’agit de vérifier la validité d’une information.
4. La substitution et le reformatage : il s’agit de reconnaître un texte pour le
réécrire en un autre.
18 II. Expressions régulières
Définition
Exemple d’une ER de validation des variables en C :
Soit L un ensemble fini de lettres, S un ensemble de séparateurs (ensemble valide du
langage) et C l’ensemble fini des entiers de 0 à 9. Alors l’expression régulière des
variables valides en langage C vérifie qu’une variable commence par une lettre puis peut
comporter des lettres, des séparateurs ou des chiffres :
L(L+S+C)*
• Une ER se lit de gauche à droite comme une suite d’instructions.
• Le + représente la sélection, peut se noté |,ou…
• Les (, ) représentent les groupements des sous-expressions.
• Le * signifie 0 ou plusieurs occurrences de la sous-expression.
• La juxtaposition des symboles du vocabulaire, ici la juxtaposition de L et () représente
leur concaténation.
19 II. Expressions régulières
Définition
Exemple de construction (mot d’un langage) :
1. L’ER a+b dénote le langage {a,b} pour un alphabet constitué des
caractères a et b.
2. L’ER (a+b)(a+b) dénote le langage {aa, ab, ba, bb}, soit le langage
de toutes les chaînes de longueur 2 sur l’alphabet .
3. L’ER a* dénote le langage des chaînes de 0,1 ou plusieurs a, soit
{,a,aa,aaa,…}.
Remarque : IL est à noter que représente l’élément vide.
20 II. Expressions régulières
Définition
Exercices :
Sur l’alphabet constitué des lettres a et b, quels sont
les langages représentés par les ER suivantes :
1. (a+b)*
2. b*
3. a+(ab)*
21 Plan Du Cours
I. Introduction
II. Les expressions régulières
III. Les automates
IV. Les analyses
V. LEX : outil de compilation
22 III. Les automates
Les automates à états finis
Premier exemple: le tourniquet de métro
Application au langage
Automates lexicaux
Expressions régulières vs automates
23 III. Les automates
Les automates à états finis
Un automate à états finis : est en substance un graphe avec un ou
plusieurs états reconnaisseurs.
Les automates à états finis sont des reconnaisseurs qui disent « oui »
ou « non » à propos de chaque chaîne d’entrée possible.
Un automate est constitué d’un ensemble fini S d’états, d’un alphabet
de symboles d’entrée et d’une fonction de transition qui pour chaque
symbole de permet d’atteindre un état S.
24 III. Les automates
Premier exemple : le tourniquet de métro
Deux états :
Bloqué (état de départ)
Passant
Bloqué
Deux transitions :
ticket: l’introduction d’un ticket fait
passer de l’état bloqué à l’état passant ticket passage
passage: la détection du passage fait
passer de l’état passant à l’état bloqué
Passant
25 III. Les automates
Premier exemple : le tourniquet de métro
Refus
A l’automate précédent nous ajoutons
Un troisième état :
ticket
Retrait
refus non
valide
Deux transitions :
ticket non valide : fait passer de l’état Bloqué
bloqué à l’état refus
retrait : fait passer de l’état refus à ticket passage
l’état bloqué.
Passant
26 III. Les automates
Application au langage
Les langages engendrés par les expressions régulières et les
grammaires peuvent être analysés par un automate à états
finis.
Un tel automate peut se trouver dans différents états en
nombre fini.
Il change d’état selon les caractères qu’il trouve lors de la lecture
du code source à analyser.
Le changement d’état d’un automate s’appelle une transition.
Remarque : Un automate à états finis se trouve initialement
dans un état neutre.
27 III. Les automates
Application au langage
Caractères autorisés : Suite illimitée de “ba”, ER = ba(ba)*
b a
b a b a
Deux automates peuvent générer le langage ba(ba)*. Les états n’ont
pas de nom car ils n’ont pas d’intérêt en eux-mêmes.
Le nombre de séquence que l’automate accepte ou génère est infini,
du fait de la présence d’une boucle (comme le tourniquet).
L’état reconnaisseur peut contenir un ou plusieurs arcs sortant. L’état
reconnaisseur indique que l’automate peut s’arrêter, mais pas
nécessairement qu’il doit s’arrêter.
28 III. Les automates
Application au langage
a
Ici à partir du point central, deux
transitions portent l’étiquette «a»: l’automate b a
est dit non-déterministe (dit NDFA, Non
Deterministic finite State automaton).
Certains nœuds peuvent avoir plusieurs arcs
sortant portant les mêmes caractères.
b
Ici l’automate est dit déterministe (dit b a
DFA, Deterministic finite state
automaton). Tous les arcs partant d’un
même nœud correspondent à des caractères
différents
29 III. Les automates
Les automates à états finis
L’exemple des deux automates «ba(ba)*» précédents illustre le
fait que nous pouvons convertir un automate non-déterministe
en automate déterministe, engendrant le même langage. Cette
transformation ne sera pas abordée dans ce module.
Remarque : il y a une difficulté pour un automate non-
déterministe lorsqu’il s’agit de reconnaître une séquence, car il
peut prendre une direction bloquante là où il y a une solution. Il
faut alors une procédure d’aller-retour (back tracking). Il sera
préférable de faire des automates déterministes pour éviter ces
ambiguïtés et ces retours.
30 III. Les automates
Les automates lexicaux
Passons des séquences de lettres aux séquences de mots : Nous
voulons décrire un automate lexical générant les phrases
suivantes :
le chien aboie
le chat aboie
le chien miaule
les chiens aboient
les chats aboient
Exercice :
Donnez l’automate permettant d’engendrer cette grammaire.
III. Les automates
Les automates lexicaux
chat
miaule
Le
chien
aboie
chats miaulent
Les
aboient
chiens
III. Les automates
Les automates lexicaux
1. Cet automate ne permet pas les phrases «agrammaticales »
suivantes :
le chien aboient
chien chat miaulent
(etc.)
2. Cet automate est de type déterministe, à états finis
3. Cet automate engendre exactement les phrases données.
III. Les automates
Les automates lexicaux
1. L’automate suivant veut illustrer les notions de
boucle
circuit
2. Il permet maintenant les phrases suivantes :
le chien est méchant
le chien est très méchant
le loup qui mange le chien qui mange le chat est très très méchant
(etc)
Exercice :
Donnez l’automate permettant d’engendrer cette grammaire.
III. Les automates
Les automates lexicaux
chat
loup
le
est
chien
méchant
qui
mange très
35 III. Les automates
Les automates lexicaux
III. Les automates
Exercices
Reprendre les exercices des expressions:
Sur l’alphabet constitué des lettres a et b, quels
sont les langages représentés par les ER suivantes :
1. (a+b)*
2. b*
3. a+(ab)*
Et construisez les automates correspondant.
