Perl正则表达式是否完整？

发布时间：2020-12-15 21:27:52 所属栏目：大数据来源：网络整理

导读：我看过Ruby和Perl程序员完全用正则表达式做了大约 complicated code challenges。 Perl regex的 lookahead and lookbehind功能使它们比大多数其他语言的正则表达式实现更强大。我想知道他们真的是多么强大。有没有一个简单的方法来证明或反驳Perl正则表达式

我看过Ruby和Perl程序员完全用正则表达式做了大约 complicated code challenges。 Perl regex的 lookahead and lookbehind功能使它们比大多数其他语言的正则表达式实现更强大。我想知道他们真的是多么强大。

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

解决方法

排除任何种类的嵌入式代码，如？{}，它们可能不会覆盖所有的上下文，更不用说图灵机。他们可能，但据我所知，没有人实际上以某种方式证明了这一点。由于人们一直试图用Perl正则表达式解决某些无上下文的问题，并且还没有提出解决方案，所以很可能它们不是上下文无关的。

有一个有趣的讨论是什么功能只是方便，实际上增加了权力。例如，匹配0n * 1 * 0n(这是“任意数目的零，后面跟一个，后面跟前面相同数目的零”的符号)不是可以用纯正则表达式完成的。你可以证明这不能使用正则表达式使用Pumping引理，但简单的，非正式的证明是正则表达式必须计数任意数量的零，正则表达式不能做计数。

然而，反向引用可以匹配：

/(0*) 1 1/x;

这意味着反向引用给你更多的权力，而不仅仅是方便。还有什么可能给我们更多的力量，我不知道？

此外，Perl6“模式”(他们甚至不假装他们是正则表达式)被设计为看起来像Perl5正则表达式(所以你不需要重新学习很多)，但他们有足够的功能添加到完全上下文，自由。它们实际上是设计的，所以你可以使用它们来改变语言在语法范围内解析的方式。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!