Pattern matching using JavaScript generators

index.js

// http://www.inf.puc-rio.br/~roberto/docs/MCC15-04.pdf

function prim(str) {
  const len = str.length;
  return function* primMatcher(S, pos) {
    if (S.substr(pos, len) === str) {
      yield pos + len;
    }
  };
}

function alt(p1, p2) {
  return function* altMatcher(S, pos) {
    yield* p1(S, pos);
    yield* p2(S, pos);
  };
}

function seq(p1, p2) {
  return function* seqMatcher(S, pos) {
    for (const nextPos of p1(S, pos)) {
      yield* p2(S, nextPos);
    }
  };
}

function match(S, p) {
  for (const pos of p(S, 0)) {
    if (pos === S.length) {
      return true;
    }
  }
  return false;
}

// (abc|de)x
const p = seq(alt(prim('abc'), prim('de')), prim('x'));

const data = ['abcx', 'abcde', 'abcdex', 'dex', 'abc', 'de', 'x'];
data.forEach(s => console.log(`${s}: ${match(s, p)} `));

// abcx: true
// abcde: false
// abcdex: false
// dex: true
// abc: false
// de: false
// x: false