Cómo construir un árbol de sintaxis abstracta
Tengo una idea general de lo que es un AST, pero quiero saber cómo construir uno.
Si se te da una gramática y un árbol de análisis, ¿cómo construyes el AST?
¿Cómo se hace si se le da una gramática y una expresión?
2 answers
Bueno, en primer lugar, la gramática se utiliza para construir un árbol de análisis a partir de una expresión. Así que si ya tienes un árbol de análisis, no necesitas la gramática.
Dependiendo de cuánto trabajo haga su analizador, el árbol resultante que se forma al analizar una expresión podría ser ya un árbol de sintaxis abstracta. O podría ser un simple árbol de análisis que requiere una segunda pasada para construir el ast.
Para construir el árbol de análisis a partir de una gramática y una expresión, primero tendría que convierte tu gramática en código de trabajo. Normalmente, dividiría el trabajo en un tokenizador que divide el flujo 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.
Así que 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 real del texto. El segundo representa el tipo de token. Estos tokens se introducen en el analizador sintáctico, que se construye a partir de su gramática y reconoce los tokens y construye el árbol de análisis.
Entonces, ¿cómo se escribe el tokenizador léxico y el analizador sintáctico real? Podrías rodar el tuyo a mano. O, más comúnmente, use un generador de analizador como coco o antlr o lex / yacc. Estas herramientas toman una descripción de su gramática y generan el código para un tokenzier y un analizador sintáctico. (Los generadores de código existen para los lenguajes más populares y algunos impopulares también.)
Cómo construir su analizador depende en gran medida de lo que el lenguaje que usas. 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 te muestra cómo construir tu propio recursivo descent parser .
Coco es un generador de parser para varios lenguajes, que también viene con documentación sobre cómo empezar.
Si Python es lo tuyo, entonces pyparsing tal vez para ti.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-10-04 13:58:29
Responderé esto desde una perspectiva general, sin tratar de hablar de lexers y analizadores.
Un árbol de análisis contiene símbolos no terminales que son parte de una gramática libre de contexto, y muestran la cadena de producciones para obtener una cadena que consiste en símbolos terminales, ya sea recursivamente o no. Así que cuando tienes el árbol de análisis no necesitas la gramática - puedes derivar la gramática del árbol de análisis.
Un AST no contiene símbolos no terminales. Solo contiene simbolo.
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, el tipo de recorrido que haga (en orden, pre-orden, post-orden) Esta sería una función general que codifique en su árbol de búsqueda. Sin embargo, en general, el AST para ese árbol de análisis podría verse así:
+
| |
a *
| |
a b
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-01-24 19:20:22