Quelle est la différence entre un arbre de syntaxe abstrait et un arbre de syntaxe concret?

un arbre de syntaxe concret représente le texte source exactement sous forme parsée. En général, il est conforme à la grammaire sans contexte qui définit la langue source.

cependant, la grammaire et l'arbre concrets ont beaucoup de choses qui sont nécessaires pour rendre le texte source facilement compréhensible, mais ne contribuent pas à la signification réelle. Par exemple, pour implémenter la priorité de l'opérateur, votre CFG a généralement plusieurs niveaux d'expression (terme, facteur, etc.), avec les opérateurs les connectent aux différents niveaux (vous ajoutez des termes pour obtenir des expressions, les termes sont composés de facteurs éventuellement multipliés, etc.). Pour réellement interpréter ou compiler le langage, cependant, vous n'avez pas besoin de cela; vous avez juste besoin de noeuds D'Expression qui ont des opérateurs et des opérandes. L'arborescence de syntaxe abstraite est le résultat de la simplification de l'arborescence de syntaxe concrète à cette chose réellement nécessaire pour représenter le sens du programme. Cet arbre a une définition beaucoup plus simple et est donc plus facile à traiter dans les derniers stades de l'exécution.

Vous n'avez généralement pas besoin de construire un arbre de syntaxe concrète. Les routines d'action dans votre YACC (ou Antlr, ou Menhir, ou autre...) la grammaire peut construire directement l'arbre de syntaxe abstraite, de sorte que l'arbre de syntaxe concrète n'existe qu'en tant qu'entité conceptuelle représentant la structure parse de votre texte source.

a arbre de syntaxe concret correspond à ce que les règles de grammaire disent être la syntaxe. Le but du arbre de syntaxe abstraite est d'avoir une représentation" simple "de ce qui est essentiel dans"l'arbre de syntaxe".

une valeur réelle dans L'AST IMHO est qu'il est plus petit que le CST, et donc prend moins de temps à traiter. (Pourrait-on dire, qui s'en soucie? Mais je travaille avec un outil où nous avons des dizaines de millions des noeuds vivent à la fois!).

la plupart des générateurs d'analyseur qui ont n'importe quel support pour construire des arbres de syntaxe insistent que vous spécifiez personnellement exactement comment ils sont construits sous l'hypothèse que vos noeuds d'arbre seront" plus simples " que le CST (et en cela, ils sont généralement justes, car les programmeurs sont assez paresseux). On peut soutenir que cela signifie que vous devez coder moins de fonctions de visiteur de l'arbre, et c'est précieux, aussi, en ce qu'il minimise l'énergie de l'ingénierie. Lorsque vous avez 3500 règles (par exemple, pour COBOL) cette matière. Et cette " simplicité "conduit à la bonne propriété de la"petitesse".

mais avoir de tels ASTs crée un problème qui n'était pas là: il ne correspond pas à la grammaire, et maintenant vous devez suivre mentalement les deux. Et quand il y a 1500 noeuds AST pour une règle de grammaire 3500, cela compte beaucoup. Et si la grammaire évolue (ils le font toujours!), vous avez maintenant deux ensembles géants de choses à garder en synchronisation.

une autre solution est de laisser le l'analyseur construira simplement des noeuds CST pour vous et vous n'aurez qu'à les utiliser. C'est un avantage énorme lors de la construction des grammaires: il n'y a pas besoin d'inventer 1500 noeuds AST spéciaux pour modéliser 3500 règles de grammaire. Il suffit de penser à l'arbre étant isomorphe à la grammaire. Du point de vue de la grammaire ingénieur, il est complètement sans cervelle, qui lui permet de se concentrer sur la grammaire droit et le piratage dans son cœur. On peut soutenir que vous devez écrire plus de règles de visiteur de noeud, mais cela peut être géré. Plus sur cela plus tard.

ce que nous faisons avec le DMS Software Reengineering Toolkit est de construire automatiquement un CST basé sur les résultats d'un processus D'analyse (GLR). Le DMS construit alors automatiquement un CST "comprimé" pour des raisons d'efficacité de l'espace, en éliminant les terminaux non porteurs de valeurs (mots-clés, ponctuation), les productions unaires sémantiquement inutiles, et en formant des listes pour les paires de règles de grammaire qui sont des listes comme:

    L = e ;
    L = L e ;
    L2 = e2 ;
    L2 = L2  ','  e2 ;

et une grande variété de variantes de ces formes. Vous pensez en termes de règles de grammaire et le virtuel CST; l'outil fonctionne sur la représentation compressée. Facile sur votre cerveau, plus rapide / plus petit à l'exécution.

remarquablement, le CST compressé construit de cette façon ressemble beaucoup à un AST que vous pourriez avoir conçu à la main (Voir le lien à la fin des exemples). En particulier, le CST compressé ne contient aucun noeud qui n'est qu'une syntaxe concrète. Il existe quelques morceaux de maladresse: par exemple, alors que les noeuds en béton pour '(' et ')' trouvés classiquement dans les sous-programmes d'expression ne sont pas dans l'arbre, un "noeud entre parenthèses" "ne apparaît dans le CST comprimé et doit être manipulé. Un vrai AST n'aurait pas ça. Cela semble comme un prix assez petit à payer pour la commodité de ne pas avoir à spécifier la construction AST, jamais. Et la documentation pour l'arbre est toujours disponible et correcte: la grammaire est 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 L'AST et L'AST de manière transparente. DMS offre également un" attribut grammar " evaluator (AGE), qui est une méthode pour passer des valeurs calculées un noeud de haut en bas de l'arbre; L'âge gère tous les problèmes de représentation de l'arbre et donc l'ingénieur d'outil ne se soucie de l'écriture des calculs efficacement directement sur le les règles de grammaire eux-mêmes. Enfin, DMS fournit également des modèles" surface-syntaxe", qui permet des fragments de code de la grammaire à utiliser pour trouver des types spécifiques de sous-noeuds, sans connaître la plupart des types de noeuds impliqués.

L'une des autres réponses observe que si vous voulez construire des outils qui peuvent régénérer la source, votre AST devra correspondre au CST. Ce n'est pas vraiment juste, mais il est beaucoup plus facile de régénérer la source si vous avez des noeuds CST. DMS génère la plupart du prettyprinter automatiquement car il a accès aux deux: -}

conclusion: les TSA sont bons pour les petits, à la fois physiques et conceptuels. La construction automatisée AST du CST fournit les deux, et vous permet d'éviter le problème du suivi de deux ensembles différents.

modifier mars 2015: lien vers des exemples de CST vs. "AST" construit de cette façon

ce billet de blog peut être utile.

il me semble que L'AST" jette " beaucoup d'informations grammaticales/structurelles intermédiaires qui ne contribueraient pas à la sémantique. Par exemple, vous ne vous souciez pas que 3 est un atome est un terme est un facteur est A.... Vous vous souciez juste que c'est 3 quand vous mettez en œuvre l'expression d'exponentiation ou peu importe.

Ceci est basé sur le Évaluateur d'Expression la grammaire par Terrence Parr.

la grammaire pour cet exemple:

grammar Expr002;

options 
{
    output=AST;
    ASTLabelType=CommonTree; // type of $stat.tree ref etc...
}

prog    :   ( stat )+ ;

stat    :   expr NEWLINE        -> expr
        |   ID '=' expr NEWLINE -> ^('=' ID expr)
        |   NEWLINE             ->
        ;

expr    :   multExpr (( '+'^ | '-'^ ) multExpr)*
        ; 

multExpr
        :   atom ('*'^ atom)*
        ; 

atom    :   INT 
        |   ID
        |   '('! expr ')'!
        ;

ID      : ('a'..'z' | 'A'..'Z' )+ ;
INT     : '0'..'9'+ ;
NEWLINE : '\r'? '\n' ;
WS      : ( ' ' | '\t' )+ { skip(); } ;

entrée

x=1
y=2
3*(x+y)

Arbre D'Analyse

L'arbre d'analyse est une représentation concrète de l'entrée. L'arbre d'analyse conserve toutes les informations de l'entrée. Les cases vides représentent les espaces, c'est à dire la fin de la ligne.

AST

L'AST est une représentation abstraite de l'entrée. Notez que les parens ne sont pas présents dans L'AST car les associations sont dérivables de la structure de l'arbre.

EDIT

pour une explication plus détaillée, voir Compilateurs et générateurs de compilateurs pg. 23

le arbre de syntaxe concret suit les règles de la grammaire de la langue. Dans la grammaire, les "listes d'expressions" sont typiquement définies avec deux règles

• expression_list peut être: l'expression
• expression_list peut être: expression, expression_list

suivi littéralement, ces deux règles donnent une forme de peigne à toute liste d'expressions qui apparaît dans le programme.

le arbre de syntaxe abstraite est dans la forme qui est commode pour la manipulation ultérieure. Il représente les choses d'une manière qui a du sens pour quelqu'un qui comprend la signification des programmes, et pas seulement la façon dont ils sont écrits. La liste d'expressions ci-dessus, qui peut être la liste d'arguments d'une fonction, peut commodément être représentée comme un vecteur d'expressions, car il est préférable pour l'analyse statique d'avoir le nombre total d'expressions explicitement disponibles et être capable d'accéder à chaque expression par son index.

l'arbre de syntaxe concret contient toutes les informations comme les parenthèses superflues et les espaces et les commentaires, l'arbre de syntaxe abstraite résume loin de cette information.

NB: assez drôle, quand vous mettez en œuvre un moteur de reconfiguration votre AST contiendra à nouveau toutes les informations concrètes, mais vous allez continuer à se référer à elle comme un AST parce que c'est devenu le terme standard dans le domaine (donc on pourrait dire qu'il a longtemps il y a perdu son sens originel).

c'est une différence qui ne fait pas de différence.

un AST est habituellement expliqué comme une façon d'approcher la sémantique d'une expression du langage de programmation en rejetant le contenu lexical. Par exemple, dans une grammaire libre de contexte, vous pourriez écrire la règle EBNF suivante

term: atom (('*' | '/') term )*

alors que dans le cas AST vous utilisez seulement mul_rule et div_rule qui exprime l'arithmétique appropriée opérations.

ces règles ne peuvent-elles pas être introduites dans la grammaire? Bien sûr. Vous pouvez réécrire le compact ci-dessus et abstract règle en le cassant dans un plus béton règles utilisées pour imiter les noeuds AST mentionnés:

term: mul_rule | div_rule
mul_rule: atom ('*' term)*
div_rule: atom ('/' term)*

maintenant, quand vous pensez en termes de top-down parsing puis le second terme introduit un premier / premier conflit entre mul_rule et div_rule quelque chose d'un LL(1) analyseur ne peut pas traiter. La première forme de règle était la version de gauche factored de la deuxième qui a effectivement éliminé la structure. Vous avez à payer un certain prix pour l'utilisation de LL(1) ici.

So ASTs sont un supplément ad hoc utilisé pour corriger les déficiences de grammars et parsers. La transformation CST - > AST est un mouvement de refonte. Personne ne s'est jamais inquiété quand une virgule ou un côlon supplémentaire est stockés dans l'arbre syntaxique. Au contraire, certains auteurs les adaptent en ASTs parce qu'ils aiment utiliser ASTs pour faire des refactorisations au lieu de maintenir divers arbres en même temps ou écrire un moteur d'inférence supplémentaire. Les programmeurs sont paresseux pour de bonnes raisons. En fait, ils stockent même les informations de ligne et de colonne recueillies par l'analyse lexicale dans ASTs pour la déclaration d'erreur. Très abstrait en effet.

simplement, AST ne contient que la sémantique du code, Parse tree/CST inclut également des informations sur la façon dont le code a été écrit.

CST (Concrete Syntax Tree) est une représentation en arbre de la grammaire(règles sur la façon dont le programme doit être écrit). Selon l'architecture du compilateur, il peut être utilisé par l'Analyseur pour produire un AST.

AST (Arbre de syntaxe abstraite) est une représentation arborescente de la source Parsée, produite par la partie analyseur du compilateur. Il stocke des informations sur les jetons+grammaire.

selon l'architecture de votre compilateur, le CST peut être utilisé pour produire AST. Il est juste de dire que le Gend se transforme en AST. Or, AST is a richer Gend.

plus d'explications peuvent être trouvées sur ce lien: http://eli.thegreenplace.net/2009/02/16/abstract-vs-concrete-syntax-trees#id6