Recursive descent parser that supports functions

parser.js

function Interpreter() {
  this.scopeStack = [{}];
  this.functions = {};
}

const operators = ['+', '-', '/', '*', '%', '=', '=>', ')'];

Interpreter.prototype.tokenize = function (program) {
  if (program === "") return [];

  var regex =
    /\s*(=>|[-+*\/\%=\(\)]|[A-Za-z_][A-Za-z0-9_]*|[0-9]*\.?[0-9]+)\s*/g;
  return program.split(regex).filter(function (s) {
    return !s.match(/^\s*$/);
  });
};

Interpreter.prototype.reduceTree = function (ast) {
  const vars = this.scopeStack[0];

  if (ast.op === "nop") return "";
  if (ast.op === "lit") {
    return ast.child;
  }

  if (ast.op === "id") {
    if (ast.child in vars) {
      return vars[ast.child];
    } else {
      throw new Error(
        `Invalid variable reference. No variable '${ast.child}' found`
      );
    }
  }

  let ident = null;

  switch (ast.op) {
    case "+":
      return this.reduceTree(ast.left) + this.reduceTree(ast.right);
    case "-":
      return this.reduceTree(ast.left) - this.reduceTree(ast.right);
    case "/":
      return this.reduceTree(ast.left) / this.reduceTree(ast.right);
    case "*":
      return this.reduceTree(ast.left) * this.reduceTree(ast.right);
    case "%":
      return this.reduceTree(ast.left) % this.reduceTree(ast.right);
    case "=":
      ident = ast.left.child;
      if (ident in this.functions)
        throw new Error(`Function with name '${ident}' already exists`);
      vars[ident] = this.reduceTree(ast.right);
      return vars[ident];
    case "=>":
      ident = ast.id.child;
      if (ident in vars)
        throw new Error(`Variable with name '${ident}' already exists`);
      this.functions[ident] = { name: ident, args: ast.args, body: ast.body };
      return "";
    case "call":
      ident = ast.id.child;
      const func = this.functions[ident];

      if (ast.variables.length !== func.args.length) {
        throw new Error(
          `Function '${ident}' expected ${func.args.length} parameters but got ${ast.variables.length} parameters instead`
        );
      }

      const variables = ast.variables.map((v) => this.reduceTree(v));

      const newScope = func.args.reduce((a, b, i) => {
        a[b.child] = variables[i];
        return a;
      }, {});

      this.scopeStack.unshift(newScope);
      const result = this.reduceTree(func.body);
      this.scopeStack.shift();
      return result;
  }
};

Interpreter.prototype.input = function (expr) {
  var tokens = this.tokenize(expr);
  var ast = parse(tokens, this.functions);
  console.log(ast);
  return this.reduceTree(ast);
};

function parse(tokens, functions) {
  let index = 0;

  function parseCall() {
    const node = { op: "call" };

    node.id = parseIdentifier();
    
    let nArgs = functions[node.id.child].args.length;

    node.variables = [];

    while (nArgs > 0) {
      if (tokens[index] in functions) {
        node.variables.push(parseCall())
      } else {
        node.variables.push(parseElement(true));
      }
      nArgs --;
    }

    return node;
  }

  function parseFn() {
    const node = { op: "=>" };
    node.id = parseIdentifier();

    node.args = [];
    while (tokens[index] != "=>") {
      node.args.push(parseIdentifier());
    }
    
    const argsSet = new Set(node.args.map(a => a.child));
    
    if (argsSet.size !== node.args.length) {
      throw new Error("Duplicate arguments in function definition")
    }

    index++;
    node.body = parseAdditive();
    
    function verifyFuncVars(body) {
      if (body.op === 'lit') {
        return;
      }
      
      if (body.op === 'id' && !node.args.find(a => a.child === body.child)) {
        throw new Error(`Variable '${body.child}' is not defined in function scope`)
      } else if (body.op === 'id') {
        return;
      }
      
      verifyFuncVars(body.left);
      verifyFuncVars(body.right);
    }
    
    verifyFuncVars(node.body)

    return node;
  }
  
  function parseLine() {
    if (!tokens[0]) {
      return { op: "nop" };
    }
    
    if (tokens[0] === "fn") {
      index++;
      return parseFn();
    }
    
    if (tokens[1] === "=") {
      return parseAssignment();
    }
        
    if (tokens[0] in functions) {
      const result = parseCall();
      if (tokens[index]) {
        throw new Error("Invalid program")
      }
      return result;
    }
    return parseAdditive();
  }

  function parseAssignment() {
    const node = {};

    if (tokens[index + 1] === "=") {
      node.op = "=";
      node.left = parseIdentifier();
      index += 1;
      node.right = parseAssignment();

      return node;
    }

    return parseAdditive();
  }

  function parseMultiplicative() {
    let node = parseFactor();
    while (index < tokens.length && /[\/*%]/.test(tokens[index])) {
      let op = { op: tokens[index] };
      index++;
      op.left = node;
      op.right = parseFactor();
      node = op;
    }
    return node;
  }

  function parseAdditive() {
    let node = parseMultiplicative();

    while (index < tokens.length && /[+\-]/.test(tokens[index])) {
      let op = { op: tokens[index] };
      index++;
      op.left = node;
      op.right = parseMultiplicative();
      node = op;
    }
    return node;
  }

  function parseParentheses() {
    index++;
    let node = null;
    if (tokens[index + 1] === '=') {
      node = parseAssignment()
    } else {
      node = parseAdditive();
    }
    index++;
    return node;
  }

  function parseFactor() {
    if (tokens[index] === "(") {
      return parseParentheses();
    }

    return parseElement();
  }

  function parseIdentifier() {
    const isIdentifier = /^[a-zA-Z_]/.test(tokens[index]);

    if (isIdentifier) {
      const node = { op: "id", child: tokens[index] };
      index++;
      return node;
    }
  }

  function parseLiteral() {
    if (!isNaN(tokens[index])) {
      const isFloat = /\./.test(tokens[index]);
      const numValue = isFloat
        ? parseFloat(tokens[index])
        : parseInt(tokens[index]);
      index++;
      return { op: "lit", child: numValue };
    }
  }

  function parseElement(asArg = false) {
    let node = parseIdentifier();
    if (!node) node = parseLiteral(); 

    if (!asArg && tokens[index] && !operators.includes(tokens[index])) {
      throw new Error("Invalid program")
    }
    return node;
  }

  return parseLine();
}