Attraversare un AST usando Visitatori

Question

Attraversare un AST usando Visitatori

#1 da (3 voti)
#2 da (1 voti)

4

Sto scrivendo un compilatore per un linguaggio simile a C, e sto cercando un modo elegante per attraversare il mio albero di sintassi astratto. Sto cercando di implementare il pattern Visitor, anche se non sono convinto che lo stia facendo correttamente.

struct Visitor {   
    // Expressions
    virtual void visit(AsgnExpression&);
    virtual void visit(ConstantExpression&);
    ...
    virtual void visit(Statement&);
    ...

    virtual void finished(ASTNode&);

protected:
    virtual void visit(ASTNode&) = 0;
};

visit è sovraccarico per ogni tipo e, per impostazione predefinita, ciascun overload chiamerà visit(ASTNode&) che le sottoclassi sono costrette a implementare. Questo rende più facile fare cose veloci e sporche, sebbene la definizione di un visit per ogni tipo sia noiosa. Ogni sottoclasse di ASTNode deve implementare un metodo accept che viene utilizzato per attraversare la struttura ad albero.

class ASTNode {
public:
    virtual ~ASTNode();
    virtual void accept(Visitor& visitor) = 0;
};

Tuttavia, questo design sta diventando noioso perché i metodi accept sono spesso molto simili.

Chi dovrebbe essere responsabile per attraversare la struttura, i nodi o il visitatore? Mi sto proponendo di avere ASTNode di fornire un iteratore per accedere ai suoi figli, e quindi di far attraversare il visitatore alla struttura . Se hai qualche esperienza nella progettazione di Abstract Syntax Trees, per favore condividi la tua saggezza con me!

c++ design-patterns data-structures parsing visitor-pattern

posta user2844493 27.04.2014 - 23:31

fonte

2 risposte

1

Diversi problemi richiedono differenti strategie trasversali. Quindi il mio suggerimento sarebbe di implementare un Traverser separato usando il modello di strategia.

Il pattern Visitor può richiedere un sacco di codice boilerplate. In realtà è adatto alla generazione automatica di codice (vedi Java jaxb-visitor ). Il mio suggerimento è di implementare un visitatore di base / predefinito che fondamentalmente non fa nulla per ogni tipo di nodo. Qualsiasi visitatore che sta per fare qualcosa di interessante dovrebbe estendere il visitatore di baseplice di base. Quando un nuovo tipo di nodo viene aggiunto all'interfaccia del visitatore, devi solo fornire l'implementazione vuota nella classe base. Altrimenti, ogni volta che aggiungi un nuovo tipo di nodo devi cercare tutte le implementazioni e aggiungere il nuovo metodo.

risposta data 12.01.2015 - 21:00

fonte

Leggi altre domande sui tag c++ design-patterns data-structures parsing visitor-pattern

Codifica banalmente ordinabile per decimali arbitrari di precisione Le biblioteche devono utilizzare eventi o un'azione impostata

score 3 · Accepted Answer

Chi è responsabile per l'attraversamento dipende in gran parte dall'analisi che si desidera fare nei visitatori, dai dettagli della struttura linguistica e anche da una preferenza personale parziale.

In particolare, se ci sono casi in cui il visitatore di un nodo genitore deve intraprendere un'azione a metà dell'elaborazione dei bambini, è necessario inserire la logica di attraversamento nel visitatore. Ad esempio, se la lingua ha un costrutto in cui una variabile introdotta di recente è disponibile solo in alcuni dei nodi figlio del nodo che introduce la variabile.
Un altro caso è quando hai bisogno di una miscela di traversamento pre-ordine e post-ordine. Con l'attraversamento nei nodi, ogni nodo deve chiamare il visitatore due volte, una volta prima e una volta dopo i bambini. In tal caso, potrebbe essere più semplice lasciare che il visitatore faccia l'attraversamento.

Altrimenti, è soprattutto una questione di preferenza. L'attraversamento può essere nei nodi o nel visitatore.