実際動かない(struct リテラルくらいしかパースできない)

parser.js

var util = require('util');

function Nothing () {}

Object.Nothing = Nothing;

Array.prototype.maybeMap = function (callback, thisArg) {
  var T, A, k;
  if (this == null) {
    throw new TypeError(" this is null or not defined");
  }
  var O = Object(this);
  var len = O.length >>> 0;
  if ({}.toString.call(callback) != "[object Function]") {
    throw new TypeError(callback + " is not a function");
  }
  if (thisArg) {
    T = thisArg;
  }
  A = new Array(len);
  k = 0;
  while(k < len) {
    var kValue, mappedValue;
    if (k in O) {
      kValue = O[ k ];
      mappedValue = callback.call(T, kValue, k, O);
      if (mappedValue === Object.Nothing) {
        return A.slice(0, k);
      }
      A[ k ] = mappedValue;
    }
    k++;
  }
  return A;
};

var TOKENS = [
  ['SP', ' '],
  'func',
  'var',
  'struct',
  'return',
  'if',
  'for',
  'switch',
  'break',
  '(',
  ')',
  '{',
  '}',
  '[',
  ']',
  '&',
  ',',
  '.',
  '+',
  '-',
  '*',
  '/',
  '%',
  '<',
  '>',
  '==',
  '!',
  '=',
  ':',
  ['NL', '\n'],
  ['NUM', /[0-9]+(\.[0-9]+)?/],
  ['ID', /[a-zA-Z_][a-zA-Z0-9_]*/]
].map(function (t) {
  return new Token(t);
});

function Token (t, p, l, c) {
  if (Array.isArray(t)) {
    this.n = t[0];
    this.v = t[1];
  } else {
    this.n = t;
    this.v = t;
  }
  this.p = p;
  this.l = l;
  this.c = c;
}

Token.prototype.clone = function () {
  var t = new Token(null, this.p, this.l, this.c);
  t.n = this.n;
  t.v = this.v;
  return t;
};

function ScanError (p, l, c) {
  this.p = p;
  this.l = l;
  this.c = c;
}

function ScanResult (tokens) {
  this.tokens = tokens;
}

function scan (text) {
  var pos = 0,
      line = 1,
      col = 0,
      tokens = [];

  while (pos < text.length) {
    var token = null;

    for (var i = 0; i < TOKENS.length; ++i) {
      var t = TOKENS[i];
      if (typeof t.v === 'string') {
        if (text.indexOf(t.v, pos) === pos) {
          token = t;
          break;
        }
      } else {
        if (text.substring(pos).search(t.v) === 0) {
          token = new Token();
          token.n = t.n;
          token.v = RegExp.lastMatch;
          break;
        }
      }
    }

    if (token === null) {
      return new ScanError(pos, line, col);
    }

    token = token.clone();

    if (token.n === 'NL') {
      line ++;
      col = 0;
    }

    token.p = pos;
    token.l = line;
    token.c = col;

    pos += token.v.length;
    col += token.v.length;

    if (token.n !== 'SP') {
      tokens.push(token);
    }
  }
  tokens.push(new Token('EOF', pos, line, col));
  return new ScanResult(tokens);
}

function ParseState (t, i) {
  this.t = t;
  this.i = i;
  this.isFailed = false;

  this.p = 0;
  this.l = 1;
  this.c = 0;
  this.e = null;
}

ParseState.prototype.recover = function () {
  this.isFailed = false;
};

ParseState.prototype.succeed = function () {
  this.i ++;
};

ParseState.prototype.fail = function () {
  this.isFailed = true;
};

ParseState.prototype.next = function (parser) {
  if (!this.isFailed) {
    if (parser === undefined) {
      throw new Error();
    }

    return parser.bind(this)();
  } else {
    return Nothing;
  }
};

ParseState.prototype.now = function () {
  var t = this.t[this.i];
  this.p = t.p;
  this.l = t.l;
  this.c = t.c;
  return t;
};

ParseState.prototype.expect = function (name) {
  var t = this.now();
  this.e = name;
  if (t.n === name) {
    this.succeed();
    return t;
  } else {
    this.fail();
    return Nothing;
  }
};

function Skip () {}

function Leaf (token) {
  if (token === Nothing) {
    return Nothing;
  }
  this.type = token.n;
  this.value = token.v;
  this.isLeaf = true;
  return this;
}

function t (name) {
  return function () {
    return new Leaf(this.expect(name));
  };
}

function Node (value) {
  this.type = null;
  this.value = value;
  this.isLeaf = false;
}

function p (name) {
  return function () {
    var r = ps[name].bind(this)();
    if (r.type === null) {
      r.type = name;
    }
    return r;
  };
}

function combine (ps) {
  return function () {
    var i = this.i, r;
    r = new Node(ps.maybeMap(function (p) {
      var r = this.next(p);
      return this.isFailed ? Nothing : r;
    }.bind(this)).filter(function (r) {
      return r !== Skip;
    }));
    if (this.isFailed) {
      this.i = i;
    }
    return r;
  };
}

function many (p) {
  return function () {
    var rs = [];
    while (true) {
      var r = this.next(p);
      if (this.isFailed) {
        break;
      } else {
        rs.push(r);
      }
    }
    this.recover();
    return new Node(rs);
  };
}

function many1 (p) {
  return function () {
    var rs = [], r;
    r = this.next(p);
    if (this.isFailed) {
      return Nothing;
    }
    rs.push(r);
    while (true) {
      r = this.next(p);
      if (this.isFailed) {
        break;
      } else {
        rs.push(r);
      }
    }
    this.recover();
    return new Node(rs);
  };
}

function or (ps) {
  return function () {
    var p, r, i = 0;
    while (i < ps.length) {
      p = ps[i];
      this.recover();
      r = this.next(p);
      if (!this.isFailed) {
        return r;
      }
      i++;
    }
    return Nothing;
  };
}

function skip (p) {
  return function () {
    p.bind(this)();
    return Skip;
  };
}

function sepBy (p1, p2) {
  return function () {
    var r = this.next(combine([p1, many(combine([p2.skip, p1]))]));
    if (this.isFailed) {
      return Nothing;
    }
    return new Node([r.value[0]].concat(r.value[1].value.map(function (e) {
      return e.value[0];
    })));
  };
}

function sepBy (p1, p2) {
  return function () {
    var r = this.next(combine([p1, many(combine([p2.skip, p1]))]));
    if (this.isFailed) {
      return Nothing;
    }
    return new Node([r.value[0]].concat(r.value[1].value.map(function (e) {
      return e.value[0];
    })));
  };
}

function between (p1, p2) {
  return combine([p2, p1, p2]);
}

Object.defineProperties(Array.prototype, {
  c : { get: function () { return combine(this); } },
  or: { get: function () { return      or(this); } }
});

Object.defineProperties(String.prototype, {
  t: { get: function () { return t(this.valueOf()); } },
  p: { get: function () { return p(this.valueOf()); } }
});

Object.defineProperties(Function.prototype, {
  many : {   get: function ()   { return             many(this); } },
  many1: {   get: function ()   { return            many1(this); } },
  skip : {   get: function ()   { return             skip(this); } },
  sepBy: { value: function (p2) { return        sepBy(this, p2); } }
});

var ps = {
  '='  : '='.t.skip,
  '('  : '('.t.skip,
  ')'  : ')'.t.skip,
  '{'  : '{'.t.skip,
  '}'  : '}'.t.skip,
  '['  : '['.t.skip,
  ']'  : ']'.t.skip,
  nl0  : 'NL'.t.many.skip,
  nl1  : 'NL'.t.many1.skip,

  negative
  : [
    ['-'.t, 'NUM'.t].c
    ,
    'NUM'.t
  ].or,
  constructor
  : ['ID'.t, '{'.p, 'expr'.p.sepBy(','.t), '}'.p].c
  ,
  variable
  : 'ID'.t.sepBy('.'.t)
  ,
  assignment
  : ['variable'.p, '='.p, 'expr'.p].c
  ,
  fact
  : [
    'assignment'.p
    ,
    'negative'.p
    ,
    'constructor'.p
    ,
    'variable'.p
    ,
    ['('.p, 'expr'.p, ')'.p].c
  ].or
  ,
  mul
  : ['fact'.p, '*'.t.skip, 'term'.p].c
  ,
  div
  : ['fact'.p, '/'.t.skip, 'term'.p].c
  ,
  mod
  : ['fact'.p, '%'.t.skip, 'term'.p].c
  ,
  term
  :
  ['mul'.p, 'div'.p, 'mod'.p, 'fact'.p].or
  ,
  add
  :
  ['term'.p, '+'.t.skip, 'expr'.p].c
  ,
  sub
  :
  ['term'.p, '-'.t.skip, 'expr'.p].c
  ,
  expr
  :
  ['add'.p, 'sub'.p, 'term'.p].or
  ,
  function
  : ['func'.t.skip, 'ID'.t, '('.p, 'ID'.t.sepBy(','.t), ')'.p,
     '{'.p, 'nl1'.p, 'inner_statement_list'.p, 'nl1'.p, '}'.p
    ].c
  ,
  var
  : ['var'.t.skip, [
    'ID'.t.sepBy(','.t)
    ,
    ['ID'.t, '='.p, 'expr'.p].c
  ].or].c
  ,
  struct
  : ['struct'.t.skip, 'ID'.t, '{'.p, 'nl1'.p,
     'ID'.t.sepBy('nl1'.p), 'nl1'.p,
     '}'.p
    ].c
  ,
  statement
  : [
    'function'.p
    ,
    'inner_statement'.p
  ].or
  ,
  inner_statement
  : [
    'struct'.p,
    'var'.p,
    'expr'.p

  ].or,
  statement_list
  : 'statement'.p.sepBy('nl1'.p)
  ,
  inner_statement_list
  : 'inner_statement'.p.sepBy('nl1'.p)
  ,
  program
  : ['statement_list'.p, 'EOF'.t].c
};

if (!module.parent) {
  var fs = require('fs');

  var code1 = fs.readFileSync('./sample1.k', 'utf8');
  var tokens = scan(code1);
  var s = new ParseState(tokens.tokens, 0);
  console.log(util.inspect(s.next('program'.p), false, null));
}

sample1.k

struct foo {
  field1
  field2
}