Regex Engine — JavaScript Project

1. The Problem

Build a regex matcher that supports three things: literal characters, . (matches any single character), and * (zero or more of the preceding character). match(pattern, text) returns whether the pattern matches the whole text from the start.

Why this project? This is the classic Kernighan & Pike "tiny regex" — one of the most elegant recursive algorithms in programming. It teaches recursion, backtracking, and how a pattern language actually gets interpreted.

2. How to Think About This

Match recursively, one character at a time. An empty pattern matches (we are done). If the next pattern token is followed by *, hand off to a star helper. Otherwise the first pattern character must equal the first text character (or be .), then recurse on the rest of both. The star case is where backtracking lives: try matching zero occurrences first (skip the star), and if that fails, consume one matching character and try again.

3. The Build

regex.mjs

// Does `pattern` match `text` from the beginning?
export function match(pattern, text) {
  if (pattern.length === 0) return true;          // empty pattern -> done

  // Is the next token followed by a star? (e.g. "a*")
  if (pattern.length >= 2 && pattern[1] === "*") {
    return matchStar(pattern[0], pattern.slice(2), text);
  }

  // A normal char (or ".") must match the first text character.
  const firstMatches = text.length > 0 && (pattern[0] === text[0] || pattern[0] === ".");
  if (firstMatches) return match(pattern.slice(1), text.slice(1));
  return false;
}

// "char*" means zero or more of char.
function matchStar(char, restPattern, text) {
  // Option 1: match zero — skip the star, try the rest now.
  if (match(restPattern, text)) return true;
  // Option 2: consume one matching char, then try again (backtrack).
  while (text.length > 0 && (char === text[0] || char === ".")) {
    text = text.slice(1);
    if (match(restPattern, text)) return true;
  }
  return false;
}

// Demo
console.log(match("a*b", "aaab"));   // true
console.log(match("a.c", "axc"));    // true
console.log(match("a*b", "aaac"));   // false

4. Test & Prove

regex.test.mjs

import { match } from "./regex.mjs";

let pass = 0, fail = 0;
function test(desc, fn) {
  try { fn(); console.log("  \u2713", desc); pass++; }
  catch (e) { console.log("  \u2717", desc, "\u2014", e.message); fail++; }
}
function assert(cond, msg) { if (!cond) throw new Error(msg || "assertion failed"); }

test("literal characters match", () => assert(match("abc", "abc")));
test("a mismatch fails", () => assert(match("abc", "abx") === false));
test("dot matches any single char", () => assert(match("a.c", "axc")));
test("star matches many", () => assert(match("a*b", "aaab")));
test("star matches zero", () => assert(match("a*b", "b")));
test("star that cannot finish fails", () => assert(match("a*b", "aaac") === false));
test("dot-star matches anything ending right", () => assert(match(".*c", "abcxyzc")));

console.log(`\n${pass} passed, ${fail} failed`);

5. The Interface

node regex.mjs

true
true
false

6. Run It

node regex.mjs
node regex.test.mjs

🎯 Try this next

Add "+" (one or more) — it is "one occurrence then star"
Add "?" (zero or one occurrence)
Add "^" and "$" anchors for start/end of string
Add character classes like [abc] and ranges like [a-z]

What you practised

Recursion and backtracking, interpreting a small pattern language, and how * tries the greedy-then-fallback strategy that underlies every real regex engine.

Reference: Functions · Strings · Recursion