Théorie des langages : Exercices automate fini l3 inf6act
Télécharger PDFUniversité de Caen - Année 2017/2018
UFR des Sciences - 1ère session
Lundi 19 mars
L3 – INF6ACT
Théorie des langages et compilation
Durée : 2 heures
Les notes de cours et TD sont autorisées.
Exercice I. Automate fini (à rendre avec l'exercice III)
Question 1. Quel est le langage reconnu par l'automate fini déterministe décrit par le graphe de transition ci-dessous ?
L'AFDA reconnaît les mots : ba, bb.
Question 2. On considère l'automate fini B représenté par le graphe de transition suivant :
L'AFDB reconnaît les mots : a, bb, ab, b.
a) Pourquoi l'automate B est-il non déterministe ?
L'automate B est non déterministe car il existe des transitions avec plusieurs étiquettes ou des transitions multiples depuis un même état pour une même entrée.
b) Donner 3 mots de longueur 3 acceptés par B et 2 mots de longueur 4 rejetés par B.
Exemples de mots acceptés : aab, bab, bbb.
Exemples de mots rejetés : aaaa, abbb.
c) Donner une expression régulière du langage reconnu par l'automate B.
L'expression régulière est : (a|b)*a(a|b) ou (a|b)*b(a|b) selon la structure exacte de l'automate.
Question 3. Donner la table de transition de l'automate B. Déterminiser cet automate.
La table de transition de l'automate B doit être complétée selon le graphe donné. Pour le déterminer, il faut fusionner les états non discriminables.
Question 4. Donner une grammaire qui engendre le langage reconnu par l'automate B.
Exemple de grammaire :
S → aS | bS | ε
S → aA | bB
A → aS | bS | ε
B → bS | aS | ε
Exercice II. Compilation (à rendre sur une copie séparée)
On cherche à ajouter l'opérateur ternaire ?: au langage de la calculette. Pour cela, on ajoute à la règle expression la syntaxe suivante :
expression returns [String code]
| ’(’ condition ’?’ e1=expression ’:’ e2=expression ’)’ { // À compléter };
La sémantique associée est : si la condition est vraie, alors la valeur de l'expression e1 est utilisée ; sinon, on utilise la valeur de l'expression e2.
Question 5. Compléter la trace d'exécution suivante.
pc || fp pile
====================================================
0 | JUMP 30
30 | PUSHI 0
32 | PUSHI 2
34 | CALL 2
2 | PUSHL -3
4 | PUSHI 1
6 | INF
7 | JUMPF 13
13 | PUSHL -3
15 | PUSHI 0
17 | PUSHL -3
19 | PUSHI 1
21 | SUB
22 | CALL 1
2 | PUSHL -3
4 | PUSHI 1
6 | INF
7 | JUMPF 13
13 | PUSHI 1
11 | JUMP 26
26 | STOREL -4
28 | RETURN
24 | POP
25 | MUL
26 | STOREL -4
28 | RETURN
36 | POP
37 | WRITE
38 | POP
39 | HALT
Question 6. Donner le code MVaP généré par le programme suivant :
int x = 1
println(1 + (x > 2 ? 4 : x))
Question 7. Compléter le code ANTLR pour obtenir la génération de code.
Exemple de complétion :
’(’ condition ’?’ e1=expression ’:’ e2=expression ’)’ :
{
String cond = $condition.code;
String e1 = $e1.code;
String e2 = $e2.code;
code = "CALL 2 POP " + cond + " JUMPF " + e2 + " " + e1 + " RETURN";
}
Question 8. Expliquer ce que fait le code MVaP donné en début d'exercice. Donner un programme produisant ce code.
Le code MVaP simule une opération ternaire en utilisant des appels de fonctions et des sauts conditionnels. Il calcule d'abord la condition, puis selon son résultat, exécute l'une des deux branches avant de retourner le résultat.
Exercice III. Analyse LL(1) (à rendre avec l'exercice I)
On considère la grammaire G qui engendre l'ensemble des mots ayant autant de a que de b.
Elle est définie par l'axiome S, les variables {S, C, D}, les terminaux {a, b} et les règles de production suivantes :
S → aDbS | bCaS | ε
D → aDbD | ε
C → bCaC | ε
Question 9. Donner pour le mot bbaaab un arbre d'analyse et la dérivation gauche associée.
Arbre d'analyse : (À compléter selon la dérivation)
Dérivation gauche :
S → bCaS
C → bCaC
a → a
C → bCaC
a → a
C → ε
S → aDbS
D → aDbD
b → b
D → ε
S → aDbS
D → aDbD
b → b
D → ε
S → ε
Question 10. Indiquer comment est déterminé l'ensemble Premier(S) et l'ensemble Suivant(C).
Premier(S) : {a, b}. Premier(S) est déterminé en analysant les règles de production de S.
Suivant(C) : {a, b, $}. Suivant(C) est déterminé en analysant les règles où C apparaît et en considérant les terminaux qui peuvent suivre C.
Question 11. Construire la table d'analyse LL(1) de la grammaire G. Qu'est-ce qui permet d'affirmer que cette grammaire est LL(1) ?
La table LL(1) est construite en utilisant les ensembles Premier et Suivant. La grammaire est LL(1) si aucun conflit n'existe dans la table (pas de case avec deux productions différentes).
Question 12.
a) Dérouler l'analyse LL(1) sur l'entrée bbaaab. À partir de cette analyse, comment retrouver la dérivation gauche associée à bbaaab ?
b) Dérouler l'analyse LL(1) sur l'entrée abab.
FAQ
Qu'est-ce qu'une grammaire LL(1) ?
Une grammaire LL(1) est une grammaire qui permet d'analyser une chaîne d'entrée de gauche à droite avec un seul symbole de regard en avant (1), sans ambiguïté.
Comment déterminer un automate fini déterministe à partir d'un non déterministe ?
On utilise la méthode de la fermeture transitive ou la construction de l'automate par produit pour éliminer les transitions non déterministes.
Quelle est la différence entre Premier et Suivant dans une grammaire ?
Premier(X) est l'ensemble des terminaux qui peuvent démarrer une dérivation de X, tandis que Suivant(X) est l'ensemble des terminaux qui peuvent suivre immédiatement X dans une dérivation.