Elegante modello AST

Question

Sono in procinto di scrivere un compilatore di giocattoli in scala. La lingua di destinazione stessa sembra scala, ma è un campo aperto per l'esperimento.

Dopo diversi grandi refactoring non riesco a trovare un buon modo per modellare il mio albero di sintassi astratto. Mi piacerebbe utilizzare le funzionalità di corrispondenza dello schema di scala, il problema è che l'albero trasporta informazioni mobili (come tipi, simboli) lungo il processo di compilazione.

riesco a vedere un paio di soluzioni, nessuna delle quali mi piace:

• classi case con i campi mutabili (credo che il compilatore Scala fa questo): il problema è che questi campi non sono presenti un ogni fase della compilation e quindi deve essere annullata (o Option'd) e diventa davvero pesante per il debug/write code. Inoltre, se per esempio, trovo un nodo di tipo null dopo la fase di digitazione, ho davvero difficoltà a trovare la causa del bug.

• enorme gerarchia trait/caso classe: qualcosa come Node, NodeWithSymbol, NodeWithType, ... sembra un dolore per scrivere e lavorare con

• qualcosa di completamente lavorato a mano con estrattori

Non sono nemmeno sicuro se sia una buona pratica andare con un AST completamente immutabile, specialmente in scala dove non c'è una condivisione implicita (perché il compilatore non è consapevole dell'immutabilità) e potrebbe danneggiare le prestazioni per copiare l'albero tutto il tempo .

Riesci a pensare a un modello elegante per modellare il mio albero utilizzando il potente sistema di tipi di scala?

Answer 1

Recentemente ho iniziato a scrivere un verificatore di giocattoli per una lingua piccola e sto utilizzando la libreria Kiama per le fasi di parser, resolver e type checker.

Kiama è una libreria Scala per l'elaborazione del linguaggio. Consente un'analisi e una trasformazione convenienti dei dati strutturati. Gli stili di programmazione supportati dalla libreria sono basati su noti paradigmi di elaborazione del linguaggio formale, tra cui attribute grammars, tree rewriting, abstract state machines e pretty printing.

Cercherò di riassumere la mia esperienza (abbastanza limitata):

• [+] Kiama viene fornito con diversi esempi, e il principale collaboratore di solito risponde rapidamente alle domande sulla mailing list

• [+] Il paradigma attributo grammatica permette per una bella separazione in "componenti immutabili" dei nodi, ad esempio, i nomi e le sotto-nodi, e "componenti mutevoli", ad esempio, il tipo di informazione

• [+] La libreria viene fornita con un sistema di riscrittura versatile che - finora - copriva tutti i miei casi d'uso

• [+] La libreria, ad es., La stampante piuttosto, fare delle belle esempi di DSL e di varie funzionali modelli/approcci/idee

• [-] La curva di apprendimento è decisamente ripida, anche con esempi e la lista a portata di mano

• [- ] L'implementazione della fase di risoluzione in uno stile "puramente funzionale" (vedere my question) sembra complicata, ma un approccio ibrido (che non ho ancora provato) sembra essere possibile

• [-] Il paradigma della grammatica degli attributi e la risultante separazione delle preoccupazioni non rende ovvio come documentare le proprietà dei nodi alla fine (my question)

• [-] Si dice, che il paradigma attributo di grammatica non produce più veloci implementazioni

Riassumendo la mia sintesi, mi piace utilizzare Kiama molto e vi consiglio vivamente di fare un tentativo , o almeno dare un'occhiata agli esempi.

(PS Io non sono affiliato con Kiama.)

Answer 2

TL; DR preferisco mantenere l'AST immutabile e portare le cose come le informazioni di tipo in una struttura separata, per esempio una mappa, che può essere indirizzata dagli ID memorizzati nell'AST. Ma non c'è una risposta perfetta.

Non sei affatto il primo a lottare con questa domanda. Consentimi di elencare alcune opzioni:

1) Strutture mutevoli che vengono aggiornate in ogni fase. Tutti gli aspetti negativi che menzioni.

2) Tratti/motivo a torta. Fattibile, ma costoso (non c'è condivisione) e un pò brutto.

3) Un nuovo tipo di albero in ciascuna fase. In un certo senso questo è teoricamente più pulito. Ogni fase può trattare solo con una struttura prodotta per la fase precedente. Inoltre, lo stesso approccio si estende dal front end al back end. Ad esempio, potresti "desugar" ad un certo punto e avere un nuovo tipo di albero significa che le fasi a valle non devono nemmeno prendere in considerazione la possibilità di tipi di nodi che vengono eliminati dal desugaring. Inoltre, le ottimizzazioni a basso livello di solito richiedono IR che sono significativamente inferiori rispetto all'AST originale. Ma questo è anche un sacco di codice poiché quasi ogni cosa deve essere ricreata ad ogni passaggio. Questo approccio può anche essere lento poiché non vi può essere quasi nessuna condivisione di dati tra le fasi.

4) Etichettare ogni nodo nell'AST con un ID e utilizzare tale ID per fare riferimento alle informazioni in altre strutture di dati (mappe e vettori e tali) che contengono informazioni calcolate per ciascuna fase. In molti modi questo è il mio preferito. Mantiene l'immutabilità, massimizza la condivisione e minimizza il codice "in eccesso" che devi scrivere. Ma devi ancora gestire il potenziale di informazioni "mancanti" che possono essere complicate per il debug. Inoltre, non è veloce quanto l'opzione mutabile, sebbene sia più veloce di qualsiasi opzione che richiede la produzione di un nuovo albero in ogni fase.