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.

Exercice 1

Soit G la grammaire :
S -> T | U
T -> a T b T | ε
U -> a T b U | a S
  1. G est-elle ambiguë ?

    Note : pour répondre à cette question on pourra donner une interprétation graphique du langage reconnu par cette grammaire.

  2. G est-elle LL(1) ?

  3. Construire l'automate associé à un analyseur ascendant de G. Analyser les conflits. G est-elle LR(0) ? G est-elle SLR(1) ?

  4. 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.

Exercice 2

Soit G la grammaire habituelle des expressions postfixées :
E -> E E + | E E * | id | num
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 :
produit (i = 1 .. 3, x i +)
désigne Π(x+i) pour i variant entre 1 et 3, soit en notation postfixée :
x 1 + x 2 + * x 3 + *
A cet effet on ajoute les règles :
E -> U (id = num .. num, E)
U -> somme | produit
Dans toute la suite G désigne la grammaire ainsi complétée.
  1. 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.

  2. G est-elle LL(1) ?

  3. Construire l'automate associé à un analyseur ascendant de G. Analyser les conflits. G est-elle LR(0) ? G est-elle SLR(1) ?

  4. 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.