interface Empty {
kind: "empty";
}
function empty(): Empty { return { kind: "empty" } }
interface Epsilon {
kind: "epsilon";
}
interface Char {
kind: "char"
value: string;
}
function char(value: string): Char { return { kind: "char", value } }
interface Cat {
kind: "cat"
left: Language
right: Language
}
function cat(left: Language, right: Language): Cat {
return { kind: "cat", left, right }
}
interface Alt {
kind: "alt"
left: Language
right: Language
}
function alt(left: Language, right: Language): Alt {
return { kind: "alt", left, right }
}
interface Rep {
kind: "rep";
value: Language;
}
function rep(value: Language): Rep { return { kind: "rep", value: value } }
type Language = Empty | Epsilon | Rep | Cat | Alt | Char
function is_nullable(l: Language): boolean {
switch (l.kind) {
case "empty":
return false;
case "epsilon":
return true;
case "char":
return false;
case "alt":
return is_nullable(l.left) || is_nullable(l.right);
case "cat":
return is_nullable(l.left) && is_nullable(l.right);
case "rep":
return true;
}
}
function derive(pat: Language, char: string): Language {
switch (pat.kind) {
case "epsilon":
case "empty":
return empty();
case "char":
if (pat.value == char) {
return { kind: "epsilon" };
} else {
return { kind: "empty" };
}
case "rep":
return cat(derive(pat.value, char), pat);
case "alt":
return {
kind: "alt",
left: derive(pat.left, char),
right: derive(pat.right, char)
};
case "cat":
const base = cat(derive(pat.left, char), pat.right);
if (is_nullable(pat.left)) {
return alt(derive(pat.right, char), base);
} else {
return base;
}
}
}
function matches(pat: Language, text: string): boolean {
if (text.length == 0) {
return is_nullable(pat)
} else {
return matches(derive(pat, text[0]), text.slice(1))
}
}
module.exports = { char, cat, alt, rep, matches }