CODEWITHSUNDEEP
c++boost
user1588017
user1588017

Reputation: 31

Spirit parser for boolean expression

I'm using spirit first time. I'm trying to write a boolean expression (with only &, | and ! operators) parser. I've defined my grammar like following:

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;
};

I'm facing few hurdles here:

  1. It's not working for any binary expression (like 'A + B'). It's working fine for unary expressions (like '!(A)' or '(!A)'.

Can someone point me what I'm doing wrong?

  1. I want store it in tree form (as I want to build a BDD out of it). Can someone point me how to do that?

  2. Also, why on_error<> is not working even when I enable it?

I'm using boost 1.49 and gcc-4.2.2.

Regards, ~ Soumen

Upvotes: 3

Views: 402

Answers (1)

Archie
Archie

Reputation: 6844

There are quite a lot problems with your parser. First of all, you meet a left-side recursion here, so the parser will crash with Stack Overflow. Your grammar should look like this:

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

In this case you don't have left-recursion and everything parses.

Why your approach was failing? In your case:

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

So it should parse only A, and return without fail, but with input not fully parsed.

Also, the operator > you overused. Its purpose is to fail parsing if there is no match after it. On the other hand the operator >> returns and lets the parser check other possibilities.

Upvotes: 3

Related Questions