Skip to content

Instantly share code, notes, and snippets.

@TangerineCat
Created December 19, 2020 12:59
Show Gist options
  • Save TangerineCat/db399f18a327144e935ab67b9400c2a6 to your computer and use it in GitHub Desktop.
Save TangerineCat/db399f18a327144e935ab67b9400c2a6 to your computer and use it in GitHub Desktop.
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));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment