A arbre syntaxique concret correspond à ce que les règles de grammaire disent être la syntaxe. Le but de la arbre syntaxique abstrait est d'avoir une représentation "simple" de ce qui est essentiel dans "l'arbre syntaxique".
La valeur réelle de l'AST, selon moi, est qu'elle est plus petit que le CST, et prend donc moins de temps à traiter. (Vous pourriez dire, qui s'en soucie ? Mais je travaille avec un outil où nous avons des dizaines de millions de nœuds en direct en même temps).
La plupart des générateurs d'analyseurs syntaxiques qui prennent en charge la construction d'arbres syntaxiques insistent pour que vous spécifiiez personnellement la manière dont ils sont construits, en partant du principe que les nœuds de votre arbre seront plus "simples" que la CST (et en cela, ils ont généralement raison, car les programmeurs sont plutôt paresseux). On peut soutenir que cela signifie que vous devez coder moins de fonctions de visiteur d'arbre, et cela est également valable, dans la mesure où cela minimise l'énergie d'ingénierie. Lorsque vous avez 3500 règles (par exemple, pour COBOL), cela compte. Et cette "simplicité" conduit à la bonne propriété de "petitesse".
Mais le fait d'avoir de tels AST crée un problème qui n'existait pas : il ne correspond pas à la grammaire, et maintenant vous devez suivre mentalement les deux. Et quand il y a 1500 nœuds AST pour une grammaire de 3500 règles, cela compte beaucoup. Et si la grammaire évolue (c'est toujours le cas !), vous avez maintenant deux ensembles géants de choses à garder en synchronisation.
Une autre solution est de laisser l'analyseur syntaxique construire simplement les noeuds CST pour vous et de n'utiliser que ceux-ci. C'est un avantage énorme lors de la construction des grammaires : il n'y a pas besoin d'inventer 1500 nœuds AST spéciaux pour modéliser 3500 règles de grammaire. Il suffit de penser que l'arbre est isomorphe à la grammaire. Du point de vue de l'ingénieur grammairien, c'est complètement inutile, ce qui lui permet de se concentrer sur l'obtention d'une grammaire correcte et de la modifier à sa guise. On peut dire que vous devez écrire plus de règles pour les visiteurs de nœuds, mais cela peut être géré. Nous y reviendrons plus tard.
Ce que nous faisons avec le Boîte à outils de réingénierie du logiciel DMS consiste à construire automatiquement un CST sur la base des résultats d'un processus d'analyse syntaxique (GLR). DMS construit ensuite automatiquement une CST "compressée" pour des raisons d'efficacité de l'espace, en éliminant les terminaux non porteurs de valeur (mots-clés, ponctuation), les productions unaires sémantiquement inutiles, et en formant des listes directement indexables pour les paires de règles de grammaire qui sont semblables à des listes :
L = e ;
L = L e ;
L2 = e2 ;
L2 = L2 ',' e2 ;
et une grande variété de variations de ces formes. Vous pensez en termes de règles de grammaire et de CST virtuelle ; l'outil fonctionne sur la représentation compressée. Facile pour votre cerveau, plus rapide/plus petit au moment de l'exécution.
De façon remarquable, la CST compressée construite de cette façon ressemble beaucoup à une AST que vous auriez pu concevoir à la main (voir le lien à la fin pour des exemples). En particulier, la CST compressée ne comporte aucun nœud qui ne soit qu'une syntaxe concrète. Il y a quelques petites maladresses : par exemple, alors que les nœuds concrets pour '(' et ')' que l'on trouve classiquement dans les sous-programmes d'expression ne sont pas dans l'arbre, un " nœud de parenthèses " est présent. fait apparaissent dans la CST compressée et doivent être traitées. Une véritable AST n'aurait pas cela. Cela semble être un prix assez faible à payer pour la commodité de ne pas avoir à spécifier la construction AST, jamais. Et la documentation de l'arbre est toujours disponible et correcte : la grammaire es la documentation.
Comment éviter les "visiteurs supplémentaires" ? Nous ne le faisons pas entièrement, mais DMS fournit une bibliothèque AST qui parcourt l'AST et gère les différences entre la CST et l'AST de manière transparente. DMS offre également un évaluateur de "grammaire d'attributs" (AGE), qui est une méthode pour passer les valeurs calculées d'un nœud vers le haut et vers le bas de l'arbre ; l'AGE gère tous les problèmes de représentation de l'arbre et l'ingénieur outil ne se soucie donc que d'écrire des calculs efficaces directement sur les règles de grammaire elles-mêmes. Enfin, DMS fournit également des modèles de "syntaxe de surface", qui permettent d'utiliser des fragments de code de la grammaire pour trouver des types spécifiques de sous-arbres, sans connaître la plupart des types de nœuds impliqués.
Une des autres réponses observe que si vous voulez construire des outils qui peuvent régénérer les sources, votre AST devra correspondre à la CST. Ce n'est pas vraiment exact, mais il est beaucoup plus facile de régénérer la source si vous avez des nœuds CST. DMS génère la plupart des prettyprinter automatiquement parce qu'il a accès aux deux :-}
En résumé : AST sont bons pour les petits, à la fois phyisque et conceptuel. La construction automatisée d'AST à partir de la CST fournit les deux, et vous permet d'éviter le problème du suivi de deux ensembles différents.
EDIT mars 2015 : Lien vers des exemples de CST vs. "AST" construits de cette manière
