Was ist der Unterschied zwischen einem abstrakten Syntaxbaum und einem konkreten Syntaxbaum?

Ich habe ein wenig darüber gelesen, wie Interpreter / Compiler funktionieren, und ein Bereich, in dem ich verwirrt bin, ist der Unterschied zwischen einem AST und einem CST. Mein Verständnis ist, dass der Parser ein CST erstellt und es dem semantischen Analysator übergibt, der es in ein AST verwandelt. Nach meinem Verständnis stellt der semantische Analysator jedoch lediglich sicher, dass die Regeln eingehalten werden. Ich verstehe nicht wirklich, warum es tatsächlich Änderungen vornehmen würde, um es eher abstrakt als konkret zu machen.

Fehlt mir etwas am semantischen Analysator oder ist der Unterschied zwischen AST und CST etwas künstlich?

Ein konkreter Syntaxbaum repräsentiert den Quelltext genau in analysierter Form. Im Allgemeinen entspricht es der kontextfreien Grammatik, die die Ausgangssprache definiert.

Die konkrete Grammatik und der konkrete Baum enthalten jedoch viele Dinge, die erforderlich sind, um den Quelltext eindeutig analysierbar zu machen, tragen jedoch nicht zur tatsächlichen Bedeutung bei. Um beispielsweise die Priorität von Operatoren zu implementieren, verfügt Ihre CFG normalerweise über mehrere Ebenen von Ausdruckskomponenten (Begriff, Faktor usw.), wobei die Operatoren sie auf den verschiedenen Ebenen verbinden (Sie fügen Begriffe hinzu, um Ausdrücke zu erhalten, Begriffe bestehen aus Faktoren, die optional multipliziert werden , etc.). Um die Sprache tatsächlich zu interpretieren oder zu kompilieren, benötigen Sie dies jedoch nicht. Sie benötigen nur Ausdrucksknoten mit Operatoren und Operanden. Der abstrakte Syntaxbaum ist das Ergebnis der Vereinfachung des konkreten Syntaxbaums auf die Dinge, die tatsächlich zur Darstellung der Bedeutung des Programms benötigt werden. Dieser Baum hat eine viel einfachere Definition und ist daher in späteren Ausführungsphasen einfacher zu verarbeiten.

Normalerweise müssen Sie keinen konkreten Syntaxbaum erstellen. Die Aktionsroutinen in Ihrer YACC-Grammatik (oder Antlr oder Menhir oder was auch immer ...) können den abstrakten Syntaxbaum direkt erstellen, sodass der konkrete Syntaxbaum nur als konzeptionelle Einheit existiert, die die Analysestruktur Ihres Quelltextes darstellt.

Ein konkreter Syntaxbaum entspricht den Syntaxregeln der Syntax. Der Zweck des abstrakten Syntaxbaums besteht darin, eine "einfache" Darstellung dessen zu haben, was im "Syntaxbaum" wesentlich ist.

Ein echter Wert im AST IMHO ist, dass es kleiner als das CST ist und daher weniger Zeit für die Verarbeitung benötigt. (Man könnte sagen, wen interessiert das? Aber ich arbeite mit einem Tool, bei dem zig Millionen Knoten gleichzeitig leben!).

Die meisten Parser-Generatoren, die das Erstellen von Syntaxbäumen unterstützen, bestehen darauf, dass Sie persönlich genau angeben, wie sie erstellt werden, unter der Annahme, dass Ihre Baumknoten "einfacher" als das CST sind (und diesbezüglich sind sie im Allgemeinen richtig, da Programmierer hübsch sind faul). Es bedeutet wahrscheinlich, dass Sie weniger Baumbesucherfunktionen codieren müssen, und das ist auch insofern wertvoll, als es die technische Energie minimiert. Wenn Sie 3500 Regeln haben (z. B. für COBOL), ist dies wichtig. Und diese "einfachere" Ness führt zu der guten Eigenschaft der "Kleinheit".

Aber solche ASTs zu haben, schafft ein Problem, das es nicht gab: Es stimmt nicht mit der Grammatik überein, und jetzt müssen Sie beide mental verfolgen. Und wenn es 1500 AST-Knoten für eine 3500-Regel-Grammatik gibt, ist dies sehr wichtig. Und wenn sich die Grammatik weiterentwickelt (das tun sie immer!), Haben Sie jetzt zwei riesige Dinge, die Sie synchron halten müssen.

Eine andere Lösung besteht darin, den Parser einfach CST-Knoten für Sie erstellen zu lassen und diese einfach zu verwenden. Dies ist ein großer Vorteil beim Erstellen der Grammatiken: Es müssen keine 1500 speziellen AST-Knoten erfunden werden, um 3500 Grammatikregeln zu modellieren. Denken Sie nur daran, dass der Baum isomorph zur Grammatik ist. Aus Sicht des Grammatikingenieurs ist dies völlig hirnlos, so dass er sich darauf konzentrieren kann, die Grammatik richtig zu machen und sie nach Herzenslust zu hacken. Möglicherweise müssen Sie mehr Knotenbesucherregeln schreiben, aber das kann verwaltet werden. Dazu später mehr.

Mit dem DMS Software Reengineering Toolkit erstellen wir automatisch ein CST basierend auf den Ergebnissen eines (GLR-) Analyseprozesses. DMS erstellt dann aus Gründen der Raumeffizienz automatisch ein "komprimiertes" CST, indem nicht werttragende Terminals (Schlüsselwörter, Interpunktion), semantisch nutzlose unäre Produktionen eliminiert und Listen für Grammatikregelpaare erstellt werden, die wie folgt aufgelistet sind:

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

und eine Vielzahl von Variationen solcher Formen. Sie denken in Bezug auf die Grammatikregeln und die virtuelle CST; Das Werkzeug arbeitet mit der komprimierten Darstellung. Schont Ihr Gehirn, ist zur Laufzeit schneller / kleiner.

Bemerkenswerterweise sieht das so erstellte komprimierte CST wie ein AST aus, das Sie möglicherweise von Hand entworfen haben (siehe Link am Ende zu den Beispielen). Insbesondere enthält das komprimierte CST keine Knoten, die nur eine konkrete Syntax sind. Es gibt kleinere Bits von Ungeschicklichkeit: zum Beispiel , während die konkreten Knoten für ‚(‘ und ‚)‘ klassisch in Ausdruck Subgrammars gefunden sind nicht im Baum, ein „Klammern Knoten“ wird in der komprimierten CST angezeigt und gehandhabt werden muss. Ein echter AST hätte das nicht. Dies scheint ein ziemlich kleiner Preis zu sein, um die AST-Konstruktion niemals spezifizieren zu müssen. Und die Dokumentation für den Baum ist immer verfügbar und korrekt: Die Grammatik ist die Dokumentation.

Wie vermeiden wir "zusätzliche Besucher"? Wir wissen es nicht ganz, aber DMS bietet eine AST-Bibliothek, die den AST durchläuft und die Unterschiede zwischen CST und AST transparent behandelt. DMS bietet auch einen "Attribut Grammatik" Evaluator (AGE) an, eine Methode zum Übergeben von Werten, die von einem Knoten im Baum berechnet wurden. Das AGE kümmert sich um alle Probleme mit der Baumdarstellung, sodass sich der Werkzeugingenieur nur darum kümmert, Berechnungen effektiv direkt auf die Grammatikregeln selbst zu schreiben. Schließlich bietet DMS auch "Oberflächensyntax" -Muster, mit denen Codefragmente aus der Grammatik verwendet werden können, um bestimmte Arten von Teilbäumen zu finden, ohne die meisten beteiligten Knotentypen zu kennen.

Eine der anderen Antworten besagt, dass Ihr AST mit dem CST übereinstimmen muss, wenn Sie Tools erstellen möchten, mit denen die Quelle neu generiert werden kann. Das ist nicht wirklich richtig, aber es ist viel einfacher, die Quelle neu zu generieren, wenn Sie CST-Knoten haben. DMS generiert den größten Teil des Pretty Printer automatisch, da es Zugriff auf beide hat: -}

Fazit: ASTs sind gut für kleine, sowohl phyiskale als auch konzeptionelle. Die automatisierte AST-Konstruktion aus dem CST bietet beides und vermeidet das Problem, zwei verschiedene Sätze zu verfolgen.

EDIT März 2015: Link zu Beispielen von CST vs. "AST", die auf diese Weise erstellt wurden

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 Felder stehen für Leerzeichen, dh das Zeilenende.

AST

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

BEARBEITEN

Weitere Informationen finden Sie unter Compiler und Compilergeneratoren . 23

Dieser Blog-Beitrag kann hilfreich sein.

Es scheint mir, dass der AST viele intermediäre grammatikalische / strukturelle Informationen "wegwirft", die nicht zur Semantik beitragen würden. Zum Beispiel ist es dir egal, dass 3 ein Atom ist, ein Begriff ist ein Faktor ist ein ... Es ist dir nur wichtig, dass es ist, 3wenn du den Exponentiationsausdruck implementierst oder was auch immer.

Der konkrete Syntaxbaum folgt den Regeln der Grammatik der Sprache. In der Grammatik werden "Ausdruckslisten" normalerweise mit zwei Regeln definiert

• expression_list kann sein: expression
• expression_list kann sein: expression, expression_list

Wörtlich befolgt, geben diese beiden Regeln jeder Ausdrucksliste, die im Programm angezeigt wird, eine Kammform.

Der abstrakte Syntaxbaum hat die Form, die für die weitere Bearbeitung geeignet ist. Es repräsentiert Dinge auf eine Weise, die für jemanden Sinn macht, der die Bedeutung von Programmen versteht und nicht nur die Art und Weise, wie sie geschrieben sind. Die obige Ausdrucksliste, bei der es sich möglicherweise um die Liste der Argumente einer Funktion handelt, kann zweckmäßigerweise als Vektor von Ausdrücken dargestellt werden, da es für die statische Analyse besser ist, die Gesamtzahl der explizit verfügbaren Ausdrücke verfügbar zu haben und auf jeden Ausdruck über dessen Ausdruck zugreifen zu können Index.

AST enthält einfach nur die Semantik des Codes, Parse Tree / CST enthält auch Informationen darüber, wie genau Code geschrieben wurde.

Der konkrete Syntaxbaum enthält alle Informationen wie überflüssige Klammern, Leerzeichen und Kommentare. Der abstrakte Syntaxbaum abstrahiert von diesen Informationen.

NB: Witzigerweise enthält Ihr AST bei der Implementierung einer Refactoring-Engine wieder alle konkreten Informationen, aber Sie werden es weiterhin als AST bezeichnen, da dies der Standardbegriff auf diesem Gebiet geworden ist (man könnte also sagen, dass es lange dauert vor seiner ursprünglichen Bedeutung verloren).

Es ist ein Unterschied, der keinen Unterschied macht.

Ein AST wird normalerweise erklärt, um die Semantik eines Programmiersprachenausdrucks durch Wegwerfen lexikalischer Inhalte zu approximieren. In einer kontextfreien Grammatik können Sie beispielsweise die folgende EBNF-Regel schreiben

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

Im AST-Fall verwenden Sie nur mul_rule und div_rule, die die richtigen arithmetischen Operationen ausdrücken.

Können diese Regeln nicht überhaupt in die Grammatik eingeführt werden? Natürlich. Sie können die obige kompakte und abstrakte Regel umschreiben, indem Sie sie in konkretere Regeln aufteilen, die zur Nachahmung der genannten AST-Knoten verwendet werden:

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

Wenn Sie nun an Top-Down-Parsing denken, führt der zweite Term einen FIRST / FIRST-Konflikt zwischen mul_rule und div_rule ein , mit dem sich ein LL (1) -Parser nicht befassen kann. Die erste Regelform war die links faktorisierte Version der zweiten, die die Struktur effektiv beseitigte. Sie müssen hier einen Preis für die Verwendung von LL (1) bezahlen.

ASTs sind also eine Ad-hoc-Ergänzung, mit der die Mängel von Grammatiken und Parsern behoben werden. Die CST -> AST-Transformation ist ein Refactoring-Schritt. Es hat niemanden gestört, wenn ein zusätzliches Komma oder ein Doppelpunkt im Syntaxbaum gespeichert ist. Im Gegenteil, einige Autoren rüsten sie in ASTs nach, weil sie ASTs gerne für Refactorings verwenden, anstatt verschiedene Bäume gleichzeitig zu pflegen oder eine zusätzliche Inferenz-Engine zu schreiben. Programmierer sind aus guten Gründen faul. Tatsächlich speichern sie sogar Zeilen- und Spalteninformationen, die durch lexikalische Analyse in ASTs für die Fehlerberichterstattung gesammelt wurden. Sehr abstrakt.

CST (Concrete Syntax Tree) ist eine Baumdarstellung der Grammatik (Regeln, wie das Programm geschrieben werden soll). Abhängig von der Compilerarchitektur kann der Parser einen AST erstellen.

AST (Abstract Syntax Tree) ist eine Baumdarstellung der analysierten Quelle, die vom Parser-Teil des Compilers erstellt wird. Es speichert Informationen zu Token + Grammatik.

Abhängig von der Architektur Ihres Compilers kann das CST zum Erstellen eines AST verwendet werden. Es ist fair zu sagen, dass sich CST zu AST entwickelt. Oder AST ist eine reichhaltigere CST.

Weitere Erklärungen finden Sie unter diesem Link: http://eli.thegreenplace.net/2009/02/16/abstract-vs-concrete-syntax-trees#id6