regex - Perl 正则表达式图灵完备吗？

Question

我见过 Ruby 和 Perl 程序员做了一些complicated code challenges完全用正则表达式。 lookahead and lookbehind Perl 正则表达式中的功能使其比大多数其他语言中的正则表达式实现更强大。我想知道他们到底有多强大。

有没有一种简单的方法可以证明或反驳 Perl 正则表达式是 Turing complete ？

Answer 1

排除任何类型的嵌入式代码，例如 ?{ }，它们可能无法涵盖所有​​上下文无关的内容，更不用说图灵机了。他们可能会这样做，但据我所知，没有人真正以这种或那种方式证明过这一点。鉴于人们一直在尝试使用 Perl 正则表达式解决某些上下文无关问题，但尚未找到解决方案，因此它们很可能不是上下文无关的。

关于哪些功能只是方便，哪些功能实际上增加了功能，有一个有趣的讨论。例如，匹配 0ⁿ*1*0ⁿ (这是“任意数量的零，后跟一个 1，后跟与之前相同数量的零”的表示法) ) 不是可以用纯正则表达式完成的事情。您可以使用泵引理证明这不能通过正则表达式来完成，但简单、非正式的证明是正则表达式必须计算任意数量的零，而正则表达式无法进行计数。

但是，反向引用可以与以下内容相匹配:

/(0*) 1 \1/x;

因此，这意味着反向引用可以为您提供更多功能，而不仅仅是一种便利。我想知道还有什么可以给我们更多的力量？

此外，Perl6“模式”(它们甚至不再假装它们是正则表达式)的设计看起来有点像 Perl5 正则表达式(因此您不需要重新学习太多)，但它们添加了足够的功能完全与上下文无关。实际上，它们的设计目的是让您可以使用它们来改变词法范围内解析语言的方式。