boost::spirit

現在受けている仕事は簡単な用件ばかりであり特に実装に悩むことはほとんどない。(納期の短さと実装量の多さ以外は)
そんな中でただ一箇所どうしようか頭を悩ませていたものがある。
数式入力が可能な電卓を実装しなくてはならないのだ。

つまり、『1+2』と入力された時点で『3』と計算結果のみが画面に表示される通常の電卓のようなものではなく
『1+2』と入力したら『1+2』と入力がそのまま表示され、計算ボタンを押した段階で式の評価を行う必要があるのだ。

ちなみに『1 2 +』と入力する逆ポーランド記法ではスタックを用いて簡単に実装可能である。
が、今回はいわゆる普通の式の記述(中間記法)に対して実装しなければならない。
また括弧にも対応しなければならないので括弧の対応がおかしな数式はエラーとして検出しなくてはならない。

一般的にはこのような四則演算と括弧だけを用いた中間記法の数式は

式 ::= 項 ( '+'項 | '-'項 )*
項 ::= 因数 ( '*'因数 | '/'因数 )*
因数 ::= 数値 | '(' 式 ')'

といった書き換え規則で表せる。(数値の定義は割愛)
このような書き換え規則の記述方法は拡張BNF記法という。
つまり式とは項に対して0個以上の項を足したり引いたりしたものであり、
また、項とは因数に対して0個以上の因数を掛けたり割ったりしたものであり、
因数とは数値もしくは式を括弧で括ったものである。
また逆にこの置き換え規則で表せないものは(四則演算と括弧だけを用いた)式ではない。

ちなみにこのような置き換え規則によって生成される文字列は文脈自由言語といい、プッシュダウンオートマトンで受理できる言語となる。
なお比較的良く知られた正規表現で記述できる正規言語は有限オートマトンで受理できる言語で、文脈自由言語の一種である。
このあたりは以下の書籍が詳しい。

計算理論とオートマトン言語理論―コンピュータの原理を明かす (Information & Computing)

話が少し逸れたが、今回の案件を正確に実現するには

1. 字句解析
2. 構文解析
3. 式として正しい文字列かの評価
4. 構文解析木の生成
5. 式の評価

をしなくてはならない。これを短期間で実装するのは容易ではない。

そこで調べてみるとboostライブラリにまさにピッタリのライブラリがあることがわかった。
boost::spiritライブラリである。
このライブラリを紹介している各個人ページでは軒並み「変態的」との評価を受けている。
いったいどのぐらい「変態的」なのか見てみよう。

まずは文法を定義する構造体を定義する。

#include <boost/spirit/core.hpp>

using namespace boost::spirit;

struct Grammar : public grammar<Grammar>
{
	// 定義
	template<typename S>
	struct definition {
		rule<S> factor;
 		rule<S> term;
		rule<S> expression;

		definition(const Grammar& self) {
			expression = term >> *( ('+' >> term) | ('-' >> term) ) ;
			term = factor >> *( ('*' >> factor) | ('/' >> factor) ) ;
			factor = real_p | '(' expression ')';
		}

		const rule<S>& start() const {
			return expression;
		}
	} ;
} ;

文法のルールとしてexpression,term,factorがあるが、これらがそれぞれ式、項、因数に該当する。
ここで注目して欲しいのは、このルールの記述が前述した書き換え規則である拡張BNF記法をほぼそのまま記述できる点である。
演算子オーバーロードを駆使して、結合は『>>』演算子(『&&』演算子でも可)、選択は『|』演算子、0以上の繰り返しは『(前置)*』演算子を用いることができるので、きわめて自然に記述できるのだ。
ちなみに1回以上の繰り返しは『(前置)+』演算子、省略可能(0回か1回の繰り返し)は『(前置)!』演算子で記述できる。
また、実数の定義はプリミティブなルールとしてreal_pで用意されているのも嬉しい。

さらに最終的に評価を行いたい『式』のルールをstart()メソッドの返り値として返す。
ではこの文法を用いてテストしてみよう。

int main() {
	Grammar gr; // 文法

	std::string str1 = "1 + 2 + 3 + ( 4 + 5 )" ;// 正しい式
	std::string str2 = "1 + 2 +" ;              // 正しくない式(+演算子の後に項がない)
	std::string str3 = "((1+2)+3))";            // 正しくない式(括弧が対応していない)

	if ( boost::spirit::parse( str1, gr, boost::spirit::space_p ).full )
		std::cout << "OK" << std::endl;
	else
		std::cout << "NG" << std::endl;

	if ( boost::spirit::parse( str2, gr, boost::spirit::space_p ).full )
		std::cout << "OK" << std::endl;
	else
		std::cout << "NG" << std::endl;

	if ( boost::spirit::parse( str3, gr, boost::spirit::space_p ).full )
		std::cout << "OK" << std::endl;
	else
		std::cout << "NG" << std::endl;

}

parse()関数に、解析する文字列、文法、スキップパーサ(読み飛ばす文字列のパーサ)を渡せばよい。
(空白にマッチするプリミティブとしてspace_pが用意されている)
また、返り値としてparse_info構造体を返し、このfullメンバがtrueかどうかで構文解析が最後まで到達した(=成功した)かどうかがわかる。
このプログラムの出力は

OK
NG
NG

となり、式として正しいかどうかきちんと解析してくれている。

さて、目的は式を評価することであった。
このboost::spiritライブラリ、当然(?)のように構文解析木を作る機能もサポートしている至れり尽くせりなライブラリなわけだが、
今回はより容易な実装としてセマンティックアクションと呼ばれる機能を利用することにする。
セマンティックアクションとはつまりは文字列が一部のルールにマッチした段階で呼ばれるコールバックを設定できる機能である。

// セマンティックアクション
void print(double val)
{
	std::cout << val << endl;
}

...
// 文法ルールにセマンティックアクションを設定する
			factor = real_p[&print] | '(' expression ')'; // 実数にマッチしたらprintが呼ばれる

『[]』演算子がセマンティックアクションを設定する演算子としてオーバーロードされており、上記の例ではreal_pにマッチした段階でマッチした値が渡され、printが呼ばれることになる。
real_pのように一部のパーサは引数に特殊な型をとるvoid (*action)(double)といった関数ポインタが渡せるが、
一般的なセマンティックアクションはマッチした最初の文字(begin)と最後の文字の次(end)を引数に取るvoid (*action)(const char*, const char*)といった形の
関数ポインタを指定することになる。
また、セマンティックアクションとして関数オブジェクト(ファンクタ)を指定することもできる。

これを利用すると逆ポーランド記法のようにスタックを一つ用意するだけで式の評価ができることになる。
(簡単のためスタックはグローバル変数として定義する)

std::stack<double> st ;

void Push(double val)
{
	st.push( val );
}

void Add(const char*, const char*)
{
	double rhs = st.top() ; st.pop();
	double lhs = st.top() ; st.pop();
	st.push( lhs + rhs );
}

void Sub(const char*, const char*)
{
	double rhs = st.top() ; st.pop();
	double lhs = st.top() ; st.pop();
	st.push( lhs - rhs );
}

void Mul(const char*, const char*)
{
	double rhs = st.top() ; st.pop();
	double lhs = st.top() ; st.pop();
	st.push( lhs * rhs );
}

void Div(const char*, const char*)
{
	double rhs = st.top() ; st.pop();
	double lhs = st.top() ; st.pop();
	st.push( lhs / rhs );
}

struct Grammar : public grammar<Grammar>
{
	// 定義
	template<typename S>
	struct definition {
		rule<S> factor;
 		rule<S> term;
		rule<S> expression;

		definition(const Grammar& self) {
			expression = term >> *( ('+' >> term)[&Add] | ('-' >> term)[&Sub] ) ;
			term = factor >> *( ('*' >> factor)[&Mul] | ('/' >> factor)[&Div] ) ;
			factor = real_p[&Push] | '(' expression ')';
		}

		const rule<S>& start() const {
			return expression;
		}
	} ;
} ;

以上のように実装し、parseを行い、スタックに残っているたった一つの値が式の評価値ということになる。

簡単な例で説明すれば
1+2*3-(4/5+1)
という式の値の評価は次のようなステップで評価されることになる。

1. 1 (real_p)のマッチ(スタック:1)
2. 2 (real_p)のマッチ(スタック:1, 2)
3. 3 (real_p)のマッチ(スタック:1, 2, 3)
4. *3 ('*' >> factor)のマッチ(スタック:1, 6)
5. +2*3 ('+' >> term)のマッチ(スタック:7)
6. 4 (real_p)のマッチ(スタック:7, 4)
7. 5 (real_p)のマッチ(スタック:7, 4, 5)
8. /5 ('/' factor)のマッチ(スタック:7, 0.8)
9. 1 (real_p)のマッチ(スタック:7, 0.8, 1)
10. +1 ('+' >> term)のマッチ(スタック:7, 1.8)
11. -(4/5+1) ('-' >> term)のマッチ(スタック:5.2)

ここで最後にスタックに残った5.2が式の評価である。
注意点として、セマンティックアクションはパース途中に呼ばれるため、全体の構文解析が失敗したとしても一部のセマンティックアクションは呼ばれる可能性があることを忘れてはならない。

さて、実際今回の案件では三角関数(sin,cos,tan)や平方根(sqrt)も利用したいということであったがその拡張が容易であることは言うまでもない。
この「変態的な」ライブラリに大いに助けられることになると同時に、本ライブラリがなかったらどうなっていたのだろうかと思うと恐ろしい。