Last active
April 29, 2022 00:43
-
-
Save SimonMeskens/de69859dd62c2785886c26e96901062d to your computer and use it in GitHub Desktop.
Tiny Parser Combinator Library
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
Copyright 2022 Simon Meskens | |
Permission to use, copy, modify, and/or distribute this software for any purpose with | |
or without fee is hereby granted, provided this license is preserved. This software is | |
offered as-is, without any warranty. | |
Generate your own tiny license: | |
https://simonmeskens.github.io/SimpleLicenseCollection/ | |
*/ | |
export const isFail = res => res == null; | |
export const isResult = res => Object(res) === res; | |
export const isSuccess = res => isResult(res) && restOf(res).length === 0; | |
export const isDone = res => isFail(res) || isSuccess(res); | |
export const nodeOf = res => (!isResult(res) ? null : Array.isArray(res) ? res[0] : res); | |
export const restOf = res => (!isResult(res) ? res : res[1]); | |
export const typeOf = res => nodeOf(res)?.type; | |
export const valueOf = res => nodeOf(res)?.value; | |
export const parse = par => str => (res => (isSuccess(res) ? nodeOf(res) : null))(par(str)); | |
export const node = (type, value) => ({ type, value }); | |
export const result = (type, value, rest) => [node(type, value), rest]; | |
export const chain = (res, fn) => (isDone(res) ? res : fn(restOf(res))); | |
export const map = (res, fn) => { | |
if (!isResult(res)) return res; | |
const token = fn(nodeOf(res)); | |
return result(typeOf(token), valueOf(token), restOf(res)); | |
}; | |
export const reduce = (res, ...args) => { | |
const acc = valueOf(res)?.reduce(...args); | |
return !isResult(acc) ? acc : result(typeOf(acc), valueOf(acc), restOf(res)); | |
}; | |
export const reg = pat => str => { | |
const res = str.match(new RegExp(`^${pat.source}`)); | |
if (isFail(res)) return null; | |
return result("str", res[0], str.slice(res[0].length)); | |
}; | |
export const str = pat => str => str.startsWith(pat) ? result("str", pat, str.slice(pat.length)) : null; | |
export const opt = par => str => chain(str, par) ?? str; | |
export const rep = par => str => { | |
let acc = null; | |
while (true) { | |
const res = par(restOf(acc ?? str)); | |
if (isFail(res)) break; | |
acc = result("rep", !isResult(acc) ? [nodeOf(res)] : [...valueOf(acc), nodeOf(res)], restOf(res)); | |
} | |
return acc; | |
}; | |
export const alt = (...arr) => str => arr.reduce((res, par) => (!isResult(res) ? chain(str, par) : res), str); | |
export const seq = (...arr) => str => { | |
let acc = null; | |
for (const par of arr) { | |
const res = par(restOf(acc ?? str)); | |
if (isFail(res)) return null; | |
acc = result("seq", !isResult(acc) ? [nodeOf(res)] : [...valueOf(acc), nodeOf(res)], restOf(res)); | |
} | |
return acc; | |
}; | |
export const log = (parser, str) => { | |
console.log(`Input: ${str}`); | |
console.log(JSON.stringify(parser(str), null, 2)); | |
}; | |
export const join = (type, par) => str => reduce(par(str), (acc, { value }) => node(type, valueOf(acc) + value)); | |
export const rename = (type, par) => str => map(par(str), ({ value }) => ({ type, value })); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import { log, parse, rename, join, alt, opt, seq, str, reg } from "./efficient.mjs"; | |
const integer = join("int", seq(opt(str("-")), alt(str("0"), reg(/[1-9]\d*/)))); | |
const fraction = join("frac", seq(str("."), reg(/\d+/))); | |
const exponent = join("exp", seq(alt(str("E"), str("e")), opt(alt(str("-"), str("+"))), reg(/\d+/))); | |
const number = rename("num", seq(integer, fraction, exponent)); | |
log(parse(number), "-4.37E-6"); | |
Input: -4.37E-6 | |
{ | |
"type": "num", | |
"value": [ | |
{ | |
"type": "int", | |
"value": "-4" | |
}, | |
{ | |
"type": "frac", | |
"value": ".37" | |
}, | |
{ | |
"type": "exp", | |
"value": "E-6" | |
} | |
] | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment