ATTRIBUTS HERITES
EXEMPLES
TYPES DES EXPRESSIONS
YACC/BISON
ORDRE DE CALCUL DES
ATTRIBUTS
On ne peut pas décider l'ordre de calcul des attributs par inspection des règles des noeuds voisins:
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.
REPRESENTATION PAR UN GRAPHE
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).
UN ALGORITHME DE TRI TOPOLOGIQUE
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.
FAUT-IL LE FAIRE?
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.
SECURITE DE CALCUL DES
ATTRIBUTS
Grammaires non-circulaires
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?
ALGORITHME DE DECISION DE CIRCULARITE
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.
TEMPS DE CALCUL
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).
UN COMPROMIS
Les grammaires fortement non-circulaires
ALGORITHME DE DECISION DE
NON-CIRCULARITE FORTE
TEMPS DE CALCUL
ORDRE DE CALCUL