|
Grammaire S-attribuéeUne grammaire S-attribuée est une grammaire ne contenant que des attributs synthétisés où chaque attribut ne dépend que des attributs fils. GénéralitésUn 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).
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.
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.  Méthodes d'évaluation des attributsLes méthodes d'évaluation des attributs permettent d'associer une action sémantique à tout non-terminal de la grammaire. Méthode à plusieurs passes
Méthode à une passe
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-hocIl 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 syntaxeProprié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. ExempleLa 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.
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épendancesUn 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 :
Ordre d'évaluation des attributsLorsque 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.  Une analyse syntaxique ascendanteUne 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
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
 Considérations pratiquesLes grammaires S-attribuées sont propres mais ne sont pas toujours efficaces
Notes et références
Articles connexesInformation related to Grammaire S-attribuée |
