LA COMPILATION
Section : SMI - Semestre 5
A.U: 2020-2021
[Link]@[Link]
1
LES EXPRESSIONS
RÉGULIÈRES
26
NOTIONS DE BASE
➤ Alphabet : ensemble fini et non vide ∑ de symbols
➤ Mot ou chaine : une séquence de symboles de ∑ juxtaposés.
la longueur d’un mot w est le nombre des symboles qui le
composent et sera noté |w|
(Exemple: dans ∑={a, b, c, …,z} |abd|=3, |errahim| =7 ,
dans ∑={0, 1, espace} |01 101|=6, |0|=1 )
➤ Le mot de longueur 0 est le mot vide(ou la chaine vide) et
sera notée 𝜀
➤ Langage : ensemble (fini ou non) de mots composés
des symboles de ∑
27
NOTIONS DE BASE
➤ La concaténation de deux mots U=u1u2…un et V=v1v2…vp de l’alphabet ∑ est le mot
U.V= u1u2…unv1v2…vp où ui vj ∈∑
(Rq : |U.V| = |U|+|V| U.𝜀 = 𝜀.U=U
Ex: U=bon V=jour U.V= bonjour mais V.U = jourbon ;
La concaténation est une loi de composition interne non commutative, elle admet comme 𝜀
élément neutre)
➤ La concaténation de 2 langages L1 et L2 est le langage L1.L2 ={U.V tel que U∈ L1 et V ∈L2 }
➤ Soit ∑ un alphabet, on note ∑* et on l’appelle l’étoile de Kleene l’ensemble de toutes les
chaines possibles composées des symboles de ∑ dont 𝜀 est parmi eux.
➤ On note aussi ∑n l’ensemble des chaines de ∑ de longueur n
(Rq : ∑* =n∪
≥0
∑ n ∑n = ∑i.∑j si i+j=n
∑n est un ensemble fini mais ∑* est infini)
On définit ∑+ l’ensemble de tous les mots non vide de ∑* on peut écrire ∑*= ∑+ ∪{ 𝜀 }
28
LANGAGES RÉGULIERS
➤ Problème à résoudre: comment décrire tous les mots d’un langage ?
➤ ∃ plusieurs types de langages certains sont simples à décrire et
d’autres sont difficiles. Nous nous intéressons dans un 1er temps
aux langages réguliers.
➤ Définition: (récursive) soit ∑ un alphabet,
∅ est un langage régulier sur ∑
{𝜀} est un langage régulier sur ∑
Pour tout symbole s de ∑ { s } est un langage régulier sur ∑
Si L et H sont deux langages réguliers sur ∑
alors L∪H , L.H , L* sont des langages réguliers sur ∑
29
EXPRESSIONS RÉGULIÈRES
➤ Les langages réguliers se décrivent facilement à l’aide des expressions régulières (ER).
➤ Définition: (récursive) soit ∑ un alphabet,
ø est une ER qui décrit le langage vide ∅
𝜀 est une ER qui décrit le langage {𝜀}
s est une ER qui décrit le langage {s} où s appartient à ∑
si r1 et r2 sont des ER qui décrits respectivement les langages L1 et L2
alors r1|r2 est une ER qui décrit L1 ∪ L2
r1.r2 " " " " " " L1.L2 On peut la noter seulement par r1r2
r 1* " " " " " " L1*
➤ Dans une formule des ER s’il n’y a pas des parenthèses, on conviendra la priorité
décroissante : * , . , |
➤ Nous ajoutons l’opérateur + en posant r1+ est une ER qui décrit L1+
➤ Dans le cas où les symboles sont ordonnés on utilise l’opérateur .. : s1.. s2 pour désigner
tous les symboles qui existent entre s1 et s2 Exemple: A..E désigne A|B|C|D|E
30
EXEMPLES D’EXPRESSIONS ET DE LANGAGES RÉGULIERS
➤ 1* décrit { 𝜀, 1, 11,111, 1111, 11111, …}
➤ ab* décrit {a}. { 𝜀, b, bb, bbb, …}= {a, ab,abb, abbb, …}
➤ a(a|b)* décrit toutes les chaines composées des a et des b qui commencent
avec a {a}.{a,b}*={a,aa,ab, aab, aaa, aba, abb, aaaa,aaab,aaba,aabb,abbb, …}
➤ (a|b)*bb décrit toutes les chaines composées des a et des b qui se terminent
par bb
➤ (0|1)(0|1)(0|1)(0|1) décrit {0 , 1}.{0, 1}.{0, 1}.{0, 1}=
➤ = {00, 01, 10, 11}. {00, 01, 10, 11}= {0000,0001, 0010,0011, O100,
0101, 0110,0111, 1000,…..,1111}
➤ a|b*c décrit {a, c, bc, bbc, bbbc, bbbbc ,….}
➤ (a*|b*)* = (a|b)* =((a|𝜀 )b*)*
31
EXEMPLES
➤ ab* décrit {a, ab, abbé, abbb, abbbb, …}
➤ a*b* décrit {𝜀, a, aa, aaa, aaaa, …, b, ab, aab, aaab, aaaab, …,bb, abb, aabb, aaabb, …,
bbb, abbb, … …} ={aibj avec i, j entiers positifs}≠
{anbn n entiers positif}
➤ (ab)* ={𝜀, ab, abab, ababab, ….}
➤ (a | b |c)*(c | ø) décrit l’ensemble de toutes les chaines composées des a,b et c dont le
dernier symbole est c ={c, ac, bc, cc, bac, abc, acc, bac, bbc, bcc, bac, cbc, ccc, …}
Questions
➤ (a* | b*) = (a | b)* ? non on a seulement (a* | b*) ⊊ (a | b)*
➤ (a | b)* b = (a | b)* ?
➤ (a*b)* = (a | b)*b ?
32
Exemples :
Unité Modèle expression régulière
lexicale
suite non vide de caractères
IDENT composée de lettres, chiffres et ‘_’ [a..z|A..Z|_][a..z|A..Z|_|0..9]*
et ne commence pas par un chiffre
suite non vide de chiffre peut
NOMBRE 𝛂=0|(+|-|𝜀 )[1..9][0..9]*
commencer par ‘-‘ ou ‘+’
NOMBRE suivi d’un point suivi
REEL d’un NOMBRE suivi ou non de ‘E’ 𝛂 .𝛂((E|e)𝛂|𝜀 )
ou ‘e’ suivi d’un NOMBRE
33
DÉFINITION & PROPRIÉTÉS
➤ Un langage d’un alphabet est dit régulier s’il peut être décrit
par une expression régulière.
➤ Les langages réguliers sont stables par les opérations :
- Réunion en effet : L(r1)∪L(r2) = L(r1|r2)
- Concaténation " " : L(r1).L(r2) = L(r1.r2)
- L’étoile de Kleene " " : (L(r))* = L(r*)
ch(a..z)* (a..z)*x
34
PROBLÉMATIQUE
➤ Si les expressions régulières servent à développer
manuellement des modèles. Comment vérifier si un lexème
concorde avec le modèle d’une unité lexicale?
➤ La solution :
➤ L’utilisation des automates finis déterministes (DFA).
➤ A chaque modèle, construire un DFA, puis développer un
programme de simulation.
➤
35
LES AUTOMATES FINIS
36
AUTOMATES FINIS DÉTERMINISTES
➤ DETERMINISTIC FINITE AUTOMATA (DFA)
Fonctionnement d’un DFA
➤ La tête de lecture se déplace du gauche à droite (case par case)
➤ L’unité de contrôle change d’état selon le symbole lu
➤ Parmi les états : un désigné pour le départ, certains sont marqués finaux
➤ Le mot entré sera accepté si après l’examen de son dernier symbole, l’unité de contrôle se
trouve dans un état final.
➤ Le mot sera rejeté si l’unité de contrôle est bloquée ou s’il se trouve dans un état non final
(après l’examen du dernier symbole)
37
EXEMPLES DFA
➤ l’ascenseur
➤ le guichet bancaire automatique
➤ distributeur des boissons
➤ billetterie automatique
➤ Machine à laver
➤ Lave vaisselle
➤ …
38
