29 0 747KB
École Nationale d’Ingénieurs de Carthage
Université de Carthage
Examen Final 2
ème
Génie Informatique
AU : 2020-2021
TLA et Compilation
Enseignants : Mme M. Fourati, Mme E. Menif, Mr H. Ben Salem
Nom :……………………………………
Prénom :…………………………………
Durée : 1h30
CIN :……………………………………
Exercice 1 : Question du cours (points 3: 0,5 pour une bonne réponse, -0,25 pour une mauvaise réponse et 0 si pas de réponse) V 1. 2. 3. 4. 5. 6.
Toute grammaire non récursive à gauche peut être LL(1) Dans un automate LR(0), un item de la forme peut engendrer une action de réduction Pour une grammaire , ssi l’axiome à une production Une grammaire est LL(1) ssi toute case de sa table d’analyse contient au moins une règle de production Dans le terme SLR, la lettre R désigne le sens de parcours de la chaine Toute grammaire contextuelle est aussi une grammaire hors contexte
Exercice 2 :Automates à pile
3 points
Soit le langage 1. Donner un automate à pile qui reconnaisse
. (il est interdit d’utiliser le crayon)
2. Donner une grammaire , avec tous ses composants, qui génère . ..………………………….…………………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….……………………………………………………………………………………
Exercice 3 : Grammaires
Soit la grammaire
4 points
avec
formé des productions suivantes :
Page 1 sur 5
F
1. Éliminer les productions
de
.
..………………………….…………………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… 2. Éliminer la récursivité gauche dans . ..………………………….…………………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… 3. Donner la grammaire qui génère . ..………………………….…………………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….……………………………………………………………………………………
Page 2 sur 5
4. Transformer la grammaire pour la rendre sous forme normale de Chomsky. ..………………………….…………………………………………………………………………………………… ..………………………….…………………………………………………………………………………………… ..………………………….…………………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ..………………………….…………………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ..………………………….…………………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….……………………………………………………………………………………
Exercice 4 : Analyse syntaxique
10 points . L’ensemble des productions
On considère la grammaire
est le suivant :
1. Calculer les ensembles Premier (First) et Suivant (Follow) pour chaque variable Premier (First)
Suivant (Follow)
............................................................................... ...............................................................................
............................................................................... ...............................................................................
............................................................................... ...............................................................................
............................................................................... ...............................................................................
............................................................................... ...............................................................................
............................................................................... ...............................................................................
............................................................................... ...............................................................................
............................................................................... ...............................................................................
2. La grammaire est elle LL(1)? Justifier ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… ………..………………………….…………………………………………………………………………………… Page 3 sur 5
3. Terminer l’automate canonique LR(0) pour que les étiquettes manquantes des transitions.
par les items correspondants à chaque état de l’automate ainsi
4. Remplir la table d’analyse SLR(1)
Page 4 sur 5
École Nationale d’Ingénieurs de Carthage
Université de Carthage
Examen Final 2
ème
Génie Informatique
AU : 2020-2021
TLA et Compilation
Enseignants : Mme M. Fourati, Mme E. Menif, Mr H. Ben Salem
Nom :……………………………………
Prénom :…………………………………
Durée : 1h30
CIN :……………………………………
5. Simuler l’analyse ascendante SLR(1) de la chaîne
................................
................................
................................
........................................................
........................................................
...........................
........................................................
........................................................
...........................
........................................................
........................................................
...........................
........................................................
........................................................
...........................
........................................................
........................................................
...........................
........................................................
........................................................
...........................
........................................................
........................................................
...........................
........................................................
........................................................
...........................
........................................................
........................................................
...........................
........................................................
........................................................
...........................
........................................................
........................................................
...........................
........................................................
........................................................
...........................
........................................................
........................................................
...........................
........................................................
........................................................
...........................
........................................................
........................................................
...........................
........................................................
........................................................
...........................
........................................................
........................................................
...........................
........................................................
........................................................
...........................
........................................................
........................................................
...........................
........................................................
........................................................
...........................
Page 5 sur 5