3

初めて霊を使います。ブール式 (&、|、および ! 演算子のみを使用) パーサーを作成しようとしています。次のように文法を定義しました。

template <typename Iterator>
struct boolean_expression_parser : qi::grammar<Iterator, std::string(), ascii::space_type>
{
    boolean_expression_parser() : boolean_expression_parser::base_type(expr)
    {
        using namespace qi;
        using ascii::char_;
        using boost::spirit::ascii::alnum;
        using namespace qi::labels;

        using phoenix::construct;
        using phoenix::val;

        operand %= lexeme[+(alnum)];

        simple_expr %= ('(' > expr > ')') | operand;

        unary_expr  %= ('!' > simple_expr ) ;

        and_expr %= ( expr > '*' > expr);

        or_expr  %= (expr > '|' > expr);

        expr %= simple_expr | unary_expr | *and_expr | *or_expr;

        // on_error<fail>
        //         (
        //             unary_expr,
        //             std::cout
        //             << val("Error! Expecting ")
        //             << _4                               // what failed?
        //             << val(" here: \"")
        //             << construct<std::string>(_3, _2)   // iterators to error-pos, end
        //             << val("\"")
        //             << std::endl
        //          );
    }

    qi::rule<Iterator, std::string(), ascii::space_type> operand;
    qi::rule<Iterator, std::string(), ascii::space_type> simple_expr;
    qi::rule<Iterator, std::string(), ascii::space_type> unary_expr;
    qi::rule<Iterator, std::string(), ascii::space_type> and_expr;
    qi::rule<Iterator, std::string(), ascii::space_type> or_expr;
    qi::rule<Iterator, std::string(), ascii::space_type> expr;
};

ここでいくつかのハードルに直面しています：

  1. バイナリ式（「A + B」など）では機能しません。単項式 (「!(A)」や「(!A)」など) では正常に機能しています。

誰かが私が間違っていることを指摘できますか?

  1. ツリー形式で保存したい（BDDを構築したいので）。誰かがそれを行う方法を教えてもらえますか?

  2. また、有効にしても on_error<> が機能しないのはなぜですか?

ブースト 1.49 と gcc-4.2.2 を使用しています。

よろしく〜 そうめん

4

1 に答える 1

3

パーサーには非常に多くの問題があります。まず、ここで左側の再帰に遭遇するため、パーサーはStack Overflowでクラッシュします。文法は次のようになります。

expr = or_expr;
or_expr = and_expr >> -('|' > expr);
and_expr = unary_expr >> -('*' > expr);
unary_expr = ('!' > expr) | operand | ('(' >> expr > ')');

この場合、左再帰はなく、すべてが解析されます。

なぜあなたのアプローチは失敗したのですか？あなたの場合：

input: A * B
1: expr
  1.1: check simple_expr 
       -> fail at '(', try next
       -> operand matches, return from simple_expr
  matched, return.

したがって、 のみを解析Aし、必ず返す必要がありますが、入力は完全には解析されません。

>また、使いすぎた演算子。その目的は、その後に一致がない場合に解析を失敗させることです。一方、オペレーター>>は戻り、パーサーに他の可能性をチェックさせます。

于 2012-08-09T16:21:06.907 に答える