为什么基于文本的正则表达式引擎无法处理惰性量词？

Question

我多次遇到过，基于文本的正则表达式引擎无法支持惰性量词。但我找不到原因。但我后来发现，他们内部使用 DFA，并且不会回溯。

然后我坐下来为惰性量词画了一个 DFA，这就是我得到的。

\/\*.*\*\/

（其中 * 是惰性的）（正确匹配 C 注释）：
（以下 DFA 的正则表达式，以确保其行为符合预期）

为了比较，我还写了贪婪量词版本。

\/\*.*\*\/

（其中 * 是贪婪的）（错误匹配 C 注释）：
（以下 DFA 的正则表达式，以确保其行为符合预期）

抱歉，我忘记在图中添加开始状态。将最左边的状态视为两者的开始。

这里，贪婪版本实际上需要备份！此外，可以使用 DFA 完成惰性量词。我做错了什么吗？为什么很多人说基于文本的正则表达式引擎不支持惰性？

PS：为了简单起见，我没有完成上述两个 DFA。要完成它们，只需将每个状态中所有不存在的移动添加到新的错误状态即可。一旦进入错误状态，就无法退出。

Answer 1

免责声明：我是 RE/flex 的作者，发布它是希望对其他人有用。

有人说，不可能多次为基于文本的正则表达式（POSIX 正则表达式）实现惰性量词。

但是，有时可以绘制一个“模拟”惰性量词的 DFA。这并非易事，但（很大程度上）是可能的。

为了自动执行此操作，我在 2015 年提出（发明）了一种特殊的新 DFA 转换，并于 2016 年公开发布了它，它就是这样做的。它接受惰性可选

??

并重复 POSIX 正则表达式模式中的

*?

和

+?

。惰性模式匹配是在线性时间内执行的，即没有回溯。 DFA 是直接从正则表达式生成的，即没有汤普森变换。 DFA 状态使用线性时间 DFA 扫描进行注释，该扫描实际上在构建 DFA 的第一遍中进行“动态”转换。

我最近重新审视了该算法，调整它以处理所有 Perl 正则表达式惰性量词形式，例如嵌套惰性和非惰性重复及其组合，我用大量正则表达式模式对此进行了验证。由于基于文本 (DFA) 与基于 Perl (NFA) 正则表达式匹配不同，因此在将惰性重复与非惰性重复组合时，匹配情况可能会略有不同，因为非惰性模式始终匹配最左边、最长的输入字符序列如您所知，可以匹配。

DFA 转换在 RE/flex 中实现。

reflex

工具还可以生成DFA graphviz点文件，以可视化生成的DFA，详细信息请参阅手册。