Como exatamente uma árvore de sintaxe abstrata é criada?

Acho que entendi o objetivo de um AST e construí algumas estruturas de árvores antes, mas nunca um AST. Estou confuso porque os nós são texto e não número, por isso não consigo pensar em uma maneira agradável de inserir um token / string enquanto estou analisando algum código.

Por exemplo, quando observei os diagramas de ASTs, a variável e seu valor eram nós de folhas com um sinal de igual. Isso faz todo o sentido para mim, mas como eu implementaria isso? Acho que posso fazê-lo caso a caso, de modo que, quando deparei com um "=", o uso como um nó e adiciono o valor analisado antes do "=" como a folha. Parece errado, porque eu provavelmente teria que defender toneladas de coisas, dependendo da sintaxe.

E então me deparei com outro problema: como a árvore é atravessada? Desço a altura e volto a subir um nó quando bato no fundo, e faço o mesmo pelo vizinho?

Eu já vi vários diagramas em ASTs, mas não consegui encontrar um exemplo bastante simples de um no código, o que provavelmente ajudaria.

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

Para sua informação, este é o algoritmo 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 dos idiomas, usarei a pilha de expressões para armazená-los.

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 legal com o meu código. Eu sei que ele não é robusto; é apenas um 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 escrevi produziria esse AST:

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

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

Há uma diferença significativa entre como um AST é normalmente representado no teste (uma árvore com números / variáveis ​​nos nós das folhas e símbolos nos nós internos) e como ele é realmente implementado.

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

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

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

Criar o AST a partir do texto de origem é "simplesmente" analisado . Como exatamente isso é feito depende da linguagem formal analisada e da implementação. Você pode usar geradores de analisador como menhir (para Ocaml) , GNU bisoncom flexou ANTLR, etc. Isso geralmente é feito "manualmente", codificando algum analisador de descida recursivo (veja esta resposta explicando o porquê). O aspecto contextual da análise geralmente é feito em outro lugar (tabelas de símbolos, atributos, ....).

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

Sei que esta pergunta tem mais de 4 anos, mas acho que devo adicionar uma resposta mais detalhada.

Resumo Sintaxe Árvores não são criadas de maneira diferente de outras árvores; a afirmação mais verdadeira nesse caso é que os nós da árvore de sintaxe têm uma quantidade variável de nós, conforme necessário.

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

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? Atravessar neste caso é chamado de nós visitantes . 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 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 visita recursivamente cada nó de acordo com o tipo de nó com o qual estamos lidando.

Vamos adicionar um exemplo mais complexo, uma ifconstrução de instrução! Lembre-se de que as 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 as próprias declarações if também podem ter if, para que ocorra um tipo de recursão dentro do nosso sistema de nós. As demais instruções são opcionais para que o elsestmtcampo possa ser NULL, que a função recursiva do visitante 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 à função de impressão do visitante do nó chamada AST_PrintNode, podemos acomodar a ifconstrução AST da instrução 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 como 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!