Home

Awesome

regex2dfa

license build

This is a compiler that converts regular expressions to images of minimised DFA.

It is a pure front-end application, i.e. the server only hosts static assets while all logics are executed on the browser. The process of "from regex to DFA" can be split into three steps:

  1. Transforming the regular expression to the corresponding minimised DFA with
    1. Thompson's construction algorithm,
    2. powerset construction,
    3. Brzozowski's DFA minimisation algorithm.
  2. Serialising the topological structure of the DFA into DOT format.
  3. Transforming the DFA from DOT to SVG format with the help of Viz.js.

The first two steps were implemented in C++ and compiled into WebAssembly with the help of Emscripten.