TD1 13 .pdf
Ce document au format PDF 1.2 a été généré par TeX output 2013.02.07:1429 / dvipdfm 0.13.2c, Copyright © 1998, by Mark A. Wicks, et a été envoyé sur fichier-pdf.fr le 14/02/2013 à 22:16, depuis l'adresse IP 197.7.x.x.
La présente page de téléchargement du fichier a été vue 2150 fois.
Taille du document: 42 Ko (2 pages).
Confidentialité: fichier public
Aperçu du document
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

