4

Qi と Karma を使用して、いくつかの小さな言語で処理を行ってきました。ほとんどの文法はかなり小さい (20 ～ 40 のルール)。私はオートルールをほぼ排他的に使用することができたので、解析ツリーは完全にバリアント、構造体、および std::vector で構成されています。

このセットアップは、一般的なケースでうまく機能します:
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ます。)

porここで、最終結果が次のようになるように、各ノードを無効にしたいとします。

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

por直接的なアプローチは、サブツリーごとに次のようになります。
-pnotノードを作成します
(作成中のコピーpor)。-ノード
内の適切なベクトル スロットを再割り当てします (ノードとそのサブツリー を コピーします)。pand
pnotpor

別の方法として、別のベクターを構築し、そのpandベクターを大規模に置換 (スワップ) して、2 回目のコピーをなくすこともできます。

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 に答える