A Regular Expression Package

This page is under construction. The idea is to write a program to translate a regular expression into a dd/sh script (or function) which reads some input and outputs 0 if it does not match, 1 if it does.

This will be done by a collection of scripts, which perform the following functions:

  1. Translate a regular expression into a non-deterministic finite automaton (NFA) using the hex codes of the characters as alphabet (so we avoid confusing the shell more than necessary)
  2. Transform a NFA into a deterministic finite automaton (DFA)
  3. Minimise a DFA
  4. Translate a DFA into a dd/sh function
  5. Translate ASCII text into hex codes (the same used by the regex-to-NFA script)
  6. Finally, a script combining the lot to read a regular expression and an input file and print lines which match the regexp. We'll probably call it grep and feel like we are reinventing the wheel.
Currently, we only have the NFA to DFA converter and the DFA to dd/sh compiler.