4

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

此设置非常适用于常见情况：
1) 解析某些东西 (Qi)，
2) 对解析树 (访问者) 进行少量操作，以及
3) 输出某些东西 (Karma)。

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

使用自动规则的 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。”）

现在，假设我想否定每个por节点，所以最终结果是：

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

对于每个por子树，直接的方法是：
- 创建pnot节点
（构造中的副本por）；- 在节点
中重新分配适当的向量槽 （复制节点及其子树）。 pand
pnotpor

或者，我可以构建一个单独的向量，然后pand批量替换（交换）向量，从而消除第二轮复制。

与基于指针的树表示相比，所有这些似乎都很麻烦，这将允许在pnot不复制现有节点的情况下插入节点。我的问题：

有没有办法使用符合自动规则的数据结构来避免复制繁重的树操作？我是否应该硬着头皮只使用非自动规则来构建基于指针的 AST（例如，http ://boost-spirit.com/home/2010/03/11/s-expressions-and-variants/ ）？

4

1 回答 1

3

复制子树不应该像你想象的那么昂贵，因为 recursive_variant 本质上是一个 shared_ptr 的包装器。我相信，这不仅是最好的，也是最简单的解决方案。

于 2011-01-10T23:51:32.987 回答