Théorie des langages : Td 6 automate fini automate
Télécharger PDFUniversité de Technologie de Compiègne - NF11 : TD6
Exercice 1
Soit c = [1−9] et l = [a−zA−Z]. Voici les expressions régulières :
- Id → l(l|c)*
- Cst → c+
- Op → <|>|<=|>=|<>|=|+|−
On ne définit pas de modèle particulier pour les mots-clés. Ils sont traités a priori comme des identificateurs. L'analyse vérifie, en état d'acceptation, si un "identificateur" appartient à une table prédéfinie à l'aide de l'exécution de code.
Exercice 2
Soit C = [1−9]. L'automate est donné par la table de transition suivante (Table 1), où les erreurs sont codées par des entiers négatifs :
- -1 : Caractère non autorisé
- -2 : "+" ou "-" non attendu
- -3 : "E" non attendu
- -4 : "." non attendu
| + | - | 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 le suivant :
- Début Algorithme
- Entier : E ← 0
- Lire un caractère c
- Tant que (c ≠ $ et E ≥ 0)
- E ← Transition[E][c]
- Lire un caractère c
- Fin Tant que
- Si (E < 0) alors Afficher_Erreur(E)
- Sinon si Final(E) alors Afficher("La chaîne est valide")
- Sinon Afficher("Chaîne incomplète")
- Fin
Exercice 3
Les conditions 3 et 4 sont difficiles à modéliser par l'automate, mais leur vérification peut être faite de manière efficace au niveau de l'algorithme de l'analyseur lexical. Un automate est utilisé pour vérifier les deux premières conditions.
On note p et v l'ensemble des consonnes et des voyelles, respectivement.
Voici la table de transition de l'automate (Table 2) avec les erreurs codées par des entiers négatifs :
- -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
| v | c | Autre | |
|---|---|---|---|
| 0 | 2 | 1 | -1 |
| 2 | 1 | -2 | -1 |
| 4 | 1 | -3 | -1 |
| 3 | 1 | -1 |
L'algorithme de l'analyseur lexical est le suivant :
- Début Algorithme
- Entier : E ← 0
- Lire un caractère c
- d ← c
- l ← 0
- Tant que (c ≠ $ et E ≥ 0)
- E ← Transition[E][c]
- l++
- f ← c
- Lire un caractère c
- Fin Tant que
- Si (E < 0) alors Afficher_Erreur(E)
- Sinon si (l < 2 ou l > 8) alors Afficher("Erreur : la longueur de la chaîne doit être comprise entre 2 et 8")
- Sinon si (cons(d) = vrai et d = f) alors Afficher("Une chaîne ne peut pas commencer et se terminer par une même consonne")
- Sinon Afficher("La chaîne est valide")
- Fin
FAQ
1. Qu'est-ce qu'un état d'acceptation dans un automate ?
Un état d'acceptation est un état particulier dans lequel l'automate se trouve après avoir traité une séquence de caractères valide selon les règles définies. Il permet de déterminer si la chaîne analysée est correcte.
2. Pourquoi les erreurs sont-elles codées par des entiers négatifs ?
Les entiers négatifs sont utilisés pour distinguer les états d'erreur des états normaux (positifs) dans la table de transition. Cela simplifie la gestion des erreurs dans l'algorithme.
3. Comment vérifier la longueur d'une chaîne dans un analyseur lexical ?
La longueur est vérifiée en comptant le nombre de caractères lus pendant l'analyse. Si ce nombre dépasse ou est inférieur aux limites autorisées, une erreur est affichée.