Examen TLA [PDF]

Zitiervorschau

É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