Nota: nella mia ignoranza della differenza tra i siti di Programmer vs StackOverflow (che ora conosco), avevo pubblicato questa domanda su StackOverflow in precedenza. Quello che sto cercando è qualche elaborazione, per esempio, sul commento di Gene.
Una volta sono in grado di creare un albero sintattico astratto (AST) per un input, quindi:
-
indipendentemente dal tipo di grammatica usata per costruire l'AST (LR, LL *, o persino nessuna grammatica formale come con Perl 5);
-
indipendentemente dal generatore di parser usato per costruire l'AST (
bison,antlr, o il mio codice scritto a mano); e -
indipendentemente dal numero di passaggi che faccio sul mio input per creare l'AST;
... è vero che posso implementare qualsiasi funzione di qualsiasi lingua mai creata semplicemente visitando il N di AST di volte?
Non sono preoccupato per la complessità del codice risultante, o per le sue prestazioni, ho solo bisogno di sapere se un AST è sufficiente per consentire la costruzione di un traduttore (un compilatore o un interprete) indipendentemente dalla funzione che sono cercando di costruire.
Non sto cercando un elenco completo di ciò che non può essere fatto con un AST, solo un esempio dovrebbe essere sufficiente. Se un AST è una struttura sufficientemente fondamentale (e quindi versatile / potente) per consentire la costruzione di quasi tutti i traduttori, allora mi piacerebbe vedere una conferma di questo fatto. Ottenere la fonte del libro o un URL (se ne esiste uno) sarebbe un bonus aggiuntivo.
Proprio come un AST, essendo un albero, la struttura dei dati sarebbe più potente di (e, quindi, può anche emulare) una rappresentazione intermedia o lineare intermedia (IR) come il Codice a tre indirizzi come trattato nel libro del Drago quindi anche un grafico sintattico astratto ( ASG , se vuoi), essendo un grafico, sarebbe più potente di un AST. Quindi, approfondendo ulteriormente il mio post originale: Esiste qualche caratteristica del traduttore nota all'umanità al momento della stesura di questo documento che non può essere implementata da un AST e richiede l'uso di un ASG?