|
|
マルチパス | |
 |
 |
 |
Spirit でバックトラッキングする為には、前方向、双方向、あるいはランダムアクセス型のイテレータを用いる必要がある。 バックトラッキングなので、入力イテレータを用いることは出来ない。 従って、入力イテレータのカテゴリに分類される標準ライブラリクラス istreambuf_iterator および istream_iterator は利用できない。 これに該当する別の入力イテレータとしては、 LEX のようなレキサをラップするものがある。
 入力イテレータ 総じて Spirit はバックトラッキング構文解析器であるが、これは絶対条件ではない。 将来的には、１文字（トークン）以上の先読みを必要としない、より多くの決定性パーサが現れるだろう。 そうしたパーサでは istream_iterator のような入力イテレータを利用できるようになるだろう。 |
残念ながら入力イテレータにはイテレータの位置を保存する方法がないので、 Spirit のバックトラッキングでは正しく動作しない。 この問題の一つの解決策は、単に構文解析されるすべてのデータを vector や deque のようなコンテナに読み込み、 その後でそのコンテナの begin と end を Spirit に渡すことである。 この方法はある種のアプリケーションに対してはメモリを要求しすぎる。 それこそが multi_pass イテレータが作成された理由である。
multi_pass イテレータは、あらゆる入力イテレータを Spirit での使用に適した前方向イテレータに変換する。 multi_pass は必要な時にデータをバッファリングし、 そのイテレータのコピーがただ一つだけ存在する時はそのバッファリングを破棄する。
multi_pass イテレータを用いる場合、文法は注意深く設計しなければならない。 選択を含むもののように、バックトラックを必要としそうなルールは データをバッファリングさせる。 利用に最適なルールはシーケンスと繰り返しである。 a >> b という形のシーケンスはデータをまったくバッファリングしない。 kleene_star (*a) や (+a) のような正符号などの あらゆる繰り返しルールは、現在の繰り返しに関するデータのみをバッファリングする。
典型的な文法では曖昧性、ひいては先読みはしばしば局所化される。 実際、上手く設計された多くの言語は完全に決定性で、先読みはまったく必要としない。 入力から最初の文字を読んでみてすぐに採用する選択岐を決定する。 しかし、非常に曖昧な文法でさえ、 選択は *(a | b | c | d) のような形になることが多い。 入力イテレータは先へ進み、決して始端で行き詰まったりしない。 例として Pascal の断片を見てみよう：
program =
programHeading >> block >> '.'
;
block =
*( labelDeclarationPart
| constantDefinitionPart
| typeDefinitionPart
| variableDeclarationPart
| procedureAndFunctionDeclarationPart
)
>> statementPart
;
ルール block の Kleene star の内側にある選択に注目して欲しい。 そのルールは入力を線形に消費し、繰り返すごとに過去の履歴を捨てる。 これが完全に決定性 LL(1) 文法であれば、 １文字（トークン）読んでみるだけで選ばれない選択肢かどうかが分かる。 １文字（トークン）以上消費する選択肢が紛れもなく選ばれるものである。 その後、 Kleene star は次へ進む。
非メンバ関数を使う場合は注意すること。
これらはどれも渡されたイテレータのコピーを作る。
さて、 multi_pass を使う際に注意すべき機能について講義してきたが、
たぶんあなたは、 multi_pass は利用に当たっての制限が厳しすぎると思われただろう。
それは事実ではない。
もし文法が決定性なものであれば、
データが不要なときにバッファリングされないように flush_multi_pass を利用することができる。
再び、スキャナの節で使い始めた例を続けることにしよう。 以下は multi_pass を使った例である： 今回は、 istreambuf_iterator を用いて入力ストリームから入力を取り出す。
#include <boost/spirit/iterator/multi_pass.hpp>
using spirit::multi_pass;
using spirit::make_multi_pass;
ifstream in("input_file.txt"); // we get our input from this file
typedef char char_t;
typedef multi_pass<istreambuf_iterator<char_t> > iterator_t;
typedef skipper<iterator_t> skipper_t;
typedef scanner<iterator_t> scanner_t;
typedef rule<scanner_t> rule_t;
skipper_t skip(space, make_multi_pass(istreambuf_iterator<char_t>());
scanner_t first(make_multi_pass(istreambuf_iterator<char_t>(in)), &skip);
scanner_t last(make_multi_pass(istreambuf_iterator<char_t>()), &skip);
rule_t n_list = real_p >> *(',' >> real_p);
match m = n_list.parse(first, last);
flush_multi_pass は定義済みの疑似パーサである。 multi_pass とともに用いられると、このパーサは multi_pass::clear_queue() を呼び出す。 これはバッファリングされたあらゆるデータを消去させる。 また multi_pass の他のすべてのコピーを無効にし、利用できないようにする。 もしそれらが用いられると、 boost::illegal_backtracking 例外が発生する。
multi_pass はテンプレート化されたポリシー駆動型のクラス(templated policy driven class)である。 ここまでの話は、（ポリシーを使うより以前に） multi_pass が元来どのように実装されていたかを述べたものであり、現在のデフォルトの設定である。 しかし、 multi_pass はそれ以上の能力を持っている。 制限を受けないポリシーの性質のおかげで、 想像だにしなかった方法で multi_pass を振る舞わせるような独自のポリシーを書くことができる。
multi_pass クラスは五つのテンプレートパラメータを持つ：
すべての定義済み multi_pass ポリシーは名前空間 boost::spirit::multi_pass_policies の中にある。
このポリシーは multi_pass が InputT 型の入力イテレータから読み込むように指示する。
このポリシーは yylex() を呼び出すことによってその入力を得る。 この関数は典型的には LEX が生成したスキャナによって提供される。 もしこのポリシーを使うなら、 LEX の生成したスキャナをコードにリンクしなければならない。
この入力ポリシーは InputT 型のファンクタを呼び出すことによってデータを得る。 そのファンクタはある種の必要条件を満たさなければならない。 それは operator() から返される型の typedef である result_type を持たなければならない。 また、 入力ポリシーは入力の終端に至ったことを判断する方法を必要とするので、 そのファンクタは result_type の変数と比較できる eof という static 変数を持たなければならない。
このクラスは参照カウント方式を用いる。 multi_pass はカウントがゼロになると共有コンポーネントを削除する。
このポリシーが使われると、 最初に作成された multi_pass が共有データを削除する。 各コピーは共有データの所有権を取得しない。 イテレータの動的アロケーションが為されないので、これは spirit に対して上手く働く。 すべてのコピーはスタック上に作られるので、 オリジナルのイテレータが最も長い寿命を持つことになる。
このポリシーはまったくチェックを行わない。
buf_id_check はバッファ ID またはバッファの年齢を手元に置いておく。 multi_pass イテレータの clear_queue() が呼び出されるときはいつでも 他のすべてのイテレータが無効になり得る。 clear_queue() が呼ばれると、 buf_id_check はバッファ ID をインクリメントする。 イテレータが参照剥がし(dereference)されると、このポリシーは そのイテレータのバッファ ID が共有されたバッファ ID と一致するかチェックする。 このポリシーは StoragePolicy の std_deque と一緒に用いられたとき最も効率がよい。 StoragePolicy の fixed_size_queue は範囲外の参照剥がし(dereference)を検出しないので、これと一緒に用いるべきではない。
このポリシーはまだ実装されていない。 実装されれば、すべてのイテレータを追跡し、それらすべてが有効であるか確認する。
このポリシーは、バッファリングされたすべてのデータを std::deque に保存する。 すべてのデータは一つ以上のイテレータがある限り保持される。 ひとたびイテレータカウントが１未満になれば、そのキューはもはや必要とされず、クリアされ、メモリを解放する。 そのキューは multi_pass::clear_queue() を呼び出すことで強制的にクリアできる。
fixed_size_queue はサイズが N+1 で N 個の要素を格納する循環バッファを保持する。 fixed_size_queue はキューのサイズを指定する std::size_t パラメータを持つテンプレートである。 N がパーサに対して十分に大きいことを保証するのはあなたの責任である。 最も先頭にあるイテレータがインクリメントされると、バッファの最後の文字は自動的に消去される。 現在のところ、あるイテレータがずっと後まで続きすぎて無効になるかどうか知る術はない。 通常のイテレータ操作の間、このポリシーによって動的なアロケーションが行われることはない。 初期構築時のみ行われる。 この StoragePolicy のメモリ使用量は N+1 バイトに設定され、 無制限な std_deque とは異なる。
ポリシーを基盤とする設計の美しさは、 望みのポリシーを選択することによって、 独自のカスタムクラスを作成するためにポリシーを混合したりマッチしたりできるということである。 以下は istream_iterator<char> をラップするカスタム multi_pass を指定する方法の例である。 これは OnwershipPolicy として first_owner を、 CheckingPolicy として no_check を用いているので、デフォルトよりも若干効率が良くなっている：
typedef multi_pass<
istream_iterator<char>,
multi_pass_policies::input_iterator,
multi_pass_policies::first_owner,
multi_pass_policies::no_check,
multi_pass_policies::std_deque
> first_owner_multi_pass_t;
multi_pass のデフォルトのテンプレートパラメータは以下の通りである： InputPolicy として input_iterator 、 OwnershipPolicy として ref_counted 、 CheckingPolicy として buf_id_check 、 そして StoragePolicy として std_deque 。 そのため、 multi_pass<istream_iterator<char> > を用いると、 istream_iterator<char> をラップする一方で それら定義済みの振る舞いが得られる。
look_ahead と呼ばれるもう一つの定義済みクラスがある。 look_ahead は二つのテンプレートパラメータを持つ： ラップする入力イテレータの型である InputT と、 fixed_size_queue ポリシーにバッファリングのサイズを指定する std::size_t の N である。 デフォルトの multi_pass の設定が無難に設計されている一方で、 look_ahead は速度を目的に設計されている。 look_ahead は multi_pass から以下のポリシーで派生されたものである： InputPolicy として input_iterator 、 OwnershipPolicy として first_owner 、 CheckingPolicy として no_check 、 そして StoragePolicy として fixed_size_queue<N> 。
InputPolicy に functor_input を使いたいのであれば、 multi_pass へ入力を供給する独自のファンクタを書けばよい。 そのファンクタは二つの必要条件を満たさなければならない。 それは operator() の戻り値型を指定する result_type という typedef を持たなければならない。これは STL の標準的な流儀である。 また、それは入力が終端に達したかどうか知るために比較される eof と呼ばれる static 変数を供給しなければならない。以下は例である：
class my_functor
{
public:
typedef char result_type;
my_functor()
: c('A') {}
char operator()() const
{
if (c == 'M')
return eof;
else
return c++;
}
static result_type eof;
private:
char c;
};
my_functor::result_type my_functor::eof = '\0';
typedef multi_pass<
my_functor,
multi_pass_policies::functor_input,
multi_pass_policies::first_owner,
multi_pass_policies::no_check,
multi_pass_policies::std_deque
> functor_multi_pass_t;
functor_multi_pass_t first = functor_multi_pass_t(my_functor());
functor_multi_pass_t last;
InputPolicy は以下のインタフェースを持たなければならない：
class my_input_policy // ポリシーの名称
{
public:
// クラス inner は multi_pass に InputT として
// 与えられた型によってインスタンス化される。
template <typename InputT>
class inner
{
public:
// これらの typedefs は multi_pass の iterator_traits を決定する
typedef x value_type;
typedef x difference_type;
typedef x pointer;
typedef x reference;
protected:
inner();
inner(InputT x);
inner(inner const& x);
// すべての状態を削除または整理する
void destroy();
// もし *this と x が同じ入力を持っていれば真を返す
bool same_input(inner const& x) const;
void swap(inner& x);
public:
// 入力からインスタンスを得る
result_type get_input() const;
// 入力を進める
void advance_input();
// 入力が終端にあれば真を返す
bool input_at_eof() const;
};
};
multi_pass は複数のコピーの間でバッファと入力を共有するので、 クラス inner は入力へのポインタを保持すべきである。 コピーコンストラクタは単にそのポインタをコピーすべきである。 destroy() はそれを削除すべきである。 same_input はそのポインタを比較すべきである。 さらなる詳細については様々な InputPolicy の実装を参照のこと。
OwnershipPolicy は以下のインタフェースを持たなければならない：
class my_ownership_policy
{
protected:
my_ownership_policy();
my_ownership_policy(my_ownership_policy const& x);
// clone はイテレータのコピーが作られるときに呼び出される
void clone();
// コピーが削除されるとき呼び出される。リソースが
// 解放されるべきであることを示すために真を返す
bool release();
void swap(my_ownership_policy& x);
public:
// 存在するイテレータが一つだけなら真を返す。
// もしこれが真を返せば std_dequeue StoragePolicy は
// バッファリングしたデータを解放する。
bool unique() const;
};
CheckingPolicy は以下のインタフェースを持たなければならない：
class my_check
{
protected:
my_check();
my_check(my_check const& x);
void destroy();
void swap(my_check& x);
// check はこのイテレータが有効であるか確認すべきである
void check() const;
void clear_queue();
};
StoragePolicy は以下のインタフェースを持たなければならない：
class my_storage_policy
{
public:
// クラス inner は InputPolicy から value_type でインスタンス化される
template <typename ValueT>
class inner
{
protected:
inner();
inner(inner const& x);
// 最後のイテレータのデストラクタから呼び出される
void destroy();
void swap(inner& x);
// これはイテレータが参照剥がしされたときに呼び出される。
// テンプレートメソッドなので multi_pass イテレータの型を復元し、
// アクセスすることができる。
template <typename MultiPassT>
static ValueT dereference(MultiPassT const& mp);
// これはイテレータがインクリメントされるとき呼び出される。
// テンプレートメソッドなので multi_pass イテレータの型を復元し、
// アクセスすることができる。
template <typename MultiPassT>
static void increment(MultiPassT& mp);
void clear_queue();
// イテレータが eof イテレータであるかどうかを決定するために呼び出される
template <typename MultiPassT>
static bool is_eof(MultiPassT const& mp);
// operator== から呼び出される
bool equal_to(inner const& x) const;
// operator< から呼び出される
bool less_than(inner const& x) const;
}; // クラス inner
};
StoragePolicy は書き方がもっともトリッキーなポリシーである。 独自のものを試作する前に、既存の StoragePolicy クラスを研究し、理解すべきである。
|
|
|
Copyright © 2001-2002 Daniel C. Nuffer
Permission to copy, use, modify, sell and distribute this document
is granted provided this copyright notice appears in all copies. This document
is provided "as is" without express or implied warranty, and with
no claim as to its suitability for any purpose.
Japanese Translation Copyright © 2003-2004 Kent.N
オリジナルの、及びこの著作権表示が全ての複製の中に現れる限り、この文書の複製、利用、変更、販売そして配布を認める。このドキュメントは「あるがまま」に提供されており、いかなる明示的、暗黙的保証も行わない。また、いかなる目的に対しても、その利用が適していることを関知しない。
このドキュメントの対象: Boost Version 1.30.0
最新版ドキュメント（英語）