Efficient Matching of Regular Expressions with Lookaround Assertions

Explore an innovative approach to matching regular expressions with lookaround assertions in this 21-minute conference talk from POPL 2024. Delve into the formal mathematical semantics of lookaround, learn about equational properties for simplifying assertions, and discover a new algorithm with O(m · n) time complexity. Examine the concept of oracle-NFAs and understand how they enable efficient evaluation of lookaround assertions. Compare the performance of this new implementation against state-of-the-art regex engines like PCRE and Java's regex library through experimental results. Gain insights into optimizing regex matching for improved speed and efficiency, particularly when dealing with complex patterns involving lookahead and lookbehind assertions.

[POPL'24] Efficient Matching of Regular Expressions with Lookaround Assertions