copy - Boost::Spirit::Qi 自动规则——避免重复复制 AST 数据结构

Question

我一直在使用 Qi 和 Karma 对几种小语言进行处理。大多数语法都很小(20-40 条规则)。我几乎可以完全使用自动规则，所以我的解析树完全由变体、结构和 std::vectors 组成。

此设置适用于常见情况:
1)解析一些东西(Qi)，
2)对解析树(访问者)进行细微的操作，以及
3)输出一些东西(业力)。

但是，我担心如果我想对语法树进行复杂的结构更改(例如移动大子树)会发生什么。考虑以下玩具示例:

使用自动规则的 s-expr 式逻辑表达式的语法...

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

...这导致解析树表示看起来像这样......

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

假设我有一个看起来像这样的解析树:

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

(省略号的意思是“pand 的更多类似形状的 child 。”)

现在，假设我想否定每个 por节点，因此最终结果是:

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

直接的方法是，对于每个 por子树:
- 创建 pnot节点
(副本 por 正在 build 中)；
- 在 pand 中重新分配适当的向量槽节点
(复制 pnot 节点及其 por 子树)。

或者，我可以构建一个单独的向量，然后替换(交换)pand矢量批发，消除了第二轮复制。

与基于指针的树表示相比，所有这些似乎都很麻烦，这将允许 pnot要插入的节点，而无需复制现有节点。我的问题:

有没有办法避免使用符合自动规则的数据结构进行繁重的树操作？我应该咬紧牙关，只使用非自动规则来构建基于指针的 AST(例如， http://boost-spirit.com/home/2010/03/11/s-expressions-and-variants/ )吗？

Answer 1

复制子树不应该像您假设的那样昂贵，因为 recursive_variant 本质上是 shared_ptr 的包装器。我相信，这不仅是最好的，也是最简单的解决方案。