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.
Grammaire |
---|
E → E + T {écrire ”+”} |
| T |
T → T * F {écrire “*”} |
| F |
F → (E) |
| id {écrire valeur id} |
Traduction de (a+b)*c
en utilisant une dérivation gauche :
E | → | T |
→ | T * F {écrire “*”} | |
→ | F * F {écrire “*”} | |
→ | (E) * F | |
→ | (E + T {écrire ”+”} * F {écrire “*”} | |
→ | (T + T {écrire ”+”} * F {écrire “*”} | |
→ | (F + T {écrire ”+”} * F {écrire “*”} | |
→ | (id + T {écrire ”+”} * F {écrire “*”} | |
→ | (id {écrire “a”} + T {écrire ”+”} * F {écrire “*”} | |
→ | (id {écrire “a”} + F {écrire ”+”} * F {écrire “*”} | |
→ | (id {écrire “a”} + id {écrire “b”} {écrire ”+”} * F {écrire “*”} | |
→ | (id {écrire “a”} + id {écrire “b”} {écrire ”+”} * id {écrire “c”}{écrire “*”} |
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
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.
Grammaire (non-attribuée) | ||
---|---|---|
E | → | E+T |
| | T | |
T | → | T*F |
| | F | |
F | → | (E) |
| | I | |
I | → | I chiffre |
| | chiffre |
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.
Grammaire (non-attribuée) | Grammaire attribuée | |||||
---|---|---|---|---|---|---|
E | → | E+T | E | → | E(1)+T {E.val=E(1).val+ T.val} | |
| | T | | | T {E.val=T.val} | |||
T | → | T*F | T | → | T(1)*F {T.val=T.(1).val*F.val} | |
| | F | | | F {T.val=F.val} | |||
F | → | (E) | F | → | (E) {F.val=E.val} | |
| | I | | | I(1) {F.val = I.val} | |||
I | → | I chiffre | I | → | I chiffre {I.val * 10 + valeur(chiffre) } | |
| | chiffre | | | chiffre {I.val = valeur(chiffre) |
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\}
Pile (avant) | ||
---|---|---|
Z | Z_{z_1} Z_{z_2} | ← top |
Y | Y.y | |
X | X.x | |
… |
Pile après réduction | ||
---|---|---|
A | A.a | ← top |
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.
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.
Grammaire (non-attribuée) | Grammaire attribuée |
---|---|
D → T L | D → T L {L.her=T.type} |
T → int | T → int {T.type = entier} |
| float | | {T.type=réel} |
L → L ”,” id | L → L(1) ”,” id {L(1).her=L.her, ajout-type(id.ptr, L.her)} |
| id | | id {ajout-type(id.ptr, L.her)} |
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.
rajouter l'exemple
a | Les actions sont exécutées au moment des réductions ⇒ elles doivent être placées en fin de règle. | |
---|---|---|
Sol'n | Transformer la grammaire pour déplacer les actions en fin de règles. On introduit les marqueurs : un non-terminal M et une règles M\rightarrow \epsilon. On remplace l'action en milieu de règle par un marqueur M et on associe l'action à la règle M\rightarrow \epsilon. | |
ex | E' → +T {écrire(”+”)} E' devient E' → +TME' M→ epsilon {écrire(”+”)+ |
|
b | La restriction (pas de dépendance envers les frères droits) permet de garantir que la valeur d'un attribut hérité est toujours quelque part au sommet de la pile. Le problème est de savoir où cette valeur se trouve. | |
Sol'n | Modifier la grammaire de façon à ce que l'emplacement de la valeur d'un attribut hérité soit toujours le même quelque soit les règles utilisées. | |
ex.1 | S → AX {X.her=A.synth} (1) S → ADX {X.her=A.synth} (2) X → Y {X.synth=f(X.her)} |
|
Au moment de la réduction X → Y on a besoin de la valeur de X.her : il faut accéder à la valeur de A.synth. Or, cette valeur se trouve à top-1 si la règle (1) a été utilisée et à top-2 si c'est la règle (2) qui a été utilisée. | ||
Sol'n 1 | S→ AMX {X.her=A.synth} S → ABX {X.her=A.synth} X→ Y {X.synth=f(X.her)} M → epsilon la valeur de A.synth se trouve à top-2. |
|
Sol'n 2 | S → AX {X.her=A.synth} S → ABMX {X.her=M.synth;M.her=A.synth} X → Y {X.synth=f(X.her)} M → epsilon { M.synth=M.her} la valeur de A.synth se trouve à top-1. |
|
ex.2 | Cas où la valeur de l'attribut hérité n'est pas une simple copie d'une valeur d'un attribut synthétisé mais calculé avec une fonction (f'). | |
Sol'n | Empiler le résultat du calcul | |
S → AX {X.her=f'(A.synth)} X→ Y {X.synth=f(X.her)} |
||
devient : | ||
S → AMX {X.her=M.synth; M.her=A.synth} X → Y {X.synth=f(X.her)} M → epsilon {M.synth=f'(M.her)} |
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.
D → T L | {ajout-type(L.liste,T.type)} |
T → int | {T.type = entier } |
| float | {T.type=réel} |
L → L(1) id | {L.liste=ajout-liste(L(1).liste, id.ptr)} |
| id | {L.liste=crée-liste(id.ptr)} |
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)