lispparser.js

/* UPDATE --- It's working!
   Just needed to make sure I was consistently spreading the args (or not spreading them) 
   and not forget that javascript typeof [] === 'object'.
*/

/* 
  lispparser is a lisp parser! It's meant to turn a lisp string
  like this:

    "(first (list 1 (+ 2 3) 9))"
    
  ...into an AST that can be evaluated, like this:
  
  ["first", ["list", 1, ["+", 2, 3], 9]]
*/

/* A map of token kinds to regexes used for tokenizing the expression */
const TOKENS = {
  open:  /^\(/,
  close: /^\)/,
  cmd:   /^(first|last|list|\+|\-|\*|\\)(?!\w)/i,
  num:   /^-?[0-9]+(\.[0-9]+)?/,
  space: /^\s+/,
}

const COMMANDS = {
  first: args=>args.length>0 ? args[0] : undefined, 
  last: args=>args.length>0 ? args[args.length-1] : undefined, 
  list: args=>args,
  "+": args=>args.reduce((a, b)=>a+b, 0),
  "-": args=>args.reduce((a, b)=>a-b, 0),
  "*": args=>args.reduce((a, b)=>a*b, 0),
  "/": args=>args.reduce((a, b)=>a/b, 0)
}

function getNextToken(str) {
  for (let [kind, regex] of Object.entries(TOKENS)) {      
    let match = str.match(regex)
    if (match) {
      return [kind, match[0]]
    }
  }
  return ['error', str]
}

/* Tokenizes the string, returning a list of [tokenKind, token] pairs. */
function tokenizer(str) {
  let result = []
  while (str.length) {
    const token = getNextToken(str)
    if (token[0] === 'num') {
      result.push([token[0], Number(token[1])])
    } else if (token[0] !== 'space') {
      result.push(token)
    }
    str = str.slice(token[1].length)
  }
  return result
}

/* Parses a list of tokens, returning an AST */
function parser(tokens) {
  let result = []
  let next = tokens.shift()
  if (next[0] === 'open') {
    next = tokens.shift();
  }
  if (next[0] !== 'cmd') {
    throw "Syntax error: first list element must be a command"
  }
  result.push(next[1])
  while(tokens.length) {
    next = tokens.shift()
    if (next[0] === 'open') {
      const [nested, rest] = parser(tokens)
      result.push(nested)
      tokens = rest
    } else if (next[0] === 'close') {
      if (tokens.length) {
        return [result, tokens]
      } else {
        return result
      }
    } else {
      result.push(next[1])
    }
  }
}

function evaluate(args) {
  args = args.map(el=>typeof el === 'object' ? evaluate(el) : el)
  return COMMANDS[args[0]](args.slice(1))  
}

console.log(evaluate(parser(tokenizer("(first 1 (+ 2 3) 9)"))))  // -> 1
console.log(evaluate(parser(tokenizer("(- 1 (+ 2 3 -2.3) 9)")))) // -> -12.7