Analyse Lexicale

L1={ε, ab, ba, c, cc, cabccc, accbcccbcccca, aabb, baab, bbccccaccbaabccccaccc, … }

0*nnww

Analyse Lexicale

13

● Soit L2 l'ensemble de tous les mots de A*ayant exactement 4 a. Le langage L1 est un langage

infini :

L2={aaaa, abcabbbaacc, … }

Définition : Sur les langages, on peut définir les opérations suivantes : (i) Union : L1L2={w tq wL1 ou wL2}. (ii) Intersection : L1L2={w tq wL1 et wL2}. (iii) Concaténation : L1L2={w tq w=w1w2 où w1L1 et w2L2}.

(iv) Fermeture de Kleene :

(v) Fermeture positive : L+=L*\{ε}

Remarque : La concaténation n fois d’un langage L sera notée Ln :

LL … L=Ln

Problème : Etant donné un langage, comment décrire tous les mots appartenant à ce langage?

Autrement dit, comment décrire un langage?

Il existe plusieurs types de langage, certains étant plus facile à décrire que d'autres. Dans ce

cours, on ne s'intéresse qu’aux langages réguliers.

Définition : Un Langage Régulier (LR), définit sur un alphabet A, est un langage vérifiant l’une

des propriétés suivantes :

(i) {ε}est un langage régulier sur A. (ii) Si a est une lettre de A alors {a}est un langage régulier sur A. (iii) Si L est un langage régulier sur A alors Ln et L* sont des langages réguliers sur A. (iv) Si L1 et L2 sont des langages réguliers sur A alors L1L2 et L1L2 sont des langages réguliers. Il n'y a pas d'autres langages réguliers sur A

Un LR se décrit facilement par une expression régulière.

Définition : Une Expression Régulière (ER), définit sur un alphabet A, est une expression

vérifiant l’une des propriétés suivantes :

(i) ε est une ER qui décrit le langage {ε} (ii) Si aA alors a est une ER qui décrit le langage {a}. (iii) Si e est une ER qui décrit le langage L alors (e)* est une ER qui décrit le langage L* (iv) Si e est une ER qui décrit le langage L alors (e)+ est une ER qui décrit le langage L+ (v) Si e1 et e2 sont des ER qui décrivent respectivement les langages L1 et L2 alors (e1)|(e2), notée aussi (e1)+(e2), est une ER décrivant L1L2. (v) Si e1 et e2 sont des ER qui décrivent respectivement les langages L1 et L2 alors (e1)(e2) est

une ER dénotant L1L2.

Il n'y a pas d'autres ER.

Remarques : pour économiser le nombre des parenthèses, on conviendra des priorités

décroissantes suivantes : *, concaténation, |.

Exemple : ab*|c=((a)((b)*))|(c) La concaténation est distributive par rapport à |. On a alors : r(s|t)=rs|rt et (s|t)r=sr|tr.

0*nnLL

Analyse Lexicale

14

Exemples : ● (a|b)* dénote l'ensemble des mots formés des a ou bien des b, ou le mot vide. ● (a)|((b)*(c))=a|b*c dénote l'ensemble des mots égaux soit au mot a, soit aux mots formés de 0

ou plusieurs b suivies d'un c. C'est à dire, l'ensemble {a, c, bc, bbc, bbbc, bbbbc, … }. ● (a|b)*abb(a|b)* dénote l'ensemble des mots sur {a,b}contenant le facteur abb ● b*ab*ab*ab* dénote l'ensemble des mots sur {a,b} contenant exactement 3 a ● (abbc|baba)+aa(cc|bb)*

3. AUTOMATES FINIS

Comme nous l’avons dit précédemment, lors de l’analyse lexicale, le compilateur identifie les

unités lexicales. Une unité lexicale peut être représentée par une ER.

Exemple : Une ER décrivant les identificateurs en C pourrait être : ident = lettre (lettre | chiffre | sép)* lettre = A | B | … | Z| a | b | … | z chiffre = 0 | 1 | … | 9 sép = _

La représentation ci-dessus est une représentation textuelle d’une ER. Cette représentation est assez fastidieuse, surtout, quand une ER fait appel à plusieurs autres ER. C’est la raison pour laquelle, on préfère une représentation graphique en utilisant la notion d’Automate Fini (AF). Cette représentation est plus conviviale et plus expressive.

Définition : Un Automate Fini (AF) est un graphe orienté tel que : (i) Un sommet i représente l’état i. (ii) Un arc, portant l’étiquette k, partant d’un sommet i et arrivant à un sommet j représente le

fait que le symbole k fait transiter de l’état i vers l’état j.

(iii) Il existe un sommet dans ce graphe désigné comme étant l’état initial, à partir du quel doit

nécessairement commencer toute séquence de transition.

(iv) Il existe des sommets dans ce graphe désignés comme étant les états finaux, vers lesquels

peut s’achever une séquence de transition.

Remarque : Un chemin partant de l’état initial et arrivant à un état final dans un AF représente

un mot du LR reconnu par cet AF.

Voici une autre définition d’un AF :

Définition : Un AF M est un quintuple (Q, A, q0, F, δ) tel que : (i) Q est l’ensemble des états de M, (ii) A est l’alphabet utilisé par M, (iii q0 est l’état initial de M : C’est l’état à partir du quel doit nécessairement commencer toute

séquence de transition dans M,

(iv) F est l’ensemble des états finaux de M : Ceux sont les états vers lesquels peut s’achever une

séquence de transition dans M,

(v) Et δ est la fonction de transition entre les états de M :

δ : Q×A → Q (s,a) → s

Analyse Lexicale

15

Théorème : Un LR est reconnu par un AF.

On distingue deux types d’AF : (i) Les Automates Finis Non Déterministes (AFND), (ii) Et les Automates Finis Déterministes (AFD).

Définition : Un Automate Fini Non Déterministe (AFND) est un AF tel que pour un état peut

avoir plusieurs arcs portant la même étiquette quittant cet état.

Définition : Un Automate Fini Déterministe (AFD) est un AF tel que : (i) D’une part, pour chaque état on ne peut pas avoir deux arcs portant la même étiquette

quittant cet état.

(ii) D’autre part, aucun état ne possède de ε-transition, i.e., transition sur l’entrée ε.

Légende :

: état quelconque

: état final

Fig. 1 Un AFND représentant l’ER aa*|bb*.

Fig. 2 AFND représentant l’ER (a|b)*abb.

Fig. 3 AFD représentant l’ER (a|b)*abb.

Analyse Lexicale

16

Exemple : Dans l’AFND de la figure Fig. 2, les transitions 1→2 et 1→4 sont des ε-transition.

Fig. 4 Autre AFD représentant l’ER (a|b)*abb.

Remarque : Comme le montre les figurent Fig. 2, Fig. 3 et Fig. 4, une ER peut être représentée, aussi bien, par un AFND et qu’un AFD. En fait, on peut transformer un AFND N en un AFD D. Pour ce faire, on peut utiliser l’algorithme Construction_des_Sous-Ensembles. Cet algorithme fait appelle aux définitions suivantes :

-fermeture(e) : Ensemble des états de l'AFND N accessibles depuis l'état e de N par des -

transitions uniquement (-transition = transition portant l'étiquette 

-fermeture(T) : Ensemble des états de l'AFND N accessibles depuis un état e appartenant à T

par des -transitions uniquement (T est un ensemble d’états de l’AFND N) :

-fermeture(T) =

Transiter(T,x) : Ensemble des états de l'AFND N vers lesquels il existe une transition sur le

symbole x à partir d'un état e appartenant à T.

Détats : Ensemble des états de l'AFD D

Dtrans : Table de transition de l'AFD D

e0 : Etat de départ de l'AFND N

Algorithme Construction_des_Sous-Ensembles (Données N : AFND; Résultats D : AFD) début

Considérer -fermeture(e0) comme l’unique état de Détats, cet état est non marqué tant que il existe un état non marqué T dans Détats faire

Marquer T pour chaque symbole x de l’alphabet faire

U:= -fermeture(Transiter(T,x)) si U n'appartient pas à Détats alors

Ajouter U comme noeud non marqué dans Détats

fsi Dtrans[T,x] : = U

ffaire

ffaire

fin

Exercice : Montrez qu’on peut convertir l’AFND de la Fig. 2 en l’AFD de la Fig. 4.

Teefermeture)(-

Analyse Lexicale

17

Nous présentons, un algorithme de construction d’un AFND à partir d’une ER, appelé aussi algorithme de construction de Thompson. Il existe plusieurs variantes de cet algorithme, mais, nous présentons ici une version simple et facile à implémenter. Présentons, d’abord, ces règles de constructions :

Règle 1 : Pour ε, construire l’AFND M(ε) suivant :

Où i est un nouvel état initial et f est un nouvel état final.

Règle 2 : Pour a, aA, construire l’AFND M(a) suivant :

Règle 3 : Supposons que M(s) et M(t) sont, respectivement, les AFND des ER s et t.

(a) Pour l’ER s|t, notée aussi s+t, construire l’AFND M(s|t) suivant :

(b) Pour l’ER st, construire l’AFND M(st) suivant :

(c) Pour l’ER s*, construire l’AFND M(s*) suivant :

Analyse Lexicale

18

(d) Pour l’ER (s), utiliser l’AFND M(s) déjà construit.

Algorithme Construction de Thompson (Donnée r : ER, A : alphabet ; Résultat M(r) : AFND)

Début

(i) Pour tout r, r  A{ε}, faire

Construire un AFND en utilisant les Règles 1 et 2

ffaire

(ii)

(ii.i) En suivant la structure syntaxique de r, combiner les AFND construits lors de l’étape

(i), en utilisant la Règle 3.

(ii.ii) Affecter cette combinaison d’AFND à M(r)

Fin

***