Théorie des langages : Td automates finis et compilation
Télécharger PDFUniversité de Caen – Année 2018/2019
UFR des Sciences – 2ème session
Mercredi 3 juillet
L3 – INF6ACT
Théorie des langages et compilation
durée : 2h
Documents autorisés : notes personnelles, diapositives du cours.
Chaque candidat doit, en début d’épreuve, porter son nom dans le coin de la copie réservée à cet usage. Il le cachettera par collage après la signature de la feuille d’émargement. Sur chacune des copies intercalaires, il portera son numéro de place.
Exercice I. Automate fini
On se donne l’automate fini suivant :
0 1 2 3
a, b a b a b a
Question 1
Donner la table de transitions de cet automate.
Question 2
Parmi les mots suivants, lesquels sont reconnus par l’automate ?
aaa, aba, aabbaba, abaaba, aababaaaa, abcb
Question 3
Quel est le langage reconnu par cet automate ?
Question 4
Déterminiser l’automate.
Question 5
On considère maintenant le langage : aba(a + b)*
Parmi les mots suivants, lesquels appartiennent à ce langage ?
aaa, aba, aabbaba, abaaba, aababaaaa, abcb
Question 6
Construire un automate fini reconnaissant ce langage.
Exercice II. Compilation
On souhaite ajouter à notre calculette le support des tableaux.
Pour la suite, on supposera qu’un tableau de taille connue et fixe 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 taille.
On utilise les opcodes suivants :
PUSHR n : P[sp-1] := P[P[sp-1] + n] ; sp += 2
STORER n : P[P[sp-2] + n] := P[sp-1] ; sp -= 2
Question 7
Compléter la trace d’exécution suivante.
pc || fp pile
====================================================
0 | PUSHI 3
0 [ ] 0
2 | PUSHI 3
0 [ 3 ] 1
4 | PUSHI 0
0 [ 3 3 ] 2
6 | PUSHI 1
0 [ 3 3 0 ] 3
8 | PUSHI 2
0 [ 3 3 0 1 ] 4
10 | PUSHI 5
0 [ 3 3 0 1 2 ] 5
12 | STORER 1
0 [ 3 3 0 1 2 5 ] 6
14 | PUSHI 0
0 [ 3 3 0 5 ] 4
16 | PUSHI 0
0 [ 3 3 0 5 0 ] 5
18 | PUSHR 1
0 [ 3 3 0 5 0 0 ] 6
20 | PUSHI 1
0 [ 3 3 0 5 0 3 ] 6
22 | SUB
0 [ 3 3 0 5 0 2 ] 6
23 | PUSHR 1
0 [ 3 3 0 5 0 2 3 ] 7
25 | STORER 1
0 [ 3 5 0 5 ] 5
27 | PUSHI 0
0 [ 3 5 0 5 0 ] 6
29 | PUSHR 1
0 [ 3 5 0 5 0 0 ] 7
31 | WRITE
0 [ 3 5 0 5 ] 5
32 | POP
0 [ 3 5 0 5 ] 4
33 | HALT
Question 8
Écrire le code MVaP correspondant à la fonction suivante :
int b = [2, 5, 6]
int f(x) { b[x] = 1; return b[x+1]; }
println(f(1))
Question 9
Compléter les actions de la grammaire suivante pour générer le code MVaP correct :
declaration returns [String code]
| ’int’ IDENTIFIANT ’=’ ’[’ elems ’]’ { $code = "PUSHI " + $size + "\n"; }
| ’int’ IDENTIFIANT ’=’ ’[’ elems ’]’ { $code = "PUSHI " + $size + "\n"; } ;
elems returns [String code, int size]
@init { $code = new String(); $size = 0; }
: ENTIER { $size++; $code += "PUSHI " + $ENTIER + "\n"; }
( ’,’ ENTIER { $size++; $code += "PUSHI " + $ENTIER + "\n"; })* )?
Question 10
Compléter les actions de la grammaire suivante pour générer le code MVaP :
instruction returns [String code]
| IDENTIFIANT ’[’ expr ’]’ ’=’ expr finInstruction { $code += "STORER " + $1 + "\n"; $code += $3; }
expr returns [String code]
| IDENTIFIANT ’[’ expr ’]’ { $code = "PUSHR " + $1 + "\n"; }
Exercice III. Analyse LLR et SLR
Question 11
Donner un arbre d’analyse pour le mot suivant : id [ nb ] [ nb ].
Question 12
Cette grammaire est-elle LL(1) ? Justifier.
Question 13
On considère la version augmentée de la grammaire G :
init → S
S → id A
A → [ B ] A | [ B ]
B → nb
On dispose de l’automate fini caractéristique des items LR(0) de G :
init → •S
S → •id A
A → •[ B ] A
A → •[ B ]
B → •nb
init → S•
S → id•A
A → [•B ] A
A → [•B ]
B → nb•
A → [ B•] A
A → [ B•]
A → [ B ]•A
A → [ B ]•
Question 13.a
Quel état de l’automate contient un conflit décaler/réduire ?
Question 13.b
Donner la table des ensembles Suivant.
Question 13.c
Expliquer comment le conflit décaler/réduire précédent se résout.
Question 14
On donne la table d’analyse SLR de G.
$ id nb [ ]
S A B
0 d 2 1
1 accepter
2 d 4 3
3 r S → id A
4 d 6 5
5 d 7
6 r B → nb
7 r A → [ B ] d 4 8
8 r A → [ B ] A
Question 14.a
Expliquer comment est déterminée la ligne associée à l’état 0.
Question 14.b
Expliquer comment est déterminée la ligne associée à l’état 1.
Question 14.c
Expliquer comment est déterminée la ligne associée à l’état 7.
Question 15
Question 15.a
Déroulez l’analyse SLR sur l’entrée id [ nb ] [ nb ].
Question 15.b
Grâce à cette analyse, comment obtient-on la dérivation droite pour id [ nb ] [ nb ] ?
Question 15.c
Déroulez l’analyse SLR sur l’entrée id [ nb [ nb ].
FAQ
Qu’est-ce qu’un automate fini déterministe (AFD) ?
Un automate fini déterministe est un modèle mathématique utilisé en informatique et en linguistique pour reconnaître des langages formels. Il se compose d’un ensemble d’états, d’un alphabet de symboles, d’une fonction de transition unique entre un état et un symbole, et d’un état initial et final. Chaque symbole ne peut mener qu’à un seul état pour un état donné.
Comment distinguer un langage LL(1) d’un langage non LL(1) ?
Un langage est LL(1) si sa grammaire permet une analyse syntaxique en un seul passage de gauche à droite, sans ambiguïté et en utilisant au plus une anticipation d’un symbole. Pour vérifier cela, on construit une table de prédiction LL(1) et on s’assure qu’il n’y a pas de conflits. Si la table contient des entrées avec plusieurs productions ou des erreurs, la grammaire n’est pas LL(1).
Quelle est la différence entre les opcodes PUSHR et STORER ?
L’opcode PUSHR n permet d’accéder à un élément de la pile en utilisant l’adresse calculée comme P[sp-1] + n, puis d’empiler ce résultat. L’opcode STORER n permet de stocker la valeur au sommet de la pile dans une position de la pile déterminée par P[sp-2] + n, puis de retirer les deux éléments du sommet de la pile.