[TUHS] Regex archaeology

[Douglas McIlroy via TUHS]

A descendant of Ken's regexp recognizer that may be of interest:

https://mcilroy.cs.dartmouth.edu/nfa.pdf (J of Functional Programming
14 (2004) 503-518) gives a 20-line Haskell program (r2n: regexp to
NFA) that yields an automaton with fewer states (but not necessarily
faster) than Ken's. The program constructs an automaton from a parsed
regexp that contains n terminal symbols in time O(n^2).The automaton
has exactly one state for each terminal symbol and no epsilon
transitions.

The program (available at https://mcilroy.cs.dartmouth.edu/nfa.hs)
depends on Haskell's lazy evaluation, but the paper tells how laziness
can be avoided by deterministic traversal of the parse tree.

Doug