#dfa

regex_dfa

A crate for turning regexes into DFAs

6 releases (breaking)

Uses old Rust 2015

0.5.0 Aug 8, 2016
0.4.0 Jan 11, 2016
0.3.0 Oct 3, 2015
0.2.0 Sep 26, 2015
0.0.1 Aug 16, 2015

#1653 in Algorithms

Download history 22/week @ 2023-10-29 24/week @ 2023-11-05 16/week @ 2023-11-12 22/week @ 2023-11-19 36/week @ 2023-11-26 31/week @ 2023-12-03 14/week @ 2023-12-10 24/week @ 2023-12-17 30/week @ 2023-12-24 9/week @ 2023-12-31 15/week @ 2024-01-07 17/week @ 2024-01-14 23/week @ 2024-01-21 21/week @ 2024-01-28 20/week @ 2024-02-04 35/week @ 2024-02-11

99 downloads per month

MIT/Apache

170KB
3K SLoC

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.

Dependencies

~8.5MB
~141K SLoC