PCRE正则表达式无法描述什么？

Question

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

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

任何人都可以解释正则表达式的正式限制吗？我知道这可能是一个相当学术性的问题，但我是一个好奇的人;-)

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

平衡括号的匹配似乎是常规表达式无法匹配的一个示例，但可以使用PCRE进行匹配（请参阅qazxsw poi的实例）：

http://sandbox.onlinephpfunctions.com/code/fd12b580bb9ad7a19e226219d5146322a41c6e47

Answer 1

我想到的第一个例子是匹配像

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

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

这样的字符串。这将是由XOOXXXOOOOXXXXX...和X的交替序列组成的字符串，其中每个仅由字符O或X组成的子部分长于另一个字符的预先序列。

是的，可以做到。

---

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

---

至于主要问题。 。 。我相信PCRE可以匹配任何无上下文的语言，因为在第n个捕获组之外支持^(?=o*(?:(x(?1)?o)o+)*x*$)x*(?:(o(?2)?x)x+)*o*$ 意味着你基本上可以为每个非终端创建一个子程序。例如，这种无上下文语法：

• S→aTb
• S→ε
• T→cSd
• Ť→ETF

可以写成：

• 捕获组＃1（S）→(?n)
• 捕获组＃2（T）→(a(?2)b|)

要将它组合成一个正则表达式，我们可以将它们全部连接起来，但是除了起始非终端之外，追加(c(?1)d|e(?2)f)，然后添加{0}和^：

$

但正如您在第一个示例中看到的那样，PCRE也可以匹配一些非上下文语言。 （另一个例子是anbncn，它是一个非上下文无关语言的典型例子。你可以将它与PCRE相匹配，通过使用前向预测断言将用于anbncm的PCRE与用于ambncn的PCRE相结合。虽然是两种常规语言的交集必须是常规的，两个无上下文语言的交集不一定是无上下文的;但是两个PCRE定义的语言的交集可以由PCRE定义。）

Answer 2

可以通过正则表达式识别的所有语言的集合被称为“^(a(?2)b|)(c(?1)d|e(?2)f){0}$ ”，这并不奇怪。

接下来最复杂的语言是regular languages。它们无法被任何正则表达式解析。标准示例是“所有平衡括号” - 所以“（）（）”和“（（））”但不是“（（）”。

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

Answer 3

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

1）数学很糟糕。

例如，我不相信使用PCRE可以检测一系列升序的数字：即，在“1 2 7 97 315 316 ...”上返回true。

2）我不确定是否有可能匹配从1连续增加的序列，如“1 2 3 ...”，没有详尽地列出所有可能性，例如context-free languages，直到你想检查的最大长度。

通过向已测试的字符串添加已知文本（例如/1( 2( 3(...)?)?)?/通过在文件末尾添加一系列数字来工作），可以使其工作。但作为原始正则表达式，简单的数学只能通过强制执行。

3）我认为它将失败的另一个例子是“匹配任何与N相加的序列”。

因此，对于N = 4，它应该匹配http://www.rexegg.com/regex-trick-line-numbers.html，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）以同样的方式，我认为你不能用SI单位分析一个方程，并验证单位在方程的两边是否平衡。例如，“10N = 2kg * 5ms ^ -1”。不要在意检查数值，只需检查单位是否正确。

5）然后存在计算机程序当前无法完成的所有类问题，例如“检查字符串是否已正确地用英语标题”，这将需要上下文敏感的自然语言解析器来正确地检测不同的感官“时间飞得像箭，但果蝇像香蕉一样”中的“喜欢”。