Code Style No.7

Lemon Parser Generatorが生成したCコードをヘッダオンリーのパーサとして提供するにはどうしたら良いかのまとめ。Lemon自体とテンプレートには手を加えない縛り。なお、例題は四則演算で、Boost.Variantを生成する（スキャナはなし）。

関連記事は下記。

• Boost.Variant - recursive (4)
• Header Only Lemon (1)
• Header Only Lemon (2)
• Lemon - malloc and realloc

まずは文法ファイル。

%token_prefix MORLA_EXAMPLE_PARSER_
%token_type {token}
%extra_argument {builder* ctx}

%left ADD SUB.
%left MUL DIV.

root ::= expression. {
  std::cout << "root ::= expression.\n";
}

expression ::= expression ADD expression. {
  std::cout << "expression ::= expression ADD expression.\n";
  ctx->push_operator<add>();
}

expression ::= expression SUB expression. {
  std::cout << "expression ::= expression SUB expression.\n";
  ctx->push_operator<sub>();
}

expression ::= expression MUL expression. {
  std::cout << "expression ::= expression MUL expression.\n";
  ctx->push_operator<mul>();
}

expression ::= expression DIV expression. {
  std::cout << "expression ::= expression DIV expression.\n";
  ctx->push_operator<div>();
}

expression ::= NUMBER(x). {
  std::cout << "expression ::= NUMBER(" << x.number << ").\n";
  ctx->push_number(x);
}

ドライバのソースコード。長い。
【修正】メモリ管理をshared_ptrさんにお願いした。

#include <stdlib.h>
#include <iostream>
#include <memory>
#include <stack>
#include <boost/variant.hpp>

// we explicitly include <stdio.h> outside of namespaces
#include <stdio.h>

// see: http://w.livedoor.jp/csn7/d/Boost.Variant%20-%20recursive%20%284%29
namespace boost {
  struct recursive_variant_ {};
}

namespace morla {
  namespace example {
    namespace parser {
      struct token {
        double number;
      };

      inline token make_token() {
        return token();
      }

      inline token make_token(double number) {
        return token({ number });
      }

      struct add {
        static const char value = '+';
        double operator()(double x, double y) const { return x + y; }
      };

      struct sub {
        static const char value = '-';
        double operator()(double x, double y) const { return x - y; }
      };

      struct mul {
        static const char value = '*';
        double operator()(double x, double y) const { return x * y; }
      };

      struct div {
        static const char value = '/';
        double operator()(double x, double y) const { return x / y; }
      };

      template <typename T_op, typename T>
      struct expression {
        T_op op;
        T x;
        T y;
      };

      typedef typename boost::make_recursive_variant<
        boost::blank,
        double,
        expression<add, boost::recursive_variant_>,
        expression<sub, boost::recursive_variant_>,
        expression<mul, boost::recursive_variant_>,
        expression<div, boost::recursive_variant_>
      >::type variant_type;

      struct builder {
        std::stack<variant_type> stack;

        template <typename T_op>
        void push_operator() {
          variant_type y = stack.top(); stack.pop();
          variant_type x = stack.top(); stack.pop();
          stack.push(expression<T_op, variant_type>({ T_op(), x, y }));
        }

        void push_number(token const& tk) {
          stack.push(tk.number);
        }
      };

      class printer : public boost::static_visitor<> {
      public:
        explicit printer(std::ostream& out) : out_(out) {}

        void operator()(double value) {
          out_ << value;
        }

        template <typename T_op>
        void operator()(expression<T_op, variant_type> const& value) {
          out_ << "(" << T_op::value << " ";
          apply(value.x);
          out_ << " ";
          apply(value.y);
          out_ << ")";
        }

        template <typename T>
        void operator()(T const&) {}

        void apply(variant_type const& value) {
          boost::apply_visitor(*this, value);
        }

      private:
        std::ostream& out_;
      };

      struct evaluator : public boost::static_visitor<double> {
        double operator()(double value) const {
          return value;
        }

        template <typename T_op>
        double operator()(expression<T_op, variant_type> const& value) const {
          return value.op(apply(value.x), apply(value.y));
        }

        template <typename T>
        double operator()(T const&) const {}

        double apply(variant_type const& value) const {
          return boost::apply_visitor(*this, value);
        }
      };

      // see: http://w.livedoor.jp/csn7/d/Header%20Only%20Lemon%20%282%29
      namespace {
#include "example.h" /* generated by lemon */

// see: http://w.livedoor.jp/csn7/d/Lemon%20-%20malloc%20and%20realloc
#define YYSTACKDEPTH 0
#if defined(YYSTACKDEPTH) && YYSTACKDEPTH <= 0
        // overloaded realloc is required
        struct yyStackEntry;
        inline yyStackEntry* realloc(yyStackEntry* ptr, size_t size) {
          return static_cast<yyStackEntry*>(::realloc(ptr, size));
        }
#endif

#include "example.c" /* generated by lemon */

// see: http://w.livedoor.jp/csn7/d/Header%20Only%20Lemon%20%281%29
#undef INTERFACE
#undef ParseARG_FETCH
#undef ParseARG_PDECL
#undef ParseARG_SDECL
#undef ParseARG_STORE
#undef ParseTOKENTYPE
#undef TOKEN
#undef YYACTIONTYPE
#undef YYCODETYPE
#undef YYERRORSYMBOL
#undef YYERRSYMDT
#undef YYFALLBACK
#undef YYNOCODE
#undef YYNRULE
#undef YYNSTATE
#undef YYSTACKDEPTH
#undef YYWILDCARD
#undef YY_ACCEPT_ACTION
#undef YY_ACTTAB_COUNT
#undef YY_ERROR_ACTION
#undef YY_NO_ACTION
#undef YY_REDUCE_COUNT
#undef YY_REDUCE_MAX
#undef YY_REDUCE_MIN
#undef YY_REDUCE_USE_DFLT
#undef YY_SHIFT_COUNT
#undef YY_SHIFT_MAX
#undef YY_SHIFT_MIN
#undef YY_SHIFT_USE_DFLT
#undef yytestcase
      }

      class parser {
      public:
        parser(builder& ctx)
          : ctx_(&ctx),
            ptr_(ParseAlloc(malloc), [](void* ptr){ ParseFree(ptr, free); }) {
          if (! ptr_) {
            throw std::bad_alloc();
          }
        }

        void operator()() {
          Parse(ptr_.get(), 0, make_token(), ctx_);
        }

        void operator()(int major) {
          Parse(ptr_.get(), major, make_token(), ctx_);
        }

        template <typename T>
        void operator()(int major, T const& minor) {
          Parse(ptr_.get(), major, make_token(minor), ctx_);
        }

      private:
        builder* ctx_;
        std::shared_ptr<void> ptr_;
      };
    }
  }
}

int main(int argc, char* argv[]) {
  morla::example::parser::builder builder;
  {
    morla::example::parser::parser parser(builder);
    parser(MORLA_EXAMPLE_PARSER_NUMBER, 42);
    parser(MORLA_EXAMPLE_PARSER_SUB);
    parser(MORLA_EXAMPLE_PARSER_NUMBER, 7);
    parser(MORLA_EXAMPLE_PARSER_MUL);
    parser(MORLA_EXAMPLE_PARSER_NUMBER, 6);
    parser(MORLA_EXAMPLE_PARSER_ADD);
    parser(MORLA_EXAMPLE_PARSER_NUMBER, 42);
    parser();
  }

  morla::example::parser::printer printer(std::cout);
  printer.apply(builder.stack.top());
  std::cout << "\n";

  std::cout << morla::example::parser::evaluator().apply(builder.stack.top());
  std::cout << "\n";

  return 0;
}

出力。

expression ::= NUMBER(42).
expression ::= NUMBER(7).
expression ::= NUMBER(6).
expression ::= expression MUL expression.
expression ::= expression SUB expression.
expression ::= NUMBER(42).
expression ::= expression ADD expression.
root ::= expression.
(+ (- 42 (* 7 6)) 42)
42