Perl正则表达式是否完整? [英] Are Perl regexes turing complete?

问题描述

我已经看到Ruby和Perl程序员完全使用正则表达式来进行一些复杂的代码挑战. Perl正则表达式中的先行和后视功能使它们比大多数其他正则表达式实现更强大语言.我想知道它们到底有多强大.

I've seen Ruby and Perl programmers do some complicated code challenges entirely with regexes. The lookahead and lookbehind capabilities in Perl regexes make them more powerful than the regex implementations in most other languages. I was wondering how powerful they really are.

是否有简单的方法来证明或否定Perl正则表达式是转换完成?

Is there an easy way to either prove or disprove that Perl regexes are Turing complete?

推荐答案

不包括任何嵌入式代码，例如?{ }，它们可能不会涵盖所有与上下文无关的内容，更不用说图灵机了.他们可能会，但是据我所知，没有人实际上以一种或另一种方式证明了这一点.鉴于人们一段时间以来一直在尝试使用Perl正则表达式解决某些与上下文无关的问题，并且还没有提出解决方案，所以很可能他们不是上下文无关的.

Excluding any kind of embedded code, such as ?{ }, they probably don't cover all of context-free, much less Turing Machines. They might, but to my knowledge, nobody has actually proven it one way or another. Given that people have been trying to solve certain context-free problems with Perl regexes for a while and haven't come up with a solution yet, it's likely that they are not context-free.

关于哪些功能仅是方便的，哪些功能真正增加了功能，将进行有趣的讨论.例如，匹配0 ⁿ * 1 * 0 ⁿ (表示为任意数量的零，后跟1，后跟相同数量的零" )不能用纯正则表达式来完成.您可以证明使用Pumping Lemma的正则表达式无法做到这一点，但是简单，非正式的证明是，正则表达式必须计数任意数量的零，而正则表达式不能进行计数.

There is an interesting discussion to be had about what features are merely convenient, and which actually add power. For instance, matching 0ⁿ*1*0ⁿ (that's notation for "any number of zeros, followed by a one, followed by the same number of zeros as before") is not something that can be done with pure regexes. You can prove this can't be done with regexes using the Pumping Lemma, but the simple, informal proof is that the regex would have to count an arbitrary number of zeros, and regexes can't do counting.

但是，后向引用可以将其与以下项匹配:

However, backreferences can match that with:

/(0*) 1 \1/x;

因此，这意味着反向引用可以为您提供更多功能，而不仅仅是提供方便.我想知道还有什么可以给我们带来更大的力量?

So that means backreferences give you more power, and are not a mere convenience. What else might give us more power, I wonder?

此外，Perl6模式"(甚至不再假装它们是正则表达式)被设计为看起来像Perl5正则表达式(因此您无需重新学习)，但是它们具有足够的功能完全不依赖上下文.它们实际上是经过设计的，因此您可以使用它们来改变在词法范围内分析语言的方式.

Also, Perl6 "patterns" (they're not even pretending they're regexes anymore) are designed to look kinda like Perl5 regexes (so you don't need to relearn much), but they have enough features added to be fully context-free. They're actually designed so you can use them to alter the way the language is parsed within a lexical scope.

这篇关于Perl正则表达式是否完整?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！