この記事はAizu Advent Calendar 2016の15日目の記事です。
はじめに
艦これイベントとテストとHaskellにどっぷりハマって内容薄いです(本当にすいません)。
数日前、構文解析に使うパーサジェネレータを探していたらcaperを見つけました。
構文解析?パーサジェネレータ?なにそれ?みたいな方はこちらへ
構文解析 - Wikipedia
caperとは
caperとはモダンでクリーンなC++コードを出力するパーサジェネレータで、C++以外にもJavaScript/C#/D/Java/Boo/Ruby/PHP/Haxeにも対応しているみたいです。
こんな感じで定義できます。
非終端記号名<非終端記号の型> : [セマンティックアクション名] 項 項 | [セマンティックアクション名] 項(0) 項(1) | [セマンティックアクション名] 項(0) 項 項(1) ;
(0)とか(1)とか付けるとセマティックアクションに引数として渡すことができます。
詳しくはこちら。
本題
公式のチュートリアルに電卓プログラムがあるのですが(ここ)、cpg(文法ファイル)をよく見ると
%token Number<int> Add Sub Mul Div; %namespace calc; %dont_use_stl; Expr<int> : [Identity] Term(0) | [MakeAdd] Expr(0) Add Term(1) | [MakeSub] Expr(0) Sub Term(1) ; Term<int> : [Identity] Number(0) | [MakeMul] Term(0) Mul Number(1) | [MakeDiv] Term(0) Div Number(1) ;
8 + 3 * 7 とかの計算はできるみたいですけど ( 8 + 3 ) * 7 は未対応ですね...
ということで対応させました。
%token Number<int> Add Sub Mul Div Begin End; %namespace calc; %dont_use_stl; Expr<int> : [Identity] Term(0) | [MakeAdd] Expr(0) Add Term(1) | [MakeSub] Expr(0) Sub Term(1) ; Term<int> : [Identity] Primary(0) | [MakeMul] Term(0) Mul Primary(1) | [MakeDiv] Term(0) Div Primary(1) ; Primary<int> : [Identity] Number(0) | [Negative] Begin Sub Number(0) End | [Identity] Begin Expr(0) End ;
こんな感じでPrimaryを新しく作ってNumberと(Expr)を[Identity]で返せば綺麗ですね。
ちなみにBeginは ' ( ' を表してEndは ' ) ' を表してます。
ついでに(-1)なども適正に処理されるようにしました
実際に上手く動作するか確認しましょう。
上手くいきました。
ここまで来て纏めたらあまりにも内容が薄すぎたので本来整数にしか対応してませんが小数に対応させました。cppファイルを一から作るのも面倒だったので公式のサンプルを引用して一部変更させました。変更点としては計算の結果をdouble型にしてparser.accept(v)のvをdouble型に変更などなど。upcast, downcastも適宜変更しました。
%token Number<double> Add Sub Mul Div Begin End Point; %namespace calc; %dont_use_stl; Expr<double> : [Identity] Term(0) | [MakeAdd] Expr(0) Add Term(1) | [MakeSub] Expr(0) Sub Term(1) ; Term<double> : [Identity] Primary(0) | [MakeMul] Term(0) Mul Primary(1) | [MakeDiv] Term(0) Div Primary(1) ; Primary<double> : [Identity] Factor(0) | [Negative] Begin Sub Factor(0) End | [Identity] Begin Expr(0) End ; Factor<double> : [Identity] Number(0) | [MakeDouble] Number(0) Point Number(1) ;
MakeDoubleはこんな感じで書きました。
double MakeDouble(double x, double y){ int nod = log10(y) + 1;//桁数を求める for(int i = 0; i < nod; i++) y /= 10;//小数点以下にする return x + y; }
こんな感じで綺麗に計算結果が小数で出てくれました。
doubleに対応させただけだと微妙なので三角関数や平方根にも対応させました。
非終端記号名が思いつかなかったので適当にAdvancedにします。
%token Number<double> Add Sub Mul Div Begin End Point Sin Cos Tan; %namespace calc; %dont_use_stl; Expr<double> : [Identity] Term(0) | [MakeAdd] Expr(0) Add Term(1) | [MakeSub] Expr(0) Sub Term(1) ; Term<double> : [Identity] Advanced(0) | [MakeMul] Term(0) Mul Advanced(1) | [MakeDiv] Term(0) Div Advanced(1) ; Advanced<double> : [Identity] Primary(0) | [MakeSin] Sin Primary(0) | [MakeCos] Cos Primary(0) | [MakeTan] Tan Primary(0) | [MakeSqrt] Sqrt Primary(0) ; Primary<double> : [Identity] Factor(0) | [Negative] Begin Sub Factor(0) End | [Identity] Begin Expr(0) End ; Factor<double> : [Identity] Number(0) | [MakeDouble] Number(0) Point Number(1) ;
こんな感じで動きます。
もちろん括弧は最優先処理になっているのでこんな書き方でもきちんと出力されます。
三角関数や平方根を使う際はNaNに気を付けないとですね。
やろうと思えばlogとかも行けたり階乗、冪乗も簡単に追加できます。
簡単に変更できるのは便利ですね。
まとめ
公式のサンプルを拡張させていったらcppファイルが結構ぐちゃぐちゃになってしまったので非公開にしました。近いうちに全部書き直して綺麗になったらGitHubにあげようと思います。
今回本当に軽く触った程度なのでなんとも言えませんが、結構扱いやすかったです。