用於布爾表達式的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，並返回沒有失敗，但不能輸入完全解析。

此外，運營商>你過度使用。它的目的是在它後面沒有匹配時解析失敗。另一方面，運營商>>返回並讓解析器檢查其他可能性。