Preface

I was looking for a light and unstrict xml parser. Boost.Spirit and Boost.Xpressive were big and not good at compile-time performance. I suspected that they were not static, but YARD written by Christopher Diggins was really static, small and fast. In time, I noticed that the lazy instantiation of templates could allow us to write recursive grammars, and I found that YARD and the finite state machine found at C++ Template Metaprogramming, could be binded. It was named biscuit.

Introduction

biscuit is an object-oriented recursive-descent parser generator framework implemented using class templates. The templates allow us to author Extended Backus-Normal Form (EBNF) in C++. Technical informations are available at YARD.

A simple EBNF grammar snippet:

group      ::= '(' expression ')'
factor     ::= integer | group
term       ::= factor (('*' factor) | ('/' factor))*
expression ::= term (('+' term) | ('-' term))*

is approximated using biscuit's facilities as seen in this code snippet:

struct expression ;
struct group      : seq< str<'('>, expression, str<')'> > { };
struct factor     : or_< integer, group > { };
struct term       : seq< factor, star< or_< seq< str<'*'>, factor >, seq< str<'/'>, factor > > > > { };
struct expression : seq< term, star< or_< seq< str<'+'>, term >, seq< str<'-'>, term > > > > { };

Through the magic of the lazy template instantiation, they are the perfectly valid types. The production rule expression is in fact a type that has a static member function parse. As parse will be instantiated later by algorithms, all you have to do is not to define but to declare a type:

struct element; // forward declaration

struct content :
  seq<
    opt<CharData>,
    star<
      seq<
        or_<
          element, // the magical recursion!
          Reference,
          CDSect,
          PI,
          Comment
        >,
        opt<CharData>
      >
    >
  >
{ };

struct element :
  or_<
    EmptyElemTag, 
    seq<STag, content, ETag>
  >
{ };

Quick Start

1. Get and install the latest release of the Boost C++ Libraries. (biscuit uses only their headers.)

2. Include headers of biscuit:

   #include "biscuit/algorithm.hpp"
   #include "biscuit/parser.hpp"
   using namespace biscuit;
   

3. Define your own parser type:

   typedef seq<
     str<'/','*'>,
     star_until< any, str<'*','/'> >
   > c_comment;
   

4. Call algorithms:

   if (match<c_comment>("/* hello, biscuit */")) {
     //...
   }

5. If you build test project, it is required to build Boost.Test:

   bjam -sTOOLS=vc-7_1 --with-test install
   

Basic Concepts

template< class State, class UserState >
static bool parse(State& s, UserState& us);

void operator()(ForwardIter first, ForwardIter last, UserState& us);

Predefined Parsers

Some parser templates are predefined as a means for parser composition and embedding.

struct decorate_action
{
  template< class ForwardIter, class Stream >
  void operator()(ForwardIter first, ForwardIter last, Stream& out)
  {
    out << "[";
    out << std::string(first, last);
    out << "]";
  }
};

struct xml_comment :
  seq<
    str<'<','!','-','-'>,
    star<
      or_<
        minus< any, str<'-'> >,
        seq<
          str<'-'>,
          minus< any, str<'-'> >
        >
      >
    >,
    str<'-','-','>'>
  >
{ };

struct xml_comment_action : actor< xml_comment, decorate_action >
{ };

std::stringstream out;
std::string s0("<!-- xml comment no.1 -->");
match<xml_comment_action>(s0, out);
BOOST_CHECK( std::string("[<!-- xml comment no.1 -->]") == out.str() );

Algorithms

Algorithms of biscuit work with Forward Range. Bear in mind that parsers don't know value_type of the range. For instance, a parser str works fine if value_type of the range is comparable with char.

BOOST_CHECK( match<xml_comment>("<!-- hello, xml comment -->") );
BOOST_CHECK( !match<xml_comment>("<!-- not well-formed comment -- -->") );

std::string s0("  /* c comment no.1 */x int i; /* c comment no.2 */ i = 1; /* c comment no.3 */ ++i;  ");
boost::sub_range<std::string> sr = search<c_comment>(s0);
BOOST_CHECK( std::string(boost::begin(sr), boost::end(sr)) == "/* c comment no.1 */" );

Ranges

typedef filter_range< c_comment, std::string > fr_t;
std::string s0("  /* c comment no.1 */ int i; /* c comment no.2 */ i = 1; /* c comment no.3 */ ++i;  ");
fr_t fr(s0);
BOOST_CHECK(( match< repeat< c_comment, 3 > >(fr) ));

BOOST_CHECK((
  match< str<'x','y','z'> >(
    make_filter_range< alpha >(
      make_filter_range< not_<space> >(
        make_filter_range< not_<digit> >("x & 4 y . 125 %  z")
      )
    )
  )
));

typedef match_results<c_comment, std::string> mrs_t;
typedef boost::range_const_iterator<mrs_t>::type iter_t;

std::string s0("  /* c comment no.1 */int i; /* c comment no.2 */i = 1; /* c comment no.3 */ ++i;  ");
mrs_t mrs(s0);
for (iter_t it = boost::const_begin(mrs); it != boost::const_end(mrs); ++it)
{
  std::cout << std::string(boost::begin(*it), boost::end(*it)) << std::endl;
}

/* c comment no.1 */
/* c comment no.2 */
/* c comment no.3 */

Grammar

As parsers are just types, they has no runtime-state. Nontype template argument is farely limited. If value_type of Forward Range is not Integral Constants like char, what can we do? But C++ Template Metaprogramming says that member function pointers are available. They can bind templates and objects. Boost.Spirit makes a expression templates object from expression templates objects, but you can make expression type from expression templates using biscuit.

grammar binds parsers and objects:

struct my_grammar : grammar< my_grammar, std::vector<std::string> >
{
  std::string text0() { return "hello"; };
  std::string text1() { return "grammar"; };
  std::string text2() { return "value"; };

  struct start :
    seq<
      value_<&my_grammar::text0>,
      value_<&my_grammar::text1>,
      value_<&my_grammar::text2>
    >
  { };
};

void grm_value_test()
{
  std::cout << "grm_value_test ing..." << std::endl;

  std::vector<std::string> texts;
  texts.push_back(std::string("hello"));
  texts.push_back(std::string("grammar"));
  texts.push_back(std::string("value"));
  
  my_grammar the_grammar;
  BOOST_CHECK( match< typename grammar_start<my_grammar>::type >(texts, the_grammar) );
}

Now that biscuit has no limitation of value_type of Forward Range parsed. As std::vector<std::string> is a Forward Range of std::string, it works. Keep in mind that UserState object is now your grammar object.

struct calculator : grammar< calculator, std::string >
{
  void do_int(iterator_type str, iterator_type end)
  {
    std::string s(str, end);
    std::cout << "PUSH(" << s << ')' << std::endl;
  }

  void do_add(iterator_type, iterator_type)   { std::cout << "ADD\n"; }
  void do_subt(iterator_type, iterator_type)  { std::cout << "SUBTRACT\n"; }
  void do_mult(iterator_type, iterator_type)  { std::cout << "MULTIPLY\n"; }
  void do_div(iterator_type, iterator_type)   { std::cout << "DIVIDE\n"; }
  void do_neg(iterator_type, iterator_type)   { std::cout << "NEGATE\n"; }

  struct expression;
  struct term;
  struct factor;

  struct expression :
    seq<
      term,
      star<
        or_<
          actor_< seq< str<'+'>, term >, &calculator::do_add >,
          actor_< seq< str<'-'>, term >, &calculator::do_subt >
        >
      >
    >
  { };
  
  struct term :
    seq<
      factor,
      star<
        or_<
          actor_< seq< str<'*'>, factor >, &calculator::do_mult >,
          actor_< seq< str<'/'>, factor >, &calculator::do_div >
        >
      >
    >
  { };

  struct factor :
    or_<
      actor_< plus<digit>, &calculator::do_int >,
      seq< str<'('>, expression, str<')'> >,
      actor_< seq< str<'-'>, factor >, &calculator::do_neg >,
      seq< str<'+'>, factor >
    >
  { };

  struct start : expression { };
};

Debugger

biscuit emulates Boost.Spirit's debugging:

struct start_tag { };
struct integer_tag { };
struct factor_tag { };
struct term_tag { };
struct expression_tag { };

template< class ForwardRange >
struct calculator_debug :
  grammar< calculator_debug, ForwardRange >, private boost::noncopyable
{
  calculator_debug(std::stack<long>& eval_) : eval(eval_) { }

  void push_int(iterator_type first, iterator_type last)
  {
    std::string s(first, last);
    long n = boost::lexical_cast<long>(s); // std::strtol(str, 0, 10);
    eval.push(n);
    std::cout << "push\t" << long(n) << std::endl;
  }

  // ...

  struct integer;
  struct factor;
  struct term;
  struct expression;

  // struct start : debugger<start,
  //  also ok, but long...
  struct start : debugger<start_tag, 
    expression
  >
  { };

  struct integer : debugger<integer_tag,
    actor_< plus<digit>, &calculator_debug::push_int >
  >
  { };
  
  // ...

debugger uses type-name of the first argument for outputs. If your grammar is a class template like above, type-name can be very long. So I think that you want to define start_tag etc. Well, debugger automatically disappears on release-compile.

Outputs:

1 + 2
struct start_tag: "1+2"
  struct expression_tag: "1+2"
    struct term_tag: "1+2"
      struct factor_tag: "1+2"
        struct integer_tag: "1+2"
push    1
        /struct integer_tag: "+2"
      /struct factor_tag: "+2"
    /struct term_tag: "+2"
    struct term_tag: "2"
      struct factor_tag: "2"
        struct integer_tag: "2"
push    2
        /struct integer_tag: ""
      /struct factor_tag: ""
    /struct term_tag: ""
popped 1 and 2 from the stack. pushing 3 onto the stack.
  /struct expression_tag: ""
/struct start_tag: ""
-------------------------
Parsing succeeded
result = 3
-------------------------

Points of Interest

You can find the idea of composing inlined algorithms from Boost.MPL TODO list. YARD and biscuit seem to be the example of it. By the way, this article was the hopeless war, vs Boost.Spirit. But don't you think another war will break out?

A snippet:

using namespace cranberry;

int x = 7;
int a = apply< plus< _1, _2 > >(x)(8);
int b = apply< plus< _1, _2 > >()(7, 8);
int c = apply< plus< _1, _2 > >(7, 8)();
int d = apply< plus< _1, int_<8> > >(7)();
int e = apply< bind< _1, _2, _3 > >(std::plus<int>())(7, 8);
int f = apply< bind< _1, _2, _3 > >(&free_plus)(7, 8);

int ar[5] = {1,2,3,4,5};
std::transform(ar, ar+5, ar, apply< plus< _1, _2 >, int const& >(x));
std::transform(ar, ar+5, ar, apply< bind< _1, _2, _3 > >(std::plus<int>(), x));
std::transform(ar, ar+5, ar, apply< bind< _1, _2, int_<7> > >(&free_plus));
std::for_each(ar, ar+5, apply< std_cout< _1 > >());

References

• p-stade
• Christopher Diggins
• YARD
• A Regular Expression Tokenizer using the YARD Parser
• Parsing XML in C++ using the YARD Parser
• C++ Template Metaprogramming
• Boost C++ Libraries
• Boost.MPL
• Boost.Range
• Boost.Spirit
• Boost.Xpressive

Release Notes

• Fixed the name confusion between limit and repeat.
• Directives became first-class parsers.
• Added debugger parser.