P ® Q P.X=Q.a Q.b=P.X
P.Y=Q.c Q.d=P.Y
Q ® Q Q1.a=Q2.a Q2.b=Q1.b
Q1.c=Q2.c Q2.d=Q1.d
Q ® R Q.c=Q.b Q.a=0
Q ® S Q.a=Q.d Q.c=0
Et si on ajoutait
Q ® T Q.c=Q.b Q.a=Q.d
tout programme avec un T produirait une boucle dans le calcul
des attributs (sauf si le T ne descendait pas d'un P...)
Donc, nécessité de trouver si un programme donné produit une boucle dans le calcul des attributs et, sinon, quel est (un) bon ordre de les calculer.
Il y a une boucle dans le calcul des attributs ssi il existe un circuit dans le graphe.
Le choix d'un ordre de calcul des attributs correspond au choix d'un ordre sur les sommets tel que s'il existe un arc de Ai à Aj, Aj précède Ai dans l'ordre.
Trouver un tel ordre s'appelle faire un tri
topologique du
graphe (ou de l'ordre partiel représenté par le graphe).
si n n¢est pas marqué
alors marquer n;
pour tout prédécesseur direct s de n
faire P(s)
afficher(n)
Maintenant l'algorithme est trivial:
Tous sommets non marqués
for i to nom_sommets do P(sommet[i])
Afin de détecter les circuits, on ajoute une deuxième marque en_cours à chaque sommet; elle est vraie pendant la suite d'appels récursifs sur les prédécesseurs du sommet; si P est appelé sur un sommet avec en_cours déjà vraie, il existe un circuit.
Normalement E ³ V et on peut dire que le temps est O(E).
Mais E peut être n(n-1); même la moitié dans un graphe sans circuits.
On ne peut pas espérer de faire mieux (nécessité de prendre en compte tous les arcs)
Donc une conclusion surprenante: le tri topologique a un travail plus simple à faire qu'un tri standard (plusieurs ordres possibles pour les sorties) mais son temps de calcul est forcément supérieur.
Mais pas dans notre cas parce que E le nombre d'arcs est borné par kV où k est le nombre maximum d'attributs dans la partie droite d'une règle de calcul d'un attribut.
Souvent l'algorithme de tri topologique est caché dans un algorithme récursif (on décide l'ordre dans lequel il faut faire les calculs au fur et à mesure qu'on les fait.)
Il permet au concepteur d'une grammaire attribuée de définir et utiliser une grammaire qui, pour certains programmes va échouer!
On préfère que tout programme construit selon les règles de la grammaire soit capable d'être compilé (on ne peut pas empêcher l'utilisateur d'écrire des programmes qui plantent à l'exécution)
Donc, il serait meilleur de tester les grammaires pour garantir qu'elles ne peuvent pas générer des programmes avec boucles dans le calcul des attributs, plutôt que tester les programmes après les avoir analysés.
C'est-à-dire qu'aucun programme dérivé de la grammaire ne possède un circuit dans son graphe des dépendances des attributs.
Il suffit de tester à chaque sommet de l'arbre syntaxique qu'il n'y a pas de circuit pour lequel ce sommet est le plus haut; mais comment le faire pour tous les programmes possibles?
Idée: pour chaque symbole de la grammaire construire un
graphe des dépendances entre ses attributs
(dépendances
capables d'être produites par le sous-arbre pendant du sommet).
On déduit de nouvelles dépendances du graphe Dp des dépendances évidentes d'une production p et les graphes des symboles à droite de p; un chemin dans l'union de ces graphes montre une dépendance entre les attributs du symbole à gauche.
On fait ça pour toute production et continue tant que de nouvelles dépendances sont trouvées.
MAIS c'est trop pessimiste!
Si on a 2 productions avec S à gauche et l'une des deux peut donner une dépendance de l'attribut a de b et l'autre peut donner une dépendance de b de c, ce n'est pas forcément vrai que a peut dépendre de c.
Solution: Pour chaque symbole stocker un ensemble de graphes correspondant à chaque sous-ensemble des dépendances qui est capable d'exister simultanément; pour la production p considérer chaque combinaison possible de Dp et un des graphes de chaque symbole à droite.
Et on sait (résultat de la théorie de la complexité) que c'est impossible de réduire ce temps à un niveau raisonnable (polynomial).
Polynomial parce que chaque itération sauf la dernière ajoute une dépendance et le nombre de dépendances possibles est polynomial.