• Objectif : réaliser la traduction d'un texte (ou d'un programme) dans un code intermédiaire equivalent.
• Idée : associer des informations aux règles de grammaire. On distingue parmi les grammaires ainsi enrichies :
  • grammaires de traduction
  • grammaires attribuées

On associe aux règles de grammaire un appel à une fonction d'écriture.

Pour traduire une expression arithmétique infixée en une expression postfixée equivalente on lit l'expression et on écrit sa traduction au fur et à mesure.

• une opérande peut être écrite dès qu'elle est lue;
• une opération ne peut être écrite qu'après lecture de ses deux opérandes.

Traduction de (a+b)*c en utilisant une dérivation gauche :

Un autre exemple de grammaire, où les actions sont placées au milieu des règles :

\displaystyle \begin{eqnarray} E & \rightarrow & T\;E' \\ E' & \rightarrow & +T \left\{\text{ecrire "+"}\right\} E' \\ & | & \epsilon \\ T & \rightarrow & FT' \\ T' & \rightarrow & * F \left\{\text{ecrire "*"}\right\} T' \\ & | & \epsilon \\ F & \rightarrow & (E) \\ & | & id \left\{ \text{ecrire valeur(id)}\right\} \\ \end{eqnarray}

A chaque terminal ou non-terminal, on associe un ou plusieurs attributs. On calcule les attributs à partir d'autres attributs en ajoutant des action sémantiques aux règles de grammaire. Ainsi la valeur d'un attribut associé à un noeud de l'arbre de syntaxe est calculée à partir de la valeur d'autres attributs associés à d'autres noeuds de l'arbre. On distingue

• les attributs synthétisés
• les attributs hérités

• La valeur d'un attribut synthétisé associé à un noeud de l'arbre est calculée à partir des attributs associés aux fils de ce noeud.

• La valeur d'un attribut hérité associé à un noeud de l'arbre est calculée des valeurs des attributs associés au père et aux frères de ce noeud.

Un grammaire S-attribuée est une grammaire attribuée dont tous les attributs sont synthétisés.

Exemple (calculette de poche). Pour traduire une expression arithmétique simple (sans variable) en une valeur résultat de l'évaluation d'une expression.

On associe à E (resp. T, F, I, chiffre) un attribut synthétisé E.val (resp. T.val, F.val, I.val, chiffre). Cet attribut a pour valeur celle de la sous-expression correspondante.

Traduction de 12 + 3 * 5

chiffre   chiffre    chiffre         chiffre
   /         |          |               |   
  I.val=1    | .val=2   |.val=3         |.val=5
  \         /           |               |
   \       /            |               |
     I.val=12          I.val=3          |
      |                 |               |
     F.val=12          F.val=3         I.val=5
      |                 |               |
     T.val=12          T.val=3  *     F.val=5
      |                  \       |      /
      |                   \      |     /
      |                    \     |    /
      |                     \    |   /
      |                      \   |  /
     E.val=12                   T.val=3*5=15
       \                        /
        \          '+'         /
         \          |         /
          \         |        /
           \        |       /
            \       |      /
                   
                   E.val=12+15=27

Puisque le calcul des attributs s'effectue en remontant dans l'arbre, les attributs peuvent être évalués en même temps que le texte est analysé. Il suffit de mémoriser la valeur des attributs au sommet de la pile. Le calcul des attributs est réalisé au moment des réductions.

A\rightarrow XZY; \left\{A.a=f\left(X.x, Y_y Z_{z_1} Z_{z_2}\right)\right\}

Attention : l'action sémantique associée à une règle ne doit utiliser que les terminaux ou les non-terminaux qui apparaissent dans cette règle (de façon à ce que les valeurs nécessaires aux calculs des attributs soient présentes au sommet de la pile).

A -> XY
Y -> UV
A.att = f(X.att, U.att)

Il faut faire monter dans l'arbre “U.att” pour pouvoir calculer A.att au moment de la réduction A → XY. Une (la?) solution est de faire monter la valeur comme ceçi (passant U.att via Y.att) :

A -> XY {A.att=f(X.att, Y.att)}
Y -> UV {Y.att = U.att}

Une grammaire L-attribuée est une grammaire attribuée dont les attributs sont soit synthétisés, soit hérités, avec la seule restriction que les attributs hérités ne dépendent pas des frères droits.

Une déclaration de variables est un mot-clef signifiant un type suivi d'une liste d'identificateurs. On souhaite mettre à jour la table des symboles.

• On associe à T un attribut synthétique dont la valeur est le type correspondant à T.
• On associe à L un attribut hérité dont la valeur est le type des identificateurs de la liste L.
• On associe à id un attribut synthétique dont la valeur est le pointeur dans la table des symboles sur l'identificateur id.

On définit une fonction ajout-type(p,t) qui accède à la table de symboles et mémorise que l'objet pointé par p est de type t [ce pointeur est défini au moment de l'analyse lexicale]. Les attributs sont donce T.type, L.her, et id.ptr.

int x,y,z

rajouter schéma de l'arbre

Mais est-ce faisable? Il faut faire attention aux positionnements des actions.

Afin de garantir la faisabilité des actions, elles doivent pouvoir être positionnées correctement selon les principes suivants.

• Les actions qui utilisent uniquement les attributs synthétisés doivent être placées en fin de règle.
• Les autres actions–qui utilisent à la fois des attributs synthétisés et des attributs hérités–doivent être placées de façon à respecter les trois propriétés suivantes :
  1. un attribut hérité d'un symbole à droite d'une règle doit être calculé par une action qui se trouve avant le symbole dans la règle
  2. une action ne peut pas utiliser un attribut synthétisé d'un symbole qui se trouve à sa droite
  3. un attribut synthétisé du symbole à gauche d'une règle doit être calculé par une action que se trouve en fin de règle.

rajouter l'exemple

En pratique, YACC ne permet pas de manipuler les attributs hérités ⇒ préférer un schéma de translation S-attribué.

Retour sur les déclarations de variables en utilisant uniquement les attributs synthétisés. On associe à L un attribut synthétisé L.liste dont la valeur est la liste des pointeurs sur les identificateurs de L.

int x,y,z
 
int  
 | 
T.type=entier
 |
 |      id[x]
 |      |
 |     L.liste=[x]
 |       \        ","   id[y]
 |        \        |    /
 |         \       |   /
 |          \      |  /
 |  
 |              L.liste=[x,y]
 |                \          ","  id[z]
  \                \        /     /
   \                \      /     /
    \                \    /     /     
     \ 
      \            L.liste=[x,y,z]
       \           /
        \         /
         \       /
        
          D:ajout-type([x,y,z], entier)