L10) Grammaires d’attributs

Quand les arbres portent des propriétés

Un arbre syntaxique n’est pas qu’une structure. Il porte du sens : des valeurs montent depuis les feuilles, des contraintes descendent depuis la racine. Les grammaires d’attributs formalisent ces deux flux d’information — et révèlent pourquoi les flags de BP3 (Bol Processor 3, logiciel de composition algorithmique fondé sur des grammaires formelles) sont plus puissants qu’il n’y paraît.

Où se situe cet article ?

Dans les arbres syntaxiques (L4), nous avons découvert l’AST : une représentation arborescente du code source qui conserve la structure logique en éliminant le bruit syntaxique. Mais un AST nu est comme un squelette sans muscles — il montre la forme, pas la fonction.

Cet article prolonge L4 en montrant comment décorer un arbre syntaxique avec des propriétés calculées. L’idée, due à Donald Knuth (1968), est à la fois simple et profonde : chaque noeud de l’arbre porte des attributs dont les valeurs sont déterminées par des règles sémantiques attachées aux productions de la grammaire.

Liens dans la série :

L1 — La hiérarchie de Chomsky — le cadre classificatoire des grammaires
L4 — Les arbres syntaxiques — la structure que les attributs viennent enrichir
L8 — La sémantique axiomatique — une autre façon d’ajouter du sens au-delà de la syntaxe

Pourquoi c’est important ?

Chaque compilateur que vous utilisez repose, d’une manière ou d’une autre, sur des grammaires d’attributs. Quand le compilateur C vérifie que vous n’additionnez pas un entier et un pointeur, il propage des types de bas en haut dans l’arbre. Quand il alloue des registres, il transmet des contraintes de haut en bas. Ces deux flux — montée et descente — sont exactement ce que les grammaires d’attributs formalisent.

Mais il y a une seconde raison, moins attendue. Dans BP3, les flags (ces compteurs conditionnels qui contrôlent l’application des règles de grammaire) ressemblent étrangement à des attributs. Comprendre les grammaires d’attributs nous donnera le vocabulaire pour situer les flags dans un spectre d’expressivité, et comprendre pourquoi leur portée globale a des conséquences théoriques profondes.

L’idée en une phrase

Une grammaire d’attributs est une grammaire context-free enrichie de propriétés calculables attachées aux noeuds de l’arbre syntaxique, certaines montant des feuilles vers la racine (synthétisées), d’autres descendant de la racine vers les feuilles (héritées).

Expliquons pas à pas

L’arbre qui calcule

Prenons une expression arithmétique toute simple : 3 + 4 * 2. Son AST ressemble à ceci :

Jusque-là, c’est un arbre muet. Il montre la structure, pas le résultat. Mais si on ajoute un attribut val à chaque noeud, l’arbre se met à calculer :

        (+)  val = 11
       /   \
val=3 3    (*)  val = 8
          /   \
   val=4 4     2  val=2

Que s’est-il passé ? Les feuilles connaissent leur propre valeur (c’est immédiat : un littéral vaut ce qu’il vaut). Ensuite, l’attribut val remonte : le noeud (*) calcule 4 * 2 = 8 à partir de ses enfants, puis le noeud (+) calcule 3 + 8 = 11. L’information circule de bas en haut, des feuilles vers la racine.

Ce flux ascendant a un nom : c’est un attribut synthétisé (synthesized attribute). Le noeud parent synthétise sa valeur à partir de celles de ses enfants, comme un manager qui résume les rapports de son équipe.

Décryptage : L’attribut val est synthétisé parce que chaque noeud le calcule à partir de ses enfants, jamais à partir de son parent. La règle pour la production E -> E1 + E2 est : E.val = E1.val + E2.val. C’est une équation locale : on n’a besoin que des voisins immédiats.

Attributs synthétisés : de bas en haut

Formalisons. Un attribut synthétisé (synthesized attribute) est un attribut dont la valeur, pour un noeud donné, est calculée exclusivement à partir des attributs de ses enfants dans l’arbre.

Prenons l’exemple de la vérification de types. Voici une grammaire simplifiée avec des règles sémantiques :

Production               Règle sémantique
─────────────────────────────────────────────
E  ->  E1 + E2          E.type = if E1.type == E2.type
                                  then E1.type
                                  else error

E  ->  E1 * E2          E.type = if E1.type == E2.type
                                  then E1.type
                                  else error

E  ->  num               E.type = int
E  ->  real              E.type = float

Décryptage : Production : E -> E1 + E2. Règle sémantique : E.type = .... Le type du noeud parent E est synthétisé à partir des types de ses enfants E1 et E2. Si les deux enfants ont le même type, le parent hérite de ce type. Sinon, c’est une erreur. Pas besoin de regarder plus haut dans l’arbre.

C’est ainsi que fonctionne la vérification de types dans presque tous les compilateurs : les types montent des feuilles (littéraux, variables dont le type est connu) vers la racine (l’expression complète), en se combinant à chaque noeud selon les règles de compatibilité du langage.

Attributs hérités : de haut en bas

Mais tout ne monte pas. Certaines informations descendent. Prenons un exemple classique : la déclaration de variables.

int x, y, z;

Le type int est déclaré une seule fois, en tête. Il doit ensuite être transmis à chaque variable de la liste. L’arbre ressemble à ceci :

       (Décl)
       /    \
    int     (Liste)
           /   |   \
          x    y    z

Le type int n’est pas calculé par les feuilles x, y, z — il leur est transmis par le haut. C’est un attribut hérité (inherited attribute) : le parent (ou un frère aîné) communique une information à ses descendants.

Production                    Règle sémantique
──────────────────────────────────────────────────
Décl -> Type Liste            Liste.type_decl = Type.type
Liste -> Liste1 , id          Liste1.type_decl = Liste.type_decl
                              id.type_decl = Liste.type_decl
Liste -> id                   id.type_decl = Liste.type_decl

Décryptage : L’attribut type_decl (le type déclaré) est hérité : il descend de Décl vers Liste, puis de Liste vers chaque id. Les feuilles ne le calculent pas — elles le reçoivent. C’est le contraire d’un attribut synthétisé.

L’analogie est celle d’un arbre généalogique où les coutumes familiales se transmettent de parent à enfant. Le grand-parent décide « nous sommes des entiers », et chaque descendant hérite de cette convention.

Convention importante : le symbole de départ (la racine de l’arbre) n’a pas d’attributs hérités. C’est logique : il n’a pas de parent pour lui transmettre quoi que ce soit. L’information qui entre dans l’arbre doit commencer soit par les feuilles (synthétisée), soit par la racine (mais les attributs hérités de la racine, s’il y en avait, devraient venir de nulle part).

Le graphe de dépendances

Dans un arbre décoré, certains attributs dépendent d’autres. Le graphe de dépendances (dependency graph) rend ces relations explicites. Chaque attribut est un noeud du graphe, et une arête va de A vers B si la valeur de B dépend de celle de A.

Reprenons notre expression 3 + 4 * 2 avec un attribut synthétisé val et ajoutons un attribut hérité base (imaginons un système de numération configurable) :

            (+)
           /   \
          3    (*)
              /   \
             4     2

Dépendances (flèches = "fournit à") :

  3.val ──────────> (+).val
  (*).val ────────> (+).val
  4.val ──────────> (*).val
  2.val ──────────> (*).val

  (+).base ───────> 3.base      (hérité, descend)
  (+).base ───────> (*).base    (hérité, descend)
  (*).base ───────> 4.base      (hérité, descend)
  (*).base ───────> 2.base      (hérité, descend)

Les flèches vers le haut sont les attributs synthétisés (les valeurs montent), les flèches vers le bas sont les attributs hérités (la base descend). L’ensemble forme un graphe orienté acyclique — du moins, si tout va bien.

Décryptage — Quelques notions de théorie des graphes : Ce schéma est un graphe orienté (directed graph) — un ensemble de sommets (ici, les attributs) reliés par des flèches (les dépendances). Quand aucun chemin ne revient à son point de départ, on parle de DAG (Directed Acyclic Graph, graphe orienté acyclique). Un DAG possède une propriété précieuse : on peut toujours ordonner ses sommets de manière à ce que chaque sommet apparaisse après tous ceux dont il dépend. Cet ordonnancement s’appelle un tri topologique (Kahn, 1962). C’est exactement ce que fait le compilateur pour évaluer les attributs : un parcours en profondeur (DFS, Depth-First Search) de l’arbre suffit à déterminer l’ordre de calcul. Le DAG et le tri topologique sont des outils fondamentaux en informatique — on les retrouve dans les systèmes de build (Make, Bazel), les tableurs (ordre de recalcul des cellules), et les gestionnaires de paquets (ordre d’installation des dépendances).

Le problème des cycles. Si un attribut synthétisé de A dépend d’un attribut hérité de A qui lui-même dépend d’un attribut synthétisé de A, on obtient un cycle : une dépendance circulaire sans solution. Le graphe n’est plus acyclique, et l’évaluation est impossible.

Détecter si une grammaire d’attributs peut produire des cycles (pour certains arbres de dérivation, pas tous) est un problème très difficile. Jazayeri, Ogden et Rounds (1975) ont montré que ce problème est DEXPTIME-complet (DEXPTIME = Deterministic Exponential Time, la classe des problèmes résolubles en temps exponentiel par rapport à la taille de l’entrée — concrètement, le temps de calcul peut doubler à chaque symbole ajouté à la grammaire, ce qui rend la vérification impraticable pour des grammaires de grande taille). En pratique, on se restreint donc à des classes de grammaires d’attributs où les cycles sont impossibles par construction.

Classes pratiques : S-attributed et L-attributed

Pour éviter les problèmes de cycles et permettre une évaluation efficace, la théorie des compilateurs a identifié deux classes bien comportées.

Grammaires S-attributed

Une grammaire est S-attributed (S pour synthesized) si tous ses attributs sont synthétisés. Aucun attribut hérité, jamais. L’information ne circule que de bas en haut.

C’est la classe la plus simple. Un seul parcours bottom-up de l’arbre suffit pour tout évaluer. Cette classe est parfaitement compatible avec l’analyse LR (Left-to-right, Rightmost derivation — le parseur remonte les réductions de bas en haut, exactement le bon moment pour calculer les attributs synthétisés).

Grammaires L-attributed

Une grammaire est L-attributed (L pour left-to-right) si chaque attribut hérité d’un symbole dans le membre droit d’une production ne dépend que :

des attributs hérités du membre gauche (le parent), et
des attributs (synthétisés ou hérités) des symboles situés à sa gauche dans la production.

Autrement dit : un symbole peut regarder ce qui vient avant lui (ses frères aînés), mais jamais ce qui vient après. L’évaluation se fait en un seul parcours de gauche à droite, compatible avec l’analyse LL (Left-to-right, Leftmost derivation — analyse descendante prédictive).

Critère	S-attributed	L-attributed
Attributs autorisés	Synthétisés uniquement	Synthétisés + hérités (sous contrainte)
Direction du flux	Bas vers haut uniquement	Bas vers haut + gauche vers droite
Parcours nécessaire	Un passage bottom-up	Un passage left-to-right, depth-first
Compatible avec	Analyse LR	Analyse LL
Expressivité	Limitée	Plus riche
Cycles possibles	Jamais	Jamais
Exemples typiques	Calculatrices, évaluation d’expressions	Vérification de types, portée des variables

La relation d’inclusion est :

S-attributed  ⊂  L-attributed  ⊂  Grammaires d'attributs bien définies (acycliques)

Toute grammaire S-attributed est aussi L-attributed (puisqu’il n’y a pas d’attributs hérités, la contrainte L est trivialement satisfaite). Mais l’inverse est faux : une grammaire L-attributed avec des attributs hérités n’est pas S-attributed.

Le lien avec BP3 : les flags comme « attributs globaux »

Nous avons vu dans B4 que les flags de BP3 sont des compteurs nommés qui contrôlent l’application des règles de grammaire. Un flag comme /Ideas=20/ s’initialise, se teste (/Ideas/), se décrémente (/Ideas-1/), et conditionne la dérivation. Cela ressemble beaucoup à un attribut hérité qui descend dans l’arbre pour contrôler les choix. Mais il y a une différence cruciale.

AG classiques vs flags BP3

Aspect	Attributs (AG classiques)	Flags (BP3)
Portée	Locale au noeud et ses voisins	Globale : visible par toutes les règles
Flux	Structurel (parent-enfant, frère-frère)	Non structurel : n’importe quelle règle peut lire/écrire
Évaluation	Déterminée par la topologie de l’arbre	Dépend de l’ordre de dérivation (et du hasard)
Déterminisme	Déterministe (mêmes entrées = même résultat)	Non-déterministe (choix stochastiques)
Décidabilité	Évaluation décidable (pour S/L-attributed)	Dépend du nombre de flags (voir ci-dessous)

La taxonomie de l’expressivité

Les grammaires d’attributs et les flags de BP3 s’inscrivent dans un spectre d’expressivité croissante :

Attributs synthétisés (S-attributed)
  ⊂ Attributs hérités locaux (L-attributed)
    ⊂ Attributs hérités généraux (AG bien définies)
      ⊂ Attributs hérités GLOBAUX avec nombre borné (flags BP3 bornés)
        ⊂ Attributs globaux non bornés (Turing-complet)

Pourquoi cette progression est-elle importante ? Parce qu’elle correspond à des niveaux de décidabilité différents :

S/L-attributed : évaluation en un passage, toujours terminante, totalement décidable.
AG bien définies : évaluation en plusieurs passages, terminante si acyclique, décidable.
Flags BP3 bornés : les flags sont des entiers à valeurs finies. L’espace d’états est fini, donc la terminaison est décidable en principe (même si potentiellement coûteuse).
Attributs globaux non bornés : si on autorisait des flags à valeurs arbitrairement grandes (sans borne), on pourrait simuler les compteurs d’une machine de Minsky (deux compteurs suffisent pour la Turing-complétude). La terminaison deviendrait indécidable.

Exemple concret en BP3

Considérons cette grammaire où un flag contrôle un choix musical :

gram#1[1] /Style=1/  |S| --> |Intro| |Dev| |Coda|
gram#1[2]            |Dev| --> /Style/ |A| |Dev| /Style-1/
gram#1[3]            |Dev| --> |B|
gram#1[4]            |A| --> do4 ré4 mi4
gram#1[5]            |B| --> sol4 la4 si4

Le flag Style est initialisé à 1 par la règle 1. La règle 2 teste /Style/ (est-il non nul ?) et le décrémente. Ce flag fonctionne comme un attribut hérité global : il est défini « en haut » (à l’initialisation) et consulté « plus bas » (dans les règles de dérivation de Dev). Mais contrairement à un attribut hérité classique, il ne circule pas le long des arêtes de l’arbre — il est accessible partout, comme une variable globale.

C’est cette portée globale qui rend les flags à la fois puissants (ils peuvent coordonner des parties distantes de la grammaire) et théoriquement délicats (leur interaction avec les choix stochastiques rend le comportement plus difficile à analyser que celui d’une grammaire d’attributs classique).

Applications : ce que font les compilateurs

Les grammaires d’attributs ne sont pas un objet théorique oublié. Elles sont au coeur des compilateurs modernes, même si le vocabulaire a parfois changé.

Vérification de types. C’est l’application canonique. Les types sont des attributs synthétisés qui montent des feuilles (littéraux, variables) vers la racine (expression complète). À chaque noeud opérateur, le compilateur vérifie la compatibilité des types de ses enfants et synthétise le type résultant. Si int + float est autorisé, le type résultant est float (coercion) ; si int + string ne l’est pas, c’est une erreur de type.

Génération de code. Le compilateur transmet des informations descendantes (attributs hérités) : dans quel registre stocker le résultat ? Quelle est l’adresse de base de la pile ? Ces contraintes descendent de la racine vers les feuilles, guidant la traduction de chaque noeud en instructions machine.

Outils modernes. La tradition des grammaires d’attributs a engendré des outils spécialisés :

JastAdd (Lund, Suède) : un système de Reference Attribute Grammars (RAG) où les attributs peuvent référencer d’autres noeuds de l’arbre. Utilisé pour le compilateur ExtendJ (Java).
Silver (Minnesota, USA) : un langage de spécification de compilateurs fondé sur les grammaires d’attributs, avec support pour les extensions de langage (composable language extensions).
ANTLR (ANother Tool for Language Recognition) : bien qu’orienté parseur, ANTLR supporte des actions et des attributs attachés aux règles de grammaire, dans l’esprit des AG.

Ces outils montrent que le formalisme de Knuth est loin d’être dépassé : il a évolué, s’est enrichi, mais le principe fondamental — décorer les arbres avec des propriétés calculées — reste le même.

Ce qu’il faut retenir

Grammaire d’attributs = grammaire context-free + propriétés calculées sur les noeuds de l’arbre. Chaque production est accompagnée de règles sémantiques qui définissent comment les attributs sont évalués.
Attribut synthétisé : calculé de bas en haut, à partir des enfants. Exemple : la valeur d’une expression, le type d’un opérande.
Attribut hérité : transmis de haut en bas (ou de gauche à droite), depuis le parent ou les frères aînés. Exemple : le type déclaré dans une liste de variables.
Le graphe de dépendances relie les attributs entre eux. S’il est acyclique, l’évaluation est possible ; s’il contient un cycle, elle est impossible.
S-attributed (tout synthétisé) et L-attributed (hérité limité aux frères à gauche) sont les deux classes pratiques qui garantissent l’absence de cycles et permettent une évaluation en un seul passage.
Les flags de BP3 sont des attributs hérités globaux : ils ne circulent pas le long de l’arbre mais sont accessibles par toute règle. Leur nombre borné garantit un espace d’états fini.
Le spectre d’expressivité va de S-attributed (simple, décidable) à attributs globaux non bornés (Turing-complet, indécidable), avec les flags de BP3 dans une zone intermédiaire maîtrisée.

Pour aller plus loin

Knuth, D.E. (1968). « Semantics of Context-Free Languages », Mathematical Systems Theory 2(2), pp. 127-145. — L’article fondateur. Knuth y introduit les attributs synthétisés et hérités.
Aho, A.V., Sethi, R. & Ullman, J.D. (1986). Compilers: Principles, Techniques, and Tools (le « Dragon Book »), chapitres 5-6. — Le traitement de référence des grammaires d’attributs dans le contexte de la compilation.
Paakki, J. (1995). « Attribute Grammar Paradigms — A High-Level Methodology in Language Implementation », ACM Computing Surveys 27(2). — Une synthèse complète des paradigmes et applications des AG.
Jazayeri, M., Ogden, W.F. & Rounds, W.C. (1975). « The Intrinsically Exponential Complexity of the Circularity Problem for Attribute Grammars », Communications of the ACM 18(12). — La preuve de DEXPTIME-complétude de la détection de circularité.
Hedin, G. (2000). « Reference Attributed Grammars », Informatica 24(3). — L’extension moderne des AG utilisée dans JastAdd.
Dans cette série : L4 pour la structure de base, B4 pour les flags de BP3.

Glossaire

Attribut synthétisé (synthesized attribute) : attribut dont la valeur est calculée à partir des attributs des noeuds enfants. L’information circule de bas en haut dans l’arbre. Exemple : la valeur val d’un noeud d’expression arithmétique.
Attribut hérité (inherited attribute) : attribut dont la valeur est transmise par le noeud parent ou les frères situés à gauche. L’information circule de haut en bas ou de gauche à droite. Exemple : le type déclaré type_decl dans une liste de variables.
Graphe de dépendances (dependency graph) : graphe orienté dont les noeuds sont les instances d’attributs et les arêtes représentent les dépendances entre eux. S’il est acyclique, un ordre d’évaluation existe.
S-attributed : classe de grammaires d’attributs ne contenant que des attributs synthétisés. Évaluation en un passage bottom-up, compatible avec l’analyse LR.
L-attributed : classe de grammaires d’attributs où les attributs hérités ne dépendent que du parent et des frères à gauche. Évaluation en un passage gauche-droite, compatible avec l’analyse LL.
OAG (Ordered Attribute Grammar) : classe intermédiaire entre L-attributed et AG générale, où un ordre d’évaluation fixe peut être déterminé statiquement pour chaque production. Introduit par Kastens (1980).
Flag (BP3) : compteur nommé à portée globale qui conditionne et modifie l’application des règles de grammaire. Combine les rôles de garde (test) et d’effet (modification).
Évaluation multi-passes (multi-pass evaluation) : stratégie d’évaluation où l’arbre est parcouru plusieurs fois, chaque passage calculant un sous-ensemble d’attributs. Nécessaire quand les dépendances ne permettent pas un passage unique.
Circularité (circularity) : situation où le graphe de dépendances contient un cycle, rendant l’évaluation impossible. Détecter si une grammaire d’attributs peut produire des dépendances circulaires est DEXPTIME-complet.
Règle sémantique (semantic rule) : équation ou fonction qui définit comment calculer la valeur d’un attribut en fonction d’autres attributs. Chaque production de la grammaire est accompagnée de ses règles sémantiques.

Prérequis : L4
Temps de lecture : 15 min
Tags : #grammaires-attributs #knuth #compilation #attributs-synthetises #attributs-herites #bp3-flags

Article précédent : L9) Au-delà de Chomsky
Article suivant : L11) Autres sémantiques (à venir)
Pour les flags de BP3 en pratique, voir : B4