II. Analyse Lexicale. 4ème Cours.
II.1 Expressions régulières.
Une expression régulière notée r dénote un langage L(r). Soit un alphabet ∑, les règles
définissant les expressions régulières sont :
• ɛ est une expression régulière qui dénote l’ensemble {ɛ}.
• Si a est un symbole de ∑, alors a est une expression régulière qui dénote l’ensemble {a}.
• Supposons que r et s sont des expressions régulières dénotant les langages L(s) et L(r),
alors :
- (r) est une expression régulière dénotant L(r).
- (r)|(s) est une expression régulière dénotant L(r) U L(s).
- (r)(s) est une expression régulière dénotant L(r)L(s).
- (r)* est une expression régulière dénotant (L(r))*.
N.B :
- Un ensemble régulier est un langage dénoté par une expression régulière.
- L’opérateur * a la plus haute priorité (associatif à gauche).
- La concaténation a la deuxième haute priorité (associative à gauche).
- | « ou » a la plus faible priorité (associatif à gauche).
Exemple :
(a)|((b)*(c)) <==> a|b*c
II.2. Définitions régulières.
Si ∑ est un alphabet de symboles de base, une définition régulière d est une suite de
définitions de la forme :
d 1 → r1
d 2 → r2
…..
d n → rn
Où : di : Nom distinct, ri : Expression régulière sur ∑ U {d1, d2, …, di-1},
N.B : Dans les expressions régulières, les noms des symboles sont écrits en gras.
- Propriétés algébriques des expressions régulières.
- r|s = s|r (Commutativité)
- r|(s|t) = (r|s)|t (Associativité)
- (rs)t = r(st) (Associativité)
- r(s|t) = rs|rt (Distributivité)
- (s|t)r = sr|tr (Distributivité)
- ɛr = rɛ = r (Elément neutre)
- r = (r| ɛ)
* * (Relation entre ɛ et *)
- r** = r* (Idempotent)
- Notations abrégées.
• + : Signifie « au moins une instance de », la même priorité et la même associativité que *.
Exemples :
- Si r est une expression régulière dénotant le langage L(r), alors r+ est expression régulière
dénotant le langage (L(r))+.
- L’expression régulière a+ dénote l’ensemble de toutes les chaînes d’au moins un a.
• r* = r+| ɛ et r+ = r r* : Reliaison entre les opérateurs de fermeture positive et de Kleene.
• ? : Signifie « Zéro ou une instance », r ? = r | ɛ
II. Analyse Lexicale. 4ème Cours.
Exemples :
- Si r est une expression régulière, alors (r) ? est une expression régulière dénotant le
langage L(r)U{ ɛ }.
• Classes de caractères : Si a, b et c sont des symboles d’alphabets, la notation [abc] dénote
l’expression régulière a|b|c. La classe de caractères [a-z] dénote l’expression régulière
a|b|…|z.
II.2 Diagrammes de transition.
Ils sont produits pendant la construction d’un analyseur lexical, ils décrivent les actions qui
sont réalisées quand l’analyseur syntaxique demande la prochaine unité lexicale de l’analyseur
lexical.
Exemple :
Soit la définition régulière suivante :
Oprel → < | <= | = | <> | > | >=
L’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 en utilisant la table suivante :
Expression régulière Unité lexicale Valeur d’attribut
< Oprel PPQ
<= Oprel PPE
= Oprel EGA
<> Oprel DIF
> Oprel PGQ
>= Oprel PGE
Table II.4. Exemple des propriétés d’une expression régulière.
Voici le diagramme de transition pour les opérateurs de relation :
Début < =
0 1 2 Retourne (Oprel, PPE)
>
3 Retourne (Oprel, DIF)
Autre 4 * Retourne (Oprel, PPQ)
= 5 Retourne (Oprel, EGA)
> 6 = 7 Retourne (Oprel, PGE)
Autre 8 * Retourne (Oprel, PGQ)
Figure II.5. Exemple d’un diagramme de transition pour les opérations de relation.
II. Analyse Lexicale. 4ème Cours.
Explications :
On va prendre une partie du diagramme (les transitions : 067 et 068 pour respectivement
les modèles : >= et >) pour expliquer le fonctionnement d’un diagramme de transition. L’état
de départ du diagramme est l’état 0. Dans l’état 0, on lit le prochain caractère d’entrée. On
suit l’arc > depuis l’état 0 vers l’état 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 (unité lexicale >=
reconnue). Si on progresse dans la suite d’arcs depuis l’état de départ jusqu’à l’état
d’acceptation 8, on devait lire le caractère > avec un autre caractère, dans ce cas, on doit
reculer le pointeur avant d’un caractère (le signe * dans un état indique : le recul doit être fait).