$ template make_parser()
$ // Generate the parser.cpp file 
$ output $basedir + '/parser.cpp'
/* This file was generated by SableCC (http://www.sablecc.org/). */

#include <vector>
#include <string>
#include <stack>
#include <sstream>
#include <iostream>

#include "node.h"
#include "list.h"
#include "token.h"
#include "lexer.h"
#include "prod.h"
#include "parser.h"

using namespace $namespace;

extern "C" {

enum Command {
  CMD_POP,
  CMD_FETCHNODE,
  CMD_FETCHLIST,
  CMD_ADDNODE,
  CMD_ADDLIST,
  CMD_MAKELIST,
  CMD_MAKENODE,
  CMD_RETURNNODE,
  CMD_RETURNLIST
};

struct reduce_command {
  Command cmd;
  int result;
  int from;
  int index;
  int *args;
  const _TypeInfo *type_info;  // for makenode
};

[-!
  In principle what comes should be implemented by single DOM-inspecting
  JS function. It would be less-hackish and faster that way.
!-]
$ foreach {rules/rule}
  [- -]${sablecc:start_rule(string(@index))}[- -]
$   foreach {action}
$     choose
      [-when {@cmd='POP'}-]${sablecc:action_pop(string(@result))}[-end-]
      [-when {@cmd='FETCHLIST'}-]${sablecc:action_fetchlist(string(@result), string(@index), string(@from))}[-end-]
      [-when {@cmd='FETCHNODE'}-]${sablecc:action_fetchnode(string(@result), string(@index), string(@from))}[-end-]
      [-when {@cmd='ADDLIST'}-]${sablecc:action_addlist(string(@tolist), string(@fromlist))}[-end-]
      [-when {@cmd='ADDNODE'}-]${sablecc:action_addnode(string(@tolist), string(@node))}[-end-]
      [-when {@cmd='MAKELIST'}-]${sablecc:action_makelist(string(@result))}[-end-]
      [-when {@cmd='MAKENODE'}-]${sablecc:action_makenode(string(@result), string(concat($namespace,'::',@etype)))}[-foreach {arg}-]${sablecc:action_makenode_arg(string(text()))}[-end-]${sablecc:action_makenode_done()}[-end-]
      [-when {@cmd='RETURNLIST'}-]${sablecc:action_returnlist(string(@list))}[-end-]
      [-when {@cmd='RETURNNODE'}-]${sablecc:action_returnnode(string(@node))}[-end-]
$     end choose
$   end foreach
  [- -]${sablecc:end_rule()}[- -]
$ end foreach

${sablecc:rulecode()}

struct {
  int count;
  int go_to;
  reduce_command *commands;
} reduce_commands[] = {
$ foreach {rules/rule}
  {${count(action)}, @leftside, rcmd@index},
$ end
};

$ // make the goto table, in three goes 
$ foreach {parser_data/goto_table/row}
$   set i = {position()}
$   foreach {goto}
static int _g_${$i}_${position()}[] = {@from, @to};
$   end foreach
$ end foreach

$ foreach {parser_data/goto_table/row}
$   set i = {position()}
static int *_g_${$i}[] = {
        (int *)${count(goto)},
$   foreach {goto}
        _g_${$i}_${position()},
$   end
};
$ end foreach

static int **goto_table[] = {
$ foreach {parser_data/goto_table/row}
        _g_${position()},
$ end
};

$ // make the action table, in three goes 
$ foreach {parser_data/action_table/row}
$   set i = {position()}
$   foreach {action}
static int _a_${$i}_${position()}[] = {@from, @action, @to};
$   end foreach
$ end foreach

$ foreach {parser_data/action_table/row}
$   set i = {position()}
static int *_a_${$i}[] = {
        (int *)${count(action)},
$   foreach {action}
        _a_${$i}_${position()},
$   end
};
$ end foreach

static int **action_table[] = {
$ foreach {parser_data/action_table/row}
        _a_${position()},
$ end
};
};

namespace {
class Stack {
public:
  typedef std::vector<std::list<Node> > elems_t;

private:
  struct State {
    int state;
    elems_t elems;
  };

  class State;
  typedef std::list<State> stack_t;

public:
  inline Stack ()
  {
    list.push_back (State());
    it = list.begin();
  }

  elems_t& push (int state);
  elems_t& pop();

  inline int state ()
  {
    return (*it).state;
  }

private:
  stack_t list;
  stack_t::iterator it;
};

Stack::elems_t& Stack::push (int state)
{
  it++;
  if ( it == list.end() ) { list.push_back (State()); it = list.end(); it--; }

  State &s = *it;
  s.state = state;
  s.elems.clear();
  return s.elems;
}

Stack::elems_t& Stack::pop()
{
  State&s = *it;
  it--;
  return s.elems;
}

int errors[] = {
[-foreach {parser_data/errors/i}-]${.}, [-end-]
};

char * error_messages[] = {
$ foreach {parser_data/error_messages/msg}
        "${sablecc:escape_string_literal(string(text()))}",
$ end
};

int goTo(int index, int state)
{
  int low = 2;
  int high = (int)goto_table[index][0];
  int value = goto_table[index][1][1];

  while(low <= high) {
      int middle = (low + high) / 2;

      if(state < goto_table[index][middle][0]) {
          high = middle - 1;
      } else if(state > goto_table[index][middle][0]) {
          low = middle + 1;
      } else {
          value = goto_table[index][middle][1];
          break;
      }
  }

  return value;
}

} // namespace {


$namespace::Parser::Parser (Lexer *lexer, bool own_lexer) : lexer (lexer), own_lexer (own_lexer)
{
}

$namespace::Parser::~Parser ()
{
  if ( own_lexer ) delete lexer;
}

$namespace::Start $namespace::Parser::parse ()
{
  Node null_node;

  Stack stack;
  stack.push (0);

  while (true) {
      while ( lexer->peek().getIndex() == -1 )
          lexer->next();

      Token last_token = lexer->peek();
      int last_pos = last_token.getPos();
      int last_line = last_token.getLine();

      int state = stack.state();

      int index = last_token.getIndex();
      int action[2] = { action_table[state][1][1], action_table[state][1][2] };

      int low = 2;
      int high = (int)action_table[state][0];

      while(low <= high) {
          int middle = (low + high) / 2;

          if(index < action_table[state][middle][0]) {
              high = middle - 1;
          } else if ( index > action_table[state][middle][0] ) {
              low = middle + 1;
          } else {
              action[0] = action_table[state][middle][1];
              action[1] = action_table[state][middle][2];
              break;
          }
      }

      switch(action[0]) {
        case SHIFT: {
          Stack::elems_t& elems = stack.push(action[1]);
          std::list<Node> l;
          l.push_back (lexer->next());
          elems.push_back (l);
          break;
        }

        case ACCEPT: {
          TEOF node2 = lexer->next().unsafe_cast<TEOF>();
          Stack::elems_t& top = stack.pop();
          ${productions/production/@ename} node1 = top.front().front().unsafe_cast<${productions/production/@ename}>();
          Start node = Start::make (node1, node2);
          return node;
          break;
        }

        case ERROR: {
          std::ostringstream out;
          out << "[" << last_line << "," << last_pos << "] " << error_messages[errors[action[1]]];
          throw ParserException (last_token, out.str());
          break;
        }

        case REDUCE: {
          // here comes the significant part
          reduce_command *cmds = reduce_commands[action[1]].commands;
          int cmds_count = reduce_commands[action[1]].count;
          int go_to = reduce_commands[action[1]].go_to;

          std::list<Node> lists[${sablecc:get_maxlists()}];
          Node nodes[${sablecc:get_maxnodes()}];
          Stack::elems_t pops[${sablecc:get_maxpops()}];
          void *args[${sablecc:get_maxargs()}];

          Stack::elems_t result;

          for ( int cid = 0; cid < cmds_count; cid++ ) {
              reduce_command& cmd = cmds[cid];

              switch (cmd.cmd) {
                case CMD_POP: {
                  pops[cmd.result] = stack.pop();
                  break;
                }
                case CMD_FETCHNODE: {
                  nodes[cmd.result] = pops[cmd.from][cmd.index].front();
                  break;
                }
                case CMD_FETCHLIST: {
                  lists[cmd.result] = pops[cmd.from][cmd.index];
                  break;
                }
                case CMD_ADDNODE: {
                  if ( nodes[cmd.from] )
                      lists[cmd.result].push_back (nodes[cmd.from]);
                  break;
                }
                case CMD_ADDLIST: {
                  lists[cmd.result].insert(lists[cmd.result].end(), lists[cmd.from].begin(), lists[cmd.from].end());
                  break;
                }
                case CMD_MAKELIST: {
                  lists[cmd.result].clear();
                  break;
                }
                case CMD_MAKENODE: {
                  // XXX
                  for ( int i = 0; i < cmd.type_info->prod_elem_count; i++ ) {
                      if ( cmd.type_info->prod_elem_is_list[i] ) {
                          args[i] = (void *)&lists[cmd.args[i]];
                      } else {
                          if ( cmd.args[i] == -1 )
                              args[i] = (void *)&null_node;
                          else
                              args[i] = (void *)&nodes[cmd.args[i]];
                      }
                  }
                  nodes[cmd.result] = _GenericNode::initProd (cmd.type_info, args);
                  break;
                }
                case CMD_RETURNNODE: {
                  std::list<Node> l;
                  if ( cmd.from == -1 )
                      l.push_back (null_node);
                  else
                      l.push_back (nodes[cmd.from]);
                  result.push_back(l);
                  break;
                }
                case CMD_RETURNLIST: {
                  result.push_back(lists[cmd.from]);
                  break;
                }
              }
          }

          stack.push(goTo(go_to, stack.state())) = result;

          break;
        }
      }
  }
}
$ end output

$ // Generate the parser.h file 
$ output $incdir + '/parser.h'
/* This file was generated by SableCC (http://www.sablecc.org/). */

#ifndef __${$namespace}__parser_hh__
#define __${$namespace}__parser_hh__

#include <string>

namespace $namespace {

class Parser {
  enum Action {
    SHIFT = 0,
    REDUCE = 1,
    ACCEPT = 2,
    ERROR = 3
  };

public:
  Parser (Lexer *lexer, bool own_lexer = false);
  virtual ~Parser ();

  Start parse ();

private:
  Lexer *lexer;
  bool own_lexer;
};


class ParserException : public Exception {
public:
  inline ParserException (Token token, const std::string& msg) : Exception (msg), token(token) { }
  Token getToken () const { return token; }

private:
  Token token;
};

} // namespace $namespace {

#endif // !__${$namespace}__parser_hh__
$ end output

$ end template