abstract syntax tree - sintacticos - Cómo construir un árbol sintáctico abstracto

que es un compilador sintactico

Question

Tengo una idea general de lo que es un AST, pero quiero saber cómo construir uno.

Si te dan una gramática y un árbol de análisis sintáctico, ¿cómo construyes el AST?

¿Cómo lo haces si te dan una gramática y una expresión?

Answer 1

Bueno, primero, la gramática se usa para construir un árbol de análisis sintáctico a partir de una expresión. Entonces, si ya tiene un árbol de análisis sintáctico, no necesita la gramática.

Dependiendo de la cantidad de trabajo que haga su analizador, el árbol resultante que se forma a partir del análisis de una expresión ya podría ser un árbol de sintaxis abstracta. O podría ser un árbol de análisis simple que requiere un segundo pase para construir el ast.

Para construir el árbol de análisis sintáctico de una gramática y una expresión, primero debe convertir su gramática en código de trabajo. Normalmente, dividiría el trabajo en un tokenizador que divide la secuencia de entrada que representa la expresión en una lista de tokens, y un analizador que toma la lista de tokens y construye un árbol de análisis / ast a partir de él.

Entonces la expresión 1 + 2*(3+4) podría dividirse en una lista de tokens como esta:

1 - int
+ - add_operator
2 - int
* - mul_operator
( - lparen
3 - int
+ - add_operator
4 - int
) - rparen

La primera columna es el valor de texto real. El segundo representa el tipo de token. Estos tokens se alimentan en el analizador sintáctico, que se construye a partir de su gramática y reconoce los tokens y crea el árbol de análisis sintáctico.

Entonces, ¿cómo se escribe el tokenizador léxico y el analizador real? Podrías enrollar el tuyo a mano. O, más comúnmente, use un generador de analizadores como coco o antlr o lex / yacc. Estas herramientas toman una descripción de tu gramática y generan el código para un tokenzier y un analizador. (Existen generadores de código para la mayoría de los lenguajes populares y algunos también impopulares).

La forma en que construyas tu analizador depende en gran medida del idioma que uses. Cómo escribirías un analizador en Haskell es completamente diferente de cómo lo harías en, digamos, C.

• Aquí hay un tutorial que le muestra cómo construir su propio analizador de descenso recursivo .

• Coco es un generador de analizadores para varios idiomas, que también viene con documentación sobre cómo comenzar.

• Si Python es lo tuyo, entonces pyparsing puede ser para ti.

Answer 2

Responderé esto desde una perspectiva general, sin tratar de hablar sobre lectores y analizadores sintácticos.

Un árbol de análisis sintáctico contiene símbolos no terminales que forman parte de una gramática libre de contexto, y muestra la cadena de producciones para obtener una cadena que consta de símbolos de terminal, recursivamente o no. Entonces, cuando tienes el árbol de análisis sintáctico no necesitas la gramática, puedes derivar la gramática del árbol de análisis sintáctico.

Un AST no contiene símbolos no terminales. Solo contiene símbolos.

Ejemplo:

 E
 |
 E + T
 |   |
 T   M * M
 |   |   |
 M   a   b
 |
 a

Que es una versión muy rápida de mostrar a+a*b . Tenga en cuenta que la forma en que se interpreta el árbol de sintaxis abstracta depende de la precedencia del árbol, qué tipo de recorrido se realiza (en orden, preorden, pedido posterior). Esta sería una función general que codificaría en su árbol de búsqueda. Sin embargo, en general, la AST para ese árbol de análisis sintáctico podría verse así:

   +
 |   |
 a   * 
    | |
    a b