TD1 13 .pdf

Ens.: M.T. Bennani

FST - D´epartement G´enie Informatique
Travaux dirig´es en th´eorie de compilation

Ann´ee : 2012-2013

S´erie N1 - Analyse lexicale

1. Construction des AFDs
Soit un alphabet form´e de deux lettre ”a” et ”b”. Transformer les AFND suivants en AFD.
(a) Le premier automate est :

a,b
q0
a

b

q2

q1
a

(b) Le deuxi`eme automate est :
b
q0

a

q1

b
q2

a
b

q3

a

(c) Le troisi`eme automate est :
q0

b
a q1
a

a

q2

a
a,b

q3

b

q4

q5

2. Algorithme Maximal Munch
Soient les trois Tokens d´efinis par les expressions r´eguli`eres du listing ci-dessous.
a∗b
( a | b)∗b
c∗

printf (”1”);
printf (”2”);
printf (”3”);

Quelles sont les sorties produites en appliquant l’algorithme maxiaml munch pour :
(a) aaabccabbb
(b) cbbbbac
(c) cbabc
3. Limites de la r´
esolution de conflits
Nous avons introduit dans le cours que l’algorithme Maximal Munch associ´e `a la d´efinition
d’un crit`ere de priorit´e sur les expressions r´eguli`eres permettent de r´esoudre la r´esolution de
conflits.
(a) Expliquer ce principe avec un exemple diff´erent de celui introduit dans le cours.
(b) Soient les trois Tokens d´efinis par les expressions r´eguli`eres du listing ci-dessous.

TDs en th´eorie de compilation
aa
a
ab

TD1

Ann´ee universitaire : 2012-2013

printf (”1”);
printf (”2”);
printf (”3”);

Quelles sont les sorties produites lorsqu’on applique l’algorithme maxiaml munch pour la
chaine ”aab”?
4. Lenteur des scanners
Soient les Tokens d´efinis par les expressions r´eguli`eres du listing ci-dessous
” photo ”
” photosynthese ”
” . | \ n”

{ p r i n t f ( ”PHOTO” ) ; }
{ p r i n t f ( ”PHOTOSYNTHESE” ) ; }
{ p r i n t f ( ”X” ) ; }

(a) Quelles sont les sorties produites pour l’entr´ee ”photosynthetiser” ?
(b) D´eduire le nombre de caract`eres scann´es.
(c) Soient les deux Tokens d´efinis par les expressions r´eguli`eres du listing ci-dessous
a ∗b
a

{ printf (”1”); }
{ printf (”2”); }

Supposons le langage d´efini par L={a{n}, o`
u n > 1}. Quel est le nombre de caract`eres
scann´es ?
5. Analyseurs invers´
es
L’algorithme d’analyse introduit dans le cours est bas´e sur une lecture de gauche `a droite d’une
entr´ee. L’objectif de cet exercice est de r´ealiser un analyseur qui r´ealise la lecture de droite `a
gauche.
(a) Modifier l’algorithme permettant de convertir l’expression r´eguli`ere en AFND dans le but
d’accpeter les chaˆınes invers´ees.
(b) G´enerer un ensemble d’expressions r´eguli`eres et une chaine de caract`eres o`
u l’analyse de
gauche `a droite donne des Tokens diff´erent de l’analyse de droite `a gauche.

Page 2