Chipmunk: A Tool for Matching of Regular Expressions

Chipmunk: Nástroj pro vyhledávní podle regulárních výrazů.

software

In order to use the result by another entity, it is always necessary to acquire a license

The licensor does not require a license fee for the result

Holík Lukáš, doc. Mgr., Ph.D. (DITS)
Holíková Lenka, Ing., Ph.D. (RG VERIFIT)
Lengál Ondřej, Ing., Ph.D. (DITS)
Vojnar Tomáš, prof. Ing., Ph.D. (DITS)
Veanes Margus

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.

Nástroj i dokumentaci lze získat na URL: 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).

Spolehlivé, bezpečné a efektivní počítačové systémy, BUT, Vnitřní projekty VUT, FIT-S-20-6427, start: 2020-03-01, end: 2023-02-28, completed

Automated Analysis and Verification Research Group - VeriFIT (RG VERIFIT)

Department of Intelligent Systems (DITS)