emmesse

un langage est un ensemble de chaînes de symboles issus d'un alphabet. Avec ces langage, on peut en construire d'autres grâce à ces opérations:



par exemple, soit "L" l'ensemble des lettres et "C" l'ensemble des chiffres. Le langage L(L U C)* est l'ensemble des chaînes de lettres ou de chiffres commençant par une lettre.
Pour décrire ces langages, on peut utiliser ce que l'on appelle des expressions régulières. Par exemple l'expression régulière désignant un identificateur est la suivante:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

l(l|c)*

La barre verticale représente l'union, les parenthèses sont utilisés pour regrouper les sous-expressions. L'étoile signifie "zéro, une ou plusieurs occurrences de ". La juxtaposition de l avec le reste de l’expression est la concaténation.
Chaque expression régulière r dénote le langage L(r).
voici les règles qui définissent les expressions régulières sur un alphabet Σ et les langages que dénotent ces expressions:
1. ε est une expression régulière et L(ε) est {ε}, le langage dont le seul membre est la chaine vide
2. si a est un symbole appartenant à Σ, alors a est l'expression qui dénote le langage L(a)={a}, c'est à dire le langage comportant une seule chaîne, de longueur un, avec a en première et unique position.
soit r et s des expressions régulières dénotant respectivement les langages L(r) et L(s). Il existe quatre opérations sur les expressions régulières:
1. (r) | (s) dénote le langage L(r) U L(s)
2. (r)(s) dénote le langage L(r)L(s)
3. (r)* dénote (L(r))*
4. (r) dénote L(r), c'est à dire que l'on peut ajouter des paires de parenthèses autour d'un expression régulière sans changer le langage qu'elle dénote.

l'union est commutative : r|s = s|r
l'union est associative : (r|s)|t = r|(s|t)
la concaténation est associative : r(st) = (rs)t
la concaténation est distributive par rapport à l'union : r(s|t)= rs|rt; (s|t)r = sr|tr
ε est l'élément neutre de la concaténation εr = rε = r
ε est inclus das une fermeture : r* = (r|ε)*
* est idempotent : r**=r*

priorités des opérateurs
1. L'opérateur unaire * a la plus grande priorité et est associatif à gauche
2. La concaténation a la deuxième priorité et est associative à gauche
3. L'union a la priorité la plus faible et est associative à gauche

automates finis non déterministes
un automate fini déterministe (AFD) est un graphe orienté dont le coût des arcs est un symbole de l’alphabet d'entrée. Certains de ces états sont les état d'acceptation et ce graphe présente un état de départ. Pour chaque état s et chaque symbole d'entrée a, qui n'est jamais ε, il y a exactement un arc sortant de s étiqueté a. Nous allons voir ici comment obtenir un AFD à partir d'une expression régulière

arbre abstrait
On peut représenter une expression régulière par un arbre abstrait où chaque nœud est une opération et chaque feuille un symbole de l'alphabet. les nœuds peuvent être les suivants:



par exemple, l'arbre abstrait pour l'expression régulière (a|b)*abb



arbre abstrait augmenté:
à partir d'un arbre abstrait, on produit un arbre abstrait augmenté en concaténant la racine de l'arbre avec le symbole #.



fonctions calculés à partir de l'arbre abstrait
à chaque nœud et feuille n de l'arbre abstrait on peut calculer les fonctions annulable(n), premièrepos(n) et dernièrepos(n).



ce qui donne pour l'expression régulière (a|b)*abb:



calcul des ensembles posSuivante
on désigne par posSuivante(i), où i est une position, l'ensemble des positions suivantes de la position i.
Nous allons maintenant calculer les posSuivantes comme ceci:
1. si n est un nœud cat de fils gauche c1 et de fils droit c2, alors pour toute position i présente dans dernièrepos(c1), toutes les positions présentes dans premièrepos(c2) sont dans aussi dans posSivante(i)
2. si n est un nœud étoile, et si i est une position présente dans dernièrepos(n) alors toutes le positions présentes dans premièrepos(n) sont aussi présentes dans posSuivante(i)

exemple:
on a déjà calculé dans la dernière figure les premièrepos et dernièrepos de chaque nœud de l'arbre pour l'expression régulière (a|b)*abb. À chaque neud cat, on doit mettre chaque position présente dans premierepos de son fils droit dans l'ensemble posuivante de chaque position de dernièrepos de son fils gauche. Au nœud étoile, les positions présentes dans premièrepos de ce nœud sont aussi présente dans posSuivante des positions présentes dans dernièrepos de ce même nœud.
Voici la fonction posSuivante pour chaque position:



Algorithme de la construction de l'AFD
Soit T l'arbre abstrait de l'expression régulière (r)#
Un état de l'AFD D est un ensemble de positions dans l'arbre abstrait T.
Soit D l'AFD en construction. D_états est l'ensemble de ses états de D et D_trans, l'ensemble des transitions de D. Au départ, les états de D sont non marqués. Un état devient marqué juste avant que l'on étudie ses transitions sortantes. Le premier état de D est l'enseleble premièrepos(n0), où n0 est le nœud racine de T. Les états finaux sont ceux qui contiennent la position du marqueur de fin #.
voici l'algorithme:
Initialiser D-états pour qu'il ne contienne seulement l'état non marqué premièrepos(n0) où n0 est la racine de l'arbre abstrait T de (r)#.
tant que il existe un état non marqué E dans D_états.
marquer E;
pour chaque symbole d'entrée a
soit U l'union de posSuivante(p) pour tous les p de E qui correspondent à a
si U n'est pas dans D_état alors
ajouter U en tant qu'état non marqué dans D_état
D_trans[E,a]=U
exemple:
considérons T l'arbre abstrait de l'expression régulière (a|b)*abb. Le premier état de D est l'ensemble premièrepos de la racine de l'arbre T, soit {1;2;3}. Appelons A cet ensemble de positions. Étudions D_trans[A,a] et D_trans[A,b]. Parmis les positions {1;2;3}, 1 et 3 correspondent à a et 2 à b. Ainsi D_trans[A,a]=posSuivante(1) U posSuivante(3)={1;2;3;4} et D_trans[A,b]=posSuivante(2)={1;2;3}. Ce dernier étant l'état A, on ne l'ajoute pas à D_états, mais l'ensemble B={1;2;3;4} est ajouté à D_états:
A={1;2;3}
D_trans[A,a] = posSuivante(1) U posSuivante(3) = {1;2;3;4} = B
D_trans[A,b] = posSuivante(2) = {1;2;3} = A
D_trans[B,a] = posSuivante(1) U posSuivante(3) = {1;2;3;4} = B
D_trans[B,b] = posSuivante(2) U posSuivante(4) = {1;2;3;5} = C. L'ensemble C est ajouté à D_états
D_trans[C,a] = posSuivante(1) U posSuivante(3) = {1;2;3;4} = B
D-trans[C,b] = posSuivante(2) U posSuivante(5) = {1;2;3;6} = D. L'ensemble D est ajouté à D_états
comme D contient 6, la position du symbole #, l'état D est un état d'acceptation de l'AFD
D_trabs[D,a] = posSuivante(1) U posSuivante(3) = {1;2;3;4} = B
D_trans[D,b] = posSuivante(2) = {1;2;3} = A
il n'y a maintenant plus d'états non marqués.
L'AFD es le suivant:



pour implémenter un analyseur lexical, on a besoin d'un diagramma de transition, c'est à dire qu'il ne faut pas qu'il y ait des arcs sortant d'un état d'acceptation. Pour convertir cet AFD en diagramme de transition, D devient un etat courant. On ajoute ensuite un arc étiqueté "autre" vers un nouvel état, qui lui sera un état d'acceptation: