不能用 PCRE 正则表达式描述的内容

$data = array('()', '(())', ')(', '(((()', '(((((((((())))))))))', '()()');    
$regex = '/^((?:[^()]|'((?1)'))*+)$/';
foreach($data as $d) {
  echo "$d matched by regex: " . (preg_match($regex, $d) ? 'yes' : 'no') . "'n";
}

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

是的，这是可以做到的。

---

1. 为了匹配 x 的非空序列，后跟更多数量的 o，我们可以使用类似于平衡括号正则表达式的方法：

   (x(?1)?o)o+
   

2. 为了匹配 x 和 o 的字符串，使得任何 x 序列后面跟一个更长的 o 序列(除了可选的最后(，我们可以在模式 #1 的基础上构建：

   ^o*(?:(x(?1)?o)o+)*x*$
   

3. 当然，我们还需要模式 #2 的变体，其中 x 和 o 翻转：

   ^x*(?:(o(?1)?x)x+)*o*$
   

4. 为了匹配满足上述两个条件的 x 和 o 字符串，我们可以将模式 #2 转换为积极的前瞻断言，并在模式 #3 中对捕获组重新编号：

   ^(?=o*(?:(x(?1)?o)o+)*x*$)x*(?:(o(?2)?x)x+)*o*$
   

---

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

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

可以写成：

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

为了将其组装成一个正则表达式，我们可以将它们全部连接起来，但在除开始非终端之外的所有内容之后附加{0}，然后添加^和$：

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

但正如你从第一个例子中看到的那样，PCRE 也可以匹配一些非上下文无关的语言。(另一个例子是 nb n cⁿ，它是非上下文无关语言的典型示例。您可以通过使用前瞻性前瞻断言将 ⁿ b n c m 的 PCRE 与表示 ^mb n cⁿ 的 PCRE 组合在一起，将其与 PCRE 匹配。尽管两种常规语言的交集必然是规则的，但两种上下文无关语言的交集不一定是上下文无关的;但是由两个 PCRE 定义的语言的交集可以由 PCRE 定义。

正

则表达式可以识别的所有语言的集合被称为"常规语言"。

下一个最复杂的语言是上下文无关语言。 它们不能被任何正则表达式解析。 标准示例是"所有平衡括号" - 所以"(((("和"(((("而不是"((("。

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

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

1. 数学很差。

例如，我不认为使用 PCRE 可以检测升序的数字序列：即匹配"1 2 7 97 315 316..."而不是"127 97 315 316...">

2. 我不确定是否有可能匹配从 1 连续增加的序列，例如"1 2 3..."，而无需详尽列出所有可能性，例如/1( 2( 3(...)?)?)?/直到您希望检查的最大长度。

这些黑客通过将已知文本添加到被测试的字符串来使其工作(例如 http://www.rexegg.com/regex-trick-line-numbers.html 通过在文件末尾添加一系列数字来工作(。但作为原始正则表达式，简单的数学只能通过暴力破解来实现。

3. 另一个我认为它会失败的例子是"匹配任何总和为 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，看起来你可以暴力破解它，直到你意识到它也必须匹配4 -12 11 0 1。

4. 以同样的方式，我认为你不能让它使用 SI 单位分析方程，并验证单位是否在方程的两侧平衡。例如，"10N=2kg*5ms^-1"。不要介意检查值，只需检查单位是否正确。

5. 然后是目前没有计算机程序可以完成的所有类别的问题，例如"检查字符串是否在英语中正确标题大小写"，这将需要一个上下文相关的自然语言解析器来正确检测"时间像箭一样飞逝但水果像香蕉一样飞翔"中的"喜欢"的不同含义。