Cómo convertir una secuencia de tokens en un árbol de análisis [cerrado]

Question

Tengo un lexer construido que transmite tokens desde la entrada, pero no estoy seguro de cómo construir el siguiente paso en el proceso: el árbol de análisis. ¿Alguien tiene buenos recursos o ejemplos sobre cómo lograr esto?

Answer 1

Realmente recomendaría http://www.antlr.org/ y, por supuesto, el clásico Dragón Libro de compiladores.

Para un lenguaje fácil como JavaScript, no es difícil manejar a mano un analizador de descenso recursivo, pero casi siempre es más fácil usar una herramienta como yacc o antlr.

Creo que para volver a lo básico de tu pregunta, realmente quieres estudiar la sintaxis gramatical de BNF-esque y elegir una sintaxis para tu objetivo. Si tiene eso, el árbol de análisis debería caerse, siendo la manifestación de 'instancia' de esa gramática.

Además, no intente convertir la creación de su árbol de análisis en su solución final (como generar código o lo que no). Puede parecer factible y más eficiente; pero invariablemente llegará un momento en el que realmente desearías tener ese árbol de análisis "tal como está" por ahí.

Answer 2

Debe investigar las herramientas del generador de analizadores para su plataforma. Un generador de analizador le permite especificar una gramática libre de contexto para su idioma. El lenguaje consta de una serie de reglas que "reducen" Una serie de símbolos en un nuevo símbolo. Por lo general, también puede especificar la precedencia y la asociatividad para diferentes reglas para eliminar la ambigüedad en el lenguaje. Por ejemplo, un lenguaje de calculadora muy simple podría verse así:

%left PLUS, MINUS           # low precedence, evaluated left-to-right
%left TIMES, DIV            # high precedence, left-to-right

expr ::= INT
| expr PLUS expr
| expr MINUS expr
| expr TIMES expr
| expr DIV expr
| LEFT_PAREN expr RIGHT_PAREN

Generalmente, puede asociar un bit de código con cada regla para construir un nuevo valor (en este caso, una expresión) a partir de los otros símbolos de esa regla. El generador de analizadores asimilará la gramática y producirá código en su idioma que traduce una secuencia de tokens a un árbol de análisis.

La mayoría de los generadores de analizadores son específicos del idioma. ANTLR es bien conocido y es compatible con C, C ++, Objective C, Java y Python. Sin embargo, he oído que es difícil de usar. He usado bison para C / C ++, CUP para Java y ocamlyacc para OCaml, y todos son bastante buenos. Si ya está utilizando un generador de lexer, debe buscar un generador de analizador que sea específicamente compatible con él.

Answer 3

Creo que un enfoque común es utilizar una Máquina de estado finito . Por ejemplo, si lee un operando, entra en un estado en el que espera un operador, y generalmente lo utiliza como nodo raíz para los operandos, etc.

Answer 4

Según lo descrito anteriormente por Marcos Marin, una máquina de estado que usa las reglas de su idioma en BNF para analizar su lista de tokens hará el truco si desea hacerlo usted mismo. Solo, como se dijo en el comentario anterior de Paul Hollingsworth, la forma más fácil es usar un Pushdown-Automaton que tiene una pila de memoria FiFo simple. Cada clase de token tiene un próximo token esperado en su gramática, que también está representado en su máquina de estado. La pila se usa para "recordar" cuál era la clase de token anterior, para reducir los estados requeridos (podría hacerse sin pila, pero necesitaría un nuevo estado para cada clase y subclase dividida en el árbol de gramática). Los estados de aceptación serían (en lenguajes naturales y la mayoría de los lenguajes de programación también) el estado inicial, y tal vez algún otro estado en casos particulares.

Antlr sería mi sugerencia si desea utilizar una herramienta (mucho más rápida y menos extensa). ¡Buena suerte!