¿Cuál es el ejemplo más simple para explicar la diferencia entre los árboles Parse y los árboles de sintaxis abstracta?

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 supuestamente utiliza el compilador.

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

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

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 desechado las piezas poco interesantes.

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.

Lo primero que debes entender es que nadie te obliga a escribir un analizador o compilador de cierta manera. Específicamente, no es necesariamente el caso que el resultado de un analizador debe 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).

En segundo lugar, no es necesario retener el árbol de análisis (o cualquier estructura de datos que haya devuelto el analizador). Por el contrario, los compiladores generalmente se construyen como una secuencia de pasadas, que transforman los resultados de la pasada 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 se oye hablar de árboles de análisis sintáctico , árboles abstractos Syntac , los árboles de sintaxis concretas etc., siempre sustituyen por estructura de datos adecuada para el propósito dado , y ya está bien.