2012年09月09日

N6XBasicChecker(4)boost::spirit::qi::ruleの基礎

今回はboost::spiritを使った構文解析ツールの構成について書きたいと思います。

最初にお断りしておくと、このブログの情報だけからspiritを理解するのは無理です。
spiritに触れている日本語のブログエントリもすでに複数ありますが、やはりブログの情報だけで全容を理解できるものではありません。
英語ですが、結局boost本家のドキュメントが一番丁寧に説明されており、これを頭から「飛ばさずに」読むのが一番の近道です。
構文解析自体の知識も前提として要求されますので、予備知識がない人はコンパイラ理論の本を1冊読んだほうが良いでしょう。
私はとりあえず以下の本を読みました。
コンパイラ入門―構文解析の原理とlex/yacc、C言語による実装 (Computer Science Library) [単行本] / 山下 義行 (著); サイエンス社 (刊)

なので、本ブログでもspiritそのものの解説はオフィシャルに譲り、実際にプログラムを書く際にハマりそうなポイントを解説していきたいと思います。
ここでの構文解析の基本は入力(プログラム)を構文規則(rule)に合致しているか判定します。
ここで言うプログラムは、P6のBASICプログラムで、Txt2Bas形式のテキストファイルです。
ruleとは、boost::spiritに定義されているクラスで、ここにN6XBasicの文法を定義していきます。

本文にはソースの断片しか載せないので、spiritの調べ物で来た方はこちらでソースコードをダウンロードしてください。
N6XBasicChecker-1.1-src.zip

■spiritのライブラリ
通常こういうパーサージェネレータは、字句解析→構文解析という手順を踏みます。
N6XBasicCheckerは構文チェックして終わりですが、普通はこのあとコンパイルや整形出力などのアウトプットがあります。
boost::spiritではそれぞれに名前がついていて、
字句解析: boost::spirit::lex
構文解析: boost::spirit::qi
出力:   boost::spirit::karma
というライブラリ名になっています。
が、spiritでは字句解析と構文解析の区分が割と曖昧です。
N6XBasicCheckerはlexを使わず、qiだけで全てやっています。

■ruleクラスの宣言
話は戻りますが、ruleはqiに属するクラスで、以下のように宣言します。

typedef std::wstring::const_iterator Iterator;
typedef qi::rule<Iterator, unsigned()> UintRule;
typedef qi::rule<Iterator, int()> IntRule;
typedef qi::rule<Iterator, float()> FloatRule;
typedef qi::rule<Iterator, sw::blank_type> BasicRule;
typedef qi::rule<Iterator, std::wstring(), sw::blank_type> StringRule;

ruleクラスはテンプレートクラスで、テンプレート引数には
・文字列操作用のイテレータ
・スキッパー(空白、改行など無視する文字種別)
・アトリビュート(属性)
を取ります。
属性とは、ルールにマッチした文字列をどのような型として扱うかを指定するものです。
これはそのうち解説するセマンティックアクションのところで使いますので、とりあえず放置で。
spirit触り始めた当時、いろんなサンプルで上記のテンプレート引数の順番がまちまちなのでかなり悩んだのですが、このテンプレート引数の順番は不問という変態仕様です。
テンプレートクラスはクラス名が長いので、typedefを使って定義しておきます。
また、名前空間名も長いので、だいたいみんな短縮形を定義します。

namespace spirit = boost::spirit;
namespace qi = boost::spirit::qi;
namespace phx = boost::phoenix;
namespace sw = qi::standard_wide;
using sw::char_;
using qi::_1;
using qi::int_;
using qi::uint_;
using qi::double_;
using qi::hex;
using qi::lit;
using phx::ref;


■エンコーディング名前空間
qi::standard_wideというのは、ワイド文字列を表す名前空間です。
この手のパーサージェネレータはマルチバイト文字列を扱えないものが多いので、N6XBasicCheckerではワイド文字列に変換してパースします。

■ruleの組み立て
ruleは、まずトークン単位の細かいルールを定義し、それを組み合わせることで構文レベルのより大きなルールを構築していきます。
例として、「A1$」という入力文字列を文字列変数名だと認識するルールを書いてみます。

StringRule num_var
= qi::raw[sw::alpha >> qi::repeat(0, 4)[sw::alnum]];
StringRule str_var
= qi::raw[sw::alpha >> qi::repeat(0, 4)[sw::alnum] >> sw::string(L"$")];
StringRule var
= qi::raw[str_var | num_var];

std::wstring a = L"A1$";
bool r = qi::phrase_parse(a.begin(), a.end(), var, sw::blank);

num_varというのは、「数値型変数名」を定義したルールです。今回「数値型としてではなく、文字列型として認識する」というデモのために入れています。
sw::alphaというのはspiritの組み込みルールで、アルファベットにマッチします。swというのは先程も触れたとおり、qi::standard_wideのエイリアスです。sw::alnumも同様で、こちらはアルファベットと数字にマッチします。
num_varが定義しているのは「1文字目はアルファベット、そのあとアルファベットまたは数字が0〜4文字続く」というルールです。P6では変数名は5文字まで使えます。(識別されるのは先頭2文字のみ)
sw::alphaとsw::alnumの間にある「>>」という演算子は「後続」を表し、この順番で出現するという事を表しています。ルール間をオーバーロードされた演算子でつなぐというのがspiritの特徴であり変態と言われる所以であります。
qi::rawというのは、マッチした範囲をイテレータとして返すもので、属性をstringにするために必要なおまじないです。
str_varが「数値型変数名」です。最後に「$」がつく以外は数値型変数と同じです。
varというのは、数値変数、文字列変数をひっくるめた変数の総称として定義したルールです。
「|」という演算子は「または」を意味し、「文字列型変数または数値型変数」というルールになります。
キモは「|」でつなぐルールの順番です。「|」でつないだルールはその順番に評価されます。spiritは先頭から入力文字列を読んでいき、マッチするルールが見つかった瞬間に確定してしまいます。もし「num_var|str_var」と逆の順番でルールを定義してしまうと、「A1」を数値型変数として認識し、その後の「$」が宙ぶらりんになってエラーになります。
「|」でつなぐルールは、長い順からというのがセオリーです。(私の中で)
最後のqi::phrase_parseが実際に構文解析処理を呼び出す関数です。入力文字列(A1$)と判定するルール(var)、それからスキッパーを引数として与えます。
スキッパーはsw::blankで、これは空白またはTABを無視して読み飛ばすことを意味します。sw::spaceを指定すると改行も読み飛ばします。BASICの場合改行は読み飛ばされると困るので、ここではblankを使います。
恐ろしいことに、P6のBASICの場合、「A1$」と「A 1 $」は等価です。なのでこのスキッパーが重要な役割を果たすことになります。

次回はもう少し複雑なルールの構築ノウハウについて書いてみます。
posted by eighttails at 23:32| Comment(0) | N6XBasicChecker | このブログの読者になる | 更新情報をチェックする
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント: