Qual é o exemplo mais simples disponível para explicar a diferença entre árvores de análise e árvores de sintaxe abstrata?

Para meu entendimento, um analisador cria uma árvore de análise e a descarta depois. No entanto, ele também pode exibir uma árvore de sintaxe abstrata, da qual o compilador supostamente faz uso.

Tenho a impressão de que a árvore de análise e a árvore de sintaxe abstrata são criadas no estágio de análise. Então alguém poderia explicar por que estas são diferentes?

Uma árvore de análise também é conhecida como árvore de sintaxe concreta.

Basicamente, a árvore abstrata tem menos informações que a árvore concreta. A árvore de concreto contém cada elemento da linguagem, enquanto a árvore abstrata jogou fora as peças desinteressantes.

Por exemplo, a expressão: (2 + 5) * 8

O concreto fica assim

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

Considerando que a árvore abstrata tem:

2  5 
 \/   
  +  8
   \/
   *

Nos casos concretos, os parênteses e todas as partes da linguagem foram incorporadas à árvore. No caso abstrato, os parênteses se foram, porque suas informações foram incorporadas à estrutura da árvore.

A primeira coisa que você precisa entender é que ninguém o obriga a escrever um analisador ou compilador de uma certa maneira. Especificamente, não é necessariamente o caso em que o resultado de um analisador deve ser uma árvore. Pode ser qualquer estrutura de dados adequada para representar a entrada.

Por exemplo, o seguinte idioma:

prog:
      definition 
    | definition ';' prog
    ;

definition: .....

pode ser representado como uma lista de definições. (Nitpickers apontam que uma lista é uma árvore degenerada, mas de qualquer maneira.)

Segundo, não há necessidade de manter a árvore de análise (ou qualquer estrutura de dados que o analisador retornou). Pelo contrário, os compiladores geralmente são construídos como uma sequência de passes, que transformam os resultados do passe anterior. Portanto, o layout geral de um compilador pode ser assim:

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

Bottom Line: Se você ouvir as pessoas falam sobre árvores de análise , árvores Syntac abstratas , árvores de sintaxe concretas etc., sempre substituir pela estrutura de dados adequado para o propósito determinado , e você está bem.