¿Cómo se crea exactamente un árbol de sintaxis abstracta?

La respuesta corta es que usas pilas. This es un buen ejemplo, pero lo aplicaré a un AST.

Para tu información, este es el Algoritmo de yardas de Shunting de Edsger Dijkstra.

En este caso, usaré una pila de operadores y una pila de expresiones. Como los números se consideran expresiones en la mayoría de los idiomas, usaré la pila de expresiones para almacenarlos.

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, sea amable con mi código. Sé que no es robusto; se supone que es un pseudocódigo).

De todos modos, como se puede ver en el código, las expresiones arbitrarias pueden ser operandos de otras expresiones. Si tiene la siguiente entrada:

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

el código que escribí produciría este AST:

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

Y luego, cuando desee producir el código para ese AST, haga un Recorrido del árbol de la orden de envío . Cuando visita un nodo hoja (con un número), genera una constante porque el compilador necesita conocer los valores del operando. Cuando visita un nodo con un operador, genera las instrucciones apropiadas del operador. Por ejemplo, el operador '+' le da una instrucción de "agregar".

Hay una diferencia significativa entre la forma en que normalmente se representa un AST (un árbol con números / variables en los nodos de hoja y los símbolos en los nodos interiores) y cómo se implementa realmente.

La implementación típica de un AST (en un lenguaje OO) hace un uso intensivo del polimorfismo. Los nodos en el AST se implementan típicamente con una variedad de clases, todas derivadas de una clase común ASTNode . Para cada construcción sintáctica en el lenguaje que está procesando, habrá una clase para representar esa construcción en el AST, como ConstantNode (para constantes, como 0x10 o 42 ), VariableNode (para variable nombres), AssignmentNode (para operaciones de asignación), ExpressionNode (para expresiones genéricas), etc.
Cada tipo de nodo específico especifica si ese nodo tiene hijos, cuántos y posiblemente de qué tipo. Un ConstantNode normalmente no tendrá hijos, un AssignmentNode tendrá dos y un ExpressionBlockNode puede tener cualquier número de hijos.

El analizador construye el AST, quien sabe qué construcción acaba de analizar, por lo que puede construir el tipo correcto de nodo AST.

Al atravesar el AST, el polimorfismo de los nodos entra realmente en juego. La base ASTNode define las operaciones que pueden realizarse en los nodos, y cada tipo de nodo específico implementa esas operaciones de la manera específica para esa construcción de idioma en particular.

La creación del AST a partir del texto de origen es "simplemente" análisis . La forma exacta en que se hace depende del lenguaje formal analizado y de la implementación. Puede usar generadores de analizadores como menhir (para Ocaml) , GNU bison con flex , o ANTLR etc. etc. A menudo se realiza "manualmente" mediante la codificación de algunos analizador de descenso recursivo (consulte esta respuesta explicando por qué). El aspecto contextual del análisis a menudo se realiza en otros lugares (tablas de símbolos, atributos, ...).

Sin embargo, en la práctica, los AST son mucho más complejos de lo que crees. Por ejemplo, en un compilador como GCC , el AST mantiene la información de ubicación de origen y algo de información de escritura. Lea sobre árboles genéricos en GCC y busque en su gcc / tree.def . Por cierto, busque también en GCC MELT (que he diseñado y implementado), es relevante para su pregunta.

Sé que esta pregunta tiene más de 4 años, pero creo que debería agregar una respuesta más detallada.

Los árboles de sintaxis abstracta se crean de manera diferente a otros árboles; La afirmación más cierta en este caso es que los nodos del árbol de sintaxis tienen una cantidad variable de nodos COMO SE NECESITA.

Un ejemplo son expresiones binarias como 1 + 2 Una expresión simple como esa crearía un nodo raíz único que contiene un nodo derecho e izquierdo que contiene los datos sobre los números. En lenguaje C, se vería algo así 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;
};

Tu pregunta también fue cómo atravesar? El desplazamiento en este caso se denomina Nodos visitantes . La visita a cada nodo requiere que use cada tipo de nodo para determinar cómo evaluar los datos de cada nodo de Sintaxis.

Aquí hay otro ejemplo de eso en C, donde simplemente imprimo el contenido de cada 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;
    }
}

Observe cómo la función visita recursivamente cada nodo según el tipo de nodo con el que estamos tratando.

Agreguemos un ejemplo más complejo, una construcción de declaración if ! Recuerde que si las declaraciones también pueden tener una cláusula else opcional. Agreguemos la sentencia if-else a nuestra estructura de nodo original. Recuerde que si las declaraciones también pueden tener declaraciones if, entonces puede ocurrir un tipo de recursión dentro de nuestro sistema de nodos. Las demás instrucciones son opcionales, por lo que el campo elsestmt puede ser NULL, que la función de visitante recursivo puede 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 vuelta en nuestra función de impresión de visitantes de nodo llamada AST_PrintNode , podemos acomodar la construcción AST de la declaración if agregando 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;

¡Tan simple como eso! En conclusión, el árbol de sintaxis no es mucho más que un árbol de una unión etiquetada del árbol y sus propios datos.