Grammaire attribuée

Une grammaire attribuée est une manière formelle de définir des attributs pour les productions d'une grammaire, associant ces attributs à des valeurs. L'évaluation a lieu dans les nœuds de l'arbre syntaxique abstrait quand le langage est traité par un analyseur syntaxique ou un compilateur.

Les attributs sont divisés en deux groupes : les attributs synthétisés et les attributs hérités. Les attributs synthétisés sont le résultat des règles d'évaluation des attributs ; ils peuvent aussi utiliser les valeurs d'attributs hérités. Les attributs hérités sont passés vers les feuilles à partir des nœuds parents.

Dans certaines approches, on utilise les attributs synthétisés pour passer des informations sémantiques vers la racine de l'arbre. De même, les attributs hérités permettent de passer des informations sémantiques vers les feuilles. Par exemple, lors de la construction d'un outil de traduction de langage, tel qu'un compilateur, on peut utiliser une grammaire attribuée pour affecter des valeurs sémantiques à des constructions syntaxiques. Il est aussi possible de faire des validations sémantiques associées à une grammaire. Ces validations sémantiques représentent les règles du langage non explicitement importées par la syntaxe.

On peut aussi utiliser des grammaires attribuées pour traduire l'arbre syntaxique directement en code pour une machine spécifique, ou dans un langage intermédiaire.

Les grammaires attribuées peuvent transporter de l'information de n'importe où vers n'importe où dans l'arbre abstrait, d'une manière contrôlée et formelle. C'est leur force.

Histoire

Les grammaires attribuées furent inventées par Donald Knuth et Peter Wegner. Alors que Donald Knuth conçut l'idée générale, Peter Wegner inventa les attributs hérités pendant une conversation avec Knuth. Des idées embryonnaires peuvent être retrouvées dans le travail d' Edgar T. « Ned » Irons, l'auteur de IMP.

Types de grammaires attribuées

Liens externes

Bibliographie sur les grammaires attribuées
Why Attribute Grammars Matter, The Monad Reader, Issue 4, July 5th 2005
Semantics of context-free grammars, de Donald Knuth, papier original qui introduit les grammaires attribuées.
D. E. Knuth: The genesis of attribute grammars. Proceedings of the international conference on Attribute grammars and their applications (1990), 1–12.
Jukka Paakki: Attribute grammar paradigms—a high-level methodology in language implementation. ACM Computing Surveys 27:2 (June 1995), 196–255.