我看过Ruby和Perl程序员完全用正则表达式做了大约
complicated code challenges。 Perl regex的
lookahead and lookbehind功能使它们比大多数其他语言的正则表达式实现更强大。我想知道他们真的是多么强大。
有没有一个简单的方法来证明或反驳Perl正则表达式是Turing complete？
解决方法
排除任何种类的嵌入式代码，如？{}，它们可能不会覆盖所有的上下文，更不用说图灵机。他们可能，但据我所知，没有人实际上以某种方式证明了这一点。由于人们一直试图用Perl正则表达式解决某些无上下文的问题，并且还没有提出解决方案，所以很可能它们不是上下文无关的。
有一个有趣的讨论是什么功能只是方便，实际上增加了权力。例如，匹配0n * 1 * 0n(这是“任意数目的零，后面跟一个，后面跟前面相同数目的零”的符号)不是可以用纯正则表达式完成的。你可以证明这不能使用正则表达式使用Pumping引理，但简单的，非正式的证明是正则表达式必须计数任意数量的零，正则表达式不能做计数。
然而，反向引用可以匹配：
/(0*) 1 \1/x;
这意味着反向引用给你更多的权力，而不仅仅是方便。还有什么可能给我们更多的力量，我不知道？
此外，Perl6“模式”(他们甚至不假装他们是正则表达式)被设计为看起来像Perl5正则表达式(所以你不需要重新学习很多)，但他们有足够的功能添加到完全上下文，自由。它们实际上是设计的，所以你可以使用它们来改变语言在语法范围内解析的方式。