rules.ts

declare function assert(value: unknown): asserts value;

interface Rule {
  ref: string,
  raw: Array<string>,
  compiled: string | null,
  cyclic: boolean,
}

const orRule: Rule = {
  ref: '|',
  raw: [],
  compiled: '|',
  cyclic: false,
}

const lines = [
  '0: 4 1 5',
  '1: 2 3 | 3 2',
  '2: 4 4 | 5 5',
  '3: 4 5 | 5 4',
  '4: "a"',
  '5: "b"'
];
const rulesMap = new Map();
// input lines here
for (const line of lines) {
  const tokens = line.split(' ')
  assert(tokens.length > 1);
  // get reference
  assert(tokens[0].endsWith(':'));
  const ref = tokens[0].slice(0, -1);
  const raw = tokens.slice(1);

  const rule: Rule = {
    ref: ref,
    raw: raw,
    compiled: null,
    cyclic: false,
  };

  rulesMap.set('|', orRule);
  rulesMap.set(ref, rule);
}

const compile = function (
  ref: string,
  rulesMap: Map<string, Rule>,
  history: Array<string>): Rule {

  let rule = rulesMap.get(ref);
  assert(rule);
  if (ref in history) {
    rule.cyclic = true;
    return rule;
  }
  const newHistory = [...history, ref];
  if (rule.cyclic || rule.compiled) {
    return rule;
  }
  // we can actually compile the rule!
  const tokens = rule.raw;
  rule.compiled = "";

  let includeParens = false;
  for (const token of tokens) {
    if (token.startsWith('"')) {
      assert(token.endsWith('"'));
      rule.compiled += token.split('"').join('');
      continue;
    }
    if (token === '|') {
      rule.compiled += '|';
      includeParens = true;
      continue;
    }
    const subRule = rulesMap.get(token)
    if (!subRule) {
      throw `rule ${token} is not declared`;
    }
    if (subRule.cyclic) {
      rule.cyclic = true;
      return rule;
    }
    if (subRule.compiled) {
      rule.compiled += subRule.compiled;
      continue;
    }

    const compiledRule = compile(token, rulesMap, newHistory);
    if (compiledRule.cyclic) {
      rule.cyclic = true;
      return rule;
    }
    rule.compiled += compiledRule.compiled;
  }
  if (includeParens) {
    rule.compiled = '(' + rule.compiled + ')';
  }
  return rule;
}

const chosenRule = compile('0', rulesMap, []);
const rule = new RegExp('^' + chosenRule.compiled + '$');
// test against given
const fails = ['ababbb', 'abbbab']
const passes = ['bababa', 'aaabbb', 'aaaabbb']

console.log(fails.every((testcase) => rule.test(testcase)))
console.log(passes.every((testcase) => !rule.test(testcase)))

// test against unknown
const unknowns = ['ababbb', 'bababa', 'abbbab', 'aaabbb', 'aaaabbb']

for (const unknown of unknowns) {
  console.log(unknown + ': ' + rule.test(unknown));
}