Corrige du partiel du 31 mars 2014
I . Analyse lexicale.
1. En Caml (un langage fonctionnel concu a lINRIA), les
identificateurs sont des suites de
lettres, chiffres, _ (le caractere souligne) et (le caractere
apostrophe), commencant par une
lettre. Les identificateurs ne doivent pas contenir deux
caracteres soulignes successifs (__).
Exemples : x, x, Le_Compteur, k0, K1, mais pas ab__cd.
Donnez une expression reguliere pour reconnatre les
identificateurs de Caml.
reponse :
[A-Za-z]("_"?[A-Za-z0-9])*"_"?
2. Dans un systeme dextraction dinformations, on a besoin de
reconnatre des entites commeles dates (28 mars 2011, 28/03/11,
lundi 28 . . . ), les heures (12h30, minuit . . . ), les
adresses(12 rue du General dAusson-Ducanon, 3bis place Hauxjeunes,
152 avenue du 11 novembre).
Sachant que sont definies les expressions regulieres pour les
jours (JOUR : lundi|mardi| . . . ),les mois (MOIS :
janvier|fevrier| . . . ), les voies (VOIE : rue|avenue| . . . ),
ecrire les reglesdun programme Flex pour reconnatre ces differentes
entites. Par exemple
jeudi 24, ronde des fac, rendez-vous 14h30 place Massena.
affichera apres traitement par votre analyseur
DATE[jeudi 24], ronde des fac, rendez-vous HEURE[14h30]
LIEU[place Massena].
Vous pouvez supposer quune adresse se termine toujours sur une
ponctuation (point, vir-
gule . . . ).
reponse :
MOIS
(janvier|fevrier|mars|avril|mai|juin|juillet|aout|septembre|octobre|novembre|decembre)
JOUR (lundi|mardi|mercredi|jeudi|vendredi|samedi|dimanche)
VOIE (rue|avenue|boulevard|allee|chemin|place|impasse)
HEURE (0?[0-9]|[1][0-9]|2[0-4])
MINUTE (0?[0-9]|[1-5][0-9])
NUMJOUR (0?[1-9]|[1-2][0-9]|3[0-1])
NUMMOIS (0?[1-9]|1[0-2])
ANNEE [1-9][0-9]?[0-9]?[0-9]?
NUMRUE ([1-9][0-9]*(bis|ter)?)
SP (" "+)
%%
({NUMRUE}{SP})?{VOIE}[^.;,:\n]+ printf("LIEU[%s]", yytext);
{HEURE}[hH]{MINUTE}|midi|minuit printf("HEURE[%s]", yytext);
({JOUR}{SP})?{NUMJOUR}{SP}{MOIS}({SP}{ANNEE})?
printf("DATE[%s]", yytext);
{JOUR}{SP}{NUMJOUR} printf("DATE[%s]", yytext);
{NUMJOUR}"/"{NUMMOIS}"/"{ANNEE} printf("DATE[%s]", yytext);
.|\n ECHO;
II . Grammaires non contextuelles.
1. Soit la grammaire S AC A aAb | C bCc | .Quel est le langage
produit par cette grammaire ?reponse :
anbn bmcm = anbn+mcm, n,m 0
2. Donnez une grammaire qui produit un langage comptant le
nombre de () non appariees.Par exemple, ((()++ car il y a 2 ( de
plus que de ), (()))- car il y en a une de moins, et((())) car il y
en a autant.reponse :
S E | P | E ME (E) | P (P + | EM )M | )
3. Soit la grammaire :S DAC | BED A a | B b | C Bd | c D d | E
Db | e
(a) Donnez les Premier1 pour les non terminaux suivants
reponse :
A B C D E
a b c, d d b, e(car B annulable) (car D annulable)
a b b, c, d d b, d, e
(b) En deduire les Premier1 de DAC et BED. Que peut-on dire de
cette grammaire ?
reponse :
Prem(DAC) = Prem(D) Prem(A) Prem(C) = {d, a, b, c}car D et A
annulables
Prem(BED) = Prem(B) Prem(E) = {b, d, e} car B
annulableLintersecton des ensembles de Prem1 nest pas disjointe,
gram-maire pas LL(1) (en fait LL(2))
4. Soit la grammaire :S aAC | aBD A ac | B ab | ca C cdB D
dB
Pour quelle valeur de k cette grammaire est-elle LL(k) ?
Justifier votre reponse.
reponse :
Grammaire LL(3) : par aAC on produit par derivation gaucheaacC,
et par aBD on produit aabD. Et aussi, par aAC on pro-duit acdB, et
par aBD on produit acadB.
5. Soit la grammaire :S aAC | bAD | BD A ab | b B ab | ba C cd D
dc
(a) Donnez les Suivant1 de A et de B
reponse :Suiv(A) = c et d, Suiv(B) = d.Les ensembles ne sont pas
disjoints
(b) Donnez lautomate LR(0) de cette grammaire. Vous pouvez ne
donner que les etats quiont des transitions sur a ou b.reponse
:
tats significatifs de l'automate LR(0) de la grammaire
q0
S a A CS b A dS B dB a bB b a
a
q1
S a A cB a bA a bA b
q4
S b A dB b aA a bA b
q2
B a b A b
b
q5
A a bB b a
a Conflitdcalage/rduction :Pas LR(0)
Conflitrduction/rduction :Pas LR(0)
q7
A a ba
c
d
q6
A b
b
b
B
q3
S B d
a
A
b q8
A a b
q1
S a A cB a bA a bA b
q9
S a A c
(c) Cette grammaire est-elle LR(0), SLR(1), LALR(1) ? Justifiez
dans chaque cas.
i. LR(0) ? Pourquoi ?
Car conflits dans des etats de lautomate LR(0)
ii. SLR(1) ? Pourquoi ?
La grammaire est SLR(1) en q5 car b (le symbole sur
lequeldecaler) nest pas dans les Suiv(B) ( les symboles sur
lesquelsil faut reduire).Pas contre, probleme en q2, car les
ensembles de symbolessur lesquels on doit reduire (Suiv(A) et
Suiv(B)) ne sontpas disjointsDonc la grammaire nest pas SLR(1).
iii. LALR(1) ? Pourquoi ?
Voir lautomate : pour q2 on reduit a A sur les
suivantscontextuels de A donc c, et on reduit a B sur d.Donc
LALR(1)
