parser.js

function isMetaVariable(tk) {
  return tk[0] === '$';
}

function subst(env, replacement) {
  if (Array.isArray(replacement)) {
    return replacement.map(function (item) { return subst(env, item); });
  } else if (isMetaVariable(replacement)) {
    return env[replacement];
  } else {
    return replacement;
  }
}

function variables(pattern) {
  var ret = [];
  for (var i = 0; i < pattern.length; ++i) {
    if (isMetaVariable(pattern[i])) {
      ret.push(pattern[i]);
    }
  }
  return ret;
}

function mkEnv (args, pattern) {
  var env = {};
  var vs = variables(pattern);
  if (args.length != vs.length) {
    console.log(vs);
    console.log(args);
    throw "bad arguments";
  }
  for (var i = 0; i < args.length; ++i) {
    env[vs[i]] = args[i];
  }
  return env;
}

function keywordsInNotations(notations) {
  var kws = {};
  for (var i = 0; i < notations.length; ++i) {
    var notation = notations[i];
    for (var j = 0; j < notation.pattern.length; ++j) {
      var tk = notation.pattern[j];
      if (isMetaVariable(tk)) {
        continue;
      } else {
        kws[tk] = true;
      }
    }
  }
  return kws;
}

function notationMap(notations) {
  var ret = {};
  l:
  for (var i = 0; i < notations.length; ++i) {
    for (var j = 0; j < notations[i].pattern.length; ++j) {
      if (isMetaVariable(notations[i].pattern[j])) {
        continue;
      } else {
        ret[notations[i].pattern[j]] = notations[i];
        continue l;
      }
    }
    ret[""] = notations[i];
  }
  return ret;
}

function parse(notations, tokens) {
  var stack = [];
  var map = notationMap(notations);
  var kws = keywordsInNotations(notations);
  var left = null;

  var takeOperand = function () {
    var v = stack[stack.length - 1];
    v.args.push(left);
    v.unconsumed = v.unconsumed.slice(1);
    left = null;
  };
  
  var reduce = function () {
    var v = stack.pop();
    if (v.unconsumed.length === 0) {

      var replacement = subst(mkEnv(v.args, v.notation.pattern), v.notation.replacement);
      left = replacement;
    } else if (isMetaVariable(v.unconsumed[0])) {
      return { ParseError: { at: i }};
      // throw "parse error on input `" + tokens[i].token + "'";
    } else {
      return { ParseError: { Expected: v.unconsumed[0], at: i }};
      // throw v.unconsumed[0] + " expected";
    }
  };

  var reduceGroup = function (notation) {
    var reduce1 = function () {
      takeOperand();
      return reduce();
    };

    for (var i = stack.length - 1; i >= 0; --i) {
      var v = stack[i];
      if (v.notation.level < notation.level) {
        return;
      } else if (v.notation.level > notation.level) {
        var err = reduce1();
        if (err) {
          return err;
        }
      } else if (v.notation.associativity.left &&
                 notation.associativity.left) {
        var err = reduce1();
        if (err) {
          return err;
        }
      } else if (v.notation.associativity.right &&
                 notation.associativity.right) {
        return;
      } else {
        //console.log(v);
  //console.log(notation);
        return { ParseError: { CantAssoc: [v, notation], at: i }};
        // throw "can't assoc";
      }
    }
  };

  for (var i = 0; i < tokens.length; ++i) {
    var tk = tokens[i];

    if (kws[tk.token]) {
      var notation = map[tk.token];
      if (notation) {
        if (isMetaVariable(notation.pattern[0])) {
          reduceGroup(notation);
          var v = {
            notation: notation,
            args: [left],
            unconsumed: notation.pattern.slice(2)
          };
          left = null;
          stack.push(v);
        } else {
          var v = {
            notation: notation,
            args: [],
            unconsumed: notation.pattern.slice(1)
          };
          stack.push(v);
        }
      } else {
      }
    } else if (left) {
      var notation = map[""];
      if (notation) {
        reduceGroup(notation);
        var v = {
          notation: notation,
          args: [left],
          unconsumed: notation.pattern.slice(2)
        };
        left = tk;
        stack.push(v);
      } else {
        return { ParseError: { at: i } };
      }
    } else {
      left = tk;
    }
  }

  var len = stack.length;

  for (var i = 0; i < len; ++i) {
    takeOperand();
    reduce();
  }

  return left;
}

module.exports = {
  parse: parse
};

test.js

var fs = require('fs');
var path = process.argv[2]
var tokenizer = require('./src/tokenizer');
var parser = require('./src/parser');

fs.readFile(path, 'utf8', function (err, text) {
  //console.log(tokenizer.tokenize([".",","], text));
  var tks = tokenizer.tokenize([".",","], text);
  var ast = parser.parse(
    [ { pattern: ["$a","$b"], level: "9", associativity: { right: true }, replacement: ["$a", "$b"] }
    , { pattern: ["$a", ",", "$b"], level: "9", associativity: { right: true }, replacement: ["@UNORDERED-PAIR", "$a", "$b"] }
    , { pattern: ["$a", "=", "$b"], level: "1", associativity: { right: true }, replacement: ["@ASSIGN", "$a", "$b"] }
    , { pattern: ["$a", ";", "$b"], level: "05", associativity: { right: true }, replacement: ["@SEQUENCE", "$a", "$b"] }
    , { pattern: ["$a",".","$b"], level: "95",  associativity: { left: true }, replacement: ["@MEMBER", "$a", "$b"] }
    ], tks);
  console.log(JSON.stringify(ast, null, 2));
});

test.lth

_ = require "underscore";
console.log _.shuffle Array 1, 2, 3 

tokenizer.js

function tokenize(tokenDef, text) {
  var lineno = 0;
  var columnno = 0;
  var t = "ident";
  var tokens = [];
  var buf = "";

  var reset = function () {
    buf = "";
  };

  var take = function (n) {
    var s = text.slice(0, n);
    buf += s;
    text = text.slice(n);
    columnno += s.length;
  };

  var push_token = function () {
    if (buf !== "") {
      tokens.push({ lineno: lineno, columnno: columnno - buf.length, token: buf });
      buf = "";
    }
  };

  while (text !== "") {
    if (t === "ident") {
      for (var i = 0; i < tokenDef.length; ++i) {
        var tk = tokenDef[i];
  var look = text.slice(0, tk.length);
  if (tk === look) {
    push_token();
    take(tk.length);
    push_token();
  }
      }

      if (text[0] === '"') {
        push_token();
  take(1);
        t = "str";
      } else if (text[0] === ' ' || text[0] === '\n') {
        push_token();
  while (text[0] === ' ' || text[0] === '\n') {
    if (text[0] == '\n') {
      lineno += 1;
      columnno = 0;
    } else {
      columnno += 1;
    }
      text = text.slice(1);
  }
      } else {
  take(1);
      }
    } else if (t === "str") {
      if (text[0] === '"') {  
  take(1);
  push_token();
  t = "ident";
      } else if (text[0] === '\\') {

  if (text.length === 1) {
    take(1);
  } else {
    take(2);
  }
      } else {
  take(1);
      }
    }
  }

  push_token();

  return tokens;
}

module.exports = {
  tokenize: tokenize
};