Rappresenta un pass multiplo Abstract Syntax Tree (AST) in C++?

Question

Attualmente sto esplorando la progettazione di un compilatore che trasforma AST in più fasi. L'idea è che partendo dall'albero di analisi, ogni passaggio trasforma l'albero finché l'AST risultante è ottimizzato e contiene tutte le informazioni richieste in ciascun nodo dell'albero richiesto per generare il codice intermedio (in questo caso LLVM IR). Un passaggio sull'albero può modificare considerevolmente la sua struttura, ad esempio modificando un elenco di operatori e operandi in una gerarchia di operazioni ordinate tramite operator precedence parsing. Si noti che un passaggio può lasciare parti della struttura del tutto invariate.

Quindi, la mia domanda è: come posso fare meglio (leggi: più facilmente, con la minore ripetizione possibile) rappresentare un AST che ha più rappresentazioni intermedie in C++? Vorrei che i tipi di nodi della versione di AST di ciascuna fase rispettassero la loro incompatibilità al momento della compilazione. Credo che il problema chiave sia come dovrei rappresentare parti della struttura che non cambiano tra passaggi evitando il codice ripetitivo? Immagino che questo sia un problema risolto molte volte in passato da autori di compilatori.

Nota che attualmente sto usando Boost Variant invece del normale polimorfismo di runtime nel mio AST e vorrei che anche una soluzione fosse compatibile con esso.

Answer 1

Questo è un attacco rapido basato su AST di tipo sicuro boost::variant.

Ho incluso una semplice "struttura che preserva la trasformazione" che cambia semplicemente il tipo di dati memorizzati in ciascun nodo AST. In teoria, tuttavia, è possibile scrivere un arbitrario astFunc che esegue entrambi una trasformazione strutturale e basata sui dati dei nodi: è sufficiente scrivere uno type_list che contenga i tipi validi in ogni nodo prima e dopo.

Ora questo è solo un inizio.

Si potrebbe andare oltre, e ogni tipo di nodo ha un diverso insieme di tipi di bambini, o anche un numero diverso. È sufficiente creare classi di tratti per ciascun tipo di nodo come il mio data_type, ad esempio children_types. Quindi utilizzare una tecnica simile a come ho definito Var per definire il tipo di bambini. Fondamentalmente, si dispone di un variant di std::vector< AST_Node<ChildType<type_list_element>>> tramite un concatenamento di MapTypes. Diamine, puoi unire il std::vector di bambini e lo data insieme in una variante.

Questo permetterebbe di scrivere una mappatura per un individuo AST_Node tipo (che rende ad un altro tipo AST_Node), tutti insieme aggregare e generare un funtore AST_Node<before, after> che avrebbe poi a piedi sopra l'albero. Alcuni dei funtori opererebbero solo sui dati, quindi lasceranno che la logica genitore prenda il sopravvento sui bambini, alcuni trasformerebbero interi sottoalberi, alcuni opererebbero sui dati e impedirebbero alla logica genitrice di passare sopra ai bambini.

Questa tecnica è complicata, perché devi sintetizzare i visitatori della variante boost dalle tue singole funzioni in un modo che non richiede di accumularli tutti insieme. Se guardi il numero here vedrai alcune tecniche su come prendere un mazzo di std::function<T(U)> e trasformarle in un unico functor che prende uno qualsiasi dell'unione di U. Toss in qualche lavoro per calcolare l'unione dei tipi di ritorno (un semplice type_list con tipi duplicati rimossi, quindi pompati in un boost::variant, potrebbe farlo) - un tale "funtore unito" sarebbe un visitatore valido.

E ora è possibile scrivere i funtori "rimappa un nodo AST di tipo operator_add" e "rimappare un nodo AST di tipo operatore_mult", e pochi altri, legarli insieme in un mega-functor, lanciarli su un AST algoritmo di attraversamento, e hanno sputa fuori un albero AST con alcuni tipi convertiti in altri tipi ...

Ma sarebbe un sacco di lavoro.

Oh, e potremmo volere "tagging di fase", in cui una fase 1 e una fase 2 AST sono tipi diversi. Potremmo codificare ogni tipo nello type_list con la sua fase, oppure potremmo semplicemente taggare l'albero AST stesso. Diamine, potremmo nominare le fasi per lo AST usando il struct s altrimenti inutilizzato e definire una progressione attraverso le fasi come un tipo per digitare il functor che viene applicato e applicato nella firma di astFunc<before_phase, before_types, after_phase, after_types>.

Quindi non è male. Creiamo un type_list di tipi di nodi. Questi tipi non devono necessariamente essere i dati effettivi memorizzati. Ma può essere.

Creiamo una classe di tratti data_type che associa ogni tipo di nodo ai dati memorizzati. Creiamo una classe di tratti child_types che associa ogni tipo di nodo alla lista dei tipi degli AST secondari.

Ogni AST_Node memorizza un variant<AST_Concrete_Node<Ts>...>. AST_Concrete_Node contiene un DataType<T> data; e un MapTypes< std::vector, MapTypes< AST_Node, ChildTypes<T> > > children; (alias, std::vector< AST_Node<ChildrenTypes...> >, ma non è possibile dirlo facilmente).

Successivamente, le funzioni di trasformazione di sono unite in un difficile mesaggio di metaprogrammazione del modello in visitatori di varianti boost. Questo passaggio è davvero difficile, ma penso fattibile. Il lavoro extra è fatto in modo che i tipi non menzionati vengano saltati, quindi non dobbiamo dire continuamente "oh, e non vogliamo trasformare il nodo X", ma piuttosto dire "se colpiamo il nodo Y, non trasformare i suoi figli ".

A questo punto, sto andando a dire che sto blaterando - non averlo fatto prima, i problemi incontrati in un'implementazione concreta di questo pasticcio di ginnastica tipo sta per sopraffare la mia capacità di ragionare in modo astratto su di esso . Ma l'idea è sperabilmente utile: abbiamo trasformazioni di tipo nodo sicuro per tipo che vengono aggregate insieme e generano una trasformazione dell'albero sicura per tipo. L'albero non è semplicemente un albero astratto di varianti universali, ma un albero in cui ogni nodo sa quali sono i tipi consentiti nei suoi figli, che conoscono ricorsivamente lo stesso. Potremmo persino gestire "questo deve avere esattamente 3 figli, il primo dei quali è uno int, il secondo è uno Bob, e il terzo è uno double" se siamo andati abbastanza lontano nella tana del coniglio.

Answer 2

I nodi AST di per sé non hanno bisogno di enormi quantità di complessità. Penso che tutto questo meccanismo dei nodi AST sia solo eccessivo.

Il problema con AST non è la sicurezza del tipo di nodo; la sua sicurezza forma albero. Un AST rappresenta (presumibilmente) qualche istanza valida di una lingua L. Quello che idealmente si vuole è che le trasformazioni sull'AST producano altri AST validi (istanze del linguaggio L). Non garantirai questo garantendo che ogni nodo abbia un tipo valido; lo si può fare solo garantendo che qualsiasi patch dell'albero produca un albero valido. E questo è molto difficile da fare se le operazioni dell'albero sono atomiche (ad es. "Change node that", "replace child", "replace parent") e applicate separatamente; dopo diversi passaggi di questo tipo, cosa si può dire esattamente sull'albero?

Questa operazione è eseguita meglio utilizzando una sorta di transazione di riscrittura degli alberi, ad es., trasformazioni da sorgente a sorgente la cui struttura grammaticale è valida per il linguaggio L e che sono applicate in luoghi che sono validi per quella trasformazione.

Più standard program transformation systems fare questo. Raggiungono questo obiettivo tenendo un modello di grammatica per L e controllando che le trasformazioni proposte siano ben tipizzate. Questo assicura che le trasformazioni del linguaggio L al linguaggio L rimangano ben formate.

Questo è più difficile da ottenere se la mappa delle trasformazioni da una lingua A a un'altra lingua B; se alcune di tali trasformazioni vengono applicate, di solito ottieni un albero con tipi misti che non è legale in nessuna lingua. Con cura, si può definire un insieme di trasformazioni che mappano tutti i sottoalberi della lingua A alla lingua B, e applicarli in modo esaustivo; quindi vuoi che l'albero risultante sia ben formato per B. Puoi assicurarti che insistendo ogni volta che una patch B viene inserita in un albero misto, se è adiacente ad un'altra patch B, che il composto risultante B-patch è bene formata. Puoi farlo usando lo stesso stile di controllo grammaticale.

Utilizzando queste idee, è possibile creare un sistema che mappa un AST attraverso una serie di "rappresentazioni" (lingue A, B, C, ....) e avere una certa fiducia che l'albero dei risultati sia ben modellato. Questa idea generalizza al grafico delle riscritture.