计算正则表达式效率

Question

您将如何计算/查找正则表达式匹配给定字符串所需的操作数？我想开发一个程序，让您可以按效率对正则表达式进行排名。

另外，如果操作次数超过给定的阈值，是否有可能突破正则表达式？我希望把它变成一个网络应用程序，所以我不希望用户输入可能会杀死服务器的正则表达式（如果可能的话）。

非常感谢。

编辑：只是为了澄清，我指的是包括回溯（因此是非线性的）的普通正则表达式的超集。

Answer 1

找出解析给定字符串需要多少次操作的方法是解析它并计算操作次数。你可以做一些有限的静态分析，但一个明确的答案就等于解决停机问题。

尝试对任何输入的表达式进行排名更加复杂。取表达式A[0-9]+

• 字符串“A999”将匹配，大约需要 O(n) 时间。
• 字符串“B943”将立即失败，花费 O(1) 时间。

正则表达式解析器基本上只是一个程序。几乎总是不可能说一个程序通常比另一个程序快，仅针对特定输入。

您可以尝试基于对输入可能是什么的一些理解来使用静态分析。例如，一个可以立即消除大部分公共输入的表达式可能比一个没有的表达式要快。我想说，唯一的方法是也接受一个与被解析的表达式具有相似分布的表达式数据集，然后使用该数据进行基准测试 [easy] 或分析 [hard]。