PCRE 正则表达式不能描述什么？

Question

我使用了很多正则表达式，偶然发现了一个问题，究竟什么不能可以用正则表达式来描述。

我想到的第一个例子是匹配 XOOXXXOOOOXXXXX... 这样的字符串。这将是一个由 X 和 O 的交替序列组成的字符串，其中每个仅由字符 X 或 O 组成的子部分比前面的长另一个字符的序列。

谁能解释一下正则表达式的正式限制是什么？我知道这可能是一个相当学术的问题，但我是一个好奇的人 ;-)

编辑因为我是一个 php 人，所以我对 PCRE 标准描述的正则表达式特别感兴趣，如下所述：http://php.net/manual/en/reference.pcre.pattern.syntax.php 我知道 PCRE 允许很多不属于原始正则表达式的东西，比如反向引用。

平衡括号的数学运算似乎是一个例子，一般不能用正则表达式匹配，但它可以使用 PCRE 匹配（参见 http://sandbox.onlinephpfunctions.com/code/fd12b580bb9ad7a19e226219d5146322a41c6e47 for live例子):

$data = array('()', '(())', ')(', '(((()', '(((((((((())))))))))', '()()');    
$regex = '/^((?:[^()]|\((?1)\))*+)$/';

foreach($data as $d) {
  echo "$d matched by regex: " . (preg_match($regex, $d) ? 'yes' : 'no') . "\n";
}

Answer 1

一个正则表达式可以识别的所有语言的集合称为“regular languages”。

第二复杂的语言是 context-free languages。它们不能被任何正则表达式解析。标准示例是 "all balanced parentheses" - 所以“()()”和“(())”而不是“(()”。

上下文无关语言的另一个很好的例子是 HTML。

Answer 2

First example that came to my mind was matching a string like XOOXXXOOOOXXXXX.... This would be a string consisting of an alternating sequence of X's and O's where each subpart consisting only of the character X or O is longer than the previsous sequence of the other character.

是的，可以做到。

要匹配一个非空的 x 序列，后面跟着更多的 o，我们可以使用类似于平衡括号正则表达式的方法：
```
(x(?1)?o)o+
```
为了匹配一个由 x 和 o 组成的字符串，使得任何 x 序列后跟一个更长的 o 序列（除了最后可选的），我们可以在模式 #1 的基础上构建：
```
^o*(?:(x(?1)?o)o+)*x*$
```
当然，我们还需要 x 和 o 翻转的模式 #2 的变体：
```
^x*(?:(o(?1)?x)x+)*o*$
```
要匹配满足上述两个条件的 x 和 o 字符串，我们可以将模式 #2 转换为正向先行断言，并在模式 #3 中重新编号捕获组：
```
^(?=o*(?:(x(?1)?o)o+)*x*$)x*(?:(o(?2)?x)x+)*o*$
```

至于主要问题。 . .我相信 PCRE 可以匹配任何上下文无关语言，因为支持 (?<i>n</i>) outside 的 nth 捕获组意味着您基本上可以为每个非终端创建一个子例程。例如，这个上下文无关文法：

S→aTb
S → ε
T→cSd
T → eTf

可以写成：

捕获组 #1 (S) → (a(?2)b|)
捕获组 #2 (T) → (c(?1)d|e(?2)f)

到 assemble 到单个正则表达式，我们可以将它们全部连接起来，但毕竟附加 {0} 但开始非终端，然后添加 ^ 和 $:

^(a(?2)b|)(c(?1)d|e(?2)f){0}$

但是正如您从第一个示例中看到的那样，PCRE 也可以匹配一些非上下文无关语言。（又如aⁿbⁿcⁿ ，这是一个典型的非上下文无关语言的例子。你可以通过为 a^{n[= 组合一个 PCRE 来匹配它与 PCRE 108=]}bⁿc^m a^mbⁿcⁿ使用前瞻断言，虽然两种正则语言的交集必然是正则的，但是两种上下文无关语言的交集是不一定是上下文无关的；但是由两个 PCRE 定义的语言的交集可以由一个 PCRE 定义。）

Answer 3

我没有确凿的证据证明递归、平衡组、self-referencing 组以及将文本附加到被测试的字符串中是不可能的。我会很高兴在任何或所有这些方面被证明是错误的，因为我会学到一些东西！

数学很差

例如，我不认为可以使用 PCRE 来检测升序的数字序列：也就是说，匹配“1 2 7 97 315 316...”而不是“127 97 315” 316...

我不确定是否有可能匹配一个序列 从 1 开始连续增加， 就像“1 2 3...”，而不是像 [=] 这样详尽地列出所有可能性10=] 到您要检查的最大长度。

通过向被测字符串添加已知文本来使其工作的方法很简单（例如 http://www.rexegg.com/regex-trick-line-numbers.html 通过在文件末尾添加一系列数字来工作）。但作为原始正则表达式，简单的数学运算只能通过 brute-forcing.

我认为它会失败的另一个例子是“匹配任何总和为 N 的序列”。

所以对于 N=4，它应该匹配 4、3 1、1 3、2 2、1 1 1 1、2 1 1， 1 2 1、1 1 2、1 1 1 1，看起来你可以 brute-force，直到你意识到它也必须匹配 4 -12 11 0 1。

以同样的方式，我不认为你可以用它来分析一个使用SI单位的方程，并验证方程两边的单位是否平衡。例如，“10N=2kg*5ms^-1”。不要介意检查值，只需检查单位是否正确。
还有所有类目前没有计算机程序可以解决的问题，例如“检查字符串是否正确地以英文显示标题大小写”，这需要context-sensitive 自然语言解析器可正确检测“光阴似箭，果蝇似香蕉”中“喜欢”的不同含义。

PCRE 正则表达式不能描述什么？

What can NOT be described by a PCRE regex?

php

regex

pcre

computation-theory