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

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

FYI, este es el Algoritmo Shunting-Yard .

En este caso, usaré una pila de operadores y una pila de expresiones. Dado que 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()  

(Sea amable con mi código. Sé que no es robusto; se supone que es un pseudocódigo.)

De todos modos, como puede ver en el código, arbitrario las expresiones 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 Traslado del árbol de pedido . Cuando 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 la instrucción apropiada del operador. Por ejemplo, el «+» El operador le da una instrucción «agregar».

Comentarios

• Esto funciona para r operadores que tienen asociatividad de izquierda a derecha, no de derecha a izquierda.
• @Simon, sería extremadamente simple agregar la capacidad para operadores de derecha a izquierda. Lo más simple sería agregar una tabla de búsqueda y, si es un operador de derecha a izquierda, simplemente invierta el orden de los operandos.
• @Simon Si desea admitir ambos, ‘ es mejor buscar el algoritmo del patio de maniobras en todo su esplendor. Según los algoritmos, ‘ es un cracker absoluto.

Existe una diferencia significativa entre cómo se representa típicamente un AST en la prueba (un árbol con números / variables en los nodos hoja y símbolos en los nodos interiores) y cómo se implementa realmente.

Lo típico La implementación 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 ASTNode común. 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 nombres de variables), 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 sintáctico crea el AST, quién sabe qué construcción acaba de analizar, para que pueda construir el tipo correcto de nodo AST.

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

Construir el AST a partir del texto fuente es » simplemente » análisis . Cómo se hace exactamente depende del lenguaje formal analizado y la implementación. Puede usar generadores de analizadores sintácticos como menhir (para Ocaml) , GNU bison con flex, o ANTLR , etc., etc. A menudo se hace » manualmente » codificando un analizador de descenso recursivo (consulte esta respuesta explicando por qué). El aspecto contextual del análisis se realiza a menudo en otros lugares (tablas de símbolos, atributos, …).

Sin embargo, en la práctica, las AST son mucho más complejas de lo que cree. Por ejemplo, en un compilador como GCC , el AST conserva la información de ubicación de la fuente y cierta información de escritura. Lea acerca de Generic Trees y GIMPLE en GCC y observe dentro de su gcc / tree.def . Considere, si desea procesar C o C ++ o Fortran o Ada, escribir su propio complemento GCC . Por cierto, mire también dentro del obsoleto GCC MELT (que he diseñado & implementado), es relevante para su pregunta. Lee el Libro del dragón . Consulte también este informe preliminar para obtener referencias, y el proyecto RefPerSys y el código fuente de muchos otros proyectos de código abierto (incluidos Ocaml o Guile o SBCL o Jq ) en github o gitlab como ejemplos.

Comentarios

• Yo ‘ estoy haciendo un intérprete Lua para analizar el texto fuente y transformarlo en una matriz en JS. ¿Puedo considerarlo un AST? Se supone que ‘ debo hacer algo como esto: --My comment #1 print("Hello, ".."world.") se transforma en `[{» escriba «: » – «, » content «: » Mi comentario # 1 «}, {» escriba «: » llame a «, » nombre «: » imprimir «, » argumentos «: [[{» tipo «: » str «, » acción «: » .. «, » contenido «: » Hola, «}, {» tipo «: » str «, » contenido «: » world. «}]]}] `Creo que ‘ es mucho más simple en JS que cualquier otro idioma!
• @TheProHands Esto se consideraría tokens, no un AST.

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 no 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 SEGÚN SE NECESITA.

Un ejemplo son las expresiones binarias como 1 + 2 Una expresión simple como eso crearía un único nodo raíz 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 era cómo atravesar? En este caso, atravesar se llama Visitar nodos . Visitar cada nodo requiere que utilice 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 de acuerdo con el tipo de nodo con el que estamos tratando.

¡Agreguemos un ejemplo más complejo, una estructura de instrucción if! Recuerde que las declaraciones if también puede tener una cláusula else opcional. Vamos a añadir la sentencia if-else a nuestra estructura de nodo original. Recuerde que las declaraciones if en sí mismas también pueden tener declaraciones if, por lo que puede ocurrir una especie de recursividad dentro de nuestro sistema de nodos. Las demás declaraciones son opcionales, por lo que el campo elsestmt puede ser NULO, lo 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; }; 

volver en nuestra función de impresión de visitante de nodo llamada AST_PrintNode, podemos acomodar la construcción AST de la instrucció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!