Skip to content

Latest commit

 

History

History
31 lines (21 loc) · 3.83 KB

README.md

File metadata and controls

31 lines (21 loc) · 3.83 KB
Raw

regex_dfa

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

Build status Coverage Status

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.