Como exatamente é criada uma Árvore de Sintaxe Abstrata?

A resposta curta é que você usa pilhas. This é um bom exemplo, mas vou aplicá-lo a uma AST.

FYI, este é o Algoritmo do Shunting-Yard de Edsger Dijkstra.

Nesse caso, usarei uma pilha de operadores e uma pilha de expressões. Como os números são considerados expressões na maioria das linguagens, utilizarei a pilha de expressões para armazená-las.

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

(Por favor, seja gentil com meu código. Eu sei que não é robusto; é apenas para ser pseudocódigo.)

De qualquer forma, como você pode ver no código, expressões arbitrárias podem ser operandos para outras expressões. Se você tiver a seguinte entrada:

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

o código que eu escrevi produziria este AST:

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

E quando você quiser produzir o código para essa AST, faça uma Traversal da Árvore de Pedidos de Postagens . Quando você visita um nó folha (com um número), você gera uma constante porque o compilador precisa conhecer os valores do operando. Quando você visita um nó com um operador, gera a instrução apropriada do operador. Por exemplo, o operador '+' fornece uma instrução "add".

Existe uma diferença significativa entre como uma AST é tipicamente representada no teste (uma árvore com números / variáveis nos nós da folha e símbolos nos nós interiores) e como ela é realmente implementada.

A implementação típica de um AST (em uma linguagem OO) faz uso intenso de polimorfismo. Os nós na AST são normalmente implementados com uma variedade de classes, todas derivadas de uma classe ASTNode comum. Para cada construção sintática na linguagem que você está processando, haverá uma classe para representar essa construção na AST, como ConstantNode (para constantes, como 0x10 ou 42 ), VariableNode (para variável nomes), AssignmentNode (para operações de atribuição), ExpressionNode (para expressões genéricas), etc.
Cada tipo de nó específico especifica se esse nó tem filhos, quantos e possivelmente de que tipo. Um ConstantNode normalmente não terá filhos, um AssignmentNode terá dois e um ExpressionBlockNode poderá ter qualquer número de filhos.

A AST é construída pelo analisador, que sabe que construção acabou de analisar, para que possa construir o tipo certo de Nó AST.

Ao atravessar a AST, o polimorfismo dos nós entra realmente em jogo. A base ASTNode define as operações que podem ser executadas nos nós, e cada tipo de nó específico implementa essas operações na maneira específica para essa construção de linguagem específica.

A criação do AST a partir do texto de origem é "simplesmente" análise . Como exatamente isso é feito depende da linguagem formal analisada e da implementação. Você poderia usar geradores de parser como menhir (para Ocaml) , GNU bison com flex ou ANTLR etc etc Muitas vezes é feito "manualmente", codificando alguns analisador de descendência recursiva (consulte esta resposta explicando por que). O aspecto contextual da análise é freqüentemente feito em outro lugar (tabelas de símbolos, atributos, ....).

No entanto, na prática AST são muito mais complexas do que você acredita. Por exemplo, em um compilador como o GCC , o AST mantém informações de localização de origem e algumas informações de digitação. Leia sobre Árvores genéricas no GCC e veja dentro do gcc / tree.def . BTW, veja também em GCC MELT (que eu projetei e implementei), é relevante para sua pergunta.

Eu sei que essa pergunta tem 4 anos ou mais, mas acho que devo adicionar uma resposta mais detalhada.

Resumo As árvores de sintaxe são criadas de forma diferente das outras árvores; a afirmação mais verdadeira neste caso é que os nós da Árvore de Sintaxe possuem uma quantidade variada de nós COMO NECESSÁRIO.

Um exemplo é expressões binárias como 1 + 2 Uma expressão simples como essa criaria um único nó raiz mantendo um nó direito e esquerdo que contém os dados sobre os números. Na linguagem C, seria algo parecido com

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

Sua pergunta também foi como atravessar? A travessia neste caso é chamada Visiting Nodes . Visitar cada Nó requer que você use cada tipo de nó para determinar como avaliar os dados de cada nó da Sintaxe.

Aqui está outro exemplo disso em C, onde eu simplesmente imprimo o conteúdo de cada nó:

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

Observe como a função recursivamente visita cada nó de acordo com o tipo de nó com o qual estamos lidando.

Vamos adicionar um exemplo mais complexo, uma construção da instrução if ! Lembre-se de que instruções if também podem ter uma cláusula else opcional. Vamos adicionar a instrução if-else à nossa estrutura de nós original. Lembre-se de que, se as instruções em si também puderem ter instruções if, poderá ocorrer um tipo de recursão dentro do nosso sistema de nós. Outras instruções são opcionais, portanto, o campo elsestmt pode ser NULL, o que a função de visitante recursivo pode ignorar.

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

de volta à nossa função de impressão do visitante de nós chamada AST_PrintNode , podemos acomodar a construção AST if , adicionando este código 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;

Tão simples quanto isso! Em conclusão, a Árvore de Sintaxe não é muito mais que uma árvore de uma união marcada da árvore e seus próprios dados!