用于布尔表达式的Spirit解析器

Question

我第一次使用spirit。我试图编写一个布尔表达式（只有&，|和！运算符）解析器。我定义我的语法类似以下内容：

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。

问候， 〜Soumen

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，并返回没有失败，但不能输入完全解析。

此外，运营商>你过度使用。它的目的是在它后面没有匹配时解析失败。另一方面，运营商>>返回并让解析器检查其他可能性。