C言語完全に理解したい2.1　またはboost::spirit::qiの所感

2020年6月3日 00:24

お約束
C言語なんもわからん≒C言語のコンパイラ書ける
C言語完全に理解≒ズルすればC言語のコンパイラ書ける

前回までのまとめ

C言語完全に理解したい

C言語なんもわからんレベルになりたいと思いコンパイラを書こうとするが、しんどいのでLLVMの中間表現に変換するやつをC++で書こうとした。この方法だと低レイヤーについては学ぶことは期待できないし、コンパイラでコンパイラをコンパイルするみたいなself-containedな遊びができない。

構文解析について

典型的な構文解析の例として多項式を因子と演算子だけで表すみたいなことをやった。ポーランド記法は小学校の指導要領に盛り込むべきだというのが前回までの結論だ。

パーサージェネレータ

構文解析というのは昔からコンパイラを書くのには欠かせないものである、が近年では構文解析器（パーサー）をゼロから書くということはあまりせず、パーサーを作るプログラム（パーサージェネレータ）がよく用いられる。これはフードプロセッサよりも高級なシロモノでルールを入れればすぐにパーサーが吐き出される。代表的なものはyaccだろうか。

boost::spirit::qi

〇〇をする××をするみたいなことはC++とかboostの得意とするところであり、実際BNFライクな感じで使えるパーサーライブラリboost::spirit::qiが存在する。普通のパーサージェネレータと違って、ルールを与えることによってパーサーそのものを呼び出すことができるなんともメタプログラミングめいたライブラリだ。

もちろん多項式を因子と演算子だけに分解するなんて赤子の手をひねるごとく簡単にできて、ちょいと検索しただけでこんなに出てくる
http://lnseab.hatenablog.jp/entry/2013/04/08/211134
https://rhysd.hatenablog.com/entry/2013/12/24/003122
少し古いけど（qiじゃないけど）
http://boost.cppll.jp/HEAD/libs/spirit/doc/calc_plain.cpp.html

あれ…ちょっと難しい？

qiを使ってみる

boost::spiritは構文解析を行うqi、構文解析と逆の操作を行う（？）karma、及び字句解析をするlexから構成される。もちろんいま興味があるのはqiである。

パースする
qiを使ってすることといえば boost::spirit::qi::parseという関数を呼び出して解析してもらうことに尽きるのだが、このためのお膳立てがかなりめんどくさい。この関数は戻り値は真偽のみだが、引数として

解析する文字列の先頭へのイテレータ（非const）
解析する文字列の終端へのイテレータ（const）
解析ルール
解析結果の格納場所

戻り値は引数のみだが、最初のイテレータは変更するという太えやつである。厄介なのが解析ルールで最後の格納場所と相まってめちゃくちゃな変態ライブラリと誤解される要員になっている。

ルールの作り方

ルールはプリミティブ、演算子、（とディレクティブ）により構成される、というと身構えてしまうが要するにBNFなのである。175 * 85 * 24とかいう文字列に身長 * 体重 * 年齢とかいうルールを見出したなら

auto rule = qi::int_ >> qi::lit('*')
          >> qi::int_ >> qi::lit('*')
          >> qi::int_;

のようにすればいい。もっと書くとすると

#include <boost/spirit/include/qi.hpp>
#include <iostream>
#include <string>

using namespace std;
using namespace boost::spirit;


int main()
{
       for (;;)
       {
       string str;
       getline(cin, str);
       auto begin = str.begin();
       auto end = str.end();
       auto rule = qi::int_ >> qi::lit('*')
                 >> qi::int_ >> qi::lit('*')
                 >> qi::int_;
       int  height, weight, age; 
       if(qi::phrase_parse(begin, end, rule, ascii::space, height, weight, age))
               cout << "HEIGHT :" << height << endl
                    << "WEIGHT :" << weight << endl
                    << "AGE :" << age << endl;
       }
}

こんな感じかな。ちょっと戸惑うのはC++にありがちな">>"演算子のオーバーロードによるルールの記法である。文字列とか数字だったりするプリミティブをつなげるのがこの演算子の役割だ。となるとだんだん分かってくる…？

プリミティブ

プリミティブはルールを構成する最小の単位、つまり最悪これ一つでルールとして成り立つものだ。qi::char_とかqi::int_が文字とか整数とかのプリミティブである。プリミティブの中にはAttributeを持つものがあって、パーサーにルールを渡した後、Attributeの通りに解析結果が格納される。qi::char_だったらchar型、qi::int_だったらint型のように、プリミティブの場合は極めて単純である。なおqi::lit()は文字（列）のプリミティブであるが、Attributeを持たない。

演算子

プリミティブを繋げたり、繰り返したりするのが演算子の役割である。例えば">>"演算子はプリミティブをつなげることができるほか、0を含む任意の回数繰り返す"*"演算子、1以上の任意の回数繰り返す"+"演算子など頭がパンクすることうけあいだ。Attributeがどうなるかはちょっとした頭痛の種である。もちろんこれは演算子によって異なり、A,BのAttributeをもつa, bからa >> bというルールを作ったらAttributeはtuple<A,B>になる。

ルール（リプライズ）

以上のことを踏まえるとルールとはプリミティブから構成され、Attributeを持つ可能性があり、演算子によってさらに結合可能ななにかである。

auto rule = qi::int_ >> qi::lit('*')
         >> qi::int_ >> qi::lit('*')
         >> qi::int_;

となるとこいつのAttributeはtuple<int,tuple<int,int>>...?

ではなくBoost.Fusionのシーケンスがなんとかだそうだ。よくわからんがヨシ！結局int, int , intでいいっぽいです。

さらなる闇へ

ここまで来て、実際に構文を解析するときはAttributeどうなっちゃうの？と恐怖を抱くことだろう。実際それは悩みの種なのだが、セマンティックアクションという機能を使うことで解決できる。とはいえ構文木をうまく構築するのにはboost::variantなどが必要なので（？）結構前途多難なのだが。

たまにはうんとポエミィに

なんかコンパイラ作るの流行ってんなーとはちょっと前から思っていたのだが、一説によると"低レイヤを知りたい人のためのCコンパイラ作成入門"の著者が火付け役だそうだ。この中に「コンパイラをコンパイルするコンパイラ」みたいなコラムがあって（わりと最初の方なので探してみよう）ミトコンドリア・イブとかY染色体・アダムみたいな話が出てくる。コンパイラのバイナリがあるってことはそれをコンパイルしたコンパイラがあるのでそれをたどっていくと最初のコンパイラ（アセンブラ？）にたどり着くという話だ。こういう話をみるとコンパイラがコンパイラをコンパイルできるってことはなんかとても詩的で、俺は母親にはなれないけど俺の娘は母親になれるぜ！みたいな気分になるのだが、娘も子供もいないし、コンパイラをコンパイルできるコンパイラを作るにはC++コンパイラを書かなければいけないことになる。悲しい…

C言語完全に理解したい2.1 またはboost::spirit::qiの所感