本文介绍了Perl 正则表达式图灵完整吗?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我见过 Ruby 和 Perl 程序员完全使用正则表达式来完成一些复杂的代码挑战.Perl 正则表达式中的 lookahead 和 lookbehind 功能使它们比大多数其他正则表达式实现更强大语言.我想知道它们到底有多强大.

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 正则表达式图灵完整吗?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

08-20 08:54
查看更多