regex_dfa

A crate for compiling regular expressions down to deterministic finite automata.

Documentation

Why?

Some regular expression implementations (e.g. rust's regex library) are based on simulating non-deterministic finite automata (NFAs). By turning NFAs into DFAs, we can get a speed boost, at the cost of some compilation time and memory usage. Preliminary benchmarks show a substantial speed improvement over rust's default regex crate.

Limitations

• Turning an NFA into a DFA can take a lot of memory, especially when unicode character classes are involved.
• Subgroup captures are a bit tricky, and this crate does not handle them.
• regex_dfa currently only works on nightly rust.

License

regex_dfa is distributed under the MIT license and the Apache license (version 2.0). See LICENSE-APACHE and LICENSE-MIT for details.