Théorie des langages : Exercices automate fini
Télécharger PDFUniversité de Caen – Année 2018/2019
UFR des Sciences – 1ère session
Mercredi 20 mars
L3 – INF6ACT
Théorie des langages et compilation
Durée : 2 heures
Documents autorisés : notes personnelles, diapositives du cours.
Exercice I. Automate fini
À rendre avec l’exercice III.
Question 1.
Donner la table de transitions de l’automate fini A1 suivant :
États : {P, I, ab}
Alphabet : {a, b}
Question 2.
Donner l’exécution de l’automate A1 sur les quatre mots suivants : ε, aa, ab, abbbaaab. Lesquels sont acceptés par A1 ?
Question 3.
Quel est le langage reconnu par l’automate A1 ?
Question 4.
Donner une expression régulière de ce langage.
Question 5.
On considère également l’automate fini A2 :
États : {E, O, ba}
Alphabet : {a, b}
Quel est le langage reconnu par A2 ? En donner une expression régulière.
Exercice II. Compilation
À rendre sur une copie séparée.
Question 6.
On souhaite ajouter à notre calculette le support de la boucle for in. Le principe de cette boucle (présentée en Python) est que for el in tab effectue une boucle en prenant pour el tous les éléments du tableau tab.
Pour la suite, on supposera qu’un tableau de taille n est stocké dans la pile en empilant d’abord sa longueur puis ses éléments. Par exemple, le tableau tab = [12, 3] est transcrit par la suite de mots : 2 12 3.
On supposera également que l’adresse du tableau correspond à la position du mot indiquant sa longueur.
L’opcode PUSHR x effectue l’opération suivante :
P[sp-1] := P[P[sp-1] + x] ; sp := sp + 1.
Question 7.
Compléter la trace d’exécution suivante pour le code MVaP donné :
pc | fp | pile
-------------------------------
0 | PUSHI 0 | [ ]
2 | PUSHI 0 | [0]
4 | PUSHI 2 | [0, 0]
6 | PUSHI 12 | [0, 0, 2]
8 | PUSHI 3 | [0, 0, 2, 12]
10 | JUMP 12 | [0, 0, 2, 12, 3]
12 | PUSHI 0 | [0, 0, 2, 12, 3]
14 | STOREG 0 | [0, 0, 2, 12, 3, 0]
16 | PUSHG 0 | [0, 0, 2, 12, 3]
18 | PUSHG 2 | [0, 0, 2, 12, 3, 0]
20 | INF | [0, 0, 2, 12, 3, 0, 2]
21 | JUMPF 42 | [0, 0, 2, 12, 3, 0]
23 | PUSHG 0 | [0, 0, 2, 12, 3]
25 | PUSHR 3 | [0, 0, 2, 12, 3, 1]
27 | STOREG 1 | [0, 0, 2, 12, 3, 3]
29 | PUSHG 1 | [0, 0, 2, 12, 3]
31 | WRITE | [0, 0, 2, 12, 3, 3]
32 | POP | [0, 0, 2, 12, 3, 3]
33 | PUSHG 0 | [0, 0, 2, 12, 3]
35 | PUSHI 1 | [0, 0, 2, 12, 3, 1]
37 | ADD | [0, 0, 2, 12, 3, 1, 1]
38 | STOREG 0 | [0, 0, 2, 12, 3, 2]
40 | JUMP 16 | [1, 12, 2, 12, 3]
16 | PUSHG 0 | [1, 12, 2, 12, 3]
18 | PUSHG 2 | [1, 12, 2, 12, 3, 1]
20 | INF | [1, 12, 2, 12, 3, 1, 2]
21 | JUMPF 42 | [1, 12, 2, 12, 3, 1]
23 | PUSHG 0 | [1, 12, 2, 12, 3]
25 | PUSHR 3 | [1, 12, 2, 12, 3, 3]
27 | STOREG 1 | [1, 12, 2, 12, 3, 3]
29 | PUSHG 1 | [1, 3, 2, 12, 3]
31 | WRITE | [1, 3, 2, 12, 3, 3]
32 | POP | [1, 3, 2, 12, 3, 3]
33 | PUSHG 0 | [1, 3, 2, 12, 3]
35 | PUSHI 1 | [1, 3, 2, 12, 3, 1]
37 | ADD | [1, 3, 2, 12, 3, 1, 1]
38 | STOREG 0 | [1, 3, 2, 12, 3, 2]
40 | JUMP 16 | [2, 3, 2, 12, 3]
42 | HALT
Question 8.
Écrire le code MVaP correspondant à la fonction suivante :
int b = [4, 5];
int f(x) {
return x + 3;
}
println(f(6) + 1);
Question 9.
On donne la grammaire suivante permettant de prendre en compte la déclaration (initialisée) de tableaux :
declaration returns [String code]
| ’int’ IDENTIFIANT ’=’ ’[’ elems ’]’
{ // À compléter }
;
elems returns [String code, int size]
@init{ $code = new String(); $size = 0; }
: (ENTIER { // À compléter } (’,’ ENTIER { // À compléter })* )?;
Question 10.
Compléter les actions de la grammaire afin de générer le code MVaP correct.
Exercice III. Analyse LL(1)
À rendre avec l’exercice I.
Question 11.
Donner un arbre d’analyse pour le mot suivant :
art nom de art nom verbe prepo art nom.
Question 12.
a) Quelles sont les variables effaçables ?
b) Donner la table des ensembles PREMIER.
c) Donner la table des ensembles SUIVANT en utilisant $ pour marquer la fin des mots à analyser.
Question 13.
Expliquer comment la ligne associée à la variable S dans la table d’analyse LL(1) est obtenue. Même question pour la ligne correspondant à GP.
Question 14.
Dérouler l’analyse LL(1) sur l’entrée art nom verbe art nom. À partir de cette analyse, comment retrouver la dérivation gauche associée à art nom verbe art nom ?
FAQ
Qu’est-ce qu’un automate fini ?
Un automate fini est un modèle mathématique utilisé pour reconnaître les langages réguliers. Il est composé d’un ensemble d’états, d’un alphabet, d’une fonction de transition et d’un ou plusieurs états finaux.
Comment fonctionne la boucle for in en Python ?
La boucle for in parcourt chaque élément d’une séquence (comme un tableau ou une chaîne de caractères) et exécute un bloc de code pour chaque élément.
À quoi sert la table d’analyse LL(1) ?
La table d’analyse LL(1) permet de déterminer si une grammaire est LL(1) et de construire un analyseur syntaxique pour cette grammaire, en garantissant une dérivation unique.