Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper addresses the inefficiencies of conventional backtracking implementations of regular expressions by proposing a transformation from regular expressions with lookaheads (REwLA) to deterministic finite automata (DFA). The authors present a method that allows for the transformation of REwLA of size \( m \) into a DFA with \( O(2^{2^m}) \) states, while also extending the approach to weighted regular expressions for submatch addressing. The key result is the establishment of a framework that significantly enhances the efficiency of regular expression matching, particularly in handling practical extensions like submatch addressing.
Transforming regular expressions with lookaheads into finite automata could revolutionize regex matching efficiency, tackling the limitations of backtracking implementations.
Most of the conventional implementations of regular expressions are based on backtracking. Such implementations are slow in the worst case, and thus, we would like to develop a better matching algorithm. However, it is nontrivial to provide an efficient matching algorithm that can deal with practical extensions including submatch addressing. This paper studies regular expression with lookaheads and negative lookaheads, abbreviated to REwLA. First, we propose a transformation from a REwLA of size $m$ to a deterministic finite automaton of $\mr{O}(2^{2^m})$ states. Next, we consider weighted regular expressions, which enable us to calculate submatch addressing. We propose a transformation from a weighted REwLA of size $m$ to a weighted nondeterministic finite automaton of $\mr{O}(2^{2^m})$ states.