Die Begriffe AST (Abstract Syntax Tree), Syntaxbaum und Ableitungsbaum werden von verschiedenen Personen beschrieben, wenn sie sich auf das Ergebnis der Analyse von Texten beziehen, die einer Grammatik entsprechen. Angenommen, wir sprechen über das Parsen von Computersprachen, sind ihre Unterschiede so kurz, dass wir diese Begriffe synonym verwenden können? Wenn nicht, wie verwenden wir die Begriffe richtig?
AFAIK, "derivation tree" und "Parse Tree" sind gleich.
In der Informatik ist ein abstrakter Syntaxbaum (AST) oder nur ein Syntaxbaum eine Baumdarstellung der abstrakten syntaktischen Struktur des in einer Programmiersprache geschriebenen Quellcodes. Jeder Knoten des Baums bezeichnet ein Konstrukt, das im Quellcode vorkommt. Die Syntax ist "abstrakt" in dem Sinne, dass sie nicht jedes Detail darstellt, das in der realen Syntax erscheint.
Ein konkreter Syntaxbaum oder Parsebaum oder Parsingbaum ist ein (geordneter, verwurzelter) Baum, der die syntaktische Struktur eines Strings gemäß einer formalen Grammatik darstellt. In einem Syntaxbaum sind die inneren Knoten durch Nicht-Terminals der Grammatik gekennzeichnet, während die Blattknoten durch Terminals der Grammatik gekennzeichnet sind.
Nimm die Quelle a = (1 + 2) * 3; zum Beispiel. Der Parse-Baum könnte wie folgt aussehen:
, während der abstrakte Syntaxbaum wie folgt aussehen könnte:
%Vor%Ich würde den Ausdruck parse tree verwenden, wenn der Baum durch Parsing erzeugt wird, dh wenn eine gegebene Eingabesequenz zu der Sprache gehört und bestimmt, welche Produktionen in welcher Reihenfolge zu regenerieren sind die Sequenz.
Ein Ableitungsbaum hätte genau die gleiche Form, würde aber durch die Ableitung einer Sequenz aus einer gegebenen Produktion erzeugt werden.
Die formale Definition von parsing ist das Finden einer Ableitung für die gegebene Eingabefolge , also ist es kein Wunder, dass die Ableitungs- und Syntaxbäume identisch sind.
Konkrete versus abstrakte -Syntaxbäume unterscheiden sich dadurch, dass der erstere einen Blattknoten für jedes Token in der Eingabesequenz hat, während der letzte alle Token auslässt, die von ihm erkannt werden können Überprüfung der Grammatik. Ein konkreter Syntax-Unterbaum für if <expr> then <statement> else <statement> end hätte Blätter für wenn , dann , else und end und das abstrakte würde nicht. Der konkrete Syntaxbaum für (2+3) wäre:
Der abstrakte wäre nur:
%Vor%Parse / Derivation / Konkrete Syntaxbäume sind Synonyme für das gleiche Konzept.
Solche Bäume werden normalerweise nur in theoretischen Diskussionen verwendet, weil sie viele Details enthalten, die für die Sprachverarbeitung unnötig erscheinen; Benötigen Sie in einem Ausdrucksbaum wirklich einen Knoten, um "(" und "" "zu repräsentieren)?
Der Begriff eines "abstrakten Syntax" -Baums ist einer, der die Programmstruktur auf einer Detailebene darstellt, die für die Verarbeitung in der Praxis ausreichend ist; Normalerweise finden Sie keine Knoten für "(...)".
Eine interessante Frage: Ist ein AST direkt aus einem CST berechenbar? Die Antwort ist ja, aber die Leute tun es kaum. Sie neigen dazu, "abstrakte Syntax" -Knoten zu konstruieren, während der Parser läuft, und verwenden Ad-hoc (prozedurale rule reduction attachment), um die Knoten aus Child-Parsern mit einem Leimknoten für den Parent zu assemblieren. Meiner Meinung nach tun sie das, weil wir alle auf YACC aufgewachsen sind, und so wird es traditionell gemacht. (Wir pflegten auch Feuer mit Feuerstein anzuzünden.) Es gibt eine geringere Entschuldigung; Auf diese Weise erhält der Compiler-Builder die vollständige Kontrolle über die Struktur des AST und er kann einen solchen erzeugen, der hinsichtlich der zusätzlichen Details ziemlich minimal ist. Solch ein Ad-hoc-Baum ist von der CST nicht berechenbar, außer durch dieselbe Ad-hoc-Berechnung, die in die Parser-Aktionen eingebettet ist.
Ich habe einen anderen Ansatz gewählt: meine Tools berechnen AST direkt aus CSTs, buchstäblich durch Ablegen irrelevante Details, z. B. Auslassen von Knoten, die nichtwerttragende Token darstellen (z. B. diese sinnlosen Tokens sowie Schlüsselwörter), Komprimieren von Strings unärer Produktionen und Äquivalenz von rechts- oder linksweisenden Bäumen zu Listen, in echte Listenknoten. Der Vorteil dabei ist, dass der Parser den AST direkt aus den Grammatikregeln berechnen kann. Kein Herumfummeln mit prozeduralen Attachments. Kein Fehler. Keine Sorge mehr, dass unsere COBOL-Grammatik 3500 Regeln hat und ich sonst prozedurales goo für jeden brauchen würde einer von ihnen, und dass ich meine Grammatik hunderte Male ändern muss, um es richtig zu machen und jedes Mal an der Schmiere herumzubasteln. Und unsere Tools funktionieren so, als würden sie direkt auf dem CST arbeiten, was es leicht macht, über Baummanipulationen nachzudenken, besonders wenn Sie direkt auf die Grammatikregeln starren. (Dies erleichtert auch die Mustererkennung durch Verwendung der Oberflächensyntax. Für jedes Musterfragment gibt es einen direkt berechenbaren AST, der dem entspricht.)
Die Unterscheidung zwischen AST und CST ist also real in Bezug auf den Nutzen. Aber ich denke, sie sollten als nur isomorphe Darstellungen betrachtet werden.
Tags und Links lex parsing grammar abstract-syntax-tree