S -> S A B | epsilon
  
  A -> A a | a
  
  B -> B b | b

1. Donner un arbre de dérivation de u pour la grammaire G. G est-elle ambiguë ?

2. Donner deux expressions rationnelles simples pour le langage L reconnu par G. Donner l'automate (déterministe) minimal qui reconnaît L (on ne demande pas de prouver qu'il est bien minimal).

3. Calculer les fonctions premier et suivant pour chacun des trois symboles non terminaux A, B, S de la grammaire G.

4. Donner la table d'analyse descendante de G. G est-elle LL(1) ? Peut-on répondre à cette dernière question sans construire la table ?

   Rappel : les lignes de la table d'analyse descendante sont indexées par les symboles non terminaux (ici A, B, S), et les colonnes par les symboles terminaux (ici a, b) et par le symbole de fin de chaîne $. La cellule (X,x) contient la ou les règles applicables, s'il en existe, pour dériver X lorsque le symbole à lire est x.

5. Calculer l'automate associé à un analyseur ascendant de G (automate dit des 0-items, ou LR(0)). G est-elle LR(0) ? SLR(1) ?

6. Faire fonctionner l'analyseur ascendant (analyseur à pile) pour reconstruire l'arbre de dérivation de u = aabbbabb.

   Note : utiliser une table à deux colonnes, l'une indiquant l'action à réaliser (empiler ou réduire par la règle n ; les 6 règles seront numérotées dans l'ordre où elles apparaissent en tête de l'énoncé), et l'autre l'état de la pile.

7. On remplace a par le chiffre 1, b par 0, et on considère tout mot w du langage L reconnu par G comme représentant un entier n(w) en numération binaire. Par exemple n(u) = 4 + 64 + 128 = 196. Définir un système d'attributs, associé à G, qui calcule n(w). Ecrire le programme yacc correspondant.