Quelle est la différence entre parse tree et AST?

90

Sont-ils générés par différentes phases d'un processus de compilation? Ou s'agit-il simplement de noms différents pour la même chose?

compiler-construction terminology compiler-theory abstract-syntax-tree parse-tree Thomson
la source
Parse Tree est le résultat de votre grammaire avec ses artefacts (vous pouvez écrire une infinité de grammaires pour la même langue), un AST réduit le Parse Tree le plus proche possible de la langue. Plusieurs grammaires pour la même langue donneront des arbres d'analyse différents mais devraient aboutir au même AST. (vous pouvez également réduire différents scripts (différents arbres d'analyse de la même grammaire) au même AST)
Guillaume86
1
Cette réponse SO traite de la différence en détail: stackoverflow.com/a/1916687/120163
Ira Baxter
1
Double possible de Quelle est la différence entre les arbres d'analyse et les arbres de syntaxe abstraite?
curiousdannii

Réponses:

95

Ceci est basé sur la grammaire Expression Evaluator de Terrence Parr.

La grammaire de 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(); } ;

Contribution

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

Analyser l'arbre

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 des espaces, c'est-à-dire la fin de la ligne.

Analyser l'arbre

AST

L'AST est une représentation abstraite de l'entrée. Notez que les parenthèses ne sont pas présentes dans l'AST car les associations sont dérivables de la structure arborescente.

AST

Pour une explication plus détaillée, voir Compilateurs et générateurs de compilateurs pg. 23
ou Arbres de syntaxe abstraite à la p. 21 en syntaxe et sémantique des langages de programmation

Guy Coder
la source
5
Comment dérivez-vous l'AST de l'arbre d'analyse? Quelle est la méthode pour simplifier un arbre d'analyse en un AST?
CMCDragonkai
3
Il n'y a pas d'algorithme spécifique pour dériver l'AST de l'arborescence d'analyse. Ce qui entre dans l'AST est plus une préférence personnelle, mais doit contenir suffisamment d'informations pour accomplir la tâche. J'ai exclu les parens de l'AST en utilisant l'ANTLR ! opérateur dans la grammaire car ils ne sont pas nécessaires, mais par défaut ANTLR les aurait inclus. Je pense que l'arbre d'analyse vous donne tout, que vous en ayez besoin ou non, et l'AST vous donne le strict minimum. N'oubliez pas que vous traverserez beaucoup les arbres, donc la taille compte.
Guy Coder
2
Vous voulez dire comme CST (arbre de syntaxe concret) vs AST (arbre de syntaxe abstraite)?
CMCDragonkai
Les actions / règles sémantiques intégrées dans les fichiers de syntaxe d'un analyseur ou d'un générateur d'analyseurs sont le moyen habituel d'analyse sémantique et de création d'un AST, tandis que l'arbre d'analyse est rarement, voire jamais, construit ou utilisé par le code utilisateur, sauf peut-être pour la vérification de l'exactitude de l'analyseur.
D'intérêt: graphe sémantique abstrait
Guy Coder
16

D'après ce que je comprends, l'AST se concentre davantage sur les relations abstraites entre les composants du code source, tandis que l'arbre d'analyse se concentre sur la mise en œuvre réelle de la grammaire utilisée par le langage, y compris les détails pointilleux. Ils ne sont certainement pas les mêmes, car un autre terme pour «arbre d'analyse» est «arbre de syntaxe concret».

J'ai trouvé cette page qui tente de résoudre cette question exacte.

Ken Wayne VanderLinde
la source
11

Le livre DSL de Martin Fowler explique bien cela. L'AST ne contient que tous les éléments `` utiles '' qui seront utilisés pour un traitement ultérieur, tandis que l'arborescence d'analyse contient tous les artefacts (espaces, crochets, ...) du document original que vous analysez

Wim Deblauwe
la source
4

Prenez l'attribution pascal Âge: = 42;

L'arbre de syntaxe ressemblerait au code source. Ci-dessous, je mets des crochets autour des nœuds. [Âge] [: =] [42] [;]

Un arbre abstrait ressemblerait à ceci [=] [Âge] [42]

L'affectation devient un nœud avec 2 éléments, Age et 42. L'idée est que vous pouvez exécuter l'affectation.

Notez également que la syntaxe pascal disparaît. Ainsi, il est possible que plus d'un langage génère le même AST. Ceci est utile pour les moteurs de script multilingues.

William Egge
la source
1

Dans l'arborescence d'analyse, les nœuds intérieurs ne sont pas terminaux, les feuilles sont terminaux. Dans l'arborescence de syntaxe, les nœuds intérieurs sont des opérateurs, les feuilles sont des opérandes.

Roshani Patel
la source