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
- Parse expressions with letters, |, *, + and brackets, respecting precedence
- Build an ε-NFA with Thompson's construction
- Turn it into a DFA with the subset construction, then minimise it
- Print the minimal DFA's transition table
- Match whole words and also find every match inside a line of text
- Compare every answer with re.fullmatch on at least 1,000 random words
Technologies
- Python
- Recursive-descent parsing
- Sets and frozensets
- Breadth-first search
Step by step
- Write the parser, with one function per precedence level, and test it on small expressions.
- Build Thompson fragments and an NFA simulator; check them against re.fullmatch.
- Add the subset construction and print the DFA table.
- Add partition refinement and confirm that equivalent expressions give the same minimal DFA.
- Add searching inside text by trying each starting position.
- 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
- Every answer agrees with re.fullmatch on the random tests
- The minimal DFA has no unreachable or equivalent states
- The code separates parsing, construction, conversion and matching
- The report explains the size of each automaton for several expressions
Ways to improve it
- Add character classes such as [a-c] and the ? operator
- Build DFA states lazily while matching, as RE2 does
- Draw the automata as diagrams with Graphviz