wake-up-neo.net

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

Ich habe ein bisschen darüber gelesen, wie Dolmetscher/Compiler arbeiten, und ein Bereich, in dem ich verwirrt bin, ist der Unterschied zwischen einem AST und einem CST. Ich verstehe, dass der Parser ein CST erstellt und es dem semantischen Analysator übergibt, der es in ein AST umwandelt. Mein Verständnis ist jedoch, dass der semantische Analysator einfach sicherstellt, dass Regeln befolgt werden. Ich verstehe nicht wirklich, warum es tatsächlich Änderungen geben würde, um es abstrakt und nicht konkret zu machen.

Gibt es etwas, das mir am Semantikanalysator fehlt, oder ist der Unterschied zwischen einem AST und einem CST etwas künstlich?

67
Jason Baker

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

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

Sie müssen normalerweise keinen konkreten Syntaxbaum erstellen. Die Aktionsroutinen in Ihrer YACC- (oder Antlr- oder Menhir- oder was auch immer ...) - Grammatik können den abstrakten Syntaxbaum direkt erstellen. Der konkrete Syntaxbaum ist also nur als konzeptionelles Element vorhanden, das die Parsestruktur Ihres Quelltextes darstellt.

50

Ein konkreter Syntaxbaum entspricht der in den Grammatikregeln angegebenen Syntax. Der Zweck des abstrakten Syntaxbaums ist eine "einfache" Darstellung dessen, was im "Syntaxbaum" wesentlich ist.

Ein realer Wert in der AST IMHO ist, dass sie kleiner als die CST ist und daher weniger Zeit für die Verarbeitung benötigt. (Sie könnten sagen, wen interessiert das? Aber ich arbeite mit einem Werkzeug, bei dem wir Millionen von Knoten gleichzeitig haben!).

Die meisten Parser-Generatoren, die die Erstellung 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 die CST sind (und insofern sind sie im Allgemeinen richtig, da Programmierer hübsch sind faul). Das bedeutet wahrscheinlich, dass Sie weniger Baumbesucherfunktionen codieren müssen, und das ist auch insofern wertvoll, als es den Engineering-Aufwand minimiert. Wenn Sie 3500 Regeln haben (z. B. für COBOL), ist dies von Bedeutung. Und diese "einfachere" Art führt zu der guten Eigenschaft der "Kleinheit".

Aber solche ASTs zu haben, schafft ein Problem, das es nicht gab: Sie passen nicht zur Grammatik, und jetzt müssen Sie beide im Kopf verfolgen. Und wenn es 1500 AST Knoten für eine 3500-Regelgrammatik gibt, ist dies sehr wichtig. Und wenn sich die Grammatik weiterentwickelt (das tun sie immer!), Müssen Sie jetzt zwei Riesenmengen von Dingen synchron halten.

Eine andere Lösung besteht darin, dass der Parser einfach CST-Knoten für Sie erstellt und diese verwendet. Dies ist ein großer Vorteil beim Erstellen der Grammatik: Es ist nicht erforderlich, 1500 spezielle AST - Knoten zu erfinden, um 3500 Grammatikregeln zu modellieren. Denken Sie nur an den Baum, der isomorph zur Grammatik ist. Aus der 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 wird automatisch eine CST erstellt, die auf den Ergebnissen eines (GLR) -Parsing-Prozesses basiert. DMS erstellt dann automatisch eine "komprimierte" CST aus Gründen der Raumeffizienz, indem nicht werttragende Terminals (Stichwörter, Interpunktion), semantisch nutzlose unäre Produktionen beseitigt und Listen für Grammatikregelpaare erstellt werden, die wie folgt lauten:

    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 das virtuelle CST. Das Tool bearbeitet die komprimierte Darstellung. Schont das Gehirn, zur Laufzeit schneller/kleiner.

Bemerkenswerterweise sieht das auf diese Weise erstellte komprimierte CST wie ein AST aus, das Sie möglicherweise von Hand entworfen haben (siehe Link am Ende der Beispiele). Insbesondere enthält das komprimierte CST keine Knoten, die nur eine konkrete Syntax haben. Es gibt kleinere Ungeschicklichkeiten: Während sich die konkreten Knoten für '(' und ')', die klassisch in Ausdruckssubgrammatiken vorkommen, nicht im Baum befinden, tut ein "Klammerknoten" erscheinen in der komprimierten CST und müssen behandelt werden. Ein wahres AST hätte das nicht. Dies scheint ein ziemlich geringer Preis zu sein, um die AST -Konstruktion nicht 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 sind nicht ganz sicher, aber DMS bietet eine AST - Bibliothek, die das AST durchläuft und die Unterschiede zwischen dem CST und dem AST transparent behandelt. DMS bietet auch einen "Attribut-Grammatik" -Auswerter (AGE), eine Methode zum Übergeben von Werten, die an Knoten berechnet wurden, entlang des Baums. Das AGE kümmert sich um alle Probleme mit der Baumdarstellung, und der Werkzeugingenieur kümmert sich nur darum, 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 Typen von Teilbäumen zu finden, ohne die meisten beteiligten Knotentypen zu kennen.

In einer der anderen Antworten wird festgestellt, dass Ihr AST mit der CST übereinstimmen muss, wenn Sie Tools erstellen möchten, mit denen die Quelle regeneriert 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 Großteil des Prettyprinter automatisch weil es Zugriff auf beide hat: -}

Fazit: ASTs sind gut für kleine, sowohl phyiskalische 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 für CST vs. "AST", die auf diese Weise erstellt wurden

30
Ira Baxter

Dieser Blogbeitrag kann hilfreich sein.

Mir scheint, dass die AST viele grammatikalische/strukturelle Zwischeninformationen "wegwirft", die nicht zur Semantik beitragen. Beispielsweise ist es Ihnen egal, dass 3 ein Atom ist, ein Begriff ein Faktor ist ein .... Sie kümmern sich nur darum, dass es 3 ist, wenn Sie den Exponentiationsausdruck oder was auch immer implementieren.

18

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 speichert alle Informationen der Eingabe. Die leeren Kästchen stehen für Leerzeichen, d. H. Zeilenende.

Parse Tree

AST

Das 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

BEARBEITEN

Weitere Erläuterungen finden Sie unter Compiler und Compiler-Generatoren pg. 23

14
Guy Coder

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

  • ausdrucksliste kann sein: Ausdruck
  • ausdrucksliste kann sein: Ausdruck, Ausdrucksliste

Diese beiden Regeln folgen wörtlich einer Kammform für jede Ausdrucksliste, die im Programm angezeigt wird.

Der abstrakte Syntaxbaum ist in der Form, die für die weitere Bearbeitung geeignet ist. Es stellt Dinge auf eine Weise dar, die für jemanden Sinn ergibt, der die Bedeutung von Programmen versteht und nicht nur die Art und Weise, wie sie geschrieben werden. Die obige Ausdrucksliste, die die Liste der Argumente einer Funktion sein kann, kann zweckmäßigerweise als Vektor von Ausdrücken dargestellt werden, da es für statische Analysen besser ist, die Gesamtzahl der Ausdrücke explizit zur Verfügung zu haben und auf jeden Ausdruck über seinen Ausdruck zugreifen zu können Index.

9
Pascal Cuoq

Es ist ein Unterschied, der keinen Unterschied macht.

Ein AST wird normalerweise als Weg erklärt, um die Semantik eines Ausdrucks einer Programmiersprache durch Wegwerfen von lexikalischem Inhalt anzunähern. In einer kontextfreien Grammatik schreiben Sie beispielsweise die folgende EBNF-Regel

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

in dem Fall AST verwenden Sie nur mul_rule und div_rule das drückt die richtigen arithmetischen Operationen aus. 

Können diese Regeln nicht überhaupt in die Grammatik eingeführt werden? Na sicher. Sie können die obige kompakte und abstrakte Regel umschreiben, indem Sie sie in mehr konkrete Regeln aufteilen, die verwendet werden, um die erwähnten AST Knoten nachzuahmen:

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

Nun, wenn Sie über Top-Down-Analyse nachdenken, dann die zweite term führt einen ERSTEN/ERSTEN Konflikt zwischen ein mul_rule und div_rule etwas, mit dem ein LL (1) -Parser nicht umgehen kann. Die erste Regelform war die links faktorisierte Version der zweiten, wodurch die Struktur effektiv beseitigt wurde. Sie müssen etwas für die Verwendung von LL (1) bezahlen.

Bei AST handelt es sich also um eine Ad-hoc-Ergänzung, mit der die Mängel von Grammatiken und Parsern behoben werden. Die CST -> AST Transformation ist ein Refaktorisierungsschritt. Niemand hat sich jemals die Mühe gemacht, wenn ein zusätzliches Komma oder ein Doppelpunkt im Syntaxbaum gespeichert wird. Im Gegenteil, einige Autoren rüsten sie in ASTs um, weil sie ASTs für Refactorings verwenden möchten, anstatt verschiedene Bäume gleichzeitig zu unterhalten oder eine zusätzliche Inferenzmaschine zu schreiben. Programmierer sind aus guten Gründen faul. Tatsächlich speichern sie sogar Zeilen- und Spalteninformationen, die durch lexikalische Analyse in ASTs zur Fehlerberichterstattung gesammelt wurden. Sehr abstrakt.

1
Kay Schluehr

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

NB: komischerweise, wenn Sie eine Refactoring-Engine implementieren, enthält Ihr AST wieder alle konkreten Informationen, aber Sie bezeichnen es weiterhin als AST, da dies zum Standardbegriff in wurde das Feld (man könnte sagen, es hat längst seine ursprüngliche Bedeutung verloren).

1
akuhn

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

0
mym