Wie genau wird ein abstrakter Syntaxbaum erstellt?

Ich glaube, ich verstehe das Ziel eines AST und habe schon einige Baumstrukturen gebaut, aber niemals einen AST. Ich bin größtenteils verwirrt, weil die Knoten aus Text und nicht aus Zahlen bestehen. Daher kann ich mir keine gute Möglichkeit vorstellen, ein Token / eine Zeichenfolge einzugeben, wenn ich Code analysiere.

Wenn ich zum Beispiel Diagramme von ASTs betrachtete, waren die Variable und ihr Wert Blattknoten mit einem Gleichheitszeichen. Das macht für mich durchaus Sinn, aber wie würde ich das umsetzen? Ich denke, ich kann es von Fall zu Fall tun, so dass ich, wenn ich auf ein "=" stoße, dieses als Knoten verwende und den vor dem "=" analysierten Wert als Blatt hinzufüge. Es scheint einfach falsch zu sein, weil ich wahrscheinlich, abhängig von der Syntax, Fälle für Unmengen von Dingen machen müsste.

Und dann bin ich auf ein anderes Problem gestoßen, wie wird der Baum überquert? Gehe ich den ganzen Weg die Höhe hinunter und gehe wieder einen Knoten hinauf, wenn ich unten bin, und mache das Gleiche für den Nachbarn?

Ich habe Unmengen von Diagrammen auf ASTs gesehen, aber ich konnte kein recht einfaches Beispiel im Code finden, was wahrscheinlich helfen würde.

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

Zu Ihrer Information, dies ist der Shunting-Yard-Algorithmus von Edsger Dijkstra .

In diesem Fall verwende ich einen Operator- 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 dem Code entnehmen können, können beliebige Ausdrücke 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 dieses AST erzeugen:

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

Wenn Sie dann den Code für diesen AST erstellen möchten, führen Sie eine Nachbestellungs-Baumdurchquerung durch . 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. Der Operator '+' gibt Ihnen beispielsweise eine Anweisung zum Hinzufügen.

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

Bei der typischen Implementierung eines AST (in einer OO-Sprache) wird Polymorphismus stark genutzt. Die Knoten im AST werden in der Regel mit einer Vielzahl von Klassen implementiert, die alle aus einer gemeinsamen Ableitung ASTNodeKlasse. Für jedes syntaktisches Konstrukt in der Sprache verarbeiten, wird es eine Klasse für dieses sein Konstrukt in dem AST darstellt, wie beispielsweise ConstantNode(für Konstanten, wie 0x10oder 42), VariableNode(für Variablennamen), AssignmentNode(für die 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. Ein ConstantNodeTestament hat normalerweise keine Kinder, ein AssignmentNodeTestament hat zwei und ein Testament ExpressionBlockNodekann eine beliebige Anzahl von Kindern haben.

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 Überqueren des AST kommt der Polymorphismus der Knoten wirklich ins Spiel. Die Basis ASTNodedefiniert die Operationen, die an den Knoten ausgeführt werden können, und jeder spezifische Knotentyp implementiert diese Operationen auf die spezifische Weise für dieses spezielle Sprachkonstrukt.

Das Erstellen des AST aus dem Quelltext ist "einfach" das Parsen . 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 bisonmit flexoder ANTLR usw. usw. verwenden. Dies geschieht häufig "manuell" durch Codierung eines rekursiven Abstiegsparsers (siehe diese Antwort zur Erklärung der Gründe). Der Kontextaspekt des Parsens wird oft an anderer Stelle ausgeführt (Symboltabellen, Attribute, ....).

In der Praxis sind AST jedoch weitaus komplexer als Sie glauben. In einem Compiler wie GCC speichert der AST beispielsweise Informationen zum Quellspeicherort und einige Tippinformationen. Lesen Sie mehr über generische Bäume in GCC und schauen Sie in die Datei gcc / tree.def . Übrigens, schauen Sie auch in GCC MELT (das ich entworfen und implementiert habe), es ist relevant für Ihre Frage.

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

Abstrakte Syntaxbäume werden nicht anders als andere Bäume erstellt. Die wahrere Aussage in diesem Fall ist, dass Syntaxbaumknoten eine unterschiedliche Anzahl von Knoten haben, WIE ERFORDERLICH.

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

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 überquert? Das Verfahren wird in diesem Fall als Besuchsknoten bezeichnet . Für den Besuch jedes Knotens müssen Sie für jeden Knotentyp festlegen, wie die Daten jedes Syntaxknotens ausgewertet werden sollen.

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 jeden Knoten rekursiv besucht, je nachdem, um welchen Knotentyp es sich handelt.

Fügen wir ein komplexeres Beispiel hinzu, ein ifAnweisungskonstrukt! Denken Sie daran, dass if-Anweisungen auch eine optionale else-Klausel enthalten können. 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, so dass eine Art Rekursion innerhalb unseres Knotensystems auftreten kann. Andere Anweisungen sind optional, sodass das elsestmtFeld NULL sein kann, was von der rekursiven Besucherfunktion ignoriert werden 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 aufgerufenen Node-Visitor-Print-Funktion AST_PrintNodekönnen wir die ifAnweisung AST-Konstrukt aufnehmen, indem wir diesen C-Code hinzufügen:

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 aus einer getaggten Vereinigung des Baums und seiner Daten selbst!