Usage

これは何？

C++用のPEGパーザライブラリ

何がすごいの？

今までにない文法の記述方法！

• PEGの文法規則から簡単に文法を記述できる！
• セマンティックアクションが簡単に記述できる！
• ASTを自由に作れる！
• テンプレートを使って、ジェネリックなルールが書ける！

だめなライブラリの例

今までのパーザのよくある記述方法(Boost::Spirit)だと

definition(const calc& self)
{
  using namespace calc_action;
  expr = term >> *( ('+' >> term)[&ADD]
                    | ('-' >> term)[&SUB] );
  term = fctr >> *( ('*' >> fctr)[&MUL]
                    | ('/' >> fctr)[&DIV] );
  fctr = int_p[&PUSH]
    | '(' >> expr >> ')';
}

こんなだった。演算子オーバーロードを多用して変態的なライブラリに仕上がっている。
しかし、これでセマンティックアクションを書くのは至難の業だ。
ジェネリックなルールは関数をうまく使えば書けるのか？

他のパーザもみつけてきた(pegtl)

struct grammar
         : seq< alpha, until< eol, sor< alpha, digit > > > {};

こっちは、テンプレート引数でルールを記述するぜー。これは山かっこの対応をとるのが大変死ねる。
あと、セマンティックアクションの書き方はよく知らない。
こっちはテンプレートを使えばジェネリックなルールが書けそう。大変そうだけど
これは全然だめだ。実装が楽なように記法を定めているけども、正しくは実装できる範囲で書きやすい記述方法を採用しなければならない。

使い方

構文規則・セマンティックアクション・AST

構文規則

foo ::= bar baz

があったら

struct foo {
  void action(bar x, baz y) {
  }
};

と書くだけでよい。これにより、上記の構文規則が引数の型で自動的に認識される。
セマンティックアクションの結果はfoo構造体であり、アクションの実装はactionメソッドの中に書く。
もちろん、(非)終端記号barに対応する値は引数 x で、bazに対応する値は y である。

xとyをそのままfooの中に保持コードを実装すれば、ASTの出来上がりである。

例

struct integer {
  void action(digit x, const rep<digit>& y);
};

これはdigitの1回以上の繰り返しがintegerであるという規則だ。ここで、digitは数字にマッチする終端記号、rep<T>は0回以上の繰り返しだ。

選択肢

普通の文法規則にはこんな感じで選択肢が含まれている。

foo ::= bar baz | qix

もちろん、これは複数のactionメソッドを定義することで記述する。

struct foo {
  void action_0(bar x, baz y) {
  }
  void action_1(qix z) {
  }
};

action_9まで書くことができる。

特殊形式

他にも、0回以上の繰り返しとか色々記法があるが次の表のように記述できる。

PEG	cpppeg
e*	rep<e>	0回以上の繰り返し
e+	replus<e>	1回以上の繰り返し
e?	opt<e>	1回以下の繰り返し
&e	if_<e>	先読み
!e	unless<e>	否定先読み

終端記号

今のところこれだけ

ch<'x'> // 一文字にマッチ
chr<'a', 'z'> // 'a'以上'z'以下にマッチ
cho<T, U>  // TかUにマッチ
upper, lower, alpha, digit, ws // 大文字、小文字、アルファベット、数字、空白

非終端記号

もちろん、自分で定義した非終端記号に対応したクラスもactionの引数にできるぞ。
サイズが大きなクラスになっちゃったらconst T&で受け取ってもよい。

fusion::vectorを使う

actionの引数にfusion::vector<T1, T2, T3, …>を使うと、T1 T2 T3を並べたのと同等になり、値を使用することもできる。

パーザの実行

文法の定義が終わったら、パーザを実行するだけだ
開始記号sに対応するクラスがsならパーザのクラスはparser<s>だ

parser<s> p;
s result;
string src = "hogehoge";
bool ok = p.parse(result, src.begin(), src.end());

継承を使って本格的にASTを作る

ASTを真面目に構築する場合は基底クラスから継承して他の要素を作るほうが分かりやすいツリーができる。
この場合はactionメソッドが基底クラスへのポインタを返すstaticメソッドのほうが都合がよい。
ptrを使って非終端記号Tを参照したときは、actionメソッドをそのように定義できる

actionの返り値はT::result_type型で、ptr型の値はT::result_type型の値として使える。

struct tree;
typedef boost::shared_ptr<tree> ptree;
 
struct tree
{
  typedef ptree result_type;
  virtual ~tree() {}
  virtual int eval() const = 0;
};
 
struct binary_tree : public tree
{
  boost::function<int(int,int)> op;
  ptree left;
  ptree right;
  binary_tree(ptree, Op, ptree) { ... }
  int eval() const { return op(left->eval(), right->eval()); }
};

struct multi_expr : public binary_tree
{
  // ...
};

struct add_expr : public binary_tree
{
  static ptree action_0(const ptr<multi_expr>& e) {
     return e;
  }
  static ptree action_1(const ptr<multi_expr>& eleft, add_op op, const ptr<multi_expr>& eright) {
    return ptree(new add_expr(eleft, op, eright));
  }
};

完全な例

Example