Frage Was ist der Unterschied zwischen Parse-Baum und AST?


Werden sie durch verschiedene Phasen eines Kompilierungsprozesses generiert? Oder sind es nur verschiedene Namen für die gleiche Sache?


76
2018-02-17 08:19


Ursprung


Antworten:


Dies basiert auf der Ausdruck 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)

Parse Baum

Der Syntaxbaum ist eine konkrete Darstellung der Eingabe. Der Syntaxbaum enthält alle Informationen der Eingabe. Die leeren Kästchen stellen Leerzeichen dar, d. H. Das Ende der Zeile.

Parse Tree

AST

Der AST ist eine abstrakte Darstellung der Eingabe. Beachten Sie, dass Parens im AST nicht vorhanden sind, da die Assoziationen aus der Baumstruktur abgeleitet werden können.

AST

Für eine mehr Erklärung siehe Compiler und Compilergeneratoren pg. 23
oder Abstrakte Syntaxbäume auf pg. 21 in Syntax und Semantik von Programmiersprachen 


80
2018-03-25 22:14



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

ich habe das gefunden Seite welches versucht, diese genaue Frage zu lösen.


15
2018-02-17 08:30



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


9
2018-02-17 08:36



Nimm die Pascal-Aufgabe Alter: = 42;

Der Syntaxbaum würde genau wie der Quellcode aussehen. Im Folgenden lege ich Klammern um die Knoten. [Alter] [: =] [42] [;]

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

Die Zuweisung wird zu einem Knoten mit 2 Elementen, Alter 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 denselben AST erzeugt. Dies ist nützlich für mehrsprachige Skript-Engines.


3
2017-08-04 14:26



Im Parserbaum sind die inneren Knoten nicht terminal, die Blätter sind terminal. Im Syntaxbaum sind interne Knoten Operatoren, Blätter sind Operanden.


1
2017-11-25 12:56