Recursive Descent Parser for simple expression evaluator

recursive-descent-parser.js

function Compiler () {
};

Compiler.prototype.compile = function (program) {
  return this.pass3(this.pass2(this.pass1(program)));
};

Compiler.prototype.tokenize = function (program) {
  // Turn a program string into an array of tokens.  Each token
  // is either '[', ']', '(', ')', '+', '-', '*', '/', a variable
  // name or a number (as a string)
  var regex = /\s*([-+*/\(\)\[\]]|[A-Za-z]+|[0-9]+)\s*/g;
  return program.replace(regex, ":$1").substring(1).split(':').map( function (tok) {
    return isNaN(tok) ? tok : tok|0;
  });
};

Compiler.prototype.pass1 = function (program) {
  const tokens = this.tokenize(program);
  
  const programArgs = [];
  
  let arg = tokens.shift(); // remove the "["
  
  while(arg = tokens.shift()) {
    if (arg == "]") {
      break;
    }
    programArgs.push(arg);
  }
  
  return parse(tokens, programArgs)
};

function parse(tokens, args) {
  let index = 0;
  
  function parseImmOrArg() {
    
    const token = tokens[index];
    index++;
    const argIndex = args.findIndex(i => i === token)
    
    if(argIndex === -1) {
      return {op: "imm", n: parseInt(token)}
    }
    return {op: "arg", n: argIndex}
  }
  
  function parseAddSub() {
    let node = parseMulDiv();
    
    while (index < tokens.length && /[+\-]/.test(tokens[index])) {
      let op = {op: tokens[index]};
      index++;
      op.a = node;
      op.b = parseMulDiv();
      node = op;
    }
    return node;
  }
  
  function parseMulDiv() {
    let node = parseFactor();
    while (index < tokens.length && /[\/*]/.test(tokens[index])) {
      let op = {op: tokens[index]};
      index++;
      op.a = node;
      op.b = parseFactor();
      node = op;
    }
    return node;
  }
  
  function parseParentheses() {
    index++; // '('
    let node = parseAddSub();
    index++; // ')'
    return node;
  }
  
  function parseFactor() {
    if (tokens[index] === '(') {
        return parseParentheses();
    }
    return parseImmOrArg();
  }
  
  return parseAddSub();
}

Compiler.prototype.pass2 = function (ast) {
  // return AST with constant expressions reduced
  return reduceConstantExpr(ast)
};

function reduceConstantExpr(node) {
  const unOps = ['imm', 'arg']
  if (unOps.includes(node.op)) {
    return node;
  }
  
  node.a = reduceConstantExpr(node.a)
  node.b = reduceConstantExpr(node.b)
  const leftIsConstant = node.a.op === "imm";
  const rightIsConstant = node.b.op === "imm";
  
  if (leftIsConstant && rightIsConstant) {
    return { op: 'imm', n: eval(`${node.a.n} ${node.op} ${node.b.n}`) }
  }
  
  return node;
}

Compiler.prototype.pass3 = function (ast) {
  // return assembly instructions
  
  return toAssembly(ast);
};

const operationMap = {
  "+": "AD",
  "-": "SU",
  "/": "DI",
  "*": "MU",
  "imm": "IM",
  "arg": "AR",
}

function toAssembly(ast) {
  const operation = operationMap[ast.op]
  
  if (operation === "IM" || operation === "AR") {
    return [`${operation} ${ast.n}`];
  }
  
  const isRightRecursing = !["imm", "arg"].includes(ast.b.op)
  
  // costs an extra swap instruction
  const preserveOrder = operation === "DI" || operation === "SU" 

  return [
    ...toAssembly(ast.a),
    isRightRecursing ? "PU" : "SW",
    ...toAssembly(ast.b),
    (preserveOrder || isRightRecursing) && "SW",
    isRightRecursing && "PO",
    operation
  ].filter(Boolean)  
}