C++用汎用構文解析器pneuma
boost::spirit怖すぎとか言いながらずっと作ってた。spiritV3来るって噂もあるけど知りません
リファレンスはかったるいので作らない
サンプル見てBNFわかればなんとなくわかる
//main
std::string temp="3+2*5/(4-2)";
std::vector<std::string> v=tokenize(temp);
//vは 3 + 2 * 5 / ( 4 - 2 ) というトークンになっている
//トークナイザは自分で何とかしよう
try {
Dentaku taku;
taku.Parse(v.begin(),v.end()); //構文解析を始める。失敗するとDebugDataを投げる
int x=taku.Build(); //結果を取り出す。parseより前に書くと死ぬ
std::cout<<x; //8
}catch(Dentaku::DebugData e)
{ //DebugDataは最長どこまで解析できていたかを教えてくれる。修正のおともに
for(auto it=e.max_back;it!=v.end();++it)
std::cout<<*it;
std::cout<<"が構文解析できませんでした";
}catch(Dentaku::CompileError e) //構文が腐ってたりするとCompileErrorを投げる
{ //たいへん不名誉なのでrelease前に直そう
std::cout<<e.what();
}
メインはこんな感じ
で、肝心のDENTAKUのほうは
typedef std::vector<std::string>::const_iterator Iterator;
//pneumaを継承することでさまざまなprotectedな関数やクラスを利用できる
//std::string以外を扱いたい時はbasic_pneumaをいろいろするんだ
class Dentaku:public pneuma<Iterator,int,int> //pneuma<Iterator,result_type,build_type>
{ //イテレータの型,setで登録する関数の戻り値の型,Buildの戻り値の型
public:
Dentaku()
{
auto plus=MakeSymbol(); //MakeSymbolは非終端記号を作ります
auto mult=MakeSymbol();
auto factor=MakeSymbol();//RegexPushSymbolは正規表現で定義される終端記号を示します
auto Int=RegexPushSymbol("[0-9]+");
//正規表現に正しい場合、マッチしてトークンを保存します
SetStart(plus); //構文解析の始まりを指定します
//各式は&で連結、|で選択,*で0回以上の,+で1回以上の繰り返し
//Setでeval時に実行される構文木の関数を定義します
//指定しない場合、childを0から順に実行します
//Setは上書きすることもでき、引数はstd::function<RESULT_TYPE()>となります
//ラムダ式で書きなぐるのおすすめ
plus=mult&* ( (SP("+")|SP("-"))&mult&Set([&]{
int lhs=Child(0); //Childはeval時に子(この場合mult)を実行します
for(size_t i=0;i<TokenSize();++i) //TokenSizeは保存されたトークンの総数を返します
{
if(GetToken(i)=="+") //GetTokenはi番目に保存されたトークンを返します
lhs+=Child(i+1);
else if(GetToken(i)=="-")
lhs-=Child(i+1);
}
return lhs;
}));
//SPは引数に等しい場合マッチし、トークンを保存します
//後で出てくるSは引数に等しい場合マッチします。保存はしません。symbolのS
//ちなみにfactor&(SP("*")|SP("/")&mult と書かないのは//いい左優先方法思いつかなかったからです
//mult =mult&S("*")などとやると延々とmultを解決しようとするので気を付けてください
mult=factor&* ( (SP("*")|SP("/"))&factor&Set([&]{
int lhs=Child(0);
for(size_t i=0;i<TokenSize();++i)
{
if(GetToken(i)=="*")
lhs*=Child(i+1);
else if(GetToken(i)=="/")
lhs/=Child(i+1);
}
return lhs;
}));
//ここには書いてないですがChildSizeという関数もあります。子の数を返します
factor=(Int&Set([&]{return std::stoi(GetToken(0));}))|(S("(")&plus&S(")"));
}
build_type Build() //純粋仮想関数に指定されているので必ず定義してください
{
return eval(); //evalはparseによって作られた構文木を解決していきます
//今回はただそのまま返してるだけですがSetに登録する関数で副作用を大量におこして
//そこから組み立てたりもできます
}
};
こんな感じ。spiritよりきれいで楽。なはず
コメントばっかで見づらいね。コメントを取っ払ってラムダ式を折りたたむ*1とこんな感じ
typedef std::vector<std::string>::const_iterator Iterator;
class Dentaku:public pneuma<Iterator,int,int>
{
public:
Dentaku()
{
auto plus=MakeSymbol();
auto mult=MakeSymbol();
auto factor=MakeSymbol();
auto Int=RegexPushSymbol("[0-9]+");
SetStart(plus);
plus=mult&*( (SP("+")|SP("-"))&mult&Set(ラムダ式));
mult=factor&*( (SP("*")|SP("/"))&factor&Set(ラムダ式));
factor=(Int&Set(ラムダ式))|(S("(")&plus&S(")"));
}
build_type Build() { return eval();}
};
pneumaの子クラスを別の子クラスで使う方法もあるんだけどそれは今度書こう
*1:VS2012ではできる