Wie genau wird ein abstrakter Syntaxbaum erstellt?

Die kurze Antwort lautet, dass Sie Stapel verwenden. Dies ist ein gutes Beispiel, aber ich werde es auf einen AST anwenden.

Zu Ihrer Information, dies ist die Shunting-Yard-Algorithmus .

In diesem Fall verwende ich einen Operatorstapel und einen Ausdrucksstapel. Da Zahlen in den meisten Sprachen als Ausdrücke betrachtet werden, verwende ich den Ausdrucksstapel, um sie zu speichern.

 class ExprNode: char c ExprNode operand1 ExprNode operand2 ExprNode(char num): c = num operand1 = operand2 = nil Expr(char op, ExprNode e1, ExprNode e2): c = op operand1 = e1 operand2 = e2 # Parser ExprNode parse(string input): char c while (c = input.getNextChar()): if (c == "("): operatorStack.push(c) else if (c.isDigit()): exprStack.push(ExprNode(c)) else if (c.isOperator()): while(operatorStack.top().precedence >= c.precedence): operator = operatorStack.pop() # Careful! The second operand was pushed last. e2 = exprStack.pop() e1 = exprStack.pop() exprStack.push(ExprNode(operator, e1, e2)) operatorStack.push(c) else if (c == ")"): while (operatorStack.top() != "("): operator = operatorStack.pop() # Careful! The second operand was pushed last. e2 = exprStack.pop() e1 = exprStack.pop() exprStack.push(ExprNode(operator, e1, e2)) # Pop the "(" off the operator stack. operatorStack.pop() else: error() return nil # There should only be one item on exprStack. # It"s the root node, so we return it. return exprStack.pop()  

(Bitte seien Sie nett zu meinem Code. Ich weiß, dass er nicht robust ist; er soll nur Pseudocode sein.)

Wie Sie aus dem Code ersehen können, willkürlich Ausdrücke können Operanden für andere Ausdrücke sein. Wenn Sie die folgende Eingabe haben:

5 * 3 + (4 + 2 % 2 * 8) 

Der von mir geschriebene Code würde diesen AST erzeugen:

 + / \ / \ * + / \ / \ 5 3 4 * / \ % 8 / \ 2 2 

Wenn Sie dann den Code für diesen AST erstellen möchten, führen Sie eine Nachbestellungsbaumdurchquerung durch. Wann Wenn Sie einen Blattknoten (mit einer Zahl) besuchen, generieren Sie eine Konstante, da der Compiler die Operandenwerte kennen muss. Wenn Sie einen Knoten mit einem Operator besuchen, generieren Sie die entsprechende Anweisung vom Operator. Zum Beispiel das „+“ Der Operator gibt Ihnen eine Anweisung zum Hinzufügen.

Kommentare

• Dies funktioniert für r Operatoren mit Assoziativität von links nach rechts, nicht von rechts nach links.
• @Simon, es wäre äußerst einfach, die Funktion für Operatoren von rechts nach links hinzuzufügen. Am einfachsten wäre es, eine Nachschlagetabelle hinzuzufügen und bei einem Operator von rechts nach links einfach die Reihenfolge der Operanden umzukehren.
• @Simon Wenn Sie beide unterstützen möchten, ‚ ist es besser, den Rangierplatz-Algorithmus in seiner vollen Pracht nachzuschlagen. Nach den Algorithmen ist ‚ ein absoluter Knaller.

Es gibt einen signifikanten Unterschied zwischen der typischen Darstellung eines AST im Test (ein Baum mit Zahlen / Variablen an den Blattknoten und Symbolen an den inneren Knoten) und der tatsächlichen Implementierung.

Das typische Die Implementierung eines AST (in einer OO-Sprache) nutzt den Polymorphismus stark. Die Knoten im AST werden normalerweise mit einer Vielzahl von Klassen implementiert, die alle von einer gemeinsamen ASTNode -Klasse abgeleitet sind. Für jedes syntaktische Konstrukt in der Sprache, die Sie verarbeiten, gibt es eine Klasse zur Darstellung dieses Konstrukts im AST, z. B. ConstantNode (für Konstanten wie 0x10 oder 42), VariableNode (für Variablennamen), AssignmentNode (für Zuweisungsoperationen), ExpressionNode (für generische Ausdrücke) usw.
Jeder bestimmte Knotentyp gibt an, ob dieser Knoten untergeordnete Knoten hat, wie viele und möglicherweise von welchem Typ. Eine ConstantNode hat normalerweise keine Kinder, eine AssignmentNode hat zwei und eine ExpressionBlockNode kann Sie haben eine beliebige Anzahl von untergeordneten Elementen.

Der AST wird vom Parser erstellt, der weiß, welches Konstrukt er gerade analysiert hat, damit er die richtige Art von AST-Knoten erstellen kann.

Beim Durchlaufen Beim AST kommt der Polymorphismus der Knoten wirklich ins Spiel. Die Basis ASTNode definiert die Operationen, die an den Knoten ausgeführt werden können, und jeder bestimmte Knotentyp implementiert diese Operationen auf die spezifische Weise für dieses bestimmte Sprachkonstrukt.

Das Erstellen des AST aus dem Quelltext ist “ einfach “ Analyse . Wie genau es gemacht wird, hängt von der analysierten formalen Sprache und der Implementierung ab. Sie können Parser-Generatoren wie menhir (für Ocaml) , GNU bison mit flex oder ANTLR usw. usw. Dies geschieht häufig “ manuell “ durch Codieren eines Parser für rekursiven Abstieg (siehe diese Antwort erklärt warum). Der kontextbezogene Aspekt des Parsens wird häufig an anderer Stelle durchgeführt (Symboltabellen, Attribute usw.).

In der Praxis sind AST jedoch viel komplexer als Sie glauben. In einem Compiler wie GCC speichert der AST beispielsweise Quellspeicherortinformationen und einige Tippinformationen. Lesen Sie mehr über Generische Bäume und GIMPLE in GCC und sehen Sie sich die gcc / tree.def . Wenn Sie C oder C ++ oder Fortran oder Ada verarbeiten möchten, schreiben Sie Ihr eigenes GCC-Plugin . Übrigens, schauen Sie auch in das veraltete GCC MELT (das ich & implementiert habe), es ist relevant für Sie Frage. Lesen Sie das Drachenbuch . Siehe auch dieses Berichtsentwurfs für Referenzen sowie das RefPerSys -Projekt und den Quellcode vieler andere Open Source -Projekte (einschließlich Ocaml oder Guile oder SBCL oder Jq ) auf github oder gitlab als Beispiele.

Kommentare

• Ich ‚ mache einen Lua-Interpreter, um Quelltext zu analysieren und in ein Array in JS zu transformieren. Kann ich es als AST betrachten? Ich ‚ soll so etwas tun: --My comment #1 print("Hello, ".."world.") transformiert sich in `[{“ Geben Sie “ ein: “ – „, “ Inhalt „: “ Mein Kommentar Nr. 1 „}, {“ Typ „: “ call „, “ name „: “ print „, “ Argumente „: [[{{div id = „0edb01244e“>

Ich weiß, dass diese Frage 4+ Jahre alt ist, aber ich denke, ich sollte eine detailliertere Antwort hinzufügen.

Abstrakte Syntax Bäume werden nicht anders als andere Bäume erstellt. Die wahrere Aussage in diesem Fall ist, dass Syntaxbaumknoten je nach Bedarf eine unterschiedliche Anzahl von Knoten haben.

Ein Beispiel sind binäre Ausdrücke wie 1 + 2 Ein einfacher Ausdruck wie das würde einen einzelnen Wurzelknoten erzeugen, der einen rechten und einen linken Knoten enthält, der die Daten über die Zahlen enthält.In der Sprache C würde es ungefähr so aussehen wie

struct ASTNode; union SyntaxNode { int64_t llVal; uint64_t ullVal; struct { struct ASTNode *left, *right; } BinaryExpr; }; enum SyntaxNodeType { AST_IntVal, AST_Add, AST_Sub, AST_Mul, AST_Div, AST_Mod, }; struct ASTNode { union SyntaxNode *Data; enum SyntaxNodeType Type; }; 

Ihre Frage war auch, wie man durchquert? Das Traversieren heißt in diesem Fall Besuchsknoten . Für den Besuch jedes Knotens müssen Sie jeden Knotentyp verwenden, um zu bestimmen, wie die Daten jedes Syntaxknotens ausgewertet werden.

Hier ist ein weiteres Beispiel dafür in C, wo ich einfach den Inhalt jedes Knotens drucke:

void AST_PrintNode(const ASTNode *node) { if( !node ) return; char *opername = NULL; switch( node->Type ) { case AST_IntVal: printf("AST Integer Literal - %lli\n", node->Data->llVal); break; case AST_Add: if( !opername ) opername = "+"; case AST_Sub: if( !opername ) opername = "-"; case AST_Mul: if( !opername ) opername = "*"; case AST_Div: if( !opername ) opername = "/"; case AST_Mod: if( !opername ) opername = "%"; printf("AST Binary Expr - Oper: \"%s\" Left:\"%p\" | Right:\"%p\"\n", opername, node->Data->BinaryExpr.left, node->Data->BinaryExpr.right); AST_PrintNode(node->Data->BinaryExpr.left); // NOTE: Recursively Visit each node. AST_PrintNode(node->Data->BinaryExpr.right); break; } } 

Beachten Sie, wie die Funktion rekursiv besucht Jeder Knoten hängt davon ab, um welchen Knotentyp es sich handelt.

Fügen wir ein komplexeres Beispiel hinzu, ein if -Anweisungskonstrukt! Erinnern Sie sich an if-Anweisungen kann auch eine optionale else-Klausel haben. Fügen wir die if-else-Anweisung zu unserer ursprünglichen Knotenstruktur hinzu. Denken Sie daran, dass if-Anweisungen selbst auch if-Anweisungen haben können, sodass eine Art Rekursion innerhalb unseres Knotensystems auftreten kann. Andernfalls sind Anweisungen optional, sodass das Feld elsestmt NULL sein kann, was die rekursive Besucherfunktion ignorieren kann.

struct ASTNode; union SyntaxNode { int64_t llVal; uint64_t ullVal; struct { struct ASTNode *left, *right; } BinaryExpr; struct { struct ASTNode *expr, *stmt, *elsestmt; } IfStmt; }; enum SyntaxNodeType { AST_IntVal, AST_Add, AST_Sub, AST_Mul, AST_Div, AST_Mod, AST_IfStmt, AST_ElseStmt, AST_Stmt }; struct ASTNode { union SyntaxNode *Data; enum SyntaxNodeType Type; }; 

zurück In unserer Knotenbesucher-Druckfunktion mit dem Namen AST_PrintNode können wir das AST-Konstrukt der if -Anweisung durch Hinzufügen dieses C-Codes aufnehmen:

case AST_IfStmt: puts("AST If Statement\n"); AST_PrintNode(node->Data->IfStmt.expr); AST_PrintNode(node->Data->IfStmt.stmt); AST_PrintNode(node->Data->IfStmt.elsestmt); break; 

So einfach ist das! Zusammenfassend ist der Syntaxbaum nicht viel mehr als ein Baum einer markierten Vereinigung des Baums und seiner Daten selbst!