c++ - bool 表达式的 spirit 解析器

Question

我是第一次使用 spirit 。我正在尝试编写一个 bool 表达式(只有 &、| 和 ! 运算符)解析器。我定义了如下语法:

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<> 也不起作用？

我使用的是 boost 1.49 和 gcc-4.2.2。

问候，~素门

Answer 1

你的解析器有很多问题。首先，您在这里遇到了左侧递归，因此解析器将因堆栈溢出而崩溃。你的语法应该是这样的:

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，并在没有失败的情况下返回，但输入没有完全解析。

此外，运算符 > 你过度使用了。它的目的是如果后面没有匹配项则解析失败。另一方面，运算符 >>> 返回并让解析器检查其他可能性。