Boost :: autorules Espíritu :: Qi - evitando repiten copia de estructuras de datos AST

Question

He estado usando el Qi y Karma que hacer algún tipo de procesamiento en varias lenguas pequeñas. La mayoría de las gramáticas son bastante pequeñas (20-40 reglas). He sido capaz de utilizar autorules casi exclusivamente, por lo que mis árboles de análisis consisten enteramente de variantes, estructuras, y std :: vectores.

Esta configuración funciona muy bien para el caso común:
1) análisis sintáctico algo (Qi), Francia 2) las manipulaciones hacen menores en el árbol de análisis sintáctico (visitante), y
3) algo de salida (Karma).

Sin embargo, me preocupa lo que sucederá si quiero hacer cambios estructurales complejas a un árbol sintáctico, como mover grandes subárboles alrededor. Considere el siguiente ejemplo de juguete:

Una gramática para expresiones lógicas-estilo-expr s que utiliza autorules ...

// 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 >> ")";

... que conduce a la representación de árbol de análisis sintáctico que tiene este aspecto ...

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

Supongamos que tengo un árbol de análisis que se ve algo como esto:

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

( 'muchos más niños de forma similar para pand.' Los medios suspensivos)

Ahora, supongamos que yo quiero cambiar signo cada uno de los nodos por, por lo que el resultado final es:

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

El enfoque directo sería, para cada sub-árbol por:
- crear pnot nodo
(Copias por en la construcción);
- re-asignar la ranura vector apropiado en el nodo pand
(Copias pnot nodo y su subárbol por).

Alternativamente, podría construir un vector separado, y luego vuelva a colocar (swap) la venta al por mayor pand vector, la eliminación de una segunda ronda de la copia.

Todo esto parece complicado en comparación con una representación de árbol, basados ??en punteros, lo que permitiría a los nodos pnot a ser insertados sin ninguna copia de los nodos existentes. Mi pregunta:

¿Hay una manera de manipulaciones de los árboles contra copia pesada Evitar en caso de estructuras de datos autorule de ayuda? Debería morder la bala y sólo tiene que utilizar los no autorules para construir un AST basada en puntero (por ejemplo, http://boost-spirit.com/home/2010/03/11/s-expressions-and-variants/ )?

Answer 1

Copia de los subárboles no debería ser tan caro como se asume como el recursive_variant es esencialmente una envoltura alrededor de un shared_ptr. Creo, que no es sólo la mejor, sino también la solución más fácil.