wake-up-neo.com

Was ist der Unterschied zwischen Analysebaum und AST?

Werden sie durch verschiedene Phasen eines Kompilierungsprozesses erzeugt? Oder sind es nur verschiedene Namen für dasselbe Ding?

81
Thomson

Dies basiert auf der Expression Evaluator Grammatik von Terrence Parr.

Die Grammatik für dieses Beispiel:

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

Eingang

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

Baum analysieren

Der Analysebaum ist eine konkrete Darstellung der Eingabe. Der Analysebaum behält alle Informationen der Eingabe bei. Die leeren Kästchen stehen für Leerzeichen, d. H. Das Zeilenende.

Parse Tree

AST

AST ist eine abstrakte Darstellung der Eingabe. Beachten Sie, dass in AST= keine Parens vorhanden sind, da die Assoziationen von der Baumstruktur abgeleitet werden können.

AST

Eine ausführlichere Erklärung finden Sie unter Compiler und Compiler-Generatoren pg. 23
oder Abstrakte Syntaxbäume auf Seite. 21 in Syntax und Semantik von Programmiersprachen

88
Guy Coder

Soweit ich weiß, konzentriert sich das AST auf die abstrakten Beziehungen zwischen den Komponenten des Quellcodes, während sich der Analysebaum auf die tatsächliche Implementierung der von der Sprache verwendeten Grammatik konzentriert, einschließlich der pingeligen Details Sie sind definitiv nicht gleich, da ein anderer Begriff für "Syntaxbaum" "konkreter Syntaxbaum" ist.

Ich fand dieses Seite , das versucht, diese genaue Frage zu lösen.

16

Das DSL-Buch von Martin Fowler erklärt das sehr gut. Das AST enthält nur alle 'nützlichen' Elemente, die für die weitere Verarbeitung verwendet werden, während der Analysebaum alle Artefakte (Leerzeichen, Klammern, ...) aus dem Originaldokument enthält, das Sie analysieren

10
Wim Deblauwe

Nehmen Sie die Pascal-Zuweisung Alter: = 42;

Der Syntaxbaum würde genauso aussehen wie der Quellcode. Unten setze ich Klammern um die Knoten. [Alter] [: =] [42] [;]

Ein abstrakter Baum würde so aussehen [=] [Alter] [42]

Die Zuweisung wird zu einem Knoten mit zwei Elementen, Age und 42. Die Idee ist, dass Sie die Zuweisung ausführen können.

Beachten Sie auch, dass die Pascal-Syntax verschwindet. Somit ist es möglich, dass mehr als eine Sprache den gleichen AST erzeugt. Dies ist nützlich für sprachübergreifende Skriptmodule.

4
William Egge

Im Analysebaum sind innere Knoten nicht endständig, Blätter sind endständig. Im Syntaxbaum sind innere Knoten Operator, Blätter Operanden.

1
Roshani Patel