Quel est l'exemple le plus simple pour expliquer la différence entre les arbres d'analyse et les arbres de syntaxe abstraite?

À ma connaissance, un analyseur crée un arbre d'analyse, puis le supprime par la suite. Cependant, il peut également faire apparaître un arbre de syntaxe abstraite, que le compilateur utilise censément.

J'ai l'impression que l'arbre d'analyse et l'arbre de syntaxe abstraite sont créés sous l'étape d'analyse. Quelqu'un pourrait-il alors expliquer pourquoi ces éléments sont différents?

Un arbre d'analyse est également appelé arbre de syntaxe concret.

Fondamentalement, l'arbre abstrait a moins d'informations que l'arbre concret. L'arbre concret contient chaque élément de la langue, tandis que l'arbre abstrait a jeté les morceaux sans intérêt.

Par exemple l'expression: (2 + 5) * 8

Le béton ressemble à ceci

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

Alors que l'arbre abstrait a:

2  5 
 \/   
  +  8
   \/
   *

Dans les cas concrets, les parenthèses et toutes les parties du langage ont été incorporées dans l'arbre. Dans le cas abstrait, les parenthèses ont disparu, car leurs informations ont été incorporées dans la structure arborescente.

La première chose que vous devez comprendre est que personne ne vous oblige à écrire un analyseur ou un compilateur d'une certaine manière. Plus précisément, il n'est pas nécessairement vrai que le résultat d'un analyseur doit être un arbre. Il peut s'agir de n'importe quelle structure de données appropriée pour représenter l'entrée.

Par exemple, la langue suivante:

prog:
      definition 
    | definition ';' prog
    ;

definition: .....

peut être représenté comme une liste de définitions. (Nitpickers indiquera qu'une liste est un arbre dégénéré, mais de toute façon.)

Deuxièmement, il n'est pas nécessaire de conserver l'arbre d'analyse (ou la structure de données retournée par l'analyseur). Au contraire, les compilateurs sont généralement construits comme une séquence de passes, qui transforment les résultats de la passe précédente. Par conséquent, la présentation globale d'un compilateur pourrait être la suivante:

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: Si vous entendez les gens parler des arbres parse , arbres abstraits Syntac , arbres syntaxiques en béton , etc., toujours remplacer par la structure de données adaptées à l'objectif donné , et vous êtes bien.