Pour contrer l'inefficacité en place, plusieurs classes de grammaires
d'attributs qui imposent des restrictions sur la GA d'entrée ont été
introduites; grâce à ces limitations, il était alors possible de construire
des évaluateurs peu gourmands, mais au prix d'une perte importante de puissance
d'expression. Parmi ces classes, celle des GA l-ordonnées joue un rôle
particulier. En effet, elle est la plus large classe pour laquelle il est
possible d'engendrer un évaluateur efficace en mémoire, --- à base de séquence
de visite --- sans pour autant pénaliser l'efficacité en temps. Cette classe se
caractérise par la connaissance statique d'un ordre total d'évaluation des
attributs. En outre, toute GA peut être transformée en une GA l-ordonnée
équivalente, mais avec un risque d'exponentialité de la taille de cette
dernière. Enfin, le test de caractérisation de cette classe l-ordonnée est un
problème NP-complet. Mon premier travail a été de concevoir un nouvel
algorithme de transformation [Par87,Par88,JPJ
90], qui fait que
ce facteur d'exponentialité reste confiné à des cas pathologiques. Pour être
tout à fait précis, pour l'instant, je n'ai réalisé cette transformation qu'à
partir d'une sous-classe de GA nommée FNC --- fortement non-circulaire ---
mais dans ma thèse [Par87] j'ai défini la transformation complète, à
partir des GA bien formées qui est la plus large classe des GA.