Regex Matching with Counting-Set Automata

Regex Matching with Counting-Set Automata

WoS Article

We propose a solution to the problem of efficient matching regular expressions (regexes) with boundedrepetition, such as (ab){1,100}, using deterministic automata. For this, we introduce novel counting-setautomata (CsAs), automata with registers that can hold sets of bounded integers and can be manipulated bya limited portfolio of constant-time operations. We present an algorithm that compiles a large sub-class ofregexes to deterministic CsAs. This includes (1) a novel Antimirov-style translation of regexes with countingto counting automata (CAs), nondeterministic automata with bounded counters, and (2) our main technicalcontribution, a determinization of CAs that outputs CsAs. The main advantage of this workflow is that thesize of the produced CsAs does not depend on the repetition bounds used in the regex (while the size ofthe DFA is exponential to them). Our experimental results confirm that deterministic CsAs produced frompractical regexes with repetition are indeed vastly smaller than the corresponding DFAs. More importantly,our prototype matcher based on CsA simulation handles practical regexes with repetition regardless of sizesof counter bounds. It easily copes with regexes with repetition where state-of-the-art matchers struggle.

We propose a solution to the problem of efficient matching regular expressions (regexes) with boundedrepetition, such as (ab){1,100}, using deterministic automata. For this, we introduce novel counting-setautomata (CsAs), automata with registers that can hold sets of bounded integers and can be manipulated bya limited portfolio of constant-time operations. We present an algorithm that compiles a large sub-class ofregexes to deterministic CsAs. This includes (1) a novel Antimirov-style translation of regexes with countingto counting automata (CAs), nondeterministic automata with bounded counters, and (2) our main technicalcontribution, a determinization of CAs that outputs CsAs. The main advantage of this workflow is that thesize of the produced CsAs does not depend on the repetition bounds used in the regex (while the size ofthe DFA is exponential to them). Our experimental results confirm that deterministic CsAs produced frompractical regexes with repetition are indeed vastly smaller than the corresponding DFAs. More importantly,our prototype matcher based on CsA simulation handles practical regexes with repetition regardless of sizesof counter bounds. It easily copes with regexes with repetition where state-of-the-art matchers struggle.

regular expression matching, bounded repetition, ReDos, determinization,Antimirovs derivatives, counting automata, counting-set automata

regular expression matching, bounded repetition, ReDos, determinization,Antimirovs derivatives, counting automata, counting-set automata

HOLÍKOVÁ, L.; HOLÍK, L.; LENGÁL, O.; SAARIKIVI, O.; VEANES, M.; VOJNAR, T.

2021

01.10.2020

2475-1421

Proceedings of the ACM on Programming Languages-PACMPL

4

11

United States of America

1

30

30

https://www.microsoft.com/en-us/research/uploads/prod/2020/09/MSR-TR-2020-31.pdf