Parser using JSGenerators

matcher.js

// 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("[(][)]"));