Grammaire S-attribuée

Une grammaire S-attribuée est une grammaire ne contenant que des attributs synthetisés où chaque attribut ne dépend que des attributs fils.

Généralités

Un bon compilateur permet de traduire un code source en code objet. Il effectue trois phase d'analyse: l'analyse lexicale, syntaxique et sémantique. La phase d'analyse sémantique permet de calculer tous les attributs en évaluant toutes les conditions de contexte. Ainsi: le but d'une grammaire attribuée participe à produire non pas seulement un code objet valide mais aussi efficace. Les grammaires attribuées sont en fin de compte des grammaires non contextuelles déjà utilisées dans l'analyse syntaxique étendues aux calculs nécessaires pour l'analyse sémantique. Pour cela deux mécanismes sont mis en place: l'un pour les données et l'autre pour les calculs (Définition dirigée par la syntaxe/Traduction dirigée par la syntaxe).

• Pour tout symbole grammatical X, terminal ou non terminal, on spécifie zéro ou plusieurs attributs: chacun avec un nom et un type. Ce sont des attributs formels et servent à conserver les informations relatives à S, nœud d'un arbre abstrait.
• A chaque production A → A1...An, est associée un ensemble de règles d'évaluation des attributs qui expriment certains des attributs de la partie gauche A et des membres de la partie droite Ai,en termes de valeurs d'autres, attributs. Ces règles d'évaluation vérifient également des conditions de contexte et fournissent des messages d'avertissement ou d'erreur (règles associées au production plutôt qu'aux non terminaux).

• Définition d'attribut

Un attribut est une information jugée utile pour le processus de compilation (valeur, types etc....).

Les attributs de chaque symbole non terminal sont divisés en deux groupes: les attributs synthétisés et les attributs hérités. Notons que la production doit avoir A comme partie gauche.

• Notion d'attribut synthétisé

Un attribut synthétisé d'un non terminal A à un nœud N d'un arbre d'analyse est défini par une règle sémantique associée à la production en N.

Attribut synthétisé

Méthodes d'évaluation des attributs

Les méthodes d'évaluation des attributs permettent d'associer une action sémantique à tout non-terminal de la grammaire.

Méthode à plusieurs passes

• Créer l'arbre syntaxique
• Créer le graphe de dépendances d’attributs
• Générer un ordre d’evaluation : tri topologique

Méthode à une passe

• Les règles sémantiques sont exécutées dans un ordre décrit par la grammaire pendant l’analyse syntaxique.
• L'utilisateur doit tenir compte de ce fait pour concevoir sa définition dirigée par la syntaxe.

La méthode à une passe essaye de faire coïncider la phase d’analyse synthétique avec l’avaluation des attributs. Deux cas de figures se présentent : évaluation ascendante (coincidant avec une analyse LR) et descendante (coïncidant avec une analyse LL).

Ad-hoc

Il s'agit de faire à notre convenance. Si le graphe de dépendances d'attributs contient un cycle, alors nous sommes obligés d'utiliser des méthodes ad-hoc. En général, c'est déconseillé à un compilateur d'avoir un graphe de dépendances d'attributs cyclique.

Traduction dirigée par la syntaxe

Propriété

Une Traduction dirigée par la syntaxe qui n'impliquent que les attributs synthétisés est appelée S-attribuée. Chaque règle calcule un attribut pour le non-terminal en partie gauche de la production à partir de la partie droite de la production.

Exemple

La traduction dirigée par la syntaxe s'appuie sur notre grammaire usuelle des expressions arithmétiques avec les opérateurs + et *. Dans la traduction dirigée par la syntaxe, chacun des non terminaux a un attribut synthétisé unique appelé val. Nous supposons aussi que le terminal nbr a un attribut synthétisé vallex, à valeur entière rendu par l'analyseur lexical.

grammaire usuelle des expressions arithmétiques
L → E
E → E+T | T
T → T∗F | F
F → ( E ) | nbr

Production	Règle sémantique
E → T	E.val=T.val
E → E1+T	E.val=E1.val+T.val
E → T	E.val=T.val
T → T1*F	T.val=T1.val*F.val
T → F	T.val=F.val
F → E	F.val=E.val
F → nbr	F.val=nbr.vallex

• Une règle sémantique est une fonction associée à une production syntaxique permettant de calculer la valeur d'un attribut. Elle est exécutée lorsque la production est effectuée.

• Remarque: Certaines règles sémantiques comportent des effets de bord (cf la première règle).

Elles ne calculent aucun attribut explicitement, mais génèrent un résultat de traitement (ici affichage à l'écran). Cette DDS S-attribuée peut être implémentée naturellement en relation avec un analyseur LR Intuitivement, les attributs synthétisés sont bien adaptés aux analyses syntaxiques ascendantes.

Graphe de dépendances

Un graphe de dépendances est un outil utile pour déterminer un ordre d'évaluation pour les instances d'attributs dans un arbre d'analyse donné. Alors qu'un arbre d'analyse décoré montre la valeur des attributs, un graphe de dépendances aide à déterminer comment ces valeurs peuvent être calculées. Les arcs expriment les contraintes impliquées par les règles sémantiques. Précisément:

• Pour tout arbre d'analyse, pour tout nœud étiqueté par le symbole X, le graphe de dépendance a un nœud pour chaque attribut associé à X.
• A chaque nœud N étiqueté A de production p, on crée un arc vers l'attribut b de N depuis l'attribut C du fils de N correspondant à l'instance du symbole X dans la partie droite de la production.

Ordre d'évaluation des attributs

Lorsque la traduction dirigée par la syntaxe est s-attribuée, on peut évaluer ses attributs dans n'importe quel ordre ascendant des nœuds de l'arbre d'analyse. Il est souvent très simple d'évaluer les attributs en effectuant un parcours postfixe de l'arbre d'analyse. S'il y a un circuit dans le graphe, il n'existe pas de tri topologique: il n y a donc aucun moyen d'évaluer les nœuds avec cet arbre d'analyse.

Ordre d'évaluation

Une analyse syntaxique ascendante

Une traduction dirigée par la syntaxe s-attribuées peut être implémentée au cours d'une analyse ascendante, puisqu'une analyse ascendante correspond à un parcours postfixe. Précisément: si la grammaire sous-jacente est LR, elle peut être implémentée sur la pile d'analyse LR.

Equivalence entre grammaire S-attribuée et grammaire L-attribué

• Quel type de grammaire choisir

Pour utiliser yacc efficacement, il serait plus intéressant de construire une grammaire S-attribuée afin de calculer les attributs en une seule passe. Supposons que vous avez une grammaire L-attribuée, et vous voulez utiliser yacc

• Transformation d’une grammaire l-attribuée vers s-attribuée

Ordre d'évaluation

Considérations pratiques

Les grammaires S-attribuées sont propres mais ne sont pas toujours efficaces

• Nécessite beaucoup de copies d’attributs : redondance d’information, consommation d’espace mémoire
• Résultats propagés vers la racine d’un arbre syntaxique décoré (théoriquement!)

Notes et références

• Cours ISTY 2 Sid TOUATI (Cours de compilation)
• Compilateurs : Principes, techniques et outils. A. Aho, R. Sethi et J. Ullman. InterEditions.
• Compilateurs. D. Grune, H.E. Bal, G. J.H. Jacobs, K.G. Langendoen. Editions Dunod.
• Lex & yacc. John R. Levine, Tony Mason et Doug Brown. Edition O’Reilly.

Articles connexes

• Compilateur
• Automate fini
• Grammaire non contextuelle
• Grammaire L-attribuée
• Analyse LL
• Table des symboles