概要
Parsing Expression GrammerパーサージェネレーターのC++実装と言えば、boost::spirit が有名。
しかし、個人的にはジェネリックすぎて使い辛い。
PEGは定義がコンパクトなので簡単に書けるはずだ思ったので、自分で書いてみる。
とりあえずPEGと属性文法、セマンティックアクションくらいは実装する。
PEG
PEGには
・終端文字
・非終端文字
・空文字
・分析表現
・分析規則
が必要。
終端文字、非終端文字、空文字は分析表現。
S >> T, S | T, *S, +S, -S, &S, !S等の文字列も分析表現。ただし、S,Tは分析表現
これらの分析表現はある決まった分析規則を持っていて、
sequence, alternative, zero or more, one or more, zero or one, and predicate, not predicate等とそれぞれ呼ばれる。
分析表現は以上から再帰的に定義される。
PEGではある非終端文字Sには必ず対応するS→expressionという形の分析規則がただ1つなくてはならない。
分析規則は必ずS→expressionという形を持つ。
なので、分析規則には必ずただ1つの非終端文字が対応して、その非終端文字にはただ1つの分析表現が対応する。
これを一つのパーサーオブジェクトとして表現すれば良い。
パース関数はbool値と同時に、パースで消費されなかった文字列を返す様にする。
文字列はイテレーターのbegin,endの組で表現する事にしよう。
パース関数の返り値を格納するコンテナを定義しておく。
文字コードの問題から異なる文字列クラスを使う事が予想されるので、イテレータの種類でテンプレート化する。
template<typename Iterator> struct parse_result_container{
using iterator = Iterator;
bool boolean;
iterator begin;
iterator end;
parse_result_container(bool boolean_, iterator begin_, iterator end_)
: boolean(boolean_), begin(begin_), end(end_){};
};
終端文字
template<typename CharType, typename Iterator> struct Terminals{
using iterator = Iterator;
using parse_result_type = parse_result_container<iterator>;
using my_type = Terminals<CharType, Iterator>
const CharType char_value;
parse_reslt_type parse(iterator& begin, iterator& end) const{
if(begin != end && char_value == *begin){return parse_result_type(true,begin+1,end);}
return parse_result_type(false,begin,end)
}
};
まずは、終端文字を定義する。
正確には、終端文字'v'と1対1に対応する非終端文字Ch('v')を定義している事になっている。
パース関数の意味は入力文字列が零でなく、先頭が終端文字に一致するならtrueを返して、一文字消費する。
一致しなければ、falseを返して、入力文字列をそのまま返す。
メンバー型としてiteratorを持つが、これは後にExpression Templateを使った時に、上の方の木にイテレータの型を渡すために使う。
my_type自分の型そのものだが、後で演算子をオーバーロードする時のSFINA用に使う。
テスト
Terminals<std::string,std::string::iterator> ch('a');
std::string input("aiueo");
std::string input2("iaueo");
auto res = ch.parse(input.begin(),input.end());
auto res2 = ch.parse(input2.begin(),input2.end());
Expression template
template<typename L, typename OpTag, typename R> struct Expression{
using iterator = typename R::iterator;
using parse_result_type = typename R::parse_result_type;
using my_type = Expression<L,OpTag,R>;
const L& l;
const R& r;
Expression(const L& l_, const R& r_) : l(l_), r(r_){};
parse_result_type parse(iterator begin, iterator end) const{return OpTag::parse(l,r,begin,end);}
};
template<typename OpTag, typename R> struct Expression<unused,OpTag,R>{
using iterator = typename R::iterator;
using parse_result_type = typename R::parse_result_type;
using my_type = Expression<L,OpTag,R>;
const R& r;
Expression(const R& r_) : r(r_){};
parse_result_type parse(iterator begin, iterator end) const{return OpTag::parse(l,r,begin,end);}
};
分析規則は構文木の上の方のパース関数から順に起動される。
これは、通常の関数呼び出しと異なる順番なので、Expression templateが必要となる。
Expression templateを用いれば演算子オーバーロードも容易になるので一石二鳥である。
Expression templateといっても大して難しくはない。上に、二項演算と一項演算用のexpressionのクラステンプレートがある。
次に、例えばL >> Rからexpressionを構成するための演算子を定義する。
template<typename L, typename R> Expression<L,sequence<L,R>, R> operator>> (const L& l, const R& r){
return Expression<L,sequence<L,R>,R>(l,r);
};
この様に定義しておけば、L >> Rという式が評価されると、expressionが生成される。
もちろん、まともなコンパイラならコンパイル時にexpressionは消されて展開されたパース関数のみが残るはずだ。
ところで、この演算子のシグネチャは少々問題有る。
全体をある名前空間に突っ込んでも、その名前空間内のあらゆるオブジェクトにたいして演算子呼び出しができてしまう。
今の場合、これらの演算子はExpressionと終端文字に対してのみ定義できればよいので、そのためにmy_typeタグを使う。
template<typename L, typename R> Expression<typename L::my_type,sequence<L,R>, typename R::my_type>
operator>> (const L& l, const R& r){
return Expression<L,sequence<L,R>,R>(l,r);
};
定義された名前空間内でmy_typeを使わなければ、SFINAEによって演算子の呼び出しは正しく制限される。
準備は整った。後は定義に従って、演算子を定義するだけである。
コード
githubに上げた。
PEGの演算子と終端文字は全て実装してある。
バグがあったら教えてほしい。
次回
属性文法を追加する。
追記
boostは偉大だった。