regex - 所有的正则表达式都停止了吗？

Question

对于某些输入字符串，是否有任何正则表达式可以永远搜索匹配项？

score 33 · Accepted Answer

对于有限输入，没有不会停止的正式正则表达式。

任何正式的正则表达式都可以转换为确定性有限自动机。DFA 一次读取一个字符，在输入结束时，您要么处于接受状态，要么处于不接受状态。如果状态为接受，则输入匹配正则表达式。否则，它不会。

现在，大多数“正则表达式”库都支持非正则表达式的东西，例如反向引用。只要您远离这些功能，并且输入有限，就可以保证停止。如果您不...取决于您使用的确切内容，您可能无法保证停止。例如，Perl 允许插入任意代码，并且不保证任意的图灵机等效代码会停止。

现在，如果输入是无限的，那么可以找到永远不会停止的普通正则表达式。例如，“ .*”。

score 7 · Accepted Answer

形式正则表达式实际上是一种描述用于解析字符串的确定性有限自动机的方法。如果 DFA 在输入结束时处于接受状态，则正则表达式“匹配”。由于 DFA 是按顺序读取其输入的，所以当它到达输入的末尾时它总是会停止，而是否存在匹配只是检查它停止在 DFA 的哪个状态的问题。

子字符串匹配实际上是相同的，除了不是在字符串的一次通读结束时强制停止，而是在读取每个可能的子字符串一次后强制停止 DFA - 仍然是有限的情况。（是的，大多数正则表达式引擎以更优化的方式实现这一点，而不是仅仅将所有可能的子字符串都扔到 DFA 上——但从概念上讲，限制仍然存在）。

因此，DFA 不会停止的唯一可能情况是输入是无限的，这通常被认为超出了停止问题的范围。

score 2 · Accepted Answer

我想，不可能找到一个不会停止的正则表达式。

您输入的大小是有限的。正则表达式的任何匹配子组的最大大小是输入的最大大小。

除非使用的算法非常愚蠢（多次检查案例），否则匹配子组的数量也将是有限的。

所以，它会停止。

score 1 · Accepted Answer

不是您所描述的意义上，您可能有一些非常低效的正则表达式，它们占用大量资源并最终杀死正则表达式引擎，这与停止不同。

正如这篇文章的其他评论者所敏锐地指出的那样，我认为暂停在这里并不适用。 http://en.wikipedia.org/wiki/Halting_problem

score 1 · Accepted Answer

1

根据这个问题，每个正则表达式都会停止。

于 2009-08-06T20:38:20.193 回答

score 0 · Accepted Answer

我无法想象一个输入字符串会被永远解析，尽管无限长的字符串会被永远解析。鉴于正则表达式可以描述正则语言，这可能是无限的单词集，那么正则表达式可以描述无限单词的语言，包括无限长的单词。但是，没有输入字符串可以无限长，因此在某些时候它必须停止。

例如，如果 a*b 在语言中被接受，并且你有一个无限长的 'a' 字符串，那么是的，正则表达式永远不会停止。但实际上，这是不可能的。

score 0 · Accepted Answer

是的。

正则表达式可以用有限状态机表示。每次收到原子输入时，都会导致任何定义明确的 FSM 转换到已知状态。

例外情况是当您有无限输入时，但这不适用于停止问题，因为它处理有限输入。当您有一个有限状态机和有限输入时，总是可以确定您的机器是否会停止。

score 0 · Accepted Answer

丹尼尔的回答+1：所有有限输入都会导致真正的正则表达式（即，没有反向引用或其他非正则表达式功能）停止，并且正则表达式等效于 DFA。

奖励：正则表达式匹配可以简单快速（但在 Java、Perl、PHP、Python、Ruby 中很慢...）

请注意，文章顶部的两张图在 y 轴上有不同的刻度：一张是秒，另一张是微秒！

8 回答 8