A mio parere, un parser crea un albero di analisi, quindi lo elimina in seguito. Tuttavia, può anche estrarre un albero di sintassi astratto, che il compilatore presumibilmente usa.
Ho l'impressione che sia l'albero di analisi che l'albero di sintassi astratto vengano creati nella fase di analisi. Allora qualcuno potrebbe spiegare perché sono diversi?
Un albero di analisi è anche conosciuto come un albero di sintassi concreto.
In sostanza, l'albero astratto ha meno informazioni dell'albero in calcestruzzo. L'albero di cemento contiene ogni elemento nella lingua, mentre l'albero astratto ha gettato via i pezzi non interessanti.
Ad esempio l'espressione: (2 + 5) * 8
Il calcestruzzo sembra così
( 2 + 5 ) * 8
| \ | / | | |
| \|/ | | |
\___|__/ | |
\______|/
Mentre l'albero astratto ha:
2 5
\/
+ 8
\/
*
Nei casi concreti le parentesi e tutti i pezzi della lingua sono stati incorporati nell'albero. Nel caso astratto le parentesi sono sparite, perché le loro informazioni sono state incorporate nella struttura ad albero.
La prima cosa che devi capire è che nessuno ti obbliga a scrivere un parser o un compilatore in un certo modo. Nello specifico, non è necessariamente il caso che il risultato di un parser debba essere un albero. Può essere una qualsiasi struttura dati adatta a rappresentare l'input.
Ad esempio, la seguente lingua:
prog:
definition
| definition ';' prog
;
definition: .....
può essere rappresentato come una lista di definizioni. (Nitpickers farà notare che una lista è un albero degenerato, ma comunque.)
In secondo luogo, non è necessario mantenere l'albero di analisi (o qualsiasi altra struttura dati restituita dal parser). Al contrario, i compilatori di solito sono costruiti come una sequenza di passaggi, che trasformano i risultati del passaggio precedente. Quindi il layout generale di un compilatore potrebbe essere così:
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 senti gente parlare di parse trees , alberi syntac astratti , alberi di sintassi concreti ecc., sostituisci sempre < em> struttura dati adatta allo scopo , e stai bene.