Quelle est la différence entre l'analyse et l'AST?

StackOverflow https://stackoverflow.com/questions/5026517

Question

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

Était-ce utile?

La solution

Ceci est basé sur le Évaluateur d'expression Grammaire par 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(); } ;

Saisir

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

Analyse d'analyse

L'arbre d'analyse est une représentation en béton de l'entrée. L'arbre d'analyse conserve toutes les informations de l'entrée. Les boîtes vides représentent l'espace, c'est-à-dire la fin de la ligne.

Parse Tree

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érivées de la structure des arbres.

AST

Pour plus par explication, voir Compilateurs et générateurs de compilateurs p. 23
ou Syntaxe abstrait sur p. 21 dans Syntaxe et sémantique des langages de programmation

Autres conseils

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

j'ai trouvé ça page qui tente de résoudre cette question exacte.

La Livre DSL De Martin Fowler explique cela bien. L'AST contient uniquement tous les éléments «utiles» qui seront utilisés pour un traitement ultérieur, tandis que l'arbre d'analyse contient tous les artefacts (espaces, supports, ...) du document original que vous analysez

Prenez l'âge de la mission Pascal: = 42;

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

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

L'attribution devient un nœud avec 2 éléments, l'âge 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'une langue génère le même AST. Ceci est utile pour les moteurs de script en langue croisée.

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

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top