Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // parser = string -> [match, remainder]
- // read single item
- function* item(s) {
- if (s.length > 0) yield [s[0], s.slice(1)];
- }
- function run(p, s) {
- return [...p(s)]
- }
- // function char(c) {
- // return function *(s) {
- // for (const [a, rest] of item(s)) {
- // if (a === c) {
- // yield [c, rest];
- // }
- // }
- // }
- // }
- // function filter(pred, p) {
- // return function*(s) {
- // for (const [a, rest] of p(s)) {
- // if (pred(a)) {
- // yield [a, rest];
- // }
- // }
- // };
- // }
- function* failure(s) {
- return;
- }
- function filter(pred, p) {
- return flatMap(a => (pred(a) ? success(a) : failure), p);
- }
- function char(c) {
- return filter(a => a === c, item);
- }
- // function seq(p1, p2) {
- // return function*(s) {
- // for (const [a, rest1] of p1(s)) {
- // for (const [b, rest2] of p2(rest1)) {
- // yield [[a, b], rest2];
- // }
- // }
- // };
- // }
- // function seq(p1, p2) {
- // return flatMap(a => map(b => [a, b], p2), p1);
- // }
- function seq(...ps) {
- return sequence(ps);
- }
- function sequence(ps) {
- if (ps.length === 0) return success([]);
- return flatMap(a => map(as => [a, ...as], sequence(ps.slice(1))), ps[0]);
- }
- function alt(p1, p2) {
- return function* (s) {
- yield* p1(s);
- yield* p2(s);
- };
- }
- function many(p) {
- return alt(success([]), defer(() => many1(p)));
- }
- function success(v) {
- return function* (s) {
- yield [v, s];
- };
- }
- function many1(p) {
- return map(([a, as]) => [a, ...as], seq(p, many(p)));
- }
- // function map(f, p) {
- // return function*(s) {
- // for (const [a, rest] of p(s)) {
- // yield [f(a), rest];
- // }
- // };
- // }
- function map(f, p) {
- return flatMap(a => success(f(a)), p);
- }
- function flatMap(f, p) {
- return function* (s) {
- for (const [a, rest] of p(s)) {
- yield* f(a)(rest);
- }
- };
- }
- function defer(pf) {
- return function* (s) {
- yield* pf()(s);
- };
- }
- // function wrap(body, p, s) {
- // return seq(char(p), seq(body, char(s)));
- // }
- function wrap(body, p, s) {
- return seq(char(p), body, char(s));
- }
- const parens = many(defer(() => paren));
- const p1 = wrap(parens, "(", ")");
- const p2 = wrap(parens, "[", "]");
- const p3 = wrap(parens, "{", "}");
- const paren = alt(p1, alt(p2, p3));
- function isValid(s) {
- for (const [a, rest] of parens(s)) {
- if (rest === "") return true;
- }
- return false;
- }
- console.log(isValid("{}"));
- console.log(isValid("()[]{}()"));
- console.log(isValid("[()]"));
- console.log(isValid("[(][)]"));
Add Comment
Please, Sign In to add comment