Théorie des langages : Td 6 automate fini automate
Télécharger PDFUniversité de Technologie de Compiègne
NF11 - TD6 : Corrigé
Exercice 11. Soitc= [1−9]etl= [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 21. SoitC= [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
Table1 – Transition
+,-CE.Autre
021-3-4-1
1-2153-1
2-21-3-4-1
3-24-3-4-1
4-245-4-1
567-3-4-1
6-27-3-4-1
7-27-3-4-1
L’algorithme de l’analyseur lexical est donné par Algorithme 1. Cet algorithme
utilise la Table 1.
1Analyseur lexical EX2
1Début Algorithme
2Entier : E<−0
3caractère c
4c<−l i r e ()
5Tant que ( c<>$ et E>=0)
6E<−Transition [E ] [ c ]
7c<−l i r e ()
8Fin Tant que
9Si (E<0)
10Afficher_Erreur (E)
11sinon s i Final (E)
12Afficher (" La chaîne est valide " ) ;13sinon 14Afficher (" Chaîne incomplète " ) ;15Fin
Exercice 31. 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 parcetvl’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
Table2 – TransitionvcAutre 021-112-2-1 241-13-31-1 431-1
Enfin, l’algorithme de l’analyseur lexical est donné par Algorithme 2. Cet al-
gorithme utilise la Table 2.3 2Analyseur lexicale EX31 2Début Algorithme
3Entier : E<−0
4caractère c
5c<−l i r e ()
6d<−c
7l <−0
8Tant que ( c<>$ et E>=0)
9E<−Transition [E ] [ c ]10l++ 11f<−c
12c<−l i r e ()
13Fin Tant que
14Si (E<0) a l o r s
15Afficher_Erreur (E)
16sinon Si ( l <2 ou l >8) a l o r s
17Afficher (" Erreur : la longueur de la chaîne
18doit être comprise entre 2 et 8 " ) ;
19sinon Si ( cons (d)= vrai et d=f ) a l o r s
20Afficher (" Une chaîne ne peut pas commencer
21et se terminer par une même consonne " ) ;22sinon 23Afficher (" La chaîne est valide " ) ;
24Fin Si25Fin 4