Analyse Lexicale

D finition : Soit A un alphabet, un mot est une concat nation d l ments de A. La longueur

dun mot w, not e |w|, est le nombre de symboles qui constituent ce mot. Une portion de w est

appel e facteur. Le mot vide sera not . L'ensemble constitu de tous les mots, d finis gr ce des

l ments de A, sera not A et A+=A\{ }. On note An l'ensemble des mots de A* de longueur n.

D finition : Sur les mots, on peut d finir les op rations suivantes :

(i) Concat nation : w=w1w2

(ii) Alternance : w=w1|w2, not e aussi w=w1+w2, signifie soit w=w1, soit w=w2

(iii) Puissance : wn=ww & w, n fois o n 0.

(iv) Fermeture de Kleene :

= | w | w2 | w3 | ...

Exemples :

Soit l'alphabet A={a, b, c} : Les cha nes de caract res aaba, bbbacbb, c, , ca sont des mots

de A*, de longueurs respectives 4, 7, 1, 0 et 2.

Soit l'alphabet A={aa, b, c} : La cha ne de caract res aba n'est pas un mot de A*, puisque a

A. Mais Les cha nes de caract res baab, caa, bc, aaaa sont des mots de A*de longueurs 3, 2, 2 et 2.

D finition : On appelle langage associ un alphabet A tout sous-ensemble de A*.

Exemples : Soit l'alphabet A={a, b, c}

Soit L1 l'ensemble des mots de A* ayant autant de a que de b. Le langage L1 est un langage

infini :

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 dun 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 quaux langages r guliers.

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

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

U+ ==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|bc 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

bababab d note l'ensemble des mots sur {a,b} contenant exactement 3 a

(abbc|baba)+aa(cc|bb)*

3. AUTOMATES FINIS

Comme nous lavons dit pr c demment, lors de lanalyse 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 dune ER. Cette repr sentation est

assez fastidieuse, surtout, quand une ER fait appel plusieurs autres ER. Cest la raison pour

laquelle, on pr f re une repr sentation graphique en utilisant la notion dAutomate 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 dun 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 sachever 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 dun AF :

D finition : Un AF M est un quintuple (Q, A, q0, F, ) tel que :

(i) Q est lensemble des tats de M,

(ii) A est lalphabet utilis par M,

(iii q0 est l tat initial de M : Cest l tat partir du quel doit n cessairement commencer toute

s quence de transition dans M,

(iv) F est lensemble des tats finaux de M : Ceux sont les tats vers lesquels peut sachever 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 dAF :

(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) Dune part, pour chaque tat on ne peut pas avoir deux arcs portant la m me tiquette

quittant cet tat.

(ii) Dautre part, aucun tat ne poss de de -transition, i.e., transition sur lentr e .

L gende :

: tat quelconque

: tat final

Fig. 1 Un AFND repr sentant lER aa|bb.

Fig. 2 AFND repr sentant lER (a|b)*abb.

Fig. 3 AFD repr sentant lER (a|b)*abb.

Analyse Lexicale

16

Exemple : Dans lAFND de la figure Fig. 2, les transitions 1 2 et 1 4 sont des -transition.

Fig. 4 Autre AFD repr sentant lER (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 quun AFD. En fait, on peut transformer un AFND N en un

AFD D. Pour ce faire, on peut utiliser lalgorithme Construction_des_Sous-Ensembles. Cet

algorithme fait appelle aux d finitions suivantes :

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

transitions uniquement (e-transition = transition portant l' tiquette e).

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

par des e-transitions uniquement (T est un ensemble d tats de lAFND N) :

e-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 e-fermeture(e0) comme lunique 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 lalphabet faire

U:= e-fermeture(Transiter(T,x))

si U n'appartient pas D tats alors

Ajouter U comme noeud non marqu dans D tats

fsi

Dtrans : = U

ffaire

ffaire

fin

Exercice : Montrez quon peut convertir lAFND de la Fig. 2 en lAFD de la Fig. 4.

UTeefermeture )(-e

Analyse Lexicale

17

Nous pr sentons, un algorithme de construction dun AFND partir dune 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, dabord, ces r gles de constructions :

R gle 1 : Pour , construire lAFND M( ) suivant :

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

R gle 2 : Pour a, a A, construire lAFND M(a) suivant :

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

(a) Pour lER s|t, not e aussi s+t, construire lAFND M(s|t) suivant :

(b) Pour lER st, construire lAFND M(st) suivant :

(c) Pour lER s, construire lAFND M(s) suivant :

Analyse Lexicale

18

(d) Pour lER (s), utiliser lAFND 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 dAFND M(r)

Fin

*