RE#: how we built the fastest regex engine in F#
3 months ago
- #F#
- #regex-engine
- #performance
- RE# 是一个用F#构建的正则表达式引擎，其性能优于其他工业级正则引擎，支持完整的布尔运算符和上下文感知的环视功能，且搜索时间复杂度为O(n)。
- 该引擎基于Brzozowski派生算法，能高效处理交集(&)和补集(~)运算符——这些在其他正则引擎中通常不受支持。
- RE#采用最小项压缩技术，通过将字符空间划分为等价类来优化性能，显著降低内存占用并提升匹配速度。
- 引擎采用惰性DFA构建的确定性有限自动机匹配循环，完全跳过NFA阶段，直接从正则表达式通过派生算法构建DFA。
- RE#支持形如(?<=R1)R2(?=R3)的环视语法，将上下文信息直接编码到状态中，实现具有小常数项的线性时间匹配。
- 引擎遵循POSIX语义，确保最左最长匹配，这种确定性匹配方式避免了回溯引擎的常见缺陷。
- RE#是开源项目，提供NuGet包和交互式网页应用，可用于探索正则模式及其组合效果。