FAQ

• スキャナの働き
• 左再帰の削除
• lexeme_d ディレクティブとルール
• Kleene Star の無限ループ
• Boost CVS と Spirit CVS

スキャナの働き

問：なぜこれはコンパイルできないのですか？

    rule<> r = /*...*/;
    parse("hello world", r, space_p); // 駄目［字句レベル構文解析を試みた］

しかし、スキップパーサを取り除くと、再びすべて正常に戻ります：

    rule<> r = *anychar_p;
    parse("hello world", r); // ＯＫ［文字レベル構文解析］

時々、 Spirit が提供する parse 関数のいずれかにルールを渡したいと思うだろう。 問題は、ルールはスキャナ型によってパラメータ化されたテンプレートクラスであるということである。 これはかなり厄介だが、避けて通ることは出来ない：ルールはスキャナに束縛されている。 分かりづらいが、このスキャナはルールの parse メンバ関数に最終的に渡されるスキャナと互換性がなければならない。 さもなければ、コンパイラはエラーを返す。

なぜ一つ目の parse 呼び出しはコンパイルできないのか？スキャナが非互換だからである。 その舞台裏では、 parse 非メンバ関数は渡されたイテレータからスキャナを作成している。一つ目の parse 呼び出しでは、作成されたスキャナはふつうの(plain vanilla) scanner<> である。 これは rule<> のデフォルトのスキャナの型である。 ［ルールのデフォルトテンプレートパラメータを参照］。 二つ目の呼び出しは phrase_scanner_t 型のスキャナを作成する：

    typedef skipper_iteration_policy<>                  iter_policy_t;
    typedef scanner_policies<iter_policy_t>             scanner_policies_t;
    typedef scanner<char const*, scanner_policies_t>    phrase_scanner_t;

従って、二つ目の呼び出しが成功するためには、そのルールは rule<phrase_scanner_t> でパラメータ化されなければならない：

    rule<phrase_scanner_t> r = *anychar_p;
    parse("hello world", r, space_p);       //  ＯＫ［文字レベル構文解析］

ただし、 phrase_scanner_t が互換性を持つのは、 char const* イテレータとスキップパーサとして space_p を利用している場合に限るということに注意を払って欲しい。 そうでなければ、スキャナの正しい型を見つけなければならなくなる。 これは正しく行おうとすると非常に退屈な作業だ。 この問題を考慮すると、 parse 関数の引数にルールを渡すことは避けるに限る。 覚えておいて欲しい、 これはルールでのみ起こるということは覚えておいて欲しい。 ルールは、特定のスキャナ型に束縛される唯一のパーサである。 例えば：

    parse("hello world", *anychar_p);           //  OK  [character level parsing]
    parse("hello world", *anychar_p, space_p);  //  OK  [phrase level parsing

左再帰の削除

問： 私は YACC の文法を移植しました。 かなり「骨の折れる」作業でした - パーサそのものはエラーなしにコンパイルできたのに構文解析させようとすると "invalid page fault" をよこすんです。 以下のような文法の断片まで問題を追い詰めました：

    or_expr = xor_expr | (or_expr >> VBAR >> xor_expr);

あなたがすべきなのは直接または間接の左再帰を取り除くことである。 これはページング違反を引き起こす。そのプログラムは無限ループに陥るからだ。 上記のコードは YACC のようなボトムアップ構文解析器には良いものであるが、 Spirit のような LL 構文解析器にとってはそうではない。

以下は examples/applications にある Hartmut Kaiser の C パーサ の中のあるルールと同様のものである。

    inclusive_or_expression
    = exclusive_or_expression
    | inclusive_or_expression >> OR >> exclusive_or_expression
    ;

左再帰から右再帰へと変換すると、こうなる：

    inclusive_or_expression
    = exclusive_or_expression >> inclusive_or_expression_helper
    ;

    inclusive_or_expression_helper
    = OR >> exclusive_or_expression >> inclusive_or_expression_helper
    | epsilon_p
    ;

先に進もう。次のコードは

    r = a | epsilon_p;

以下と等価である

    r = !a;

ので、 inclusive_or_expression_helper を次のように単純化できる：

    inclusive_or_expression_helper
    = !(OR >> exclusive_or_expression >> inclusive_or_expression_helper)
    ;

さて、以下は

    r = !(a >> r);

次のものと等価であるので

    r = *a;

このようになる：

    inclusive_or_expression_helper
    = *(OR >> exclusive_or_expression)
    ;

結局、 inclusive_or_expression を完全に単純化すると、こうなる：

    inclusive_or_expression
    = exclusive_or_expression >> *(OR >> exclusive_or_expression)
    ;

電卓のことを思い出した。手短に言えば、以下の YACC の擬似コードは

    a = b | a >> op >> b;

Spirit ではこうなる：

    a = b >> *(op >> b);

なんて簡単なんだろう。見てよ、再帰はなし、繰り返しだけ。

lexeme_d ディレクティブとルール

問： lexeme_d はルールを含む式はサポートしないのですか？下の例で、 atomicRule の定義はコンパイルできるのに、

    rule<ScannerT> atomicRule
        = lexeme_d[(alpha_p | '_') >> *(alnum_p | '.' | '-' | '_')];

alnum_p | '.' | '-' | '_' を独自のルールに移すと、 コンパイラは const scanner<...> から const phrase_scaner_t& への変換に関するエラーを返します。

    rule<ScannerT> ch 
        = alnum_p | '.' | '-' | '_';

    rule<ScannerT> compositeRule
        = lexeme_d[(alpha_p | '_') >> *(ch)]; // <- エラーの源

あなたは lexeme_d とルールを混ぜてはいけないという印象を持ったようだ。実際のところ、この問題は最初の FAQ 項目：スキャナの働きに関係している。 より正確には、その lexeme_d ディレクティブと互換性のないスキャナ型を持つルールを混ぜることは出来ない。 この問題はもっと微妙だ。スキャナの非互換性を引き起こすのはそのディレクティブ自身である。 lexeme_d ディレクティブはそれが受け取るスキャナをスキップパーサを無効にするなにかに変換する。 このスキップしないパーサは、残念ながら、変換が行われる前の元のスキャナと互換性がない。

一番簡単な解決策は lexeme_d の中でルールを使わないことだ。 あるいは、 もし本当に lexeme_d の内側により複雑なパーサを必要とするなら、 lexeme_d をサブルールや文法に用いることができる。 もし本当にルールを使わなければならないなら、 そのディレクティブが用いるスキャナを正確に知っておく必要がある。 ここでは lexeme_scanner メタ関数があなたの友となる。 上述の例は、 ch ルールに正しいスキャナ型を与えると期待通りに動作するだろう：

    rule<lexeme_scanner<ScannerT>::type> ch 
        = alnum_p | '.' | '-' | '_';

注意：テンプレートクラスか関数の内側で lexeme_scanner を使う場合、その前に "typename" を必ず加えること。

as_lower_d ディレクティブの内側でルールを使う際も同じ事態が起こる。その場合は、 as_lower_scanner を利用できる。 lexeme_scanner と as_lower_scanner を参照。

Kleene Star の無限ループ

Question: なぜこれは永久にループするのですか？

    rule<> optional = !(str_p("optional"));
    rule<> list_of_optional = *optional;

これに伴う問題は、 kleene star がその内側のパーサから no-match を得るまでループし続けることである。 optional ルールは省略可能であるため、常にマッチを返す。 たとえ入力が "optional" にマッチしなくても、長さ０のマッチを返す。 list_of_optional は、 optional が決して no-match を返さないにもかかわらず、 optional を永久に呼び出し続ける。 よって一般には、 "nullable" になり得る（長さ０のマッチを返し得る）あらゆるルールは kleene star の内側に置いてはならない。

Boost CVS と Spirit CVS

問： Boost CVS と Spirit CVS がありますが、 Spirit の今後の開発はどちらで行われるのですか？

開発は概ね Spirit の CVS で行われる。 しかし、新しいバージョンの Spirit は折に触れて Boost に統合される。 これが起こった時は、開発は Boost CVS で行われる。 Spirit CVS の状態が変化したときは Spirit メーリングリストでアナウンスがあるだろう。

Copyright © 1998-2003 Joel de Guzman

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 Kent.N

オリジナルの、及びこの著作権表示が全ての複製の中に現れる限り、この文書の複製、利用、変更、販売そして配布を認める。このドキュメントは「あるがまま」に提供されており、いかなる明示的、暗黙的保証も行わない。また、いかなる目的に対しても、その利用が適していることを関知しない。

このドキュメントの対象: Boost Version 1.30.0
最新版ドキュメント（英語）