Lisp Parser - Write code that takes some Lisp code and returns an abstract syntax tree. The AST should represent the structure of the code and the meaning of each token. For example, if your code is given "(first (list 1 (+ 2 3) 9))", it could return a nested array like ["first", ["list", 1, ["+", 2, 3], 9]].

lisp-parser.js

// input "" -> null
// input "()" -> []
// input "(1)" -> [1]

//             0123456
// const input = "(first (list 1 (+ 2 3) 9))"
// example out: ["first", ["list", 1, ["+", 2, 3], 9]]
// (+ 2 3) -> ["+", 2, 3]
// (list 1 (+ 2 3) 9) -> ["list", 1, ["+", 2, 3], 9]
function parse(input) {
  let offset = 0;

  return parse_();

  function parse_() {
    const t = nextToken();
    if (t === "(") {
      const result = [];
      let cursor;
      while (true) {
        cursor = parse_();
        if (cursor === null) {
          throw new Error("Unexpected EOF offset:" + offset);
        }
        if (cursor === ")") {
          break;
        }
        result.push(cursor);
      }
      return result;
    } else {
      return t;
    }
  }

  // returns either 
  function nextToken() {
    const ch = input[offset]
    offset += 1;

    if (ch === undefined) {
      return null;
    }

    if (ch === "(") {
      return "("
    }

    if (ch === ")") {
      return ")"
    }

    if (/\s/.test(ch)) {
      return nextToken();
    }

    // number
    if (/\d/.test(ch)) {
      const begin = offset - 1;
      while (/\d/.test(current())) {
        offset += 1;
      }
      const numberStr = input.slice(begin, offset);
      return +numberStr;
    }

    // not (, ), " ", or number; so it's an ID
    const begin = offset - 1;
    while (current() !== null && !/\s|[()]/.test(current())) {
      offset += 1;
    }
    const id = input.slice(begin, offset);
    return id;
  }

  function current() {
    return input[offset] || null;
  }
}

function arrayEquals(a, b) {
  if (!Array.isArray(a) || !Array.isArray(b)) {
    return a === b;
  }

  if (a.length !== b.length) {
    return false;
  }

  for (let i = 0; i < a.length; i++) {
    if (!arrayEquals(a[i], b[i])) {
      return false;
    }
  }
  return true;
}

{
  // [input, expected output, expected exception]
  const cases = [
    ["(a 123)", ["a", 123]],
    ["(a b)", ["a", "b"]],
    ["(a 1)", ["a", 1]],
    ["(first (list 1 (+ 2 3) 9))", ["first", ["list", 1, ["+", 2, 3], 9]]],
    ["", null],
    ["()", []],
    ["id", "id"],
    ["(", undefined, "Unexpected EOF offset:2"]
  ]

  for (const test of cases) {
    try {
      const input = test[0];
      const result = parse(input);
      const pass = arrayEquals(result, test[1]);
      console.log(pass, "Parsing " + input, pass ? "" : result);
    } catch (err) {
      const pass = test[2] == err.message
      console.log(pass, err.message)
    }
  }
}