Product Details
Chipmunk: A Tool for Matching of Regular Expressions
Created: 2020
Holíková Lenka, Ing. (DITS FIT BUT)
Lengál Ondřej, Ing., Ph.D. (DITS FIT BUT)
Veanes Margus (MSR)
Vojnar Tomáš, prof. Ing., Ph.D. (DITS FIT BUT)
regular expressions, pattern matching, security, counting-set automata
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.
The tool is available at http://www.fit.vutbr.cz/research/groups/verifit/tools/chipmunk/
Free software under the terms of GNU GPL (cf. http://www.gnu.org/licenses/gpl.html).