A regular-expression engine

The problem

Build a program that compiles a regular expression into a minimal DFA and uses it to match text, without the re module.

Requirements

Technologies

Step by step

  1. Write the parser, with one function per precedence level, and test it on small expressions.
  2. Build Thompson fragments and an NFA simulator; check them against re.fullmatch.
  3. Add the subset construction and print the DFA table.
  4. Add partition refinement and confirm that equivalent expressions give the same minimal DFA.
  5. Add searching inside text by trying each starting position.
  6. Write a random tester that generates words and compares your engine with the re module.

Expected result

A working regex engine that explains itself: it shows the NFA, the DFA and the minimal DFA for any expression.

How it is evaluated

Ways to improve it