Analyse lexicale

Dr. Aida Lahouij

[email protected]

1
Plan
Introduction
Analyse lexicale automatique
Analyse lexicale manuelle
Annexe

2
Introduction
Présentation de l’analyseur lexical

• La première phase d’un compilateur est : L’analyse lexicale : Elle

consiste à lire les mots du programme source afin de les regrouper
en 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.

3
Introduction
Les terminaux

• caractères)
Les terminaux sont
produits
les symboles de base (ensemble de
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 : " Bonjour "
• Identificateurs (IDF, mots-clés du langage) : if, while, break,
return, …

4
Introduction
Les terminaux

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 5
Introduction
Les terminaux

6
Introduction
Les lexèmes
 Un programme peut être vu comme une “phrase” ; le rôle
principal de l’analyse lexicale est d’identifier les “mots” de la
phrase.
 Le scanner décompose le programme en lexèmes en identifiant
les unités lexicales de chaque lexème.

7
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 : // , /* */,

8
Introduction
Par exemple, l'instruction sum = 2 + 3;
en langage C produit après analyse lexicale la liste de symboles suivante :

Valeur Catégorie lexicale

sum identifiant
= opérateur d'affectation
2 entier littéral
+ opérateur d'addition
3 entier littéral
; fin de déclaration

9
Introduction

 L'analyseur lexical ne traite en général pas les combinaisons

d’unités lexicales, cette tâche étant laissée à l’analyseur
syntaxique.
 Par exemple, un analyseur lexical typique peut reconnaître
et traiter les parenthèses mais est incapable de les compter et
donc de vérifier si chaque parenthèse fermante « ) »
correspond à une parenthèse ouvrante « ( » précédente.

10
Analyse lexicale
automatique

11
Réalisation d’analyseurs lexicaux

MÉTHODES DE CONSTRUCTION
 Un analyseur lexical peut être écrit :

 « à la main » : il faut construire l'automate fini non

déterministe à partir d'une expression rationnelle E,
puis l'exécuter pour déterminer si une chaîne d'entrée
appartient au langage reconnu par E ;
 par une table décrivant l'automate et un programme
exploitant cette table ;
 par un générateur d'analyseurs
lexicaux : Lex, Flex., ANTLR, etc.

12
Réalisation d’analyseurs lexicaux
Utilisation de flex

 Lex est un générateur de scanner.

 lex.l : fichier contenant les expressions régulières, et les actions associées.

 lex.yy.c : fichier c qui contient la fonction exécutant l'automate (scanner).

 Cette fonction est yylex(); 13

Réalisation d’analyseurs lexicaux
Quelques regexp pour quelques tokens

14
Réalisation d’analyseurs lexicaux
Description de l’outil Flex
 Flex (Fast Lexer) est un compilateur pour la génération automatique
d’analyseurs lexicaux.

 Un fichier Flex est un fichier texte qui contient la description d’un analyseur
lexical en termes d’expressions régulières et d’actions écrites en langage C.

 Le compilateur Flex prend en entrée un fichier source Flex et produit en

sortie un fichier contenant le code C (ou C ++) du future analyseur lexical.

 Le fichier C généré est nommé « lex.yy.c ».

Ce dernier doit être compilé à l’aide d’un compilateur C (gcc, par exemple)
pour obtenir le code exécutable de l’analyseur lexical.

 Un fichier Flex porte l’extension « .l » 15

Réalisation d’analyseurs lexicaux
Description de l’outil Flex

Étapes de création d’un analyseur lexical avec Flex

16
Réalisation d’analyseurs lexicaux
Description de l’outil Flex

 Une fois l’analyseur lexical est mis en œuvre, il

analyse le fichier source pour chercher les occurrences
d’expressions régulières.

 Lorsqu’un mot est reconnu, l’analyseur lexical exécute

le code C correspondant à l’expression régulière qui
dénote c

17
Réalisation d’analyseurs lexicaux
Description de l’outil Flex
 Le contenu d’un fichier Flex comprend 3 sections
séparées par une ligne contenant le symbole « %% » :

%{
/∗ Déclarations ∗/
%}
/∗ Définitions ∗/
%%
/∗ Règles ∗/
%%
/∗ Code utilisateur ∗/
18
Réalisation d’analyseurs lexicaux
/∗ Déclarations ∗/

 Contient la déclaration des variables et des fonctions globales, des

inclusions de fichiers et des expressions régulières.

 Les inclusions de fichiers et les déclarations des variables et des

fonctions globales sont mises entre les symboles « %{ » et « %} »,
chacun sur une seule ligne qui ne doit pas être indentée).

Exemple :
%{
#include<stdio.h>
#define N 100
int x = 12;
float z = 1.5; // une variable globale
int fct(int, float); // une fonction globale
%} 19
Réalisation d’analyseurs lexicaux
/∗Définitions ∗/

 Une définition permet de nommer une expression régulière.

 Une définition est un couple formé d’un identificateur et d’une
expression régulière, séparée par au moins un caractère espace (ou
tabulation).
 Une expression régulière peut contenir une référence à un identificateur
déjà défini.
 Dans ce cas, l’identificateur doit être écrit entre les symboles ”{” et ”}”.

 Une définition doit être écrite sur une seule ligne.

 CHIFFRE [0 − 9]
 ENTIER (+|−)? {CHIFFRE} +

20
Réalisation d’analyseurs lexicaux
/∗Définitions ∗/
Définition d’une expression régulière :
Syntaxe :
Nom Expression_Régulière

- « Nom » : un identificateur qui sert à nommer une expression

régulière pour l’avoir référencer ultérieurement.
- Le nom doit être non indenté.
- Une définition d’une expression régulière doit tenir sur une seule
ligne.

Exemple :
L [a-zA-Z]
D [0-9]
U "_"
Ident ({L}|{U})({L}|{D}|{U})*
21
Réalisation d’analyseurs lexicaux
/∗Règles ∗/
 Une règle Flex est la donnée :
- d’une expression régulière e.
- et d’une action (celle qui sera exécutée lorsqu’une séquence d’entrée
est reconnue par e).
 Les règles de traduction sont de la forme
p1 { action1 }
p2 { action2 }
...
pn { actionn } où chaque pi est une expression rationnelle et
chaque action est une suite d'instructions en C.

Exemples
”int” {printf (”Mot cle int”); }
A chaque fois que la chaîne de caractères ”int” sera reconnue, le
message ”Mot cle int” sera affiché sur la sortie standard. 22
Réalisation d’analyseurs lexicaux
/∗Règles ∗/

 Une expression régulière spécifie une unité lexicale du

langage source.
 Flex utilise les expressions régulières étendues. Dans Flex,
les expressions régulières sont construites à partir des
caractères et d’opérateurs.
 Les opérateurs de Flex sont :

”\[]b−?.∗+|()$/{}%<>
 Pour utiliser ces opérateurs comme caractères ordinaires, il
faut les protéger en les plaçant dans une chaîne entourée de
double-quotes (”) ou en les plaçant après un caractère \.
 Par exemple, \n, \t et \b correspondent comme en C au saut
de ligne, `a la tabulation et au retour en arrière. 23
Réalisation d’analyseurs lexicaux
/∗Règles ∗/
 Spécification d’expressions régulières avec Flex
- ” : la chaîne elle-même.
- ”abc” : spécifie la chaîne abc
- [ ] : un des ´éléments de l’ensemble.
- [abc] : a, b ou c
- [a1-a2] correspond à l'un des caractères compris entre a1 et a2, en
supposant que l'alphabet est ordonné.
- [a − z] : toutes les lettres minuscules
- . : tout caractère sauf \n.
- ∗ : zéro ou plusieurs fois (l'étoile).
- (x|y)∗ : 0 ou plusieurs caractères x ou y.
- + : un ou plusieurs fois (l’´étoile positive).
- [a − z]+ : 1 ou plusieurs lettres minuscules.
- | : l’alternance (l’union). 24
- (ab|bc) : la chaîne ab ou la chaîne bc.
Réalisation d’analyseurs lexicaux
/∗Règles ∗/
 Spécification d’expressions régulières avec Flex
- ? : opérateur d’occurrence 0 ou 1 fois.
ab?c : la chaîne abc ou a c.
- / : condition de reconnaissance.
ab/cd : la chaîne ab seulement si elle est suivie de la chaîne cd.
- $ : reconnaissance en fin de ligne.
ab$ : la chaîne ab seulement si elle est en fin de ligne.
- b : reconnaissance en début de ligne.
bab : la chaîne ab seulement si elle est en début de ligne.
- { } : répétition bornée.
a{1, 5} : les chaînes a, aa, aaa, aaaa ou aaaaa.
a{2, } : les chaînes aa, aaa, aaa, ...etc

25
Réalisation d’analyseurs lexicaux
/∗Règles ∗/

Exemple (entier de Z) :

Chiffre=0-9 : correspond à l'un des chiffre compris entre 0 et 9

Nombre=Chiffre+ : un ou plusieurs fois

Entier= - ?Nombre ? : opérateur d’occurrence 0 ou 1 fois.

26
Réalisation d’analyseurs lexicaux
/∗Règles ∗/

 Une règle se présente sous la forme :

Motif Action

 Un motif ne doit pas être indenté et les actions doivent

commencer dans la même ligne que leur motif.

Un motif est une expression régulière qui peut référencer les
expressions régulières définies dans la section des définitions.

27
Réalisation d’analyseurs lexicaux
/∗Règles ∗/

 Une action est séparée de son motif par au moins un espace (ou une
tabulation).

 L’analyseur lexical déclenche une action autant de fois qu’il trouve un

lexème qui correspond au motif associée à cette action.

 Les règles sont toutes écrites entre les deux symboles « %% ».

Exemple:
Digit [0-9]
%%
{Digit}+ printf("Un nombre\n");
"Flex" printf("Flex\n");
%%
28
Réalisation d’analyseurs lexicaux
/∗Règles ∗/

 Quelques regexp pour quelques tokens

29
Réalisation d’analyseurs lexicaux
/∗Code utilisateur ∗/

 Sera copiée telle quelle est dans le fichier « lex.yy.c ».

 Contient des routines pouvant être appelées par
l’analyseur lexical.
 Peut aussi contenir une fonction « main ».
 Section optionnelle : si elle est absente, le second
symbole « %% » peut être omis.

30
Réalisation d’analyseurs lexicaux
/∗Code utilisateur ∗/
 Pour obtenir un analyseur lexical opérationnel, les
deux fonctions complémentaires yywrap() et main ()
doivent être fournies.
 main() : est le programme principal de l’analyseur
synthétisé. Il contient l’appel de la fonction yylex().
 yylex() : analyse le contenu du flux yyin jusqu'`a
détecter une unité lexicale.
 yywrap() : contrôle l’ouverture des fichiers de texte
soumis à l’analyseur synthétisé par Lex, comme
indiqué plus haut.

31
 Réalisation d’analyseurs lexicaux
/∗Code utilisateur ∗/
 Les variables yyin et yyout :
– Ce sont des variables globales de Flex de type « pointeur vers un fichier ».
– La variable yyin pointe vers le fichier d’entrée (fichier source) à analyser.
– Par défaut c’est stdin (yyin = stdin), c’est-à-dire que l’analyseur va lire les
données à partir du clavier.
– On peut ouvrir un fichier source par l’instruction : « yyin = fopen(…); ».
– La variable yyout pointe vers le fichier de sortie (fichier cible).
– Par défaut c’est stdout (yyout = stdout), c’est-à-dire que l’analyseur va écrire
les résultats sur l’écran.
– On peut ouvrir un fichier cible par l’instruction : « yyout = fopen(…); ».
- Une fois un lexème est reconnu, l’analyseur lexical le stocke sous forme
d’une chaîne de caractères dans une variable globale appelée « yytext ».
- La longueur du lexème est également stockée sous forme d’un entier dans
une variable globale appelée « yyleng » (yyleng = strlen(yytext)).
- Il est possible de contrôler la longueur maximale d’un lexème reconnu.
32
Réalisation d’analyseurs lexicaux
/∗Code utilisateur ∗/

 Exemple : on peut spécifier la longueur maximale d’un

lexème en utilisant la macro-définition suivante :

33
Réalisation d’analyseurs lexicaux
/∗Code utilisateur ∗/
 Fonctions complémentaires de Flex
 yymore() : indique que les prochains caractères
fournis à yytext lors du prochain appel à flex doivent
être concaténés.
 Exemple: pour l’entrée « mega-octets », le code
suivant écrira ”mega-mega-octets”

34
Réalisation d’analyseurs lexicaux
/∗Code utilisateur ∗/
 Fonctions complémentaires de Flex
 yyless(i) : Renvoie tout sauf les « n » premiers
caractères du lexème courant dans le flot d’entrée, où ils
seront réexaminés quand l’analyseur recherchera la
correspondance suivante.
 Par exemple, pour l’entrée ”bonjour”, le code suivant
écrira ”bonjourjour” :

 yyterminate() : Permet d’arrêter l’analyseur lexical en

retournant la valeur 0, en indiquant le message ”all 35
done” (terminé).
Réalisation d’analyseurs lexicaux
 Fonctions utiles dans LEX

36
Réalisation d’analyseurs lexicaux
 Exemple

comptage de caractères et
de lignes
37
 Exemple

yyin = fopen(filename, "r");

38
Fonction fopen

FILE * fopen( const char * filename, const char * accessMode );

Cette fonction permet d'ouvrir un flux de caractère basé sur fichier. Vous
pouvez choisir entre différents modes d'ouverture du fichier (ouverture en
lecture, en écriture, en ajout, ...) en fonction de vos besoins.

 filename : ce paramètre permet de définir le nom du fichier à ouvrir. Vous

pouvez spécifier un chemin absolu (à partir de la racine du système de
fichiers) ou bien un chemin relatif (à partir du répertoire courant). Notez
aussi qu'en fonction du système d'exploitation considéré, le nom du fichier
sera sensible à la casse (différences entre minuscules et majuscules) ou
non.
 accessMode : ce paramètre permet de spécifier le mode d'ouverture du
fichier. Les principaux modes supportés sont :

39
Fonction fopen

FILE * fopen( const char * filename, const char * accessMode );

 accessMode : ce paramètre permet de spécifier le mode d'ouverture du

fichier. Les principaux modes supportés sont :

40
Arguments de la ligne de commande
int main(int argc, char *argv[]);
 Les arguments d'une ligne de commande sont transmis au
programme sous la forme de chaînes de caractères.
 Le séparateur des arguments est une suite non vide de caractères
d'espacement : espace ou tabulation.
 La fonction main a deux paramètres : argc de
type int et argv de type char * [].
 argc donne le nombre d'éléments de la ligne de commande,
et argv contient ces éléments sous la forme d'un tableau de
chaînes de caractères.
 argv[0] contient le nom de la commande, argv[i],
pour i allant de 1 à argc-1, le ième argument.
41
Réalisation d’analyseurs lexicaux
Résolution des conflits
 En cas de conflit, Flex choisit toujours la règle qui produit le
plus long lexème.

Exemples
”prog” action1
”program” action2

La deuxième règle sera choisie en cas de conflit.

42
Réalisation d’analyseurs lexicaux
Résolution des conflits

 Si plusieurs règles donnent des lexèmes de mêmes

longueurs, Flex choisit la première.

Exemples
”prog” action1
[a − z]+ action2

La première règle sera choisie en cas de conflit de lexèmes

ayant mêmes longueurs

43
Réalisation d’analyseurs lexicaux
Résolution des conflits
 Si aucune règle ne correspond au flot d’entrée, Flex choisit
sa règle par défaut implicite :

.|\n {ECHO}

Cette règle par défaut, recopie le flot d’entrée sur le flot de

sortie.

44
Réalisation d’analyseurs lexicaux
Table des symboles
 Flex est un outil pour la génération de scanners lexicaux en langage C.
 Il n'utilise pas directement de structure de données pour représenter la
table des symboles, mais il fournit un moyen de générer du code C pour
effectuer l'analyse lexicale, y compris la construction de la table des
symboles.
 La structure de données utilisée pour la table des symboles dépendra
donc de la façon dont vous choisissez de la représenter dans votre code
C généré par Flex.
 En général, la table des symboles est souvent implémentée sous forme
de tableau associatif (ou dictionnaire) qui associe chaque identificateur à
ses propriétés.
 Cependant, d'autres structures de données, telles que les listes
chaînées ou les tables de hachage, peuvent également être utilisées.
Rq: Nous allons étudier tout ça dans un chapitre à part
45
Analyse lexicale
« à la main »

46
Analyse lexicale « à la main »
Principe:

- Construire l'automate fini à partir d'une

expression rationnelle E,
- puis l'exécuter pour déterminer si une
chaîne d'entrée appartient au langage
reconnu par E.

47
Analyse lexicale « à la main »
Rappel:

48
Analyse lexicale « à la main »
Rappel:

49
Analyse lexicale « à la main »

50
Analyse lexicale « à la main »

51
Analyse lexicale « à la main »

52
Analyse lexicale « à la main »
Rappel: construction d’un automate d’une expression
régulière

53
Analyse lexicale « à la main »
Rappel: construction d’un automate d’une expression
régulière

54
Analyse lexicale « à la main »
Rappel: construction d’un automate d’une expression régulière
Composer deux AFN

s, t : deux regexp
 N(s) : l'automate acceptant le langage L(s)
 N(t) : l'automate acceptant le langage L(t)

 N(s|t) : l'automate acceptant le langage L(s|t)

55
Analyse lexicale « à la main »
Rappel: construction d’un automate d’une expression régulière
Concaténer deux AFN

 L'état de départ de N(st) est l'état de départ de N(s)

 Les états finaux de N(st) sont les états finaux de N(t)
 Les états finaux de N(s) sont fusionnés avec l'état initial de
N(t) : toute transition depuis l'état de départ de N(t) devient une
transition depuis l'état final de N(s). 56
Analyse lexicale « à la main »
Rappel: construction d’un automate d’une expression régulière
Répéter une AFN

57
Analyse lexicale « à la main »
Construire un AFN pour un token

58
Analyse lexicale « à la main »
Construire un AFN pour un token

59
Analyse lexicale « à la main »
Construire un AFN pour un token

60
Analyse lexicale « à la main »
Construire un AFN pour un token

61
Analyse lexicale « à la main »
Construire un AFN pour un token

62
Analyse lexicale « à la main »
Construire un AFN pour un token

63
Analyse lexicale « à la main »
Construire un AFN pour un token

64
Analyse lexicale « à la main »
Construire un AFN pour un token

 N(s) : l'automate acceptant le langage L(s)

 N(t) : l'automate acceptant le langage L(t)

 N(s|t) : l'automate acceptant le langage L(s|t)

65
 1 i 2 f 3
a-z
a-z
ε 4 5
ε 0-9
0-9
6 0-9 7
ε
0-9 0-9
ε 0-9 .
0 8 9 10
. 0-9

11
0-9
12
Est-ce que l’automate
ε est déterministe?
- - \n
13 14 15 16
a-z
blanc, etc
17
ε blanc, etc

66
any but \n
18 19
Analyse lexicale « à la main »
Passage d’un AFN à un AFD
(fermeture arrière)

67
Analyse lexicale « à la main »
Passage d’un AFN à un AFD
(fermeture arrière)

68
Analyse lexicale « à la main »
Passage d’un AFN à un AFD
(fermeture arrière)

69
Analyse lexicale « à la main »
Passage d’un AFN à un AFD
(fermeture avant)

70
Analyse lexicale « à la main »
Passage d’un AFN à un AFD
(fermeture avant)

71
Analyse lexicale « à la main »
Passage d’un AFN à un AFD
(fermeture avant)

72
 1 i 2 f 3
i a-z
a-z
ε 4 5
ε a-z
0-9

0-9 0-9
6 0-9 7
ε
0-9 0-9 0-9
ε 0-9 .
0 8 9 10
. 0-9
.
0-9
11 12
- ε
- - \n
13 14 15 16
a-z
blanc, etc
blanc, etc
17
ε blanc, etc
any but \n
73
any but \n
18 19
 1 i 2 f 3
i a-z
a-z
4 5
a-z
0-9

0-9 0-9
6 0-9 7
0-9 0-9 0-9
0-9 .
0 8 9 10
. 0-9
.
11
0-9
12
Est-ce que l’automate
-
est déterministe?
- - \n
13 14 15 16
a-z
blanc, etc
blanc, etc
17
blanc, etc
any but \n
74
any but \n
18 19
Analyse lexicale « à la main »
rappel

75
 1 i 2 f 3
i a-z
a-z
4 5
a-z
0-9

0-9 0-9
6 0-9 7
0-9 0-9 0-9
0-9 .
0 8 9 10
. 0-9
.
0-9
11 12
-

- - \n
13 14 15 16
a-z
blanc, etc
blanc, etc
17
blanc, etc
any but \n
76
any but \n
18 19
 1 i 2 f 3
i a-z
a-z
4 5
a-z
0-9
0-9
0-9 0-9
6 0-9 7 7,9
0-9 0-9 0-9
.
0-9 .
0 8 9 10
. 0-9
.
11
0-9
12
Est-ce que l’automate
-
est déterministe?
- - \n
13 14 15 16
a-z
Oui
blanc, etc
blanc, etc
17
blanc, etc
any but \n
77
any but \n
18 19
 1 i 2 f 3
i a-z
a-z
4 5
a-z
0-9
0-9
0-9 0-9
6 0-9 7 7,9
0-9 0-9 0-9
.
0-9 .
0 8 9 10
. 0-9
.
11
0-9
12 Est-ce qu’on peux
-
minimiser l’automate?
- - \n
13 14 15 16
a-z
blanc, etc
blanc, etc
17
blanc, etc
any but \n
78
any but \n
18 19
Analyse lexicale « à la main »
rappel

79
 1 i 2 f 3
i a-z
a-z
4 5
a-z
0-9
0-9
0-9 0-9
6 0-9 7 7,9
0-9 0-9 0-9
.
0-9 .
0 8 9 10
. 0-9
.
11
0-9
12 Est-ce qu’on peux
-
minimiser l’automate?
- - \n
13 14 15 16
a-z
Oui
blanc, etc
blanc, etc
17
blanc, etc
any but \n
80
any but \n
18 19
 2 f 3
i a-z

5
a-z
0-9
0-9

0-9 7,9

0-9
.
0 10
0-9
.
0-9
11 12
-

- \n
14 15 16
a-z
blanc, etc

17
blanc, etc
any but \n
81
19
Analyse lexicale « à la main »
Gestion des conflits
Un autre exemple
 Les mots-clés : "let", "in". En général, les mots-clés ne peuvent pas être utilisés
comme noms de variables. Ce parti pris évite pas mal d’ambiguïtés lors de l’analyse
grammaticale ultérieure.
 Les variables : ['A'-'Z' 'a'-'z'] ['A'-'Z' 'a'-'z' '0'-'9']*. Les noms des variables sont des
suites de lettres et de chiffres commençant obligatoirement par une lettre.
 Les entiers : ['0'-'9']+

 Les symboles : '(', ')', '+', '*', '-', '/','='.

 Un blanc : [' ' '\n' '\t']. Les caractères '\n' et '\t' sont respectivement le retour à la
ligne et la tabulation.

82
Analyse lexicale « à la main »
Gestion des conflits
Un autre exemple

83
Analyse lexicale « à la main »
Gestion des conflits
 Mais il y a encore des cas douteux :
 let pourrait être reconnu comme une variable.

 lettre pourrait aussi être reconnu comme la séquence

LET; VAR "tre"
ou encore comme la séquence VAR "let"; VAR "tre".

Ces ambiguïtés se lèvent à l’aide de règles spécifiques.

Lors de la reconnaissance d’un mot de L, on cherchera :
1. Le lexème le plus long possible.

2.à taille égale, la reconnaissance des mots-clés prime

celle des variables
84
Analyse lexicale « à la main »
Gestion des conflits
 Ces ambiguïtés se lèvent à l’aide de règles spécifiques. Lors de la
reconnaissance d’un mot de L, on cherchera :
1. Le lexème le plus long possible.

2. à taille égale, la reconnaissance des mots-clés prime celle des variables

let lettre = 3 in 1 + fin

devrait produire la suite de lexèmes :
LET;
VAR "lettre";
EQUAL;
INT 3;
IN;
INT 1;
PLUS;
VAR "fin"
85
Analyse lexicale « à la main »
Gestion des conflits

 Voici par exemple un automate qui reconnaît le mot-clé let ainsi

que les identificateurs composés simplement de lettres minuscules, le
mot-clé étant prioritaire.

m s u

86
Analyse lexicale « à la main »
Gestion des conflits

87
Analyse lexicale « à la main »
Implémentation de l’automate

L'implémentation de l'automate de l'analyse lexicale peut être réalisée

de manière
 automatique à l'aide d'outils tels que Flex ou ANTLR,

 ou manuellement en écrivant le code qui implémente les transitions

de l'automate.

88
Analyse lexicale « à la main »
Implémentation de l’automate

Les étapes générales pour implémenter manuellement l'automate de l'analyse

lexicale :

1. Identifier les différents types de jetons : La première étape consiste à

identifier les différents types de jetons que l'on souhaite reconnaître dans le
programme source, tels que des identificateurs, des nombres, des opérateurs,
des mots-clés, etc.

2. Définir les règles lexicales : Pour chaque type de jeton, il est nécessaire de
définir une ou plusieurs règles lexicales qui permettent de reconnaître le jeton
dans le programme source. Les règles lexicales sont généralement définies sous
forme d'expressions régulières qui décrivent les motifs à rechercher dans le
texte.

89
Analyse lexicale « à la main »
Implémentation de l’automate

Les étapes générales pour implémenter manuellement l'automate de l'analyse

lexicale :

3. Implémenter les transitions de l'automate : Les transitions sont des

fonctions qui prennent en entrée un état de l'automate et un caractère de la
chaîne d'entrée, et qui renvoient l'état suivant de l'automate en fonction du
caractère.

4. Stocker les jetons reconnus : Enfin, lorsque l'automate de l'analyse lexicale

reconnaît un jeton, il est stocké dans une structure de données telle qu'une liste
ou une table de hachage pour une utilisation ultérieure par les étapes suivantes
de la compilation.

90
 Analyse lexicale « à la main »
Implémentation de l’automate
 Exemple:

 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.

91
Analyse lexicale « à la main »
Implémentation de l’automate
 Exemple:
• 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).

92
Analyse lexicale « à la main »
Implémentation de l’automate
 Exemple:

• 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.

• Besoin :
- Une fonction permettant de lire le cas suivant : suivant ().
- Une procédure permettant de reculer d’un nombre de caractères de
pointeur avant: reculer().

93
Analyse lexicale « à la main »
Implémentation de l’automate
 Exemple:
/* variables */
Unsigned char cas ; Unsigned Etat ;
/* on utilise switch */
/* initialisation */
Etat=0 ;
While (1)
{
Switch (etat)
Case 0 : cas= suivant () ; If (cas== ‘> ‘) Etat=6 ;
Break ;
Case 6 : cas= suivant () ; If (cas== ‘= ‘) Etat=7 ; else Etat=8 ;
Break ;
Case 7 : printf(‘operl >= \n’) ;
Break ;
Case 8 : printf(‘operl >\n’) ; Reculer() ;
Break ; }
94
Analyse lexicale « à la main »
Implémentation de l’automate
 Exemple:

 Supposons que nous voulons implémenter un analyseur lexical pour un

langage de programmation simple qui ne prend en charge que les
nombres entiers et les opérateurs arithmétiques de base (+, -, *, /).

 Voici les étapes pour l'implémentation de l'automate de l'analyse lexicale

en C :
1. Identification des types de jetons : les nombres entiers et les
opérateurs arithmétiques.

95
Analyse lexicale « à la main »
Implémentation de l’automate
 Exemple:

2. Définition des règles lexicales :

Pour les nombres entiers, nous pouvons définir une règle lexicales sous
forme d'une expression régulière qui recherche un ou plusieurs chiffres
décimaux.

Pour les opérateurs arithmétiques, nous pouvons définir des règles lexicales
pour chaque opérateur (+, -, *, /).
•Addition : "+" +|-|*|/
1 2
•Soustraction : "-"

•Multiplication : "*"

•Division : "/"
96
Analyse lexicale « à la main »
Implémentation de l’automate
 Exemple:
3. Implémentation des transitions de l'automate :
- Une implémentation simple utilise la fonction getchar() pour lire les
caractères d'entrée de l'utilisateur, puis utilise une simple structure de
contrôle switch pour identifier les jetons de l'expression arithmétique

- Nous pouvons implémenter l'automate de l'analyse lexicale sous forme

d'une fonction qui prend en entrée une chaîne de caractères et
renvoie une liste de jetons reconnus. La fonction utilise une boucle
pour parcourir la chaîne de caractères et applique les règles lexicales
définies pour reconnaître les différents jetons.

4. Stockage des jetons reconnus : Nous pouvons stocker les jetons

reconnus dans une liste ou une table de hachage pour une utilisation
ultérieure dans les étapes suivantes de la compilation. 97
 [0-9]
[0-9]
0 1
[0-9]
+|-|*|/
+|-|*|/
2
#include <stdio.h> case 1:
if (c >= '0' && c <= '9') {

int main() { valeur = valeur * 10 + c - '0';

}
int etat = 0;
else if (c == '+' || c == '-' || c == '*' || c == '/') {
char c; printf("Nombre: %d\n", valeur);
int valeur = 0; etat = 2;
int operateur; operateur = c;
}
while ((c = getchar()) != '\n') { else {
switch(etat) { printf("Erreur lexicale\n");
return 1;
case 0:
}
if (c >= '0' && c <= '9') { break;
etat = 1; case 2:
valeur = c - '0'; if (c >= '0' && c <= '9') {
} etat = 1;
else if (c == '+' || c == '-' || c == '*' || c == '/') { valeur = c - '0';
}
etat = 2;
else {
operateur = c; printf("Erreur lexicale\n");
} return 1; if (etat == 1) {
else { } printf("Nombre: %d\n", valeur);
printf("Erreur lexicale\n"); break; }
return 1; } else {
} printf("Erreur lexicale\n");
}
return 1;
break; }
99
return 0;
}
 La ligne de code valeur = c - '0' permet de convertir un
caractère numérique ASCII en sa valeur entière
correspondante. En effet, en ASCII, les chiffres de 0 à 9
sont représentés par les codes de caractères allant de 48
(pour '0') à 57 (pour '9'). Ainsi, en soustrayant le code de
caractère de '0' (48) à un chiffre, on obtient sa valeur
entière. Par exemple, si c est le caractère '5', la valeur de
c - '0' sera 5, qui est la valeur entière correspondante.
Cette technique est couramment utilisée dans les
analyseurs lexicaux pour convertir des chaînes de
caractères numériques en leur valeur entière
correspondante.
Annexe

101
Annexe

102
Annexe

103
Merci pour votre
attention!
[email protected]

104