Boost :: Spirit :: Qi Autoreles - Vermeidung von wiederholten Kopieren von AST Datenstrukturen

Question

Ich habe Qi und Karma verwendet, um einige kleine Sprachen zu verarbeiten. Die meisten Grammatiken sind ziemlich klein (20-40 Regeln). Ich konnte fast ausschließlich Autoregeln verwenden, daher bestehen meine Syntaxbäume vollständig aus Varianten, Strukturen und std :: vectors.

Dieses Setup funktioniert gut für den gemeinsamen Fall:
1) analysieren etwas (Qi),
2) machen kleinere Manipulationen an den Parse-Baum (Besucher) und
3) Ausgang etwas (Karma).

Allerdings mache ich mir Sorgen darüber, was passieren wird, wenn ich komplexe strukturelle Änderungen an einem Syntaxbaum vornehmen möchte, wie zum Beispiel das Verschieben großer Teilbäume. Betrachten Sie das folgende Spielzeug Beispiel:

Eine Grammatik für s-expr-Stil logische Ausdrücke, die autorules verwendet ...

// Inside grammar class; rule names match struct names... 
pexpr %= pand | por | var | bconst; 
pand %= lit("(and ") >> (pexpr % lit(" ")) >> ")"; 
por %= lit("(or ") >> (pexpr % lit(" ")) >> ")"; 
pnot %= lit("(not ") >> pexpr >> ")"; 

... die Baumdarstellung zu analysieren führt, die so aussieht ...

struct var { 
    std::string name; 
}; 
struct bconst { 
    bool val; 
}; 

struct pand; 
struct por; 
struct pnot;        

typedef boost::variant<bconst, 
         var, 
         boost::recursive_wrapper<pand>, 
         boost::recursive_wrapper<por>, 
         boost::recursive_wrapper<pnot> > pexpr; 
struct pand { 
    std::vector<pexpr> operands;      
}; 

struct por { 
    std::vector<pexpr> operands;      
}; 

struct pnot { 
    pexpr victim; 
}; 

// Many Fusion Macros here 

Angenommen, ich habe einen Parse-Baum, der etwa wie folgt aussieht:

 pand 
    /... \ 
    por  por 
/\ /\ 
var var var var 

(T er Auslassungszeichen bedeutet ‚viel mehr Kinder von ähnlicher Form für pand.‘)

Angenommen nun, dass ich jede der por Knoten negieren will, so dass das Endergebnis ist:

 pand 
    /... \ 
    pnot  pnot 
    |  | 
    por  por 
/\ /\ 
var var var var 

Der direkte Ansatz würde für jeden por Teilbaum:
- create pnot Knoten
(Kopien por in Konstruktion);
- den entsprechenden Vektorsteckplatz im pand Knoten
erneut zuweisen (Kopien pnot Knoten und seine por Unterstruktur).

Alternativ könnte ich einen separaten Vektor erstellen, und dann ersetzen (tauschen) die pand Vektor Großhandel, eine zweite Runde des Kopierens zu beseitigen.

All dies scheint umständlich im Vergleich zu einer zeigerbasierten Baumdarstellung, die es ermöglichen würde, die pnot-Knoten ohne Kopieren vorhandener Knoten einzufügen. Meine Frage:

Gibt es eine Möglichkeit zu vermeiden, Baumreproduktionen mit Autorule-kompatiblen Datenstrukturen kopieren? Sollte ich in den sauren Apfel beißen und nur Nichtautoren verwenden, um einen zeigerbasierten AST zu erstellen (z. B. http://boost-spirit.com/home/2010/03/11/s-expressions-and-variants/)?

Answer 1

Das Kopieren der Teilbäume sollte nicht so teuer sein, wie Sie annehmen, da die rekursive_variable im Wesentlichen ein Wrapper um shared_ptr ist. Ich glaube, es ist nicht nur die beste, sondern auch die einfachste Lösung.