How would I implement a forth-style reverse-polish notation parser in boost spirit? -

i'm trying implement parser old forth-based grammar of functions take form of: "num" "num" "command" command string of kind.

for example:

    0 1 hsff     41 sensor on     1 12.0 bh 4 lnon 

as can see, grammar [mostly] reverse polish notation, string of arguments preceding command. grammar pseudo white-space dependent, in that:

    0 1 hsff 41 sensor on 

is valid as:

    0 1 hsff     41 sensor on 

(in other words '\n' treated space)

extra whitespace skipped, so:

    0           1 hsff              41 sensor      on 

is 2 valid commands lot of unnecessary whitespace.

all of seemed simple enough, started chugging away @ implementing grammar. of course, things never simple seem, , found parser fails on first character (in case int). so, boiling things down, tried implementing single rule:

    namespace qi = boost::spirit::qi;     namespace ascii = boost::spirit::ascii;      qi::rule<iterator> cmd_targetsenspaircmd =          qi::int_ >> (lit("target") | lit("sensor") | lit("pair") )          >> (lit("on") | lit("off") | lit("erase") );      std::string in("0 target erase\n");      iterator = in.begin();     bool success = qi::parse(in.begin(), in.end(), cmd_targetsenspaircmd, ascii::space); 

this code block returns false, indicating parsing has failed.

as can see, rule int must followed 2 literals, in case indicating whether command target, sensor, or pair, identified int, turned on, off, or erased.

if @ iterator see parsing has stopped, shows has failed on int. changed rule +qi::int_, succeeds in parsing int, fails on literals. shortening rule qi::int_ >> lit("target") fails.

i think problem may in whitespace skipper i'm using, have been unable determine i'm doing wrong.

is there way tell spirit tokens separated whitespace, exception of quoted strings (which turn labels in grammar)?

i have phantasized little you.

the first step take come ast model:

namespace ast {     enum command  { no_cmd, target, sensor, pair };     enum modifier { no_modifier, on, off, erase };      struct modifiedcommand     {         command cmd  = no_cmd;         modifier mod = no_modifier;     };      struct othercommand     {         std::string token;         othercommand(std::string token = "") : token(std::move(token))         { }     };      typedef boost::variant<int, double> operand;      typedef boost::variant<operand, modifiedcommand, othercommand> rpnmachineinstruction;     typedef std::vector<rpnmachineinstruction> rpnmachineprogram; } 

as can see intend distinguish integers , double operand values, , treat "other" commands (like "hssf") wasn't actively described in grammar free-form tokens (uppercase alphabetical).

now, map rule definitions onto this:

rpngrammar() : rpngrammar::base_type(_start) {     _start         = *_instruction;     _instruction   = _operand | _mod_command | _other_command;      _operand       = _strict_double | qi::int_;      _mod_command   = _command >> _modifier;     _other_command = qi::as_string [ +qi::char_("a-z") ];      // helpers     _command.add("target", ast::target)("sensor", ast::sensor)("pair", ast::pair);     _modifier.add("on", ast::on)("off", ast::off)("erase", ast::erase); } 

the grammar parses result list of instructions (ast::rpnmachineprogram), each instruction either operand or operation (a command modifier, or other free-form command "hssf"). here rule declarations:

qi::rule<it, ast::rpnmachineprogram(),     skipper> _start; qi::rule<it, ast::rpnmachineinstruction(), skipper> _instruction; qi::rule<it, ast::modifiedcommand(),       skipper> _mod_command; qi::rule<it, ast::operand(),               skipper> _operand;  // note: omitting skipper has same effect wrapping `qi::lexeme` qi::rule<it, ast::othercommand()> _other_command;  qi::real_parser<double, boost::spirit::qi::strict_real_policies<double> > _strict_double; qi::symbols<char, ast::command>  _command; qi::symbols<char, ast::modifier> _modifier; 

you can see parse sample question:

parse succeeded, 10 stack instructions int:0 int:1 'hsff' int:41 sensor [on]  int:1 double:12 'bh' int:4 'lnon' 

the output created sample visitor use inspiration interpreter/executor.

see live on coliru

full listing

#include <boost/fusion/adapted/struct.hpp> #include <boost/spirit/include/qi.hpp> #include <fstream>  namespace qi = boost::spirit::qi;  namespace ast {     enum command  { no_cmd, target, sensor, pair };     enum modifier { no_modifier, on, off, erase };      struct modifiedcommand     {         command cmd  = no_cmd;         modifier mod = no_modifier;     };      struct othercommand     {         std::string token;         othercommand(std::string token = "") : token(std::move(token))         { }     };      typedef boost::variant<int, double> operand;      typedef boost::variant<operand, modifiedcommand, othercommand> rpnmachineinstruction;     typedef std::vector<rpnmachineinstruction> rpnmachineprogram;      // printing, can adapt execute stack instead     struct print : boost::static_visitor<std::ostream&>     {         print(std::ostream& os) : os(os) {}         std::ostream& os;          std::ostream& operator()(ast::command cmd) const {             switch(cmd) {                 case target: return os << "target" << " ";                 case sensor: return os << "sensor" << " ";                 case pair:   return os << "pair"   << " ";                 case no_cmd: return os << "no_cmd" << " ";                 default:     return os << "#invalid_command#" << " ";             }         }          std::ostream& operator()(ast::modifier mod) const {             switch(mod) {                 case on:          return os << "[on]"          << " ";                 case off:         return os << "[off]"         << " ";                 case erase:       return os << "[erase]"       << " ";                 case no_modifier: return os << "[no_modifier]" << " ";                 default:    return os << "#invalid_modifier#" << " ";             }         }          std::ostream& operator()(double d) const { return os << "double:" << d << " "; }         std::ostream& operator()(int    i) const { return os << "int:"    << << " "; }          std::ostream& operator()(ast::othercommand const& cmd) const {             return os << "'" << cmd.token << "'\n";         }          std::ostream& operator()(ast::modifiedcommand const& cmd) const {             (*this)(cmd.cmd);             (*this)(cmd.mod);             return os << "\n";          }          template <typename... tvariant>         std::ostream& operator()(boost::variant<tvariant...> const& v) const {              return boost::apply_visitor(*this, v);          }     };  }  boost_fusion_adapt_struct(ast::modifiedcommand, (ast::command, cmd)(ast::modifier, mod))  template <typename it, typename skipper = qi::space_type> struct rpngrammar : qi::grammar<it, ast::rpnmachineprogram(), skipper> {     rpngrammar() : rpngrammar::base_type(_start)     {         _command.add("target", ast::target)("sensor", ast::sensor)("pair", ast::pair);         _modifier.add("on", ast::on)("off", ast::off)("erase", ast::erase);          _start         = *_instruction;         _instruction   = _operand | _mod_command | _other_command;          _operand       = _strict_double | qi::int_;          _mod_command   = _command >> _modifier;         _other_command = qi::as_string [ +qi::char_("a-z") ];     }    private:     qi::rule<it, ast::rpnmachineprogram(),     skipper> _start;     qi::rule<it, ast::rpnmachineinstruction(), skipper> _instruction;     qi::rule<it, ast::modifiedcommand(),       skipper> _mod_command;     qi::rule<it, ast::operand(),               skipper> _operand;      // note: omitting skipper has same effect wrapping `qi::lexeme`     qi::rule<it, ast::othercommand()> _other_command;      qi::real_parser<double, boost::spirit::qi::strict_real_policies<double> > _strict_double;     qi::symbols<char, ast::command>  _command;     qi::symbols<char, ast::modifier> _modifier; };  int main() {     std::ifstream ifs("input.txt");     typedef boost::spirit::istream_iterator it;     ifs.unsetf(std::ios::skipws);      rpngrammar<it> grammar;      f(ifs), l;     ast::rpnmachineprogram program;     bool ok = qi::phrase_parse(f, l, grammar, qi::space, program);      if (ok)     {         std::cout << "parse succeeded, " << program.size() << " stack instructions\n";         std::for_each(                 program.begin(),                 program.end(),                 ast::print(std::cout));     }     else     {         std::cout << "parse failed\n";     }      if (f != l)     {         std::cout << "remaining unparsed: '" << std::string(f,l) << "'\n";     } }