C++11 で地味に可変長引数 template が導入されました。これを利用して字句と構文解析メタプログラムを作ります。
結構長いのですが、まずは歴史から。
関数の可変長引数と今まで
関数の可変長引数は C 言語初期の頃から存在し、 “Hello World” に代表される printf にて触れることが多いと思われます。 C++ では boost や tr1 によって利用可能な tuple が主な例だと考えられます。
printf("%d + %d = %d",1,1,2);
printf においては、スタックポインタの操作による原始的な引数受け渡しと CPU 設計の相性が良かったということもあります。引数の数によって確保するスタックの量を変えるだけです。
C++ 世代ではだいたい次のような認識ではないかと思われます。
tuple<int,float,const char*> any;
これは、
template<typename T1,typename T2=void,typename T3=void,typename T4=void> struct tuple;
C++03 時代においては、常識的にありえるであろう引数の数だけ宣言を用意することで実現できました。 tuple 自体は単なる配列や無名メンバ構造体とも見れるので目新しい事はなく、 template にて実装されているものの、 tuple 程度ではメタプログラミングという雰囲気もでていません。また、関数とは違い template は「コンパイル時に解決されるプログラム」なので（たぶん）コンパイラの実装難易度が上がってしまうため実現されませんでした。 #define や #include などのプリプロセッサを介したメタメタプログラミングも苦肉の代替手段として存在しています。
そして本題です
代表的な構文解析プログラムとして Lex/Yacc や、 boost::spirit がありますが Yacc のようにゴミクズのようなコードを散りばめる事もなく、 spirit のように無理やり C++ の構文に合わせる事もしません。
構文解析界隈はツールが非常に多いのですが、 C++ にて苦手とされる文字列処理の選択肢を一つ増やせるかもしれません。
設計
構文の定義は BNF に似せた設計にします。機能としては正規表現のほうが近いかもしれません。
実行は bool Parse(const char *&); を呼び出すことで、マッチするかしないか、マッチした場合は引数そのものを前進させることで直感的に使えるようにします。
なるべく可変長引数 template にフォーカスを当てるため、他の新機能は避けます。（よって 11 でない C++ でも、沢山の引数にデフォルトを設定すれば結構使えます）
- typename キーワードを省略しない
- template 引数を閉じる > を連続させない
- constexpr による文字列マッチは行わない
- コンパイラの都合で、 RTTI と例外は使わない
BNF って？？
XML 定義より、一部引用
[3] S ::= (#x20 | #x9 | #xD | #xA)+
[22] prolog ::= XMLDecl? Misc* (doctypedecl Misc*)?
[23] XMLDecl ::= '<?xml' VersionInfo EncodingDecl? SDDecl? S? '?>'
[24] VersionInfo ::= S 'version' Eq ("'" VersionNum "'" | '"' VersionNum '"')
[25] Eq ::= S? '=' S?
[26] VersionNum ::= '1.' [0-9]+
[27] Misc ::= Comment | PI | S
BNF では symbol ::= expression の式を組み立てていきます。正規表現よりは比較的読みやすいかもしれないですね。
BNF を参考にすると必要になるフォーマットは、
- いずれかの文字にマッチ。 S 参考。 スペース タブ CR LF のコード。
- 文字の範囲にマッチ。 [0-9] のような。
- 文字列にマッチ。 ‘<?xml’ のような。
- あってもなくてもよい。 XMLDecl? のようなハテナ。
- 0 個以上にマッチ。 Misc* のようなアスタリスク。
- 1 個以上にマッチ。 [0-9]+ のプラス。
- いずれかの条件にマッチ。 ( 条件A | 条件B | 条件C )
- 連続した条件にマッチ。 ::= の右側のスペース区切りのもの殆ど
Not もあったほうが楽しいのですが、今回は作りません。いずれかの文字と文字列マッチは最後の二つのテクニックの char 向き実装ですが、理解しやすいためまずはこれから設計します！
凡例、構文定義
typedef expression symbol;
凡例、構文処理
symbol ctx;
const char *str="anything";
if( ctx.parse(str) )
good;
else
bad;
文字列を与えてパース出来たときは good 、そうでないときは bad です。
また、一部で次のマクロを使います。
#ifndef UNUSED #define UNUSED(x) (void)(x) #endif
機能の実装はすべて namespace parser {} にて括ります。
ビルド環境
- Windows 7
- clang 3.0
- VisualStudio コマンドプロンプト
- https://github.com/wates/parser
いずれかの文字にマッチさせる
テストコード
typedef parser::Char<'a','i','u','e','o'> charany; // 構文の定義
const char *source="ouieaieAaiueo";
while(charany::Parse(source))
printf("1");
printf("\n");
上記構文では aiueo のどれかにマッチした場合 true を返し、一文字進めます。 よって 1111111 と表示されることを目指します。マッチした分だけ source 変数が進むので while で回すだけで十分です。
Char 型に一文字ずつ設定でなく、文字列で渡したいところですが constexpr でやってしまうと後々対応しきれなくなりそうなので避けます。
実装
以下の実装方法は今後のケースでもよく使う形になります。
template<char C=0,char ...rest> // 引数を受けるときは変数名の前にドット三つ
struct Char
{
static bool Parse(const char *&text)
{
if(C==*text)
{
text++;
return true;
}
else
{
return Char<rest...>::Parse(text);// 受けた引数を使うときは変数の後ろにドット三つ
}
}
};
template<char...rest>
struct Char<0,rest...>
{
static bool Parse(const char *&text)
{
UNUSED(text);
return false;
}
};
非常に重要な最初の解説
- parser::Char<‘a’,’i’,’u’,’e’,’o’> は template<char C=0,char …rest> に解決が試行されます。よって、
- parser::Char<C=’a’, rest…=’i’,’u’,’e’,’o’> のようになります。
- C が ‘a’ なのでコンパイラは最初の if 内のコードはコンパイルでき、 else 内の Char<rest…>::Parse(text); の解決に取り掛かります。
- rest… は char…rest で与えられたコードが丸ごと渡されます。よって、
- Char<‘i’,’u’,’e’,’o’>::Parse(text); のようになります。次の呼び出しは
- parser::Char<C=’i’, rest…=’u’,’e’,’o’> です。最初の if はコンパイルされ、 else の解決によって一文字削られます。
- この繰り返しにて parser::Char<C=’o’,rest…=>がコンパイルされるとき、 else 内の呼び出しは、 Char<>::Parse(text); になりますが、
- ここでデフォルト引数が設定され、 Char<0>::Parse(text); の解決が行われます。
- めでたく後半の特殊化に当てはまり、無条件で false が返ります。
関数型言語をプレイしてた方であれば難なく理解できると思われますが、 C++ の手続きから見ると template の特殊化に加えて引数の再帰呼び出しが混ざって、複雑なメタプログラミングになります。可変長引数そのものには直接アクセスすることはできないので、必ずこういった再帰呼び出しと特殊化による終点が必要になります。
特殊化定義にて引数を可変長で受け取らずともほぼ同じように動作します。その場合、特殊化に使った数値ともマッチさせられますが、 ‘\0’ を指定した場合マッチングが終端文字を突き抜けてしまう可能性があります。
次は、一息いれるために次は簡単な実装をします。
文字の範囲マッチ
英数字全部指定となると結構長いので、 [a-z] や [0-9] のような表現ができると便利です。
// 与えられた条件にマッチするかどうか、マッチした文字列、残った文字列を表示する関数。
template<typename T>
void print_result(const char *source)
{
const char *from=source;
T t;
printf("\"%s\" as %s - read %d chars. rest - \"%s\"\n",from,t.Parse(source)?"GOOD":"BAD",source-from,source);
}
テストコード
// main
{
typedef parser::Range<'0','9'> num;
print_result<num>("0");
print_result<num>("5");
print_result<num>("9");
print_result<num>("a");
print_result<num>("A");
}
{
typedef parser::Range<'a','z'> az;
print_result<az>("9");
print_result<az>("a");
print_result<az>("z");
print_result<az>("A");
}
実装
template <char min,char max>
struct Range
{
static bool Parse(const char *&text)
{
if(min<=*text &&
max>=*text)
{
text++;
return true;
}
else
{
return false;
}
}
};
今回は楽勝です！ min 以上 max 以下なら一文字進めて true を返すだけになります。この程度でも min と max が確実に定数でなのでコンパイラにとっては最適化しやすくなります。しかし char 型のため、 0x7F を超える文字コードはマイナスになることに注意してください。
また min や max が #define されている環境では変数名を変更してください。
文字列マッチ
文字列マッチでは先ほどのいずれかの文字とのマッチをちょっと変更したものを利用します。仕組みはほぼ同じです。
テストコード
{
typedef parser::Text<'a','i','u','e','o'> text;
print_result<text>("aiueooo");
print_result<text>("aiuooo");
print_result<text>("aaiueo");
}
aiueo 最初のコードは完全にマッチし、 oo が残りますが、次はマッチせずに false になるうえ、全文字残ります。
後半も問題ナシですね！
実装
template<char C=0,char...rest>
struct Text
{
static bool Parse(const char *&text)
{
if(C==*text++ &&
Text<rest...>::Parse(text))
{
return true;
}
else
{
text--;
return false;
}
}
};
template<char...rest>
struct Text<0,rest...>
{
static bool Parse(const char *&text)
{
UNUSED(text);
return true;
}
};
文字を比較したらとりあえず一文字進め、失敗したら一文字戻します。そして最後まで一致していたら true を返します。動作が Char クラスと逆になります。
あってもなくてもよい、 0 個以上マッチ、 1 個以上マッチ
ここから三つは似たような式が続きます。また、テンプレート引数には今まで作ったクラスや今後作るクラスが入るため typename 型になり、将来のパース結果を受けるときにメンバ変数へのアクセシビリティを考えて引数を継承していきます。
あってもなくてもよい。
template <typename T>
struct Option
:virtual public T
{
bool Parse(const char *&text)
{
T::Parse(text);
return true;
}
};
0 個以上にマッチ。
template<typename T>
struct Any
:virtual public T
{
bool Parse(const char *&text)
{
while(T::Parse(text))
continue;
return true;
}
};
1 個以上にマッチ。
template<typename T>
struct More
:virtual public T
{
bool Parse(const char *&text)
{
if(T::Parse(text))
{
while(T::Parse(text))
continue;
return true;
}
else
{
return false;
}
}
};
それぞれ特に難しいことはありません。 template 引数に与えられたクラスの Parse を呼び出します。
次のコードを実行すると、削られ具合と成否の違いが出てきます。
{
typedef parser::Text<'f','o','o'> seq;
typedef parser::Option<seq> opt;
print_result<opt>("foofoofoo");
print_result<opt>("vvfoofoofoo");
typedef parser::Any<seq> any;
print_result<any>("foofoofoo");
print_result<any>("vvfoofoofoo");
typedef parser::More<seq> more;
print_result<more>("foofoofoo");
print_result<more>("vvfoofoofoo");
}
いずれかの条件にマッチ
template<typename T=void,typename...rest>
struct Or
:virtual public T
,virtual public Or<rest...>
{
bool Parse(const char *&text)
{
return T::Parse(text) || Or<rest...>::Parse(text);
}
};
template<typename...rest>
struct Or<void,rest...>
{
static bool Parse(const char *text)
{
UNUSED(text);
return false;
}
};
if と else を省略していますが、おおまかな流れは最初の Char 型と同じです。失敗したら先頭の型をひとつ削り、残った型で再帰呼び出し、最後は false にします。
ポインタの前後がないので最初より簡単ですね！
仮想継承にしているのは、先祖に同じ型が存在する可能性があるときに virtual にしているとアクセスしやすくなります。今回の場合は複数の先祖の中から、同じクラスが存在した場合は同一インスタンスであるほうが適していると思われます。同じ理由で Option や Any 、 More も仮想継承です。仮想継承にすることで「父だと思っていたら祖父でもあった！」みたいな sneg にも対応できます。
テストコード
{
using namespace parser;
typedef Or<Range<'0','9'>
,Range<'a','z'>
,Range<'A','Z'> > numbet;
print_result<numbet>("a");
print_result<numbet>("z");
print_result<numbet>("Z");
print_result<numbet>("0");
print_result<numbet>(" ");
print_result<numbet>(",");
typedef Any<numbet> numbets;
print_result<numbets>("abcABC912--");
print_result<numbets>("==abcABC912==");
}
前半は英数字マッチ、後半は Any と組み合わせてあるだけ削ります。
連続した条件にマッチ
最後にして最も重要なクラスです。
template<typename T=void,typename...rest>
struct Rule
:virtual public T
,virtual public Rule<rest...>
{
bool Parse(const char *&text)
{
const char *src=text;
if(T::Parse(text)&&
Rule<rest...>::Parse(text))
return true;
text=src;
return false;
}
};
template<typename...rest>
struct Rule<void,rest...>
{
static bool Parse(const char *text)
{
UNUSED(text);
return true;
}
};
先の Or クラスとほぼ同じで、条件が逆になっています。最後までいけば true です。また、失敗したときに Text クラスではデクリメントで済みましたが、こちらはスタックを利用して戻します。
テストコードは省略し、次の実践にいきます！
実践
手ごろなスペックに RFC4180 がありました。 CSV のざっくりとした仕様が書いてあります。プログラマ的に要点だけ抜き出します。
file = [header CRLF] record *(CRLF record) [CRLF]
header = name *(COMMA name)
record = field *(COMMA field)
name = field
field = (escaped / non-escaped)
escaped = DQUOTE *(TEXTDATA / COMMA / CR / LF / 2DQUOTE) DQUOTE
non-escaped = *TEXTDATA
COMMA = %x2C
CR = %x0D ;as per section 6.1 of RFC 2234 [2]
DQUOTE = %x22 ;as per section 6.1 of RFC 2234 [2]
LF = %x0A ;as per section 6.1 of RFC 2234 [2]
CRLF = CR LF ;as per section 6.1 of RFC 2234 [2]
TEXTDATA = %x20-21 / %x23-2B / %x2D-7E
BNF とは書き方がちょっと違いますが、感覚で読めると思われます。これを今まで作った template に当てはめていきます。 typedef なので依存関係順に(上下逆にして)定義していきます。見た目上の左辺と右辺も逆になります。
using namespace parser;
typedef Or<Range<0x20,0x21>,Range<0x23,0x2B>,Range<0x2D,0x7E> > TEXTDATA;
typedef Char<0x0A> LF;
typedef Char<0x22> DQUATE;
typedef Char<0x0D> CR;
typedef Rule<CR,LF> CRLF;
typedef Char<0x2C> COMMA;
typedef Any<TEXTDATA> non_escaped;
typedef Rule<DQUATE,Any<Or<TEXTDATA,COMMA,CR,LF,Rule<DQUATE,DQUATE> > >,DQUATE> escaped;
typedef Or<escaped,non_escaped> field;
typedef field name;
typedef Rule<field,Any<Rule<COMMA,field> > > record;
typedef Rule<name,Any<Rule<COMMA,name> > > header;
typedef Rule<Option<Rule<header,CRLF> >,record,Any<Rule<CRLF,record> >,Option<CRLF> > file;
再帰的に利用している定義がなかったので楽勝でした。そのまま今まで作った template に当てはめられます。 RFC 本文のほうには文章でも補足されているのでこのままでは完璧な CSV とはいえませんが、お手軽に使う分には良さそうです。実際に Parse してみます。
// 空行や空レコードは OK
print_result<file>("100,200,300\r\nabc,def,ghij,,\r\n\r\n");
// 二重引用符はカンマと一体でないとだめ
print_result<file>("100,200,300\r\nabc,d\"ef,g\"hij");
print_result<file>("100,200,300\r\nabc,\"def,g\",hij");
// 改行は CRLF でないとだめ
// ヘッダの最後のほうまでマッチするが CRLF が無いのでヘッダに完全にはマッチしない
// その後レコードには CRLF は不要なのでレコードとして一行目だけマッチする
print_result<file>("100,200,300\nabc,def,ghij");
// 二重引用符を含めるなら二連続にしてさらに二重引用符で括ってある必要がある
print_result<file>("100,200,\"3\"\"00\"\r\nabc,def,ghij");
マッチした量しか出ないので print では非常に面白くない結果になります。
そこで値を抜き出すコードを埋め込みます。再帰的に Parse がコールされるので、同じ関数を定義すれば途中で引っかかります。
template<typename T>
struct Value
:public T
{
char value[16][16];
int size;
Value():size(0){};
bool Parse(const char *&text)
{
const char *begin=text;
if(this->T::Parse(text))
{
memcpy(value[size],begin,text-begin);
value[size++][text-begin]='\0';
return true;
}
return false;
}
};
template<typename T>
struct Record
{
T record[16];
int record_size;
Record():record_size(0){};
bool Parse(const char *&text)
{
if(record[record_size].Parse(text))
{
record_size++;
return true;
}
return false;
}
};
STL のビルドが期待通りに行かなかったので危険ですがベタな書き方にしました。 Value クラスではマッチするたびに、配列に文字列を追加していきます。 Record クラスでは、 T を継承せず、配列としてインスタンスを保持し、マッチするたびにインスタンスを消費させます。
あとはこいつを条件に加えるだけです。 Value は field へ。 Record は record をそれぞれ括ります。
typedef Value<Or<escaped,non_escaped> > field;
typedef Record<Rule<field,Any<Rule<COMMA,field> > > > record;
field が呼び出されると Value にフックされます。 record も同じです。
早速実行コード
file csv;
const char *text="100,200,\"3\"\"00\"\r\nabc,def,ghij\r\nfoo,bar,baz";
csv.Parse(text);
printf("%d\n",csv.size);
printf("%d\n",csv.record_size);
for(int j=0;j<csv.size;j++)
printf("%d : %s\n",j,csv.value[j]);
for(int i=0;i<csv.record_size;i++)
for(int j=0;j<csv.record[i].size;j++)
printf("%d,%d : %s\n",i,j,csv.record[i].value[j]);
csv インスタンスは Value と Record を多重継承しています。また Record は Value を配列で保持しています。よって Value はヘッダにマッチし、 Record は各行の Value にマッチするはずです。
そして実行結果。
3 2 0 : 100 1 : 200 2 : "3""00" 0,0 : abc 0,1 : def 0,2 : ghij 1,0 : foo 1,1 : bar 1,2 : baz
最初の csv.size は Value のメンバです。よって、レコードに当てはまらないヘッダの部分の数です。次がレコードの数になり、二行分の 2 です。ヘッダ、レコードの順に抜き出せていることがわかります。 vector や string を使い operator[] も定義したら結構きれいになるんじゃないかなと思います。 escaped 型の中にアクションを埋め込めばダブルクォートも外せます。
まとめ
- 普通のプログラマが十分にトレースできる量のコードで本格的パース。わずかな量のヘッダファイルのみで実現できる。
- Char Text Range クラスを char でなく int にするだけで Unicode に対応できる。 UTF8 対応をガチでやると美しくないコードになる。
- typedef だけでは定義の再帰やネストは作れない。たとえば element = <tag> element </tag> のようなものは複雑になってしまう。
- Variadic Template あまり利用していない。 C++03 フレンドリー。
- フックしてアクションを増やしていく。他のツールと似てると思う。
- 条件にマッチしてる文字列であれば、高速動作。オプティマイザと相性が良いがコンパイル後のサイズが大きくなる。
- 合理的で virtual public な多重継承の出番！
- sizeof すると….
このエントリは C++11 Advent Calendar 2011 のために書かれました。