parsing - que - arbol sintactico compiladores

¿Cuál es la diferencia entre un árbol de sintaxis abstracta y un árbol de sintaxis concreta?

Question

He estado leyendo un poco acerca de 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 realiza una CST, la pasa al analizador semántico y la convierte en AST. Sin embargo, tengo entendido que el analizador semántico simplemente asegura que se sigan las reglas. Realmente no entiendo por qué haría ningún cambio para hacerlo abstracto en lugar de concreto.

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

Answer 1

AST es una versión simplificada de CST. Ambos pueden ser construidos por tu analizador. En caso de que alguien necesite una explicación clara: http://eli.thegreenplace.net/2009/02/16/abstract-vs-concrete-syntax-trees#id6

Answer 2

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

NB: bastante gracioso, cuando implementes un motor de refactorización, tu AST volverá a contener toda la información concreta, pero seguirás refiriéndote a ella como AST porque ese es el término estándar en el campo (por lo que se podría decir que tiene un largo Hace tiempo perdió su significado original).

Answer 3

El árbol sintáctico concreto sigue las reglas de la gramática del lenguaje. En la gramática, las "listas de expresiones" generalmente se definen con dos reglas

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

Seguido literalmente, estas dos reglas dan una forma de peine a cualquier lista de expresiones que aparece en el programa.

El árbol sintáctico abstracto está en 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, se puede representar convenientemente como un vector de expresiones, ya que es mejor para el análisis estático tener el número total de expresiones explícitamente disponibles y poder acceder a cada expresión por su índice.

Answer 4

Es una diferencia que no hace la diferencia.

Una AST generalmente se explica como una forma de aproximar 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 AST solo usas mul_rule y div_rule que expresa las operaciones aritméticas apropiadas.

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

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

Ahora, cuando piensas en términos de análisis de arriba hacia abajo, el segundo término introduce un conflicto PRIMERO / PRIMERO entre mul_rule y div_rule algo que un analizador de LL (1) no puede manejar. La primera forma de regla fue la versión factorizada de la izquierda del segundo que eliminó la estructura de manera efectiva. Tienes que pagar un premio por usar LL (1) aquí.

Por lo tanto, los AST son un complemento ad hoc utilizado para corregir las deficiencias de gramáticas y analizadores sintácticos. La transformación CST -> AST es un movimiento de refactorización. Nadie se molestó 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 flojos por buenas razones. En realidad, almacenan incluso la información de línea y columna recopilada por análisis léxico en AST para el informe de errores. Muy abstracto de hecho.

Answer 5

Esto se basa en la gramática Evaluador de expresiones de Terrence Parr.

La gramática para 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)

Árbol Parse

El árbol de análisis sintáctico es una representación concreta de la entrada. El árbol de análisis conserva toda la información de la entrada. Los cuadros vacíos 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 del árbol.

EDITAR

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

Answer 6

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

Answer 7

Un árbol sintáctico 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 concreta y el árbol tienen muchas cosas que son necesarias para hacer que el texto fuente sea legible de forma inequívoca, pero no contribuyen al significado real. Por ejemplo, para implementar la precedencia del operador, su CFG generalmente tiene varios niveles de componentes de expresión (término, factor, etc.), con los operadores conectándolos en los diferentes niveles (agregue términos para obtener expresiones, los términos se componen de factores opcionalmente multiplicados) , etc.) Sin embargo, para interpretar o compilar el idioma, no lo necesita; solo necesita nodos de Expresión que tengan operadores y operandos. El árbol de sintaxis abstracta es el resultado de simplificar el árbol sintáctico concreto hasta llegar a las cosas realmente necesarias 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 sintáctico abstracto, por lo que el árbol sintáctico concreto solo existe como una entidad conceptual que representa la estructura analítica de su texto fuente.

Answer 8

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

La mayoría de los generadores de analizadores que tienen soporte para construir árboles sintácticos 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 en eso, en general son correctos, ya que los programadores son bonitos perezoso). 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 seguir mentalmente a ambos. 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 permitir que el analizador simplemente cree nodos CST para usted y simplemente 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 DMS Software Reengineering Toolkit es construir automáticamente un CST basado en 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 que no tienen valor (palabras clave, punctación), producciones unarias semánticamente inútiles y listas de formación para los pares de reglas gramaticales que se enumeran a continuación:

    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. Hay pequeños detalles de incomodidad: por ejemplo, mientras que los nodos concretos para ''('' y '')'' encontrados de forma clásica en los subgrammares de expresión no están en el árbol, aparece un "nodo paréntesis" en el CST comprimido y debe manejarse. 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 desea construir herramientas que puedan regenerar la fuente, su AST tendrá que coincidir con la CST. Eso no es realmente correcto, pero es mucho más fácil regenerar la fuente si tiene nodos CST. DMS genera la mayoría de las impresoras bonitas automáticamente porque tiene acceso a ambas: -}

En pocas palabras: 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 Marzo 2015: Enlace a ejemplos de CST vs. "AST" construidos de esta manera

Answer 9

Esta publicación de blog puede ser útil.

Me parece que el AST "arroja" una gran cantidad de información gramatical / estructural intermedia que no contribuiría a la semántica. Por ejemplo, no te importa que 3 sea un átomo, es un término, un factor es un .... Simplemente te importa que sea 3 cuando implementes la expresión de exponenciación o lo que sea.