A árbol de sintaxis concreto coincide con lo que dicen las reglas de la gramática es la sintaxis. El propósito del árbol de sintaxis abstracta es tener una representación "simple" de lo que es esencial en "el árbol de sintaxis".
Un valor real en el AST Mi opinión es que es más pequeño que el CST, y por lo tanto, toma menos tiempo para procesar. (Se podría decir, ¿a quién le importa? Pero yo trabajo con una herramienta donde tenemos ¡decenas de millones de nodos en vivo a la vez!).
La mayoría de los generadores de analizadores sintácticos que tienen algún soporte para compilar sintaxis insisten en que especifiques exactamente cómo se construyen bajo la suposición de que tus nodos de árbol serán "más simples" que el CST (y que, en general, tienen razón, como los programadores son bastante flojos). Podría decirse que significa que debe codificar menos funciones de visitante de árbol, y eso también es valioso, ya que minimiza la energía de ingeniería. Cuando tienes 3500 reglas (por ejemplo, para COBOL), esto importa. Y esta "simplicidad" conduce a la buena propiedad de "pequeñez".
Pero tener tales AST crea un problema que no estaba allí: no coincide con la gramática, y ahora tienes que rastrearlos mentalmente. Y cuando hay 1500 nodos AST para una gramática de reglas 3500, esto importa mucho. Y si la gramática evoluciona (¡siempre lo hacen!), Ahora tienes dos conjuntos gigantes de cosas para sincronizar.
Otra solución es dejar que el analizador simplemente cree nodos CST para usted y solo los use. Esta es una gran ventaja al compilar las gramáticas: no es necesario inventar 1500 nodos AST especiales para modelar reglas de gramática 3500. Solo piense que el árbol es isomorfo a la gramática. Desde el punto de vista del ingeniero de gramática esto es completamente descerebrado, lo que le permite enfocarse en obtener la gramática correcta y piratearla para su contenido. Podría decirse que tiene que escribir más reglas de visitante de nodos, pero eso se puede gestionar. Más sobre esto más tarde.
Lo que hacemos con el DMS Software Reengineering Toolkit es construir automáticamente un CST basado en los resultados de un proceso de análisis (GLR). DMS entonces construye automáticamente una CST "comprimido" por razones de eficiencia del espacio, mediante la eliminación de no-valor que lleva terminales (palabras clave, punteado), producciones unarios semánticamente inútiles, y formando listas para pares de reglas de gramática que son lista como:
L = e ;
L = L e ;
L2 = e2 ;
L2 = L2 ',' e2 ;
y una amplia variedad de variaciones de tales formas. Piensas en términos de las reglas gramaticales y el CST virtual; la herramienta opera en la representación comprimida. Fácil en tu cerebro, más rápido/más pequeño en tiempo de ejecución.
Sorprendentemente, el CST comprimido construido de esta manera se parece mucho a un AST que podría haber diseñado a mano (ver el enlace al final de ejemplos). En particular, la CST comprimida no lleva ningún nodo que sea solo sintaxis concreta. Existen pequeños puntos de incomodidad: por ejemplo, mientras que los nodos concretos para '(' y ')' que se encuentran clásicos en los subgrammares de expresión no están en el árbol, aparece un "nodo de paréntesis" en el CST comprimido y debe ser manejado. Un verdadero AST no tendría esto. Esto parece un precio bastante pequeño para pagar por la conveniencia de no tener que especificar la construcción de AST, nunca. Y la documentación para el árbol está siempre disponible y es correcta: la gramática es la documentación.
¿Cómo evitamos "visitantes adicionales"? No lo hacemos del todo, pero DMS proporciona una biblioteca AST que recorre el AST y maneja las diferencias entre el CST y el AST de forma transparente. DMS también ofrece un evaluador de "gramática de atributos" (AGE), que es un método para pasar valores computados a nodos arriba y abajo del árbol; el AGE maneja todos los problemas de representación de árbol y, por lo tanto, el ingeniero de herramientas solo se preocupa por escribir cálculos de forma efectiva directamente en las reglas de la gramática. Finalmente, DMS también proporciona patrones de "sintaxis de superficie", que permite utilizar fragmentos de código de la gramática para encontrar tipos específicos de subárboles, sin conocer la mayoría de los tipos de nodos involucrados.
Una de las otras respuestas observa que si quieres construir herramientas que puedan regenerar la fuente, tu AST deberá coincidir con la CST. Eso no es realmente correcto, pero es mucho más fácil regenerar la fuente si tiene nodos CST. DMS generates most of the prettyprinter automatically porque tiene acceso a ambos: -}
Conclusión: los AST son buenos para los pequeños, tanto phyiscal como conceptuales. La construcción automatizada de AST del CST proporciona ambos y le permite evitar el problema de rastrear dos conjuntos diferentes.
EDITAR de marzo de 2015: Link to examples of CST vs. "AST" built this way
entonces creamos un AST real en el código? – Joey