An unfancy Lisp parser for the Recurse Center's pairing interview programming task

recurseLispParser.js

/**
 * Lisp Parser
 *
 * This JavaScript defines some unfancy parser combinators for Lisp values and Lisp arrays
 * and composes them to define a Lisp parser. The Lisp values can be any sequence of characters
 * as long as they aren't parens, space, or newline.
 *
 * I (Elliot) wrote this on Aug 8th for the Recurse Center's pairing interview programming task.
 * Here's some types that hopefully help make the code easier to read and follow.
 *
 * A lisp parse tree represented as nested string arrays.
 * @typedef {LispAST[]} LispASTList
 * @typedef {string | LispASTList} LispAST
 *
 * A function that tries to parse part of the given string `str`. If it succeeds
 * in parsing some of the string then `parse` will not be the empty string and
 * the `str` in the result object should be the input string with the parsed part removed.
 * @typedef {(str: string) => { parse: any, str: string }} ParserCombinator
 */

/**
 * Parses Lisp values. Lisp values can be any sequence of characters
 * as long as they aren't parens, spaces, or newlines.
 *
 * @type {ParserCombinator}
 * @param {string} str parse this string if it starts with a "value" string
 * @returns {{ parse: string, str: string }}
 */
const pValue = (str) => {
  let parse = "";
  for (const char of str) {
    if (char === " " || char === "\n" || char === "(" || char === ")") break;
    parse += char;
  }
  return { parse, str: str.slice(parse.length) };
};

/**
 * @type {ParserCombinator}
 * @param {string} str parse this string if it starts with a valid value
 * @returns {{ parse: LispAST[], str: string }}
 */
const pList = (initStr) => {
  if (initStr.at(0) !== "(") return { parse: "", str: initStr };
  let str = initStr.slice(1);

  let parse = [];
  while (true) {
    // pLisp is defined below in terms of pList, to make this recursive definition work we wrap the call to pListOrVal in an arrow function.
    const res = ((str) => pLisp(str))(str.trim());
    if (res.parse === "") {
      str = str.trim();
      if (str.at(0) !== ")") return { parse: "", str: initStr };
      return { parse, str: str.slice(1) };
    }
    str = res.str;
    parse.push(res.parse);
  }
};

/**
 * @type {ParserCombinator}
 * @param {ParserCombinator} p1 this parser gets ran on the string, if it doesn't parse anything, then ignore the result and use `p2`.
 * @param {ParserCombinator} p2
 * @returns
 */
const pOr = (p1) => (p2) => (str) => {
  const res = p1(str);
  if (res.parse !== "") return res;
  return p2(str);
};

/**
 * The Lisp parser!
 *
 * @type {(str: string) => { parse: LispAST, str: string }}
 */
const pLisp = pOr(pList)(pValue);

console.assert(pLisp("hello").parse === "hello");

console.assert(Array.isArray(pLisp("(1 2 3)").parse));

console.assert(pLisp("(1 2 (a b 🤖))").parse[2][2] === "🤖");

console.assert(pLisp("(1 2 3)").str === "");

console.assert(pLisp("(1 2( 3)").parse === "");