¿Cuál es la diferencia entre un árbol de sintaxis abstracto y un árbol de sintaxis concreto?

He estado leyendo un poco sobre cómo funcionan los intérpretes / compiladores, y un área en la que me confundo es la diferencia entre un AST y un CST. Tengo entendido que el analizador genera un CST, se lo entrega al analizador semántico, que lo convierte en un AST. Sin embargo, tengo entendido que el analizador semántico simplemente garantiza que se sigan las reglas. Realmente no entiendo por qué en realidad haría cambios para hacerlo abstracto en lugar de concreto.

¿Hay algo que me falta sobre el analizador semántico, o la diferencia entre un AST y un CST es algo artificial?

Un árbol de sintaxis concreto representa el texto fuente exactamente en forma analizada. En general, se ajusta a la gramática libre de contexto que define el idioma de origen.

Sin embargo, la gramática y el árbol concretos tienen muchas cosas que son necesarias para hacer que el texto fuente se pueda analizar sin ambigüedades, pero no contribuyen al significado real. Por ejemplo, para implementar la precedencia de operadores, su CFG generalmente tiene varios niveles de componentes de expresión (término, factor, etc.), con los operadores conectándolos en los diferentes niveles (agrega términos para obtener expresiones, los términos se componen de factores opcionalmente multiplicados , etc.). Sin embargo, para interpretar o compilar el lenguaje, no es necesario; solo necesita nodos de expresión que tengan operadores y operandos. El árbol de sintaxis abstracta es el resultado de simplificar el árbol de sintaxis concreto hasta las cosas que realmente se necesitan para representar el significado del programa. Este árbol tiene una definición mucho más simple y, por lo tanto, es más fácil de procesar en las etapas posteriores de ejecución.

Por lo general, no es necesario crear un árbol de sintaxis concreto. Las rutinas de acción en su gramática YACC (o Antlr, o Menhir, o lo que sea ...) pueden construir directamente el árbol de sintaxis abstracta, por lo que el árbol de sintaxis concreto solo existe como una entidad conceptual que representa la estructura de análisis de su texto fuente.

Un árbol de sintaxis concreto coincide con lo que las reglas gramaticales dicen que 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 en mi humilde opinión es que es más pequeño que el CST y, por lo tanto, lleva menos tiempo procesarlo. (Se podría decir, ¿a quién le importa? ¡Pero yo trabajo con una herramienta en la que tenemos decenas de millones de nodos a la vez!).

La mayoría de los generadores de analizadores sintácticos que tienen soporte para construir árboles de sintaxis insisten en que usted personalmente especifique exactamente cómo se construyen bajo el supuesto de que sus nodos de árbol serán "más simples" que el CST (y en eso, generalmente tienen razón, ya que los programadores son bastante perezoso). Podría decirse que significa que tiene que codificar menos funciones de visitantes del árbol, y eso también es valioso porque minimiza la energía de ingeniería. Cuando tiene 3500 reglas (por ejemplo, para COBOL), esto importa. Y esta "sencillez" conduce a la buena propiedad de la "pequeñez".

Pero tener tales AST crea un problema que no existía: no coincide con la gramática, y ahora tienes que rastrear mentalmente a ambos. Y cuando hay 1500 nodos AST para una gramática de 3500 reglas, esto es muy importante. Y si la gramática evoluciona (¡siempre lo hace!), Ahora tienes dos conjuntos gigantes de cosas para mantener sincronizados.

Otra solución es dejar que el analizador simplemente cree nodos CST para usted y simplemente los use. Esta es una gran ventaja al construir las gramáticas: no es necesario inventar 1500 nodos AST especiales para modelar 3500 reglas gramaticales. Basta pensar que el árbol es isomorfo a la gramática. Desde el punto de vista del ingeniero gramatical, esto es completamente estúpido, lo que le permite concentrarse en corregir la gramática y hackearla al contenido de su corazón. Podría decirse que tiene que escribir más reglas de visitantes de nodos, pero eso se puede administrar. Más sobre esto más adelante.

Lo que hacemos con el kit de herramientas de reingeniería de software de DMS es crear automáticamente un CST en función de los resultados de un proceso de análisis (GLR). DMS luego construye automáticamente un CST "comprimido" por razones de eficiencia de espacio, eliminando terminales sin valor (palabras clave, puntuación), producciones unarias semánticamente inútiles y formando listas para pares de reglas gramaticales que se enumeran 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 sobre la representación comprimida. Fácil para tu cerebro, más rápido / más pequeño en tiempo de ejecución.

Sorprendentemente, el CST comprimido construido de esta manera se ve mucho como un AST que podría haber diseñado a mano (vea el enlace al final de los ejemplos). En particular, el CST comprimido no contiene ningún nodo que sea solo una sintaxis concreta. Hay trozos menores de incomodidad: por ejemplo, mientras que los nodos concretos para '(' y ')' se encuentran clásicamente en subgrammars de expresión no están en el árbol, un "paréntesis nodo" no aparecerá en el CST comprimido y tiene que ser manejado. Un verdadero AST no tendría esto. Esto parece un precio bastante pequeño a pagar por la conveniencia de no tener que especificar nunca la construcción AST. Y la documentación del árbol siempre está disponible y es correcta: la gramática es la documentación.

¿Cómo evitamos los "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 calculados a nodos arriba y abajo del árbol; AGE maneja todos los problemas de representación de árboles y, por lo tanto, el ingeniero de herramientas solo se preocupa por escribir cálculos de manera efectiva directamente en las reglas gramaticales. Finalmente, DMS también proporciona patrones de "sintaxis de superficie", lo 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 desea crear herramientas que puedan regenerar la fuente, su AST tendrá que coincidir con el CST. Eso no es realmente correcto, pero es mucho más fácil regenerar la fuente si tiene nodos CST. DMS genera la mayor parte de prettyprinter automáticamente porque tiene acceso a ambos: -}

En pocas palabras: los AST son buenos para los pequeños, tanto físicos como conceptuales. La construcción AST automatizada del CST proporciona ambas cosas y le permite evitar el problema de rastrear dos conjuntos diferentes.

EDITAR marzo de 2015: enlace a ejemplos de CST frente a "AST" construido de esta manera

Esto se basa en la gramática Expression Evaluator de Terrence Parr.

La gramática de este ejemplo:

grammar Expr002;

options 
{
    output=AST;
    ASTLabelType=CommonTree; // type of $stat.tree ref etc...
}

prog    :   ( stat )+ ;

stat    :   expr NEWLINE        -> expr
        |   ID '=' expr NEWLINE -> ^('=' ID expr)
        |   NEWLINE             ->
        ;

expr    :   multExpr (( '+'^ | '-'^ ) multExpr)*
        ; 

multExpr
        :   atom ('*'^ atom)*
        ; 

atom    :   INT 
        |   ID
        |   '('! expr ')'!
        ;

ID      : ('a'..'z' | 'A'..'Z' )+ ;
INT     : '0'..'9'+ ;
NEWLINE : '\r'? '\n' ;
WS      : ( ' ' | '\t' )+ { skip(); } ;

Entrada

x=1
y=2
3*(x+y)

Parse árbol

El árbol de análisis es una representación concreta de la entrada. El árbol de análisis conserva toda la información de la entrada. Las casillas vacías representan espacios en blanco, es decir, el final de la línea.

AST

El AST es una representación abstracta de la entrada. Observe que los parens no están presentes en el AST porque las asociaciones son derivables de la estructura de árbol.

EDITAR

Para obtener una explicación más detallada, consulte Compiladores y generadores de compiladores, pág. 23

Esta publicación de blog puede ser útil.

Me parece que el AST "tira" mucha información gramatical / estructural intermedia que no contribuiría a la semántica. Por ejemplo, no te importa que 3 sea un átomo, sea un término, sea un factor, es a ... Solo te importa que sea 3cuando estás implementando la expresión de potenciación o lo que sea.

El árbol de sintaxis concreto sigue las reglas de la gramática del idioma. En la gramática, las "listas de expresión" se definen normalmente con dos reglas

• expression_list puede ser: expresión
• expression_list puede ser: expression, expression_list

Si se siguen literalmente, estas dos reglas dan forma de peine a cualquier lista de expresiones que aparezca en el programa.

El árbol de sintaxis abstracta tiene la forma que es conveniente para una mayor manipulación. Representa las cosas de una manera que tiene sentido para alguien que comprende el significado de los programas y no solo la forma en que están escritos. La lista de expresiones anterior, que puede ser la lista de argumentos de una función, puede representarse convenientemente como un vector de expresiones, ya que es mejor para el análisis estático tener el número total de expresiones disponibles explícitamente y poder acceder a cada expresión por su índice.

Simplemente, AST solo contiene la semántica del código, Parse tree / CST también incluye información sobre cómo se escribió exactamente el código.

El árbol de sintaxis concreto contiene toda la información como paréntesis superfluos y espacios en blanco y comentarios, el árbol de sintaxis abstracta se abstrae de esta información.

NB: lo suficientemente gracioso, cuando implemente un motor de refactorización, su AST contendrá nuevamente toda la información concreta, pero seguirá refiriéndose a él como AST porque se ha convertido en el término estándar en el campo (por lo que se podría decir que tiene mucho hace perdió su significado original).

Es una diferencia que no marca la diferencia.

Un AST generalmente se explica como una forma de aproximarse a la semántica de una expresión de lenguaje de programación descartando el contenido léxico. Por ejemplo, en una gramática libre de contexto, puede escribir la siguiente regla EBNF

term: atom (('*' | '/') term )*

mientras que en el caso de AST solo usa mul_rule y div_rule que expresa las operaciones aritméticas adecuadas.

¿No se pueden introducir esas reglas en la gramática en primer lugar? Por supuesto. Puede reescribir la regla compacta y abstracta anterior dividiéndola en reglas más concretas que se usan para imitar los nodos AST mencionados:

term: mul_rule | div_rule
mul_rule: atom ('*' term)*
div_rule: atom ('/' term)*

Ahora, cuando piensa en términos de análisis de arriba hacia abajo, el segundo término introduce un FIRST / FIRST conflicto entre mul_rule y div_rule, algo con lo que un analizador LL (1) no puede lidiar. La primera forma de regla fue la versión factorizada a la izquierda de la segunda que efectivamente eliminó la estructura. Tienes que pagar algún premio por usar LL (1) aquí.

Entonces, los AST son un suplemento ad hoc que se usa para corregir las deficiencias de las gramáticas y los analizadores sintácticos. La transformación CST -> AST es un movimiento de refactorización. Nadie se molesta cuando se almacena una coma o dos puntos adicionales en el árbol de sintaxis. Por el contrario, algunos autores los adaptan a AST porque les gusta usar AST para hacer refactorizaciones en lugar de mantener varios árboles al mismo tiempo o escribir un motor de inferencia adicional. Los programadores son vagos por buenas razones. En realidad, almacenan información uniforme de líneas y columnas recopilada por análisis léxico en AST para informar errores. Muy abstracto en verdad.

CST (Concrete Syntax Tree) es una representación de árbol de la gramática (reglas de cómo se debe escribir el programa). Dependiendo de la arquitectura del compilador, el analizador puede utilizarlo para producir un AST.

AST (Abstract Syntax Tree) es una representación de árbol de la fuente Parsed, producida por la parte Parser del compilador. Almacena información sobre tokens + gramática.

Dependiendo de la arquitectura de su compilador, el CST puede usarse para producir un AST. Es justo decir que CST evoluciona a AST. O AST es un CST más rico.

Se pueden encontrar más explicaciones en este enlace: http://eli.thegreenplace.net/2009/02/16/abstract-vs-concrete-syntax-trees#id6