一句话：提出带环视断言正则表达式的形式语义和 O(m·n) 匹配算法，并用 oracle-NFA 实现，避免回溯导致的超线性时间。
正则表达式常扩展 lookaround（先行/后顾）断言，用于根据上下文限定匹配。现有实现多依赖回溯，运行时间可能随输入长度超线性增长。本文首先给出 lookaround 的形式数学语义，并据此建立若干等式化简性质；随后提出自底向上求值 lookaround 的匹配算法，时间复杂度为 O(m·n)，其中 m 为正则表达式大小、n 为输入文本长度。算法基于新定义 oracle-NFA，其 ε-转移由提供各位置 lookaround 真值的 oracle 查询保护。作者实现该算法并加入三项性能优化，与 PCRE 和 Java 正则库对比，结果表明其不会出现超线性运行时间且快数倍。
Regular expressions have been extended with lookaround assertions, which are subdivided into lookahead and lookbehind assertions. These constructs are used to refine when a match for a pattern occurs in the input text based on the surrounding context. Current implementation techniques for lookaround involve backtracking search, which can give rise to running time that is super-linear in the length of input text. In this paper, we first consider a formal mathematical semantics for lookaround, which complements the commonly used operational understanding of lookaround in terms of a backtracking implementation. Our formal semantics allows us to establish several equational properties for simplifying lookaround assertions. Additionally, we propose a new algorithm for matching regular expressions with lookaround that has time complexity O m ⋅ n , where m is the size of the regular expression and n is the length of the input text. The algorithm works by evaluating lookaround assertions in a bottom-up manner. Our algorithm makes use of a new notion of nondeterministic finite automata (NFAs), which we call oracle-NFAs. These automata are augmented with epsilon-transitions that are guarded by oracle queries that provide the truth values of lookaround assertions at every position in the text. We provide an implementation of our algorithm that incorporates three performance optimizations for reducing the work performed and memory used. We present an experimental comparison against PCRE and Java’s regex library, which are state-of-the-art regex engines that support lookaround assertions. Our experimental results show that, in contrast to PCRE and Java, our implementation does not suffer from super-linear running time and is several times faster.
@article{paperbot2636,
title = {Efficient Matching of Regular Expressions with Lookaround Assertions},
author = {Konstantinos Mamouras and Agnishom Chattopadhyay},
journal = {Proceedings of the ACM on Programming Languages},
volume = {8},
number = {POPL},
year = {2024},
doi = {10.1145/3632934}
}