yallop / ocaml-re-nfa

re-nfa: convert regular expressions to NFAs

This repository provides a library and executable for converting regular expressions into nondeterministic finite automata (NFAs) using Glushkov's construction, for converting NFAs into DFAs using the powerset construction, for minimizing DFAs using Brzozowski's algorithm and for formatting the NFAs using DOT so that they can be displayed using graphviz.

Online demo

The easiest way to try the code is to use the web UI written by Joel Jakobsson.

The re-nfa executable

The re-nfa executable accepts a single regular expression argument and prints a DOT graph for the corresponding NFA or DFA to standard output. For example, the following command

re-nfa "a*b"

produces the following output.

digraph {
  "rankdir" = "LR";
  node [ "shape" = "none";] ""
  node [ "shape" = "circle";] "1"
  node [ "shape" = "doublecircle";] "2"
  node [ "shape" = "circle";] "0"
  "" -> "0" 
  "1" -> "2" [ "label" = "b";]
  "0" -> "2" [ "label" = "b";]
  "1" -> "1" [ "label" = "a";]
  "0" -> "1" [ "label" = "a";]
}

To display the corresponding DFA or minimized DFA, pass the -type argument:

re-nfa -type dfa "a*b"

re-nfa -type dfa-minimized "a*b"

On a Unix system you might pipe the output directly to dot, and then on to display, like this:

re-nfa "a*b" | dot -Tpng | display

to display the following graph:

Here is the minimized version:

Here is a more complex graph constructed from the regex a?a?a?aaa that causes pathological backtracking behaviour in some engines, as described in Russ Cox's article Regular Expression Matching Can Be Simple And Fast:

and here is the corresponding DFA:

Library

This repository also provides a library interface. The Regex module provides an ocaml-re-style combinator interface for constructing regular expressions

seq (star (chr 'a')) (chr 'b')     (* a*b *)

as well as functions parse and compile for building a regular expression from a string and for turning a regular expression into an NFA.

val parse : string -> t
val compile : t -> Nfa.nfa

The Nfa module provides a function for testing whether an NFA accepts a string (represented as a list of characters):

val accept : Nfa.t -> char list -> bool

The Nfa_dot module provides functions for converting NFAs to DOT directed graphs and for pretty-printing the graphs:

val digraph_of_nfa : Nfa.nfa -> digraph
val format_digraph : Format.formatter -> digraph -> unit

The Dfa module provides functions for converting between NFAs and DFAs, a DFA minimization function, and and an accept function for DFAs

val determinize : Nfa.nfa -> dfa
val inject : dfa -> Nfa.nfa
val minimize : dfa -> dfa
val accept : dfa -> char list -> bool

Rationale

The code in this repository is an extracted and extended portion of an exercise from a 2018 advanced functional programming course. If you're interested in learning MetaOCaml then you may enjoy completing the original exercise, perhaps after reading the course notes.

Knowing the provenance of the code helps in understanding some of the choices made.

For example, there are several algorithms for constructing NFAs, but Glushkov's has a property that turns out to be convenient for the exercise: it constructs an automaton without ε-transitions.

Additionally, the code here is not especially efficient; the remainder of the original exercise involves using multi-stage programming to turn the rather inefficient NFA interpreter into a compiler that produces rather efficient code --- typically more efficient than production regex engines. (Similar transformations using Scala LMS are also described in the literature: see Optimizing data structures in high-level programs: New directions for extensible compilers based on staging (Rompf et al. 2013))

Installation

The re-nfa library and executable can be installed via OPAM by pinning this repository:

opam pin add re-nfa https://github.com/yallop/ocaml-re-nfa.git

ReasonML port

A ReasonML port of this project is available.