Skip to content

Lab 1 · One regex engine, four back ends (and a generated Pebble lexer ★)

Chapter: 1 · Lexical Analysis · Lessons: 1.1, 1.2, 1.3, 1.4, 1.5, 1.6 · Time: 12–18 hours (8–10 without the ★ parts) · Tests: ./course test 1 (label ch01)

Goal

You write one regular-expression front end (a parser for a small ECMAScript-compatible dialect and Thompson's construction, Lesson 1.1) and put four matching engines behind it: the Pike VM (Thompson's NFA simulation, Lesson 1.2), an eager DFA built by the subset construction and minimized (Lessons 1.2 and 1.4), a derivative matcher (Brzozowski, Lesson 1.3) and, as the ★ part, a lazy DFA with a bounded state cache as in RE2 (Lesson 1.2). All four must agree with std::regex (a backtracking matcher) on thousands of random patterns and strings, and all must stay linear on the input that makes std::regex exponential. You then compute minimal DFA sizes with Hopcroft's algorithm and, ★, with Moore's and Brzozowski's, checked against a golden file produced by an independent Python oracle. The ★ finale turns the same machinery into a table-driven lexer generator (Lessons 1.5 and 1.6) and runs it on Pebble's regular token set against the hand-written lexer you built in exercises E1–E5.

The comparison lab measures what the lessons claim: throughput of the four engines and of std::regex, the backtracking blow-up, the exponential DFA family \((a|b)^{*}a(a|b)^{k}\), and a generated lexer against a hand-written one.

You design every data structure: the regex AST, the NFA program, the DFA table, the derivative representation. The provided code is the contract header, a command-line tool, the benchmark driver and the Pebble lexer specification.

Requirements

"Byte" means one of the 256 values of unsigned char; the engines work on bytes, never on decoded characters (a UTF-8 "é" is two bytes, and . matches each of them).

  • R1 (syntax). compile(P, B) accepts exactly the dialect of Pattern syntax below for every back end B, and returns an error (a non-empty message naming the offset where possible) for everything else, including (, a), *a, [], [z-a], a{2,1}, a{x}, a trailing \, unknown escapes such as \q, the anchors ^ and $, and a repetition with nothing to repeat (a|*).
  • R2 (Pike VM). Backend::PikeVM compiles the pattern with Thompson's construction (Algorithm 1.1.6) and runs the NFA breadth-first, one ε-closed state set per input position (Algorithm 1.2.4). Time \(O(nm)\) for a text of \(n\) bytes and a program of \(m\) instructions; no backtracking.
  • R3 (DFA). Backend::DFA builds the complete DFA over byte classes ahead of time with the subset construction (Algorithm 1.2.5), minimizes it (R6), then runs one table lookup per byte.
  • R4 (derivatives). Backend::Derivative matches by repeated Brzozowski derivatives (Definition 1.3.3) on regular expressions kept in similarity-normal form (smart constructors, Definition 1.3.4; Algorithm 1.3.7), memoizing \((r, \text{byte class}) \mapsto \partial r\) so that each distinct derivative is computed once.
  • R5 ★ (lazy DFA). Backend::LazyDFA builds DFA states only when the input reaches them, caches them, and when the cache is full flushes it and continues from the current state (Algorithm 1.2.6). It stays correct on patterns whose DFA has far more states than the cache holds (the reference caps it at 4096). Until you do L6, returning your eager DFA for LazyDFA passes every test; the milestone is the design, not a test.
  • R6 (minimal DFA size). minimalDFASize(P, M) returns the number of states of the minimal complete DFA for \(L(P)\) over all 256 bytes, the dead (sink) state included when there is one. Minimizer::Hopcroft is required; Minimizer::Moore and Minimizer::Brzozowski (double reversal) are ★ and must give the same number (Theorem 1.4.8: the minimal DFA is unique). A malformed pattern returns the R1 error.
  • R7 (linear time). Every back end matches (a?){30}a{30} against \(a^{30}\) (true) and \(a^{29}\) (false) in well under a second, including compilation. std::regex needs about \(2^{n}\) steps on this family.
  • R8 ★ (table lexer). buildTableLexer(Rules) builds one DFA for all rules whose accepting states carry the index of the first rule they accept (priority, Definition 1.6.3; state tags, Algorithm 1.6.6). It fails with an error when the list is empty, a pattern is malformed, or a pattern matches the empty string.
  • R9 ★ (lexing). TableLexer::lex(Text) returns tokens covering every byte of Text in order: at each position the longest prefix accepted by some rule (maximal munch, Algorithm 1.6.5, backing up to the last accepting position), with the rule from R8; a byte where no rule matches becomes a token of length 1 with Rule == -1, and lexing resumes after it. numStates() is the number of states of the table the lexer runs on (for information; any positive number passes).

The matching semantics of Matcher are those of the header: matches(T) is std::regex_match (the whole text), and longestPrefix(T) is the largest \(k\) with \(T[0..k) \in L(P)\), or std::nullopt when no prefix (not even the empty one) is in \(L(P)\).

The contract

// labs/ch01-regex/include/regexlab/Regex.h  (provided; do not change; comments abridged)
namespace regexlab {
enum class Backend { PikeVM, DFA, Derivative, LazyDFA /* ★ */ };
enum class Minimizer { Hopcroft, Moore /* ★ */, Brzozowski /* ★ */ };

class Matcher {
public:
  virtual ~Matcher() = default;
  virtual bool matches(std::string_view Text) = 0;                           // whole text
  virtual std::optional<std::size_t> longestPrefix(std::string_view Text) = 0;
};

std::expected<std::unique_ptr<Matcher>, std::string>
compile(std::string_view Pattern, Backend B);                                // L1-L4, L6 ★
std::expected<unsigned, std::string>
minimalDFASize(std::string_view Pattern, Minimizer M = Minimizer::Hopcroft); // L5

struct LexRule { std::string Name; std::string Pattern; };  // earlier rules win ties
struct LexToken { int Rule; std::uint32_t Offset; std::uint32_t Length; };   // Rule -1 = error byte
class TableLexer {
public:
  virtual ~TableLexer() = default;
  virtual std::vector<LexToken> lex(std::string_view Text) const = 0;
  virtual unsigned numStates() const = 0;
};
std::expected<std::unique_ptr<TableLexer>, std::string>
buildTableLexer(std::span<const LexRule> Rules);                             // L7 ★
}

Where your code goes: any *.cpp under labs/ch01-regex/src/ (switch regex). It starts with Stub.cpp, whose three functions stop with TODO(ch01): …; delete it as you implement. Add private headers and as many files as you like.

Pattern syntax

A subset of ECMAScript, chosen so that std::regex (ECMAScript grammar) is a test oracle:

alt    := cat ('|' cat)*                 alternatives; an empty cat is ε ("a|", "a||b", "" are valid)
cat    := repeat*
repeat := atom ( '*' | '+' | '?' | '{' m '}' | '{' m ',}' | '{' m ',' n '}' )*
atom   := '(' alt ')' | '(?:' alt ')'    groups (no capturing semantics: both are the same here)
        | '[' '^'? item+ ']'             classes; item := char | char '-' char | escape
        | '.'                            any byte except \n and \r
        | '\' escape | literal byte      a non-ASCII literal is its UTF-8 bytes, one after another
escape := d D w W s S                    [0-9], [A-Za-z0-9_], [\t\n\v\f\r ] and complements
        | n t r f v 0                    \n \t \r \f \v and the NUL byte
        | one of  \ ^ $ . | ? * + ( ) [ ] { } / -    the character itself

Bounds satisfy \(0 \le m \le n \le 100\); r{m,n} means \(r^{m}(r?)^{n-m}\) and r{m,} means \(r^{m}r^{*}\). Inside a class, - is literal at the end or when escaped ([a\-z]), a range endpoint must be a single character (not \d), and only ASCII characters may appear (use escapes or literal bytes outside classes for UTF-8). Not supported (error): anchors ^ $ outside classes, backreferences, lookaround, lazy quantifiers, named groups, a stray ] or }, { with nothing before it.

The benchmark, the tests and pebble.lexspec use nothing else.

Input and output formats

Lexer specifications (inputs/pebble.lexspec, read by the tests and the benchmark): one rule per line, name<TAB>pattern; # starts a comment line; earlier rules win ties; names starting with _ are trivia (whitespace and comments), which the tests drop before comparing with the hand-written lexer. The file encodes the regular core of Pebble's lexical grammar: nested block comments, interpolation and the error rules of the spec are not regular and are left out (its header says exactly how).

ch01-regex (provided; try your engines by hand):

$ build/<preset>/bin/ch01-regex --backend=dfa '(a|b)*abb' abb aabb abba
abb match=yes   longest-prefix=3
aabb    match=yes   longest-prefix=4
abba    match=no    longest-prefix=3
$ build/<preset>/bin/ch01-regex --min-dfa --minimizer=moore '(a|b)*abb' '[a-z_][a-z0-9_]*'
5   (a|b)*abb
3   [a-z_][a-z0-9_]*

The 5 for (a|b)*abb is the 4-state minimal DFA of Lesson 1.4 plus the dead state that bytes other than a and b lead to. Options: --backend=pike|dfa|deriv|lazy (default pike); --min-dfa with --minimizer=hopcroft|moore|brzozowski (default hopcroft).

ch01-regexbench [--quick] (provided): prints the four measurement tables of Milestones step 6.

Provided infrastructure

File What it gives you
include/regexlab/Regex.h the contract (above)
tools/regex-cli.cpp the ch01-regex command
tools/regexbench.cpp the ch01-regexbench measurements
inputs/pebble.lexspec Pebble's regular token set as 68 lexer rules
tests/ch01/Inputs/min-dfa.regexes, min-dfa.golden 41 patterns and their minimal DFA sizes, produced by tools/course/lib/regex.py (an independent implementation)

What the tests check

Test Checks
ch01.RegexSyntax.AcceptsTheDialect R1: 18 valid patterns compile with every back end
ch01.RegexSyntax.RejectsWithAnError R1: 16 invalid patterns fail with a non-empty message on every back end
ch01.RegexEngines.FixedCases R2–R5: 19 hand-checked (pattern, text) pairs, matches and longestPrefix, including "", x{2,4}, . vs \n, and (a*)*b
ch01.RegexEngines.BytesNotCharacters bytes semantics: .. matches "é", a literal "é" does not match its first byte, \0
ch01.RegexRandom.AgreeWithStdRegex R2–R5: 300 random patterns × 25 random strings × 4 back ends = 30 000 agreements with std::regex on both queries
ch01.RegexRandom.BackendsAgreeOnLongerStrings R2–R5: 200 deeper patterns, strings up to 60 bytes, every back end vs the Pike VM
ch01.RegexPathological.LinearTimeOnNestedOptionals R7 on \(n = 30\), every back end, under 5 s including compilation
ch01.RegexLazyDFA.CorrectWhenTheCacheOverflows R5 ★: (a|b)*a(a|b){14} (a \(2^{15}\)-state DFA) on 300 random strings, lazy vs Pike VM
ch01.MinDFA.HopcroftMatchesGolden R6: all 41 golden sizes
ch01.MinDFA.MooreMatchesGolden, BrzozowskiMatchesGolden R6 ★: the same with the other minimizers
ch01.MinDFA.MinimizersAgreeOnRandomPatterns R6 ★: 150 random patterns, three minimizers agree
ch01.MinDFA.ErrorsAreReported R6: a malformed pattern is an error, not a crash
ch01.TableLexer.PriorityBreaksTies R8 ★: if vs [a-z]+, in both orders
ch01.TableLexer.MaximalMunchBacksUp R9 ★: abcab with rules ab, abcd, c; 1..2 vs 1.5
ch01.TableLexer.ErrorBytesAreSingleTokens R9 ★: aa@#a, the empty text
ch01.TableLexer.RejectsBadSpecifications R8 ★: empty-string rule, malformed pattern, no rules
ch01.TableLexer.AgreesWithTheHandWrittenPebbleLexer R8–R9 ★: on a generated 40-function program and two corpus files, the non-trivia tokens (rule name = token kind name, offset, length) equal pebble::lexFile's tokens exactly. Needs your E1–E5 lexer
ch01.lab.bench-smoke the benchmark runs to completion with --quick

The ★ tests are part of ./course test 1. They fail with TODO(ch01): L7 … until you do the ★ parts; the chapter is complete without them, and the stub message tells you which part each failure belongs to.

Milestones

  1. L1 · Parser and Thompson's construction. Parse into an AST, compile to an NFA (Lesson 1.1, Algorithm 1.1.6). Check the size on (a|b)*abb: 11 states, numbered 0–10 in the Dragon-book order (Lesson 1.1 §3). Nothing passes yet on its own; RegexSyntax.RejectsWithAnError passes once compile returns errors.
  2. L2 · Pike VM. ctest --preset <p> -R 'RegexSyntax|RegexEngines' with only Backend::PikeVM implemented (return the Pike VM for every back end at first), then RegexRandom.AgreeWithStdRegex, then RegexPathological.
  3. L3 · DFA. Byte classes, subset construction, table matcher; switch Backend::DFA to it. RegexRandom.* now tests two independent engines against each other.
  4. L4 · Derivatives. Smart constructors first, then nullable and derive, then the memo table. RegexRandom.* with three engines.
  5. L5 · Minimization. Hopcroft on your L3 DFA; MinDFA.HopcroftMatchesGolden. ★ Moore and Brzozowski; MinDFA.*.
  6. L6 ★ · Lazy DFA. Replace the eager DFA behind Backend::LazyDFA; RegexLazyDFA.*. Then run the benchmark and fill in the table:
build/<preset>/bin/ch01-regexbench
Measurement PikeVM DFA Derivative LazyDFA std::regex
[a-z_][a-z0-9_]*, 200 000 lines (1.8 MB)
(a?){20}a{20} on \(a^{20}\), per match
minimal DFA of (a|b)*a(a|b){12}: states, Hopcroft / Moore / Brzozowski time

Reference implementation on the course's CI container (for calibration, not a target): identifiers 105 / 4.1 / 13 / 7.4 / 32 ms; \(n = 20\): 0.025 / 0.15 / 0.46 / 0.13 / 123 ms; \(k = 12\): 8193 states in 25 / 36 / 30 ms. 7. L7 ★ · Table-driven lexer. One DFA for all rules with priority tags on accepting states, maximal munch with backup, error bytes. TableLexer.*. The benchmark's last table compares it with your hand-written lexer; the reference gets 135 states, 93 MB/s table-driven vs 105 MB/s hand-written on 6.9 MB.

Hints

Hint 1 — where to start

Write the parser as recursive descent over the four-level grammar above (alt, cat, repeat, atom), producing an AST whose leaves are byte sets (a 256-bit set: std::bitset<256>), not characters. Then every class, escape and . is one leaf, and every engine only ever asks "is byte \(c\) in this set?". Lesson 1.1 §2 gives Thompson's construction case by case; the Pike VM of Lesson 1.2 §2 runs directly on its output.

Hint 2 — the key idea

All three automaton engines share one step: from a set of NFA states and a byte, compute the ε-closure of the successor set. The Pike VM does it per input byte; the subset construction does it once per (state set, byte class) and remembers the result in a table; the lazy DFA does the same on demand. Write the step once. For the DFA, compute byte classes first (bytes that no leaf set distinguishes behave identically; the class map of Definition 1.5.2): the Pebble spec has 256 bytes but only a few dozen classes, and your tables shrink accordingly.

For derivatives, the invariant is similarity-normal form: without \(r \mid r = r\), commutativity (sort the alternatives) and \(\emptyset\)/\(\varepsilon\) simplification, the set of derivatives is infinite and your memo table grows without bound (Proposition 1.3.15).

Hint 3 — a design sketch
  • AST pool: nodes in a vector, referred to by index; hash-consing (a map from node contents to index) makes structural equality an integer comparison, which the derivative engine needs for memoization.
  • Program: Thompson's NFA as instructions Byte(set, next), Split(x, y), Match; Pike VM = two sparse sets (current and next) of instruction indices.
  • DFA: states numbered from 0, a std::vector<uint32_t> table indexed state * numClasses + class, a 256-entry byte-to-class map, a std::vector<bool> of accepting states. longestPrefix remembers the last accepting position and stops at the dead state.
  • Minimal size: make the DFA complete (add the dead state if some transition is missing), drop unreachable states, then minimize. Most off-by-one failures on MinDFA.* are a forgotten dead state or an unreachable one kept (Lesson 1.4 §9, pitfall).
  • Brzozowski ★: reverse the DFA into an NFA whose start is the set of old accepting states. Adding a fresh start state with ε-edges instead gives a DFA that is not minimal (Lesson 1.4 §2, Algorithm 1.4.6).
  • Table lexer ★: build one NFA with a start state that splits to every rule; tag each Match with its rule index; a DFA state accepts the smallest rule index among its NFA states. Minimize with an initial partition by tag, not just accept/reject (Lesson 1.4 §2, Algorithms 1.4.4–1.4.5); Brzozowski's method is not tag-aware.

The test that catches most bugs: RegexEngines.FixedCases on "" (the empty pattern matches only the empty text, and its longest prefix of "x" is 0, not nullopt) and on . versus \n.

Stretch goals ★

  • Submatch extraction in the Pike VM (thread-local capture arrays, leftmost-first priority), checked against std::smatch.
  • Direct-coded output: emit your lexer DFA as C++ goto code (re2c style, Lesson 1.5) and benchmark it against the table.
  • Reps' linear-time maximal munch (Algorithm 1.6.7) in your table lexer, and a test on the \(a^{n}\) worst case of Proposition 1.6.11.
  • Derivatives with intersection and complement (&, ~) as a dialect extension (Lesson 1.3 §6); compare minimal DFA sizes with the oracle's derivative_dfa.