Come è stato creato un Abstract Syntax Tree?

La risposta breve è che usi pile. Questo è un buon esempio, ma lo applicherò ad un AST.

FYI, questo è Algoritmo di smistamento di Edsger Dijkstra

In questo caso, userò uno stack operatore e uno stack di espressioni. Poiché i numeri sono considerati espressioni nella maggior parte delle lingue, userò lo stack di espressioni per memorizzarle.

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()

(Si prega di essere gentile con il mio codice. So che non è robusto, dovrebbe essere solo uno pseudocodice.)

Ad ogni modo, come puoi vedere dal codice, le espressioni arbitrarie possono essere operandi ad altre espressioni. Se hai il seguente input:

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

il codice che ho scritto produrrebbe questo AST:

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

E poi quando vuoi produrre il codice per quel AST, fai un Traversamento degli alberi degli ordini . Quando si visita un nodo foglia (con un numero), si genera una costante perché il compilatore deve conoscere i valori dell'operando. Quando si visita un nodo con un operatore, si genera l'istruzione appropriata dall'operatore. Ad esempio, l'operatore '+' ti dà un'istruzione "aggiungi".

Esiste una differenza significativa tra il modo in cui un AST viene tipicamente rappresentato nel test (un albero con numeri / variabili ai nodi foglia e simboli nei nodi interni) e come viene effettivamente implementato.

L'implementazione tipica di un AST (in un linguaggio OO) fa un uso pesante del polimorfismo. I nodi nell'AST vengono in genere implementati con una varietà di classi, tutte derivanti da una comune classe ASTNode . Per ogni costrutto sintattico nella lingua che stai elaborando, ci sarà una classe per rappresentare quel costrutto nell'AST, come ConstantNode (per costanti, come 0x10 o 42 ), VariableNode (per variabile nomi), AssignmentNode (per le operazioni di assegnazione), ExpressionNode (per le espressioni generiche), ecc.
Ogni specifico tipo di nodo specifica se quel nodo ha figli, quanti e possibilmente di quale tipo. Un ConstantNode in genere non ha figli, un AssignmentNode avrà due e un ExpressionBlockNode può avere un numero qualsiasi di bambini.

L'AST viene creato dal parser, che sa che cosa ha appena analizzato il suo costrutto, quindi può costruire il giusto tipo di nodo AST.

Quando attraversi l'AST, il polimorfismo dei nodi entra davvero in gioco. La base ASTNode definisce le operazioni che possono essere eseguite sui nodi e ogni specifico tipo di nodo implementa tali operazioni nel modo specifico per quel particolare costrutto linguistico.

Costruire AST dal testo sorgente è "semplicemente" analizzando . Il modo in cui viene eseguito esattamente dipende dal linguaggio formale analizzato e dall'implementazione. Potresti usare generatori di parser come menhir (per Ocaml) , GNU bison con flex o ANTLR ecc. ecc. Si fa spesso "manualmente" codificando alcuni parser di discesa ricorsivo (vedi questa risposta spiegando il perché). L'aspetto contestuale dell'analisi viene spesso fatto altrove (tabelle dei simboli, attributi, ....).

Tuttavia, nella pratica AST sono molto più complessi di quello che credi. Ad esempio, in un compilatore come GCC l'AST conserva le informazioni sulla posizione della fonte e alcune informazioni di digitazione. Leggi Alberi generici in GCC e guarda all'interno di gcc / tree.def . A proposito, guarda anche all'interno GCC MELT (che ho progettato e implementato), è pertinente alla tua domanda.

So che questa domanda ha 4 o più anni, ma sento che dovrei aggiungere una risposta più dettagliata.

Gli alberi sintattici astratti non vengono creati diversamente dagli altri alberi; l'affermazione più vera in questo caso è che i nodi Syntax Tree hanno una quantità variabile di nodi come necessario.

Un esempio sono espressioni binarie come 1 + 2 Un'espressione semplice come quella creerebbe un singolo nodo radice che contiene un nodo destro e uno sinistro che contiene i dati relativi ai numeri. In linguaggio C, sarebbe simile a

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;
};

La tua domanda era anche come attraversare? Il traversamento in questo caso è chiamato Nodi di visita . Per visitare ciascun nodo è necessario utilizzare ogni tipo di nodo per determinare come valutare i dati di ciascun nodo della sintassi.

Ecco un altro esempio di quello in C in cui stampo semplicemente il contenuto di ciascun nodo:

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;
    }
}

Si noti come la funzione visita ricorsivamente ciascun nodo in base al tipo di nodo con cui si ha a che fare.

Aggiungiamo un esempio più complesso, un costrutto di dichiarazione if ! Ricorda che se le istruzioni possono anche avere una clausola else opzionale. Aggiungiamo l'istruzione if-else alla nostra struttura del nodo originale. Ricorda che se le affermazioni stesse possono avere anche delle istruzioni, può verificarsi una specie di ricorsione all'interno del nostro sistema di nodi. Le istruzioni else sono facoltative, quindi il campo elsestmt può essere NULL che la funzione visitatore ricorsiva può ignorare.

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;
};

nella nostra funzione di stampa dei visitatori del nodo chiamata AST_PrintNode , possiamo accomodare il costrutto AST if dell'istruzione aggiungendo questo codice C:

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;

Semplice come quello! In conclusione, Syntax Tree non è molto più di un albero di un'unione taggata dell'albero e dei suoi dati stessi!