Skip to content

Instantly share code, notes, and snippets.

@SimonMeskens
Created November 13, 2021 22:50
Show Gist options
  • Save SimonMeskens/a7247818480cb2f106953cb984b4ff08 to your computer and use it in GitHub Desktop.
Save SimonMeskens/a7247818480cb2f106953cb984b4ff08 to your computer and use it in GitHub Desktop.
Tiny LISP parser and interpreter
// Parser
const string = /"(?:\\(?:["\\\/bfnrt]|u[a-fA-F0-9]{4})|[^"\\\0-\x1F\x7F]+)*"/;
const number = /-?(?:0|[1-9][0-9]*)(?:\.[0-9]+)?(?:[eE][+-]?[0-9]+)?/;
const identifier = /[^()\s,:"']+/;
const combine = (...args) => new RegExp(args.map(arg => `(?:${arg.source})`).join("|"), "g");
const tokenize = input => input.matchAll(combine(/[()]/, identifier, string, number));
const construct = iterator => {
const root = [];
for (const [token] of iterator) {
if (token === ")") return root;
if (token === "(") root.push(construct(iterator));
else
try {
root.push(JSON.parse(token));
} catch {
root.push(token);
}
}
return root;
};
const parse = input => construct(tokenize(input));
// Interpreter
const env = {
label: (name, value) => (env[name] = resolve(value, env)),
head: ([first]) => first,
tail: ([_, ...rest]) => rest,
list: (head, tail) => [head, ...tail],
equal: (a, b, ctx) => resolve(a, ctx) === resolve(b, ctx),
if: (cond, cons, alt, ctx) => (resolve(cond, ctx) ? resolve(cons, ctx) : resolve(alt, ctx)),
atomic: expression => !Array.isArray(expression),
id: expression => expression,
};
function apply(op, args, ctx = this ?? environment()) {
return typeof ctx[op] === "function"
? ctx[op](...args, ctx)
: resolve(ctx[op][2], {
...ctx,
...ctx[op][1].map((value, index) => [args[index], value]),
});
}
function resolve(expr, ctx = this ?? environment()) {
if (ctx.atomic(expr)) return ctx[expr] ?? expr;
const op = env.head(expr);
const args =
Array.isArray(ctx[op]) ||
(typeof ctx[op] === "function" && !["label", "if", "id"].includes(op))
? env.tail(expr).map(item => resolve(item, ctx))
: env.tail(expr);
return apply(op, args, ctx);
}
const environment = ext => Object.assign(Object.create(env), ext, { resolve, apply });
// Test
const source = `
(if (equal a 3)
(id "equal")
(id "not equal"))
`;
console.log(source);
const tree = parse(source);
console.log(tree);
const lisp = environment({
a: 4,
});
console.log(lisp);
// output = ["not equal"]
const output = tree.map(expr => lisp.resolve(expr));
console.log(output);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment