Deeply-recursive qi grammars (parsers) with synthesized and inherited attributes

Question

I'm using spirit::qi grammars that construct and return nontrivial objects as their synthesized attributes. The problem is that I want the grammars to recursively depend on each other. It is straightforward to use recursive rules, but I want recursive grammars.

Here's some example code. Notice the comments that say CIRCULAR REFERENCE. Obviously this cannot compile if I uncomment those lines, because the FooGrammar and BarGrammar objects include each other.

I can think of two ways to achieve the desired effect, but I can't seem to make them work with qi:

1. Make the BarGrammar hold a (smart) pointer to a FooGrammar. It would need to construct the FooGrammar as a semantic action on the lit("start_bar"). But I don't know the qi internals to know if this is safe -- would I need to maintain my own explicit stack of FooGrammars? When can they be safely destroyed?

2. BarGrammar could hold a FooGrammar as one of its qi::locals. But for some reason I can't get it to compile if I try to pass the grammar in qi::locals an inherited attribute.

Is there any canonical way to make recursive grammars?

.

#include <boost/fusion/include/std_pair.hpp>
#include <boost/optional.hpp>
#include <boost/ptr_container/ptr_vector.hpp>
#include <boost/shared_ptr.hpp>
#include <boost/spirit/include/phoenix_bind.hpp>
#include <boost/spirit/include/phoenix_core.hpp>
#include <boost/spirit/include/phoenix_object.hpp>
#include <boost/spirit/include/phoenix_operator.hpp>
#include <boost/spirit/include/qi.hpp>
#include <boost/variant.hpp>
namespace phoenix = boost::phoenix;
namespace spirit = boost::spirit;
namespace ascii = spirit::ascii;
namespace qi = spirit::qi;
using ascii::space_type;
using phoenix::ref;
using qi::grammar;
using qi::lit;
using qi::_r1;
using qi::_val;
using qi::lit;
using qi::omit;
using qi::rule;

#include <iostream>
#include <string>
using std::cout;
using std::endl;
using std::string;

typedef int Reffy;

struct Foo {
  int foo;
};

struct Bar {
  int bar;
};

template <typename Iterator>
struct BarGrammar;

template <typename Iterator>
struct FooGrammar : grammar<Iterator, Foo(Reffy&), space_type> {
  FooGrammar() : FooGrammar::base_type(foo_) {
    foo_ = lit("start_foo")[_val = phoenix::construct<Foo>()]
      > -bar_(_r1)
      > lit("end_foo");
    ;
  }

  BarGrammar<Iterator> bar_;
  rule<Iterator, Foo(Reffy&), space_type> foo_;
};

template <typename Iterator>
struct BarGrammar : grammar<Iterator, Bar(Reffy&), space_type> {
  BarGrammar() : BarGrammar::base_type(bar_) {
    bar_ = lit("start_bar")[_val = phoenix::construct<Bar>()]
      //> -foo_(_r1)    // CIRCULAR REFERENCE
      > lit("end_bar");
  }

  //FooGrammar<Iterator> foo_;    // CIRCULAR REFERENCE
  rule<Iterator, Bar(Reffy&), space_type> bar_;
};

int main(int argc, char *argv[]) {
  Reffy reffy(0);

  FooGrammar<string::iterator> foog;
  rule<string::iterator, space_type> top_rule = omit[ foog(ref(reffy)) ];

  string input("start_foo start_bar end_bar end_foo");
  string::iterator begin = input.begin();
  string::iterator end = input.end();
  if(qi::phrase_parse(begin, end, top_rule, ascii::space)) {
    cout << "passed" << endl;
  } else {
    cout << "failed" << endl;
  }

  return 0;
}

Thanks in advance!!

Answer 1

I had the same problem when implementing an SQL parser in qi. I had separate grammars for statements, fields, tables, etc, but fields and tables, for instance, could be statements too sometimes (subqueries). In my case, I solved the problem like this:

The top grammar (the one that you always start parsing with) held shared pointers to all sub grammars. The constructor of the top grammar would create instances of all sub grammars and pass them instances of each other as weak pointers. That way there is only one instance of each grammar created. There are no circular shared_ptr thanks to weak_ptr. So basically, the top grammar owns all sub grammars and just passes pointers around to each other.

So in your case, I would create a TopGrammar class, have it own FooGrammar and BarGrammar. Once they're constructed, pass them pointers to each other. And in TopGrammar's start rule just invoke FooGrammar.

Since TopGrammar owns all subgrammars, you're sure that their lifespan is sufficient.