¿Cuál es el ejemplo más simple que existe para explicar la diferencia entre Parse Trees y Abstract Syntax Trees?

14

A mi entender, un analizador crea un árbol de análisis y luego lo descarta. Sin embargo, también puede mostrar un árbol de sintaxis abstracta, que el compilador supuestamente hace uso.

Tengo la impresión de que tanto el árbol de análisis como el de sintaxis abstracta se crean en la etapa de análisis. Entonces, ¿podría alguien explicar por qué estos son diferentes?

    
pregunta Combinator Logic 06.02.2012 - 04:06

2 respuestas

20

Un árbol de análisis también se conoce como un árbol de sintaxis concreto.

Básicamente, el árbol abstracto tiene menos información que el árbol concreto. El árbol concreto contiene cada elemento en el lenguaje, mientras que el árbol abstracto ha tirado las piezas sin interés.

Por ejemplo, la expresión: (2 + 5) * 8

El concreto se ve así

  ( 2  + 5 )  * 8
  |  \ | / |  | |
  |   \|/  |  | |
   \___|__/   | |
       \______|/

Mientras que el árbol abstracto tiene:

2  5 
 \/   
  +  8
   \/
   *

En los casos concretos, los paréntesis y todas las partes del lenguaje se han incorporado al árbol. En el caso abstracto, los paréntesis han desaparecido porque su información se ha incorporado a la estructura de árbol.

    
respondido por el Winston Ewert 06.02.2012 - 05:43
0

Lo primero que debes comprender es que nadie te obliga a escribir un analizador o compilador de cierta manera. Específicamente, no es necesariamente el caso de que el resultado de un analizador deba ser un árbol. Puede ser cualquier estructura de datos que sea adecuada para representar la entrada.

Por ejemplo, el siguiente idioma:

prog:
      definition 
    | definition ';' prog
    ;

definition: .....

se puede representar como una lista de definiciones. (Nitpickers señalará que una lista es un árbol degenerado, pero de todos modos.)

Segundo, no es necesario mantener el árbol de análisis (o la estructura de datos que haya devuelto el analizador). Por el contrario, los compiladores generalmente se construyen como una secuencia de pases, que transforman los resultados del pase anterior. Por lo tanto, el diseño general de un compilador podría ser así:

parser :: String             -> Maybe [Definitions]      -- parser
pass1  :: [Definitions]      -> Maybe DesugaredProg      -- desugarer
pass2  :: DesugaredProg      -> Maybe TypedProg          -- type checker
pass3  :: TypedProg          -> Maybe AbstractTargetLang -- code generation
pass4  :: AbstractTargetLang -> Maybe String             -- pretty printer

compiler :: String           -> Maybe String    -- transform source code to target code
compiler source = do
   defs  <- parser source
   desug <- pass1 defs
   typed <- pass2 desug
   targt <- pass3 typed
   pass4 targt

Conclusión: si escucha a la gente hablar sobre analizar árboles , árboles abstractos sintácticos , árboles concretos de sintaxis , etc., siempre sustitúyalos por < em> estructura de datos adecuada para el propósito dado , y usted está bien.

    
respondido por el Ingo 20.02.2014 - 14:04

Lea otras preguntas en las etiquetas