Chipmunk: A Tool for Matching of Regular Expressions

The tool allows efficient matching regular expressions (regexes) with bounded repetition using deterministic automata with registers - counting-sets automata (CsA). The CsA can hold sets of bounded integers and can be manipulated by a limited portfolio of constant-time operations. Our experimental results confirm that deterministic CsAs produced from practical regexes with repetition are indeed vastly smaller than the corresponding DFAs. This prototype matcher based on CsA simulation handles practical regexes with repetition regardless of sizes of counter bounds. It easily copes with regexes with repetition where state-of-the-art matchers struggle.