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 phases 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.
À chaque production A → A₁...A_n est associé 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 A_i, 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 aux productions 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’évaluation : 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’évaluation des attributs. Deux cas de figure se présentent : évaluation ascendante (coïncidant 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'implique 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.
À 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ée 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.

Équivalence entre grammaire S-attribuée et grammaire L-attribuée

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

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.