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

Question

我使用了很多正则表达式，并偶然发现了正则表达式实际上无法描述的问题。

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

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

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

平衡括号的数学计算似乎是一个通常无法与正则表达式匹配的示例，但可以使用PCRE 进行匹配（有关实时示例，请参阅http://sandbox.onlinephpfunctions.com/code/fd12b580bb9ad7a19e226219d5146322a41c6e47）：

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

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

Answer 1

我想到的第一个例子是匹配像 这样的字符串XOOXXXOOOOXXXXX...。这将是一个X由 s 和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 → ε
• 时间 → cSd
• T → eTf

可以写成：

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

要将其组装成单个正则表达式，我们可以将它们全部连接起来，但{0}除了起始非终结符之外，还要附加，然后添加^and $：

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

但正如您从第一个示例中看到的那样，PCRE 也可以匹配一些非上下文无关语言。（另一个例子是n b ⁿ cn ^，这是非上下文无关语言的经典示例。您可以通过将^{n b} n ^cm的^PCRE与 a m b n 的PCRE组合来^将其与 PCRE 匹配c ⁿ使用前向断言，虽然两种正则语言的交集必然是正则的，但是两种上下文无关语言的交集不一定是上下文无关的；但是由两个 PCRE 定义的语言的交集可以由一个 PCRE 定义.)