将几个正则表达式合并为一个正则表达式

Question

我有几个正则表达式（实际上有几千个正则表达式），我必须检查一个字符串是否与这些正则表达式匹配。它效率不高，所以我想将所有这些正则表达式合并为一个正则表达式。

例如，如果有这些正则表达式：

• '富*栏'
• '富*拉链'
• '扎普*栏'

我想获得'foo *（bar | zip）| zap * bar'之类的东西。

是否有一些算法，库或工具来做到这一点？

Answer 1

您可以使用或连接正则表达式（（|）（以及锚定字符串的开始/结尾）。

大多数良好的正则表达式库在从正则表达式构建它们之后优化它们的有限状态自动机。例如，PCRE就是这样做的。

这一步通常会照顾你的优化问题，即。他们应用了大部分必须“手工”完成的转换。

Answer 2

即使可能，我也无法想象得到的正则表达式会更高效。

Answer 3

我非常怀疑它，理由是任何这样的工具必须非常复杂才能处理正则表达式可以结合的所有不同方式。

如果你的正则表达式比较简单，比如在你的例子中，但是你可能有一些运气写自己的东西。

Answer 4

理论上，正则表达式是一个（非确定型）有限状态自动机;因此可以合并并最小化。你可以看看this作为一个起点。

但要小心，这可能不是最正确的答案。为什么你必须处理数千个正则表达式？我只能揣测这种事情的重要性。也许你应该考虑编写一个解析器和一个语法 - 很容易完成（而语法无论如何都比regexps更强大）。