Grammaire S-attribuée
Une 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és[modifier | modifier le code]
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 → A1...An 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 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 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.
Méthodes d'évaluation des attributs[modifier | modifier le code]
Les méthodes d'évaluation des attributs permettent d'associer une action sémantique à tout non-terminal de la grammaire.
Méthode à plusieurs passes[modifier | modifier le code]
- 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[modifier | modifier le code]
- 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[modifier | modifier le code]
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[modifier | modifier le code]
Propriété[modifier | modifier le code]
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[modifier | modifier le code]
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[modifier | modifier le code]
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[modifier | modifier le code]
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.
Une analyse syntaxique ascendante[modifier | modifier le code]
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[modifier | modifier le code]
- 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
Considérations pratiques[modifier | modifier le code]
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[modifier | modifier le code]
- 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.
