Université de Technologie de Compiègne
NF11 - TD6 : Corrigé
Exercice 1
1. Soit c = [1 − 9] et l = [a − zA − Z]. Ci-dessous les expressions régulières :
Id → l(l|c) ∗
Cst → c +
Op →< | > | <= | >= | <> | = | + | −
On ne définit pas un modèle particulier pour les mots clés. On les traite a
priori comme des identificateurs. On recherche, en état d’acceptation, à l’aide
de l’exécution de code, si un "identificateur" fait partie d’une table prédéfinie.
2. L’automate est donné par le digramme de transition suivant :
Exercice 2
1. Soit C = [1−9], l’automate est donné par le diagramme de transition suivant :
1
2. On commence d’abord par construire une table de transition (voir Table 1)
de l’automate où on fait apparaitre des situations d’erreurs. Ces situations
d’erreurs seront codées par des entiers négatifs :
— -1 : Caractère non autorisé
— -2 : "+" ou "-" non attendu
— -3 : "E" non attendu
— -4 : "." non attendu
Table 1 – Transition
+,- C E . Autre
0 2 1 -3 -4 -1
1 -2 1 5 3 -1
2 -2 1 -3 -4 -1
3 -2 4 -3 -4 -1
4 -2 4 5 -4 -1
5 6 7 -3 -4 -1
6 -2 7 -3 -4 -1
7 -2 7 -3 -4 -1
L’algorithme de l’analyseur lexical est donné par Algorithme 1. Cet algorithme
utilise la Table 1.
1 Analyseur lexical EX2
1 Début Algorithme
2 E n t i e r : E<−0
3 caractère c
4 c<− l i r e ( )
5 Tant que ( c<>$ e t E>=0)
6 E<−T r a n s i t i o n [ E ] [ c ]
7 c<− l i r e ( )
8 Fin Tant que
9 S i (E<0)
10 A f f i c h e r _ E r r e u r (E)
11 s i n o n s i F i n a l (E)
12 A f f i c h e r ( " La c h a î n e e s t v a l i d e " ) ;
13 sinon
14 A f f i c h e r ( " Chaîne i n c o m p l è t e " ) ;
15 Fin
Exercice 3
1. Les conditions 3 et 4 sont très difficile à les modéliser par l’automate, par contre
leur vérification peut être faîte d’une manière efficace au niveau de l’algorithme
de l’analyseur lexical. On utilisera un automate pour la vérification des deux
premières conditions.
On note par c et v l’ensemble des consonnes et des voyelles, respectivement.
L’automate est donné par le diagramme de transition suivant :
2
2. On construit une table de transition de l’automate où on fait apparaitre des
situations d’erreurs. Ces situations d’erreurs seront codées par des entier né-
gatifs. Voir Table 2.
— -1 : Caractère non autorisé
— -2 : Les consonnes sont séparées par des voyelles (pas de consonnes consé-
cutives).
— -3 : Plusieurs voyelles (au maximum 3) peuvent se suivre
Table 2 – Transition
v c Autre
0 2 1 -1
1 2 -2 -1
2 4 1 -1
3 -3 1 -1
4 3 1 -1
Enfin, l’algorithme de l’analyseur lexical est donné par Algorithme 2. Cet al-
gorithme utilise la Table 2.
3
2 Analyseur lexicale EX3
1
2 Début Algorithme
3 E n t i e r : E<−0
4 caractère c
5 c<− l i r e ( )
6 d<−c
7 l <−0
8 Tant que ( c<>$ e t E>=0)
9 E<−T r a n s i t i o n [ E ] [ c ]
10 l++
11 f <−c
12 c<− l i r e ( )
13 Fin Tant que
14 S i (E<0) a l o r s
15 A f f i c h e r _ E r r e u r (E)
16 s i n o n S i ( l <2 ou l >8) a l o r s
17 A f f i c h e r ( " E r r e u r : l a l o n g u e u r de l a c h a î n e
18 doit ê t r e comprise entre 2 et 8 " ) ;
19 s i n o n S i ( cons ( d)= v r a i e t d=f ) a l o r s
20 A f f i c h e r ( " Une c h a î n e ne peut pas commencer
21 e t s e t e r m i n e r par une même consonne " ) ;
22 sinon
23 A f f i c h e r ( " La c h a î n e e s t v a l i d e " ) ;
24 Fin S i
25 Fin
