¿Qué es un árbol sintáctico abstracto/¿Es necesario?

Question

He estado interesado en el diseño/implementación de compiladores/intérpretes durante todo el tiempo que he estado programando (solo 5 años) y siempre me ha parecido la "magia" detrás de escena de la que nadie habla realmente (lo sé de al menos 2 foros para el desarrollo de sistemas operativos, pero no conozco ninguna comunidad para el desarrollo de compiladores/intérpretes/idiomas). De todos modos, recientemente decidí comenzar a trabajar por mi cuenta, con la esperanza de ampliar mi conocimiento de la programación en general (y bueno, es muy divertido :). Entonces, basado en la limitada cantidad de material de lectura que tengo, y Wikipedia, desarrollé este concepto de los componentes para un compilador/intérprete:

Código fuente -> Análisis léxico -> Árbol de sintaxis abstracto -> Análisis sintáctico -> Análisis semántico -> Generación de código -> Código ejecutable.

(sé que hay más a la generación de código y el código ejecutable, pero no he llegado tan lejos :)

Y con ese conocimiento, he creado un léxico muy básico (en Java) para tomar entrada de un archivo de origen, y la salida de los tokens en otro archivo. Un ejemplo de entrada/salida se vería así:

de entrada:

int a := 2 
if(a = 3) then 
    print "Yay!" 
endif 

de salida (de léxico):

INTEGER 
A 
ASSIGN 
2 
IF 
L_PAR 
A 
COMP 
3 
R_PAR 
THEN 
PRINT 
YAY! 
ENDIF 

En lo personal, creo que sería muy fácil ir desde allí a el análisis sintáctico/semántico, y posiblemente incluso la generación de código, lo que me lleva a preguntar: ¿Por qué usar un AST, cuando parece que mi lexer está haciendo un trabajo tan bueno? Sin embargo, el 100% de mis fuentes que utilizo para investigar este tema parecen inflexibles de que esta es una parte necesaria de cualquier compilador/intérprete. ¿Me estoy perdiendo el sentido de lo que realmente es un AST (un árbol que muestra el flujo lógico de un programa)?

TL; DR: Actualmente en camino a desarrollar un compilador, terminé el lexer, me parece que la salida facilitaría el análisis sintáctico/el análisis semántico, en lugar de hacer un AST. Entonces, ¿por qué usar uno? ¿Me estoy perdiendo el punto de uno?

Gracias!

Answer 1

En primer lugar, una cosa sobre su lista de componentes no tiene sentido. Crear un AST es (más o menos) el análisis sintáctico, por lo que no debería estar allí, o al menos venir antes de AST.

Lo que tienes allí es un lexer. Todo lo que te da son tokens individuales. En cualquier caso, necesitará un analizador real, porque los lenguajes regulares no son divertidos de programar. No puede anidar (correctamente) las expresiones. Diablos, ni siquiera puedes manejar la precedencia del operador. Una secuencia de token no le ofrece:

1. Una idea donde las declaraciones y expresiones comienzan y terminan.
2. Una idea de cómo las declaraciones se agrupan en bloques.
3. Una idea Qué parte de la expresión tiene qué precedencia, asociatividad, etc.
4. Una vista despejada y despejada de la estructura real del programa.
5. Una estructura que se puede pasar a través de innumerables transformaciones, sin que cada pasada conozca y que tenga el código para acomodar que la condición en un if esté encerrada entre paréntesis.
6. ... en general, cualquier tipo de comprensión por encima del nivel de un solo token.

Suponga que tiene dos pases en su compilador que optimicen ciertos tipos de operadores se aplica a ciertos argumentos (digamos, de constantes y simplificaciones algebraicas como x - x -> 0). Si les entrega tokens para la expresión x - x * 1, estos pasos están desordenados al darse cuenta de que la parte x * 1 es lo primero. Y ellos tienen para saber eso, no sea que la transformación sea incorrecta (considere 1 + 2 * 3).

Estas cosas son lo suficientemente difíciles como para solucionarlo, por lo que no querrá ser molestado por los problemas de análisis también. Es por eso que resuelve el problema de análisis primero, en un paso de análisis separado. Luego puede, por ejemplo, reemplazar una llamada a función con su definición, sin preocuparse por agregar paréntesis, por lo que el significado sigue siendo el mismo. Ahorra tiempo, separa las preocupaciones, evita la repetición, habilita el código más simple en muchos otros lugares, etc.

Un analizador lo resuelve y crea un AST que contiene toda esa información. Sin más datos sobre los nodos, la forma del AST solo le da no. 1, 2, 3 y mucho más, gratis. Ninguno de los pasos de bazillion que siguen tienen que preocuparse más por eso.

Eso no quiere decir que siempre tenga que tener un AST. Para lenguajes suficientemente simples, puede hacer un compilador de un solo pase. En lugar de generar un AST u otra representación intermedia durante el análisis, emite código sobre la marcha. Sin embargo, esto se vuelve más difícil para los lenguajes menos simples y no es razonable hacer muchas cosas (como el 70% de todas las optimizaciones y diagnósticos, y sí, acabo de hacer ese número). En general, no te aconsejaría que hagas esto. Hay buenas razones para que los compiladores de un solo paso estén casi muertos. Incluso los idiomas que lo permiten (por ejemplo, C) se implementan actualmente con múltiples pases y AST. Es una forma simple de comenzar, pero lo limitará severamente (y el lenguaje, si lo diseña) más adelante.

Answer 2

Tiene el AST en el punto incorrecto de su diagrama de flujo. Típicamente, la salida del lexer es una serie de tokens (como lo tiene en su salida), y estos se alimentan al analizador sintáctico/sintáctico, que genera el AST. Por lo tanto, el resultado de su lexer es diferente de un AST porque se usan en diferentes puntos del proceso de compilación y cumplen diferentes propósitos.

La siguiente pregunta lógica es: ¿Qué es, entonces, un AST? Bueno, el propósito del análisis sintáctico/sintáctico es convertir la serie de tokens generados por el lexer en un AST (o árbol de análisis sintáctico). El AST es una representación intermedia que captura la relación entre elementos sintácticos de una manera que es más fácil trabajar con programación. Una forma de pensar sobre esto es que un programa de texto es una construcción unidimensional y solo puede representar ideas como una secuencia de elementos, mientras que el AST se libera de esta restricción y puede representar las relaciones subyacentes entre esos elementos en 2 dimensiones (como típicamente se dibuja), o cualquier espacio de dimensión superior si así lo eliges para pensar de esa manera.

Por ejemplo, un operador binario tiene dos operandos, llamémoslos A y B. En el código, esto se puede deletrear 'A * B' (asumiendo un operador infijo - otra ventaja de un AST es ocultar tales distinciones que puede ser importante sintácticamente, pero no semánticamente), pero para que el compilador "entienda" esta expresión, debe leer 5 caracteres secuencialmente, y esta lógica puede volverse engorrosa rápidamente, dadas las muchas posibilidades incluso en un lenguaje pequeño. En una representación AST, sin embargo, tenemos un nodo "operador binario" cuyo valor es '*', y ese nodo tiene dos hijos, valores 'A' y 'B'.

A medida que avance su proyecto de compilación, creo que comenzará a ver las ventajas de esta representación.