Title °EXAMENS compilation SMI5 FSA AGADIR.pdf ✅

1 Université Ibn Zohr SMI5/LPII-2018-2019 Faculté des Sciences Agadir Département Informatique Examen de Compilation : Session Rattrapage Durée 2H Partie 1 1) Donner un exemple de GHC constituée de trois productions, deux non terminaux et de trois terminaux. ........................................................................................................ ........................................................................................................ ........................................................................................................ ........................................................................................................ ........................................................................................................ ........................................................................................................ 2) Donner le schéma montrant les différentes phases d'un compilateur. Partie 2 Conserver dans (1) à (10) la ou les assertions justes. 1) Pour une grammaire hors contexte a) on doit avoir au moins un terminal. b) on doit avoir plus de deux terminaux. c) il n'est pas nécessaire d'avoir de terminaux. 2) Pour une grammaire hors contexte a) on doit avoir au moins une production. b) on doit avoir plus de deux productions. c) il n'est pas nécessaire d'avoir de productions. 3) Une grammaire hors contexte est constituée de a) 3-uplets. b) 4-uplets. c) 5-uplets. 4) Un lexème est un a) est un terminal. b) est un non terminal. c) est une production. 5) Une unité lexicale a) est un terminal. b) est un non terminal.
2 c) est une production. 6) Pour une grammaire hors contexte a) on doit avoir au moins un axiome. b) on doit avoir plus de deux axiomes. c) il n'est pas nécessaire d'avoir d'axiome. 7) Dans une grammaire hors contexte a) l'axiome est un terminal. b) l'axiome n'est pas un terminal. c) (a) ou (b) relativement à la grammaire. 8) Dans une grammaire hors contexte a) l'axiome est un non terminal. b) l'axiome n'est pas un non terminal. c) (a) ou (b) relativement à la grammaire. 9) Dans une grammaire hors contexte a) une sentence est constituée de terminaux. b) une sentence est constituée de non-terminaux. c) une sentence est constituée de terminaux et de non-terminaux. 10)Dans une grammaire hors contexte a) une forme sentencielle est constituée de terminaux. b) une forme sentencielle est constituée de non-terminaux. c) une forme sentencielle est constituée de terminaux et de non-terminaux. Partie 3 Exercice 1 Nous donnons la grammaire hors contexte suivante : (1) XY (2) XaY (3) YYbZ|c (4) Z d 1) Indiquer les terminaux, les non-terminaux et l'axiome. T= NT= Axiome= 2) Compléter le tableau suivant : Symbole Premier Suivant 3) Compléter le tableau suivant : Production Prédiction
3 4) Compléter la table d'analyse suivante(respecter l'ordre alphabétique des éléments de la grammaire) : 5) Cette grammaire est-elle LL(1)? La réponse doit être justifiée. 6) En complétant le tableau suivant, donner le processus de reconnaissance de la chaîne acbdd. pile entrée$ produc tion $ $ $ $ $ $ $ $ $ $ $ $ $ $ Exercice 2 Eliminer la récursivité gauche de la grammaire suivante: A Xa XXb|c|d Exercice 3 Soit l'automate A défini par la table de transition suivante. Il possède a comme état initial et b comme état final. Etat/Symbol 1 2 a a b b a,b A/ 1) Pourquoi cet automate n'est pas déterministe ? ........................................................................................................ ........................................................................................................ ........................................................................................................
4 2) Donner en termes d'expressions régulières le langage défini par l'automate A. ........................................................................................................ ........................................................................................................ ........................................................................................................ ........................................................................................................ B/ Pour transformer l'automate A en automate fini déterministe nommé Y, on vous demande de répondre aux questions suivantes : 1) Calculer y0=ε-f(a). ........................................................................................................ 2) Calculer T(y0,1). ........................................................................................................ 3) Calculer T(y0,2). ........................................................................................................ 4) Chercher les autres états de l'automate Y et le construire.