C言語完全に理解したい2.2
今回はC言語あんまり関係ないです。
複雑な文法のパース
A * B * C みたいな決まりきった並びの文字列から情報を取り出すのはさほど難しくないことは前回まででやった通りだが、もうちょっと自由な形式の文章をパースするのは途端に難しくなる。再三例に出している四則演算でいうと (1 + 2) * 2 + 4 みたいなものは人間なら簡単に理解できるけど、なんの直感も使わずにこれを説明するのは難しい。ましてやそれをプログラムに落とし込むなんてとてもとても…
ところが、BNFとboost::spirit::qiを知ってしまった我々は赤子の手をひねる如く数式をパースするプログラムを実装できるのである。つまるところ多項式の分解というのは次の式だけで書けるのである。
FORMULA ::= TERM *( '+' TERM | '-' TERM)
TERM ::= FACTOR *( '*' FACTOR | '/' FACTOR)
FACTOR ::= NUMBER | '(' FORMULA ')'
これが言っているのは
・多項式(FORMULA)は単項式(TERM)に分解できる。
・単項式(TERM)は因子(FACTOR)に分解できる。
・因子とはただの数(NUMBER)あるいはカッコで閉じられた多項式(FORMULA)である。
の3つである。
(1 + 2) * 2 + 4 を見たときにまずこれはTERM (1 + 2) * 2 とTERM 4 の足し算っぽいなぁと思い、 (1 + 2) * 2 をよく見てみると FACTOR (1 + 2) と FACTOR 2 の掛け算みたいと解釈する。2はそのまま数なのでFACTOR、 ( 1 + 2 )は中になにか入っているけどFACTORみたい、 1 + 2 が FORMULAだとするとこれはTERM 1 と 2 の足し算で、1 も 2 も 分解するまでもなくFACTOR だった。よって 1 + 2 は FORMULA であり (1 + 2)はFACTOR よって、(1 + 2) * 2 は TERM だった。最初に出てきた 4 もただの数なのでやっぱり (1 + 2) * 2 + 4 は TERM (1 + 2) * 2 とTERM 4 の足し算だ。なんて考える人はあんまりいないだろうが、こう推理するのが本当は正しいのだ。たぶん…
というわけで書いてみた。
#include <boost/spirit/include/qi.hpp>
#include <iostream>
#include <string>
#include <boost/spirit/include/phoenix.hpp>
using namespace std;
using namespace boost::spirit;
int main()
{
for (;;)
{
string str;
getline(cin, str);
auto begin = str.begin();
qi::rule<decltype(begin),int(),ascii::space_type> formula, term, factor;
formula = term >> *(('+' >> term)[([](){cout << "+ ";})]
|('-' >> term)[([](){cout << "- ";})]
);
term = factor >> *(('*' >> factor)[([](){cout << "* ";})]
|('/' >> factor)[([](){cout << "/ ";})]
);
factor = qi::int_[cout << _1 << " "] | '(' >> formula >> ')';
qi::phrase_parse(begin, str.end(), formula, boost::spirit::ascii::space);
}
}
このプログラムは
入力(1 + 2) * 4 + 5 * (1 + 2)
に対して
1 2 + 4 * 5 1 2 + * + という出力を返す。これはもちろん
( ( (1 2 +) 4 * ) ( 5 ( 1 2 + ) * ) + )からカッコを取ったものである。これがみにくい、あるいはカッコがないとわからないという人はちょっと中置記法に慣れすぎである。
この中置記法を後置記法に直すプログラムは驚くほどにシンプルに書かれており、phrase_parse関数に解析結果を保存するための引数を渡さないというパースすることを放り投げたかのようなふざけた構成である。こんなことができてしまうのがqiのすごいところなのだ。その秘密はセマンティックアクションにある。ルールのうしろに"[]"で囲って命令を書いてやると、なんとパターンマッチしたときに中の命令を実行してくれるのだ。とはいってもこいつは非常に機嫌が悪く、なんか変なことを書くとコンパイラが本当に鬼のようにエラーを吐いてくる…がどうやらラムダ式を"()"でかこったものは大丈夫なようだ。
これからどうする？
文法の解析について浅いけど理解が進んでいるが、これまで文法を扱う上で絶対に避けられない構文木を意図的に無視してきた。正直セマンティックアクション絡みでなんかよくわからないことが多すぎる（し僕は日記のつもりで書いている）ので後置記法なんてものでごまかしたのだが、これは所詮カッコを外すだけのテクニックにしか過ぎず、しかも並の人間にはカッコによる注釈がないとほとんど読めないという電卓ですらないお粗末なものだ…
なので次は構文木の構築をやるしかないだろう。