Université Bordeaux 1 | UFR Mathématiques et Informatique |
Session de septembre 1998 | Epreuve de J.Bétréma |
Maîtrise d'informatique
Compilation
Durée : 3 heures
Tous documents interdits.
Les exercices sont indépendants.
Soit G la grammaire :S -> T | U T -> a T b T | ε U -> a T b U | a S
- G est-elle ambiguë ?
Note : pour répondre à cette question on pourra donner une interprétation graphique du langage reconnu par cette grammaire.
- G est-elle LL(1) ?
- Construire l'automate associé à un analyseur ascendant de G. Analyser les conflits. G est-elle LR(0) ? G est-elle SLR(1) ?
- Détailler le fonctionnement d'un analyseur syntaxique ascendant pendant l'analyse de abaab, en utilisant une table à deux colonnes : action (décalage ou réduction) et contenu de la pile.
Soit G la grammaire habituelle des expressions postfixées :On modifie cette grammaire pour ajouter des sommes et des produits avec un nombre variable de termes, analogues aux notations mathématiques Σ et Π. Par exemple :E -> E E + | E E * | id | numdésigne Π(x+i) pour i variant entre 1 et 3, soit en notation postfixée :produit (i = 1 .. 3, x i +)A cet effet on ajoute les règles :x 1 + x 2 + * x 3 + *Dans toute la suite G désigne la grammaire ainsi complétée.E -> U (id = num .. num, E) U -> somme | produit
- Ecrire un analyseur lexical (dans le format reconnu par lex) pour G.
Note : choisir une définition simple et raisonnable des identificateurs et des constantes numériques.
- G est-elle LL(1) ?
- Construire l'automate associé à un analyseur ascendant de G. Analyser les conflits. G est-elle LR(0) ? G est-elle SLR(1) ?
- Ecrire dans le format reconnu par yacc un programme qui traduise une expression engendrée par G en une expression postfixée ordinaire, c'est-à-dire débarrassée des sommes et produits ajoutés par les nouvelles règles. Voir ci-dessus un exemple d'une telle traduction.
Note : on définira avec soin les attributs nécessaires.