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<> 即使我启用它也不起作用？

我正在使用 boost 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 回答