An Operator-precedence parser, Abstract Syntax Tree and Stack Machine Experiment

test-ast.js

(function(root, factory) {
  if(typeof define === 'function' && define.amd) {
    // AMD. Register as an anonymous module.
    define(['exports'], function(exports) {
      factory((root.chocomilk = exports), b);
    });
  } else if(typeof exports === 'object' && typeof exports.nodeName !== 'string') {
    // CommonJS
    factory(exports);
  } else {
    // Browser globals
    factory((root.chocomilk = {}));
  }
}(this, function(exports) {
  'use strict';
  const symbols = {
    openParenthesis: Symbol('open parenthesis'),
    closeParenthesis: Symbol('close parenthesis'),
    separator: Symbol('separator')
  };

  const operators = mapOps([{
    // Control operators
    alias: ['(', '[', '{'],
    name: 'group', right: true, precedence: 20,
    fn(...v) { return v.length > 1 ? v : v[0]; },
    tag: symbols.openParenthesis
  }, {
    alias: [')', ']', '}'],
    name: 'groupend', left: true, precedence: 20,
    tag: symbols.closeParenthesis
  }, {
    alias: [',', ';'],
    name: 'separator', left: true, right: true, precedence: 1,
    tag: symbols.separator
  }, {
    alias: [':=', '::'],
    name: 'assign', left: true, right: true, precedence: 3,
    fn(l, r) { this.regisary[l] = r; return r; }
  }, {
    alias: ['@', 'TAKE', 'GET'],
    name: 'take', right: true, precedence: 19,
    fn(v) { return this.regisary[v]; }
  }, {
    alias: ['->', 'GOTO', 'JUMP'],
    name: 'jump', left: true, right: true, precedence: 3,
    fn(l, r) { if(l !== 0) this.jumpTo(r); return r; }
  }, {
    // Math operators
    alias: ['+', 'ADD', 'PLUS'],
    name: 'add', left: 'optional', right: true, precedence: 15,
    fn(l, r) { return (!l && l !== 0) ? r : (l + r); }
  }, {
    alias: ['-', 'SUB', 'SUBTRACT', 'MINUS'],
    name: 'substract', left: 'optional', right: true, precedence: 15,
    fn(l, r) { return (!l && l !== 0) ? -r : (l - r); }
  }, {
    alias: ['*', 'MUL', 'MULTIPLY', 'TIMES'],
    name: 'multiply', left: true, right: true, precedence: 16,
    fn(l, r) { return l * r; }
  }, {
    alias: ['/', 'DIV', 'DIVIDE'],
    name: 'divide', left: true, right: true, precedence: 16,
    fn(l, r) { return l / r; }
  }, {
    alias: ['%', 'MOD', 'MODULO', 'REM', 'REMAINDER'],
    name: 'remainder', left: true, right: true, precedence: 16,
    fn(l, r) { return l % r; }
  }, {
    alias: ['^', '**', 'POW', 'POWER'],
    name: 'power', left: true, right: true, precedence: 17,
    fn: Math.pow
  }, {
    alias: ['!', 'FRACTORIAL'],
    name: 'fractorial', left: true, precedence: 18,
    fn(v) {
      if(!this.frac) this.frac = [1, 1];
      if(this.frac[v]) return this.frac[v];
      let i = this.frac.length, r = this.frac[i];
      for(; i <= v; i++)
        this.frac[i] = r *= i;
      return r;
    }
  }, {
    // Advanced math operators
    alias: ['CEIL', 'CEILLING'],
    name: 'ceil', right: true, precedence: 4,
    fn: Math.ceil
  }, {
    alias: ['FLOOR'],
    name: 'floor', right: true, precedence: 4,
    fn: Math.floor
  }, {
    alias: ['ROUND'],
    name: 'round', right: true, precedence: 4,
    fn: Math.floor
  }, {
    alias: ['TRUNC', 'TRUNCATE'],
    name: 'trunc', right: true, precedence: 4,
    fn: Math.trunc
  }, {
    alias: ['MAX', 'BIG', 'BIGGER'],
    name: 'max', right: true, precedence: 4,
    fn: Math.max
  }, {
    alias: ['MIN', 'SMALL', 'SMALLER'],
    name: 'min', right: true, precedence: 4,
    fn: Math.min
  }, {
    alias: ['CLAMP'],
    name: 'clamp': left: true, right: true, precedence: 4,
    fn(v, min, max) { return v < min ? min : v > max ? max : v; }
  }, {
    alias: ['RANDOM', 'RAND'],
    name: 'random', precedence: 4,
    fn: Math.random
  }, {
    alias: ['SIN'],
    name: 'sin', right: true, precedence: 4,
    fn: Math.sin
  }, {
    alias: ['COS'],
    name: 'cos', right: true, precedence: 4,
    fn: Math.cos
  }, {
    alias: ['TAN'],
    name: 'tan', right: true, precedence: 4,
    fn: Math.tan
  }, {
    alias: ['ASIN'],
    name: 'asin', right: true, precedence: 4,
    fn: Math.asin
  }, {
    alias: ['ACOS'],
    name: 'acos', right: true, precedence: 4,
    fn: Math.acos
  }, {
    alias: ['ATAN'],
    name: 'atan', right: true, precedence: 4,
    fn: Math.atan
  }, {
    alias: ['SINH'],
    name: 'sinh', right: true, precedence: 4,
    fn: Math.sinh
  }, {
    alias: ['COSH'],
    name: 'cosh', right: true, precedence: 4,
    fn: Math.cosh
  }, {
    alias: ['TANH'],
    name: 'tanh', right: true, precedence: 4,
    fn: Math.tanh
  }, {
    alias: ['ASINH'],
    name: 'asinh', right: true, precedence: 4,
    fn: Math.asinh
  }, {
    alias: ['ACOSH'],
    name: 'acosh', right: true, precedence: 4,
    fn: Math.acosh
  }, {
    alias: ['ATANH'],
    name: 'atanh', right: true, precedence: 4,
    fn: Math.atanh
  }, {
    alias: ['LOG'],
    name: 'log', left: true, right: true, precedence: 4,
    fn(l, r) { return Math.log(r) / Math.log(l); }
  }, {
    alias: ['PI'],
    name: 'pi', precedence: 4,
    fn() { return Math.PI; }
  }, {
    alias: ['E'],
    name: 'e', precedence: 4,
    fn() { return Math.E; }
  }, {
    // Binary/logical operators
    alias: ['AND', '&'],
    name: 'and', left: true, right: true, precedence: 10,
    fn(l, r) { return l & r; }
  }, {
    alias: ['NAND', '~&'],
    name: 'nand', left: true, right: true, precedence: 10,
    fn(l, r) { return ~(l & r); }
  }, {
    alias: ['OR', '|'],
    name: 'or', left: true, right: true, precedence: 10,
    fn(l, r) { return l | r; }
  }, {
    alias: ['NOR', '~|'],
    name: 'nor', left: true, right: true, precedence: 10,
    fn(l, r) { return ~(l | r); }
  }, {
    alias: ['XOR'],
    name: 'xor', left: true, right: true, precedence: 10,
    fn(l, r) { return l ^ r; }
  }, {
    alias: ['XNOR'],
    name: 'xnor', left: true, right: true, precedence: 10,
    fn(l, r) { return ~(l ^ r); }
  }, {
    alias: ['NOT', '~'],
    name: 'not', right: true, precedence: 9,
    fn(v) { return ~v; }
  }, {
    alias: ['<<'],
    name: 'lshift', left: true, right: true, precedence: 13,
    fn(l, r) { return l << r; }
  }, {
    alias: ['>>'],
    name: 'rshift', left: true, right: true, precedence: 13,
    fn(l, r) { return l >> r; }
  }, {
    alias: ['>>>'],
    name: 'urshift', left: true, right: true, precedence: 13,
    fn(l, r) { return l >> r; }
  }, {
    // Compare operators
    alias: ['=', '==', '==='],
    name: 'eq', left: true, right: true, precedence: 12,
    fn(l, r) { return l === r ? 1 : 0; }
  }, {
    alias: ['=/='],
    name: 'ieq', left: true, right: true, precedence: 12,
    fn(l, r) { return l !== r ? 1 : 0; }
  }, {
    alias: ['<='],
    name: 'lte', left: true, right: true, precedence: 12,
    fn(l, r) { return l <= r ? 1 : 0; }
  }, {
    alias: ['>='],
    name: 'gte', left: true, right: true, precedence: 12,
    fn(l, r) { return l >= r ? 1 : 0; }
  }, {
    alias: ['<'],
    name: 'lt', left: true, right: true, precedence: 12,
    fn(l, r) { return l < r ? 1 : 0; }
  }, {
    alias: ['>'],
    name: 'gt', left: true, right: true, precedence: 12,
    fn(l, r) { return l > r ? 1 : 0; }
  }, {
    alias: ['?'],
    name: 'choose', left: true, right: true, precedence: 5,
    fn(l, ...r) { return r[l < r.length && l >= 0 ? l : 0]; }
  }]);

  const linebreakMatcher = /(?!\/)(?:\r|\n|\r\n)/g;
  const spaceMatcher = /^\s+/;
  const numMatcher = /^(?:0|[1-9]\d*)(?:\.\d+)?(?:E[+-]?\d+)?/i;
  const stringMatcher = /^"(?:[^"\\]+|\\.)*"/;
  const commentMatcher = /^\/\//;
  const labelMatcher = /^\s*([A-Za-z]\w*):/;

  function mapOps(ops) {
    if(!Array.isArray(ops)) return {};
    const output = {};
    for(const op of ops)
      for(const alias of op.alias)
        output[alias] = op;
    return output;
  }

  const unescapeString = (() => {
    const escapeMatcher = /\\(?:([1-7][0-7]{0,2}|[0-7]{2,3})|x([0-9A-F]{2})|u([0-9A-F]+)|(.))/ig;
    const quoteMatcher = /^"|"$/g;
    function escapeReplacer(match, oct8, hex8, hexu, literal) {
      if(oct8) return String.fromCharCode(parseInt(oct8, 8));
      if(hex8) return String.fromCharCode(parseInt(hex8, 16));
      if(hexu) return String.fromCodePoint(parseInt(hexu, 16));
      switch(literal.toLowerCase()) {
        case '0': return '\0';
        case 'b': return '\b';
        case 'e': return '\x1b';
        case 'f': return '\f';
        case 'n': return '\n';
        case 'r': return '\r';
        case 't': return '\t';
        case 'v': return '\v';
        case '\'': case '\"': case '\\': return literal;
        default: return '';
      }
    }
    return function(str) {
      return str.replace(escapeMatcher, escapeReplacer).replace(quoteMatcher, '');
    };
  })();

  const keyMatcher = (() => {
    const escapeMatcher = /[\-\[\]\/\{\}\(\)\*\+\?\.\\\^\$\|]/g;
    const lookupMatcher = /[A-Z0-9]$/i;
    function lengthSorter(l, r) {
      return r.length - l.length;
    }
    function keyMapper(key) {
      return key.replace(escapeMatcher, '\\$&') +
      (key.match(lookupMatcher) ? '(?![A-Z0-9])' : '');
    }
    return function(keys) {
      keys = Object.keys(keys)
      .sort(lengthSorter)
      .map(keyMapper)
      .join('|');
      return new RegExp(`^(?:${keys})`, 'i');
    };
  })();

  function flatten(source) {
    const result = [];
    while(source.length) {
      const entry = source.shift();
      if(Array.isArray(entry)) source.unshift(...entry);
      else result.push(entry);
    }
    return result;
  }

  class Node extends Array {
    constructor(op, fillLeft) {
      super();
      this.op = op;
      if(fillLeft) this.push(undefined);
    }
    push(child) {
      if(typeof child === 'object')
        child.parent = this;
      super.push(child);
    }
    pop() {
      const child = super.pop();
      if(typeof child === 'object')
        delete child.parent;
      return child;
    }
    toString() {
      return this.op && this.op.name;
    }
  }

  function* tokenize(expression, operators) {
    if(typeof expression !== 'string')
      throw new Error('Expression must be a string');
    const exprMatcher = keyMatcher(operators);
    while(expression.length) {
      const spaceMatch = expression.match(spaceMatcher);
      if(spaceMatch) {
        expression = expression.substr(spaceMatch[0].length);
        continue;
      }
      const commentMatch = expression.match(commentMatcher);
      if(commentMatch) {
        break;
      }
      const numMatch = expression.match(numMatcher);
      if(numMatch) {
        yield { type: 0, value: parseFloat(numMatch[0]) };
        expression = expression.substr(numMatch[0].length);
        continue;
      }
      const strMatch = expression.match(stringMatcher);
      if(strMatch) {
        yield { type: 0, value: unescapeString(strMatch[0]) };
        expression = expression.substr(strMatch[0].length);
        continue;
      }
      const exprMatch = expression.match(exprMatcher);
      if(exprMatch) {
        yield { type: 1, value: exprMatch[0].toUpperCase() };
        expression = expression.substr(exprMatch[0].length);
        continue;
      }
      throw new Error(`Unexpected token '${expression.charAt(0)}'`);
    }
  }

  function constructTree(expression, operators) {
    const rootOp = Object.assign({}, operators['('], {
      precedence: -Infinity
    });
    const root = new Node(rootOp);
    const stack = [root];
    let node = root;
    for(const token of tokenize(expression, operators)) {
      switch(token.type) {
        case 0: {
          node.push({ tip: true, value: token.value });
          break;
        }
        case 1: {
          const op = operators[token.value];
          if(!op) throw new Error(`Unexpected token '${token.value}'`);
          switch(op.tag) {
            case symbols.openParenthesis: {
              const root = new Node(rootOp);
              stack.push(root);
              node.push(root);
              node = root;
              break;
            }
            case symbols.separator: {
              const root = new Node(rootOp);
              const oldRoot = stack.pop();
              oldRoot.op = operators['('];
              oldRoot.parent.push(root);
              stack.push(root);
              node = root;
              break;
            }
            case symbols.closeParenthesis: {
              stack.pop().op = operators['('];
              node = stack[stack.length - 1];
              break;
            }
            default: {
              const child = new Node(op);
              if(op.left && (op.left !== 'optional' || node.length)) {
                while(node.op.precedence > op.precedence)
                  node = node.parent;
                child.push(node.pop());
              }
              node.push(child);
              if(op.right)
                node = child;
              break;
            }
          }
          break;
        }
        default: throw new Error(`Unexpected token type '${token.type}'`);
      }
    }
    return root;
  }

  function* constructExecuteQueue(ast) {
    const constStack = [{ node: ast, i: 0 }];
    while(constStack.length) {
      const current = constStack[constStack.length - 1];
      const node = current.node;
      if(node.tip) {
        constStack.pop();
        yield node;
      } else if(current.i < node.length) {
        constStack.push({ node: node[current.i], i : 0 });
        current.i++;
      } else {
        constStack.pop();
        yield { tip: true, value: node.length };
        yield node;
      }
    }
  }

  function runAST(ast, options) {
    const { debug, env } = options || {};
    const execStack = [];
    for(const current of constructExecuteQueue(ast)) {
      if(!current)
        throw new Error('Invalid stack');
      if(current.tip) {
        execStack.push(current.value);
        continue;
      }
      execStack.push(current);
      if(debug) debug(execStack.join(' '));
      const node = execStack.pop(), argc = execStack.pop();
      const input = argc > 0 ? execStack.splice(execStack.length - argc, argc) : [];
      const result = node.op.fn.call(env, ...input);
      if(Array.isArray(result))
        execStack.push(...result);
      else
        execStack.push(result);
      if(debug) debug(execStack.join(' '));
    }
    return execStack.pop();
  }

  exports.evalScript = function evalScript(script, options) {
    const labelMap = {};
    options = options || {};
    const op = Object.assign({}, operators, mapOps(options.operators));
    const lines = script.split(linebreakMatcher)
    .map((line, index) => {
      const labelMatch = line.match(labelMatcher);
      if(labelMatch) {
        labelMap[labelMatch[1]] = index;
        line = line.substr(labelMatch[0].length);
      }
      return constructTree(line, op);
    });
    let i;
    options = Object.assign(options || {}, {
      env: {
        regisary: {},
        jumpTo(pos) {
          switch(typeof pos) {
            case 'number': i = pos - 1; break;
            case 'string':
              if(pos in labelMap) {
                i = labelMap[pos] - 1;
                break;
              }
              pos = parseInt(pos);
              if(!Number.isNaN(pos)) {
                i = pos - 1;
              }
              break;
          }
          if(options.debug) options.debug(`Jump to ${pos} ${i}`);
        }
      }
    });
    for(i = 0; i < lines.length; i++) {
      if(options.debug) options.debug(`Line ${i}`);
      const r = runAST(lines[i], options);
      if(options.debug) options.debug(`= ${r}`);
    }
  }

  exports.evalLine = function evalLine(expression, options) {
    options = options || {};
    const op = Object.assign({}, operators,mapOps(options.operators));
    return runAST(constructTree(expression, op), options);
  }
}));