c++ - Boost Spirit Qi Grammar for Synthesizing associative Binary Operator AST nodes? -
i trying parse expressions of form "1.0 + 2.0 + 3.0 + ..." ast. have following ast node binary operations (complete, minimal code example @ end):
struct binop_t { expression_t lhs, rhs; }; i want use "boost_fusion_adapt_struct" macro allow struct synthesized boost:spirit::qi::rule:
boost_fusion_adapt_struct ( client::ast::binop_t, (client::ast::expression_t, lhs) (client::ast::expression_t, rhs) ) in other words, binary operation ast node (binop_t) requires 2 operands - left-hand side (lhs) , right-hand side (rhs) expressions should operated on. am able parse expressions of form "1.0+(2.0+(3.0+4.0))" ast node using following qi::grammar:
qi::rule<iterator, ast::literal_t(), ascii::space_type> literal; qi::rule<iterator, ast::binop_t(), ascii::space_type> binop; qi::rule<iterator, ast::expression_t(), ascii::space_type> primary_expr; qi::rule<iterator, ast::expression_t(), ascii::space_type> expr; expr = binop.alias(); binop = primary_expr > qi::lit('+') > primary_expr; primary_expr = (qi::lit('(') > expr > qi::lit(')')) | literal ; literal = qi::double_; however, struggling understand how modify grammar can parse such expressions without use of parenthesis (e.g. "1+2+3+4+...").
i have looked on "calc4.cpp" boost spirit example, , noticed uses following ast node binary operations (such add):
struct operation { optoken operator_; operand operand_; }; the difference between example , trying example defines grammar synthesizing binary operations node purely in terms of list of unary operations. list of unary operations synthesized ast node called "program":
struct program { operand first; std::list<operation> rest; }; this whole thing in synthesized using following grammar in example:
qi::rule<iterator, ast::program(), ascii::space_type> expression; qi::rule<iterator, ast::program(), ascii::space_type> term; qi::rule<iterator, ast::operand(), ascii::space_type> factor; expression = term >> *( (char_('+') >> term) | (char_('-') >> term) ) ; term = factor >> *( (char_('*') >> factor) | (char_('/') >> factor) ) ; factor = uint_ | '(' >> expression >> ')' | (char_('-') >> factor) | (char_('+') >> factor) ; in grammar, "expression" rule produces "program" list of operations". can see from grammar rule "expression" uses kleene star in grammar:
*((char_('+') >> term) this how grammar able parse chains of associative binary operations, such "1+2+3+4+...". attribute of grammar list, matches definition of "program" ast node. calculator "eval" function iterates on list of operations in "program," applying operations operands left right:
int operator()(program const& x) const { int state = boost::apply_visitor(*this, x.first); boost_foreach(operation const& oper, x.rest) { state = (*this)(oper, state); } return state; } i have looked on "mini-c" boost spirit example, , has similar ast design, there no binary operator ast node (only single "operator" node accepts single operand).
following complete, minimal code example program i've implemented far. recap, question is: how can modify program able synthesize tree of binop_t ast nodes expression "1+2+3+4+..." without use of parentheses in input text:
#include <boost/variant.hpp> #include <boost/fusion/include/adapt_struct.hpp> #include <boost/spirit/include/qi.hpp> #include <boost/spirit/include/phoenix_core.hpp> #include <boost/spirit/include/phoenix_operator.hpp> #include <iostream> #include <string> #include <exception> using boost::variant; using boost::recursive_wrapper; namespace qi = boost::spirit::qi; namespace ascii = boost::spirit::ascii; namespace phoenix = boost::phoenix; namespace client { namespace ast { struct literal_t; struct binop_t; typedef variant< recursive_wrapper<literal_t>, recursive_wrapper<binop_t> > expression_t; struct literal_t { double value; }; struct binop_t { expression_t lhs, rhs; }; }} // ns boost_fusion_adapt_struct ( client::ast::literal_t, (double, value) ) boost_fusion_adapt_struct ( client::ast::binop_t, (client::ast::expression_t, lhs) (client::ast::expression_t, rhs) ) namespace client { template <typename iterator> struct grammar_t : qi::grammar<iterator, ast::expression_t(), ascii::space_type> { qi::rule<iterator, ast::literal_t(), ascii::space_type> literal; qi::rule<iterator, ast::binop_t(), ascii::space_type> binop; qi::rule<iterator, ast::expression_t(), ascii::space_type> primary_expr; qi::rule<iterator, ast::expression_t(), ascii::space_type> expr; grammar_t() : grammar_t::base_type(expr) { expr = binop.alias(); binop = primary_expr > qi::lit('+') > primary_expr; primary_expr = (qi::lit('(') > expr > qi::lit(')')) | literal; literal = qi::double_; expr.name("expr"); binop.name("binop"); literal.name("literal"); qi::debug(expr); qi::debug(binop); qi::debug(literal); } }; } // ns int main() { try { string input = "0.1 + 1.2 "; std::string::const_iterator begin = input.begin(); std::string::const_iterator end = input.end(); typedef std::string::const_iterator iterator_type; client::grammar_t<iterator_type> g; client::ast::expression_t ast; bool status; status = qi::phrase_parse(begin, end, g, ascii::space, ast); expect_true(status); expect_true(begin == end); } catch (std::exception& e) { cout << e.what() << endl; } }
vexocide on ##spirit irc channel on freenode solved problem (http://codepad.org/wufmfufe). answer modify grammar follows:
expr = binop.alias(); binop = primary_expr >> qi::lit('+') >> (binop | primary_expr); primary_expr = (qi::lit('(') >> expr >> qi::lit(')')) | literal; literal = qi::double_; this grammar creates right recursion that's able synthesize parse tree i'm looking for.
tip encountered same problem: without spirit debug statements, boost spirit cause seg fault due stack overflow if provide left recursive grammar. if turn on debug statements, print out "infinte" amount of text tells going wrong in parser.
Comments
Post a Comment