Perl正则expression式是否完整?

我见过Ruby和Perl程序员完全用正则expression式来完成一些复杂的代码挑战 。 Perl正则expression式中的lookahead和lookbehindfunction使它们比大多数其他语言中的regex实现更强大。 我想知道他们真的有多强大。

有没有一种简单的方法来certificate或反驳Perl正则expression式是图灵完成 ?

不包括任何types的embedded式代码,例如?{ } ,它们可能不涵盖所有上下文无关的,更less的图灵机。 他们可能,但据我所知,没有人真正以这种或那种方式certificate了这一点。 鉴于人们一直试图用Perl正则expression式来解决某些上下文无关的问题,并且还没有提出解决scheme,所以很可能它们不是上下文无关的。

有一个有趣的讨论是关于哪些function只是方便的,哪些实际上增加了function。 例如,匹配0 n * 1 * 0 n (这是“任意数目的零,后跟一个,后面跟以前相同数目的零”的符号),这不是纯粹的正则expression式所能做到的。 你可以certificate这不能用正则expression式使用Pumping引理来完成,但是简单的非正式的certificate是正则expression式必须计算任意数量的零,而正则expression式不能计算。

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

 /(0*) 1 \1/x; 

所以这意味着反向引用给你更多的权力,而不仅仅是方便。 还有什么可以给我们更多的权力,我想知道?

另外,Perl6的“模式”(他们甚至不假装他们是正则expression式)被devise成看起来像Perl5的正则expression式(所以你不需要重新学习太多),但他们有足够的function,自由。 实际上,它们的devise使您可以使用它们来改变语言在词法范围内的parsing方式。

至less有两个讨论: 图灵的完整性和正则expression式 , Perl模式是普遍的吗? 有进一步的参考。

对我的未经训练的眼睛的共识似乎是答案是“不”,但我不确定是否我正确地理解了一切。

Perl中的正则expression式有两种情况:

  1. embedded代码:他们当然是图灵完成的。
  2. 没有embedded代码:他们总是停下来,所以他们不是普通的图灵机。

每一种正规的语言都可以被有限自动机所接受。 它的input必须是一个有限的string。

确定性有限自动机(DFA)也被称为确定性有限状态机,是一种接受/拒绝有限符号串的有限状态机[…]。

图灵机也是如此 :正式的定义甚至没有input。 它必须在有限数量的状态下编码。

替代(等同)定义包括input,但它必须是有限的。

Interesting Posts