php - 使用正则表达式 (PCRE) 匹配 a^n b^n c^n (例如 "aaabbbccc")

Question

众所周知，现代正则表达式实现(最著名的是 PCRE)与 regular grammars 的原始概念几乎没有共同之处。 .例如，您可以解析 context-free grammar 的经典示例{aⁿbⁿ; n>0}(例如 aaabbb)使用此正则表达式 (demo):

~^(a(?1)?b)$~

我的问题是:你能走多远？是否也可以解析 context-sensitive grammar {aⁿbⁿcⁿ;n>0}(例如 aaabbbccc)使用 PCRE？

Answer 1

受到 NullUserExceptions 答案的启发(他已经删除了，因为它在一个案例中失败了)我想我自己找到了一个解决方案:

$regex = '~^
    (?=(a(?-1)?b)c)
     a+(b(?-1)?c)
$~x';

var_dump(preg_match($regex, 'aabbcc'));    // 1
var_dump(preg_match($regex, 'aaabbbccc')); // 1
var_dump(preg_match($regex, 'aaabbbcc'));  // 0
var_dump(preg_match($regex, 'aaaccc'));    // 0
var_dump(preg_match($regex, 'aabcc'));     // 0
var_dump(preg_match($regex, 'abbcc'));     // 0

自己试试:http://codepad.viper-7.com/1erq9v

---

说明

如果您考虑没有正则先行断言((?=...) 部分)的正则表达式，您会得到:

~^a+(b(?-1)?c)$~

这只是检查是否有任意数量的 a，后跟相同数量的 b 和 c .

这还不能满足我们的语法要求，因为 a 的数量也必须相同。我们可以通过检查 a 的数量等于 b 的数量来确保这一点。这就是前瞻断言中的表达式所做的:(a(?-1)?b)c。 c 是必需的，因此我们不仅仅匹配 b 的一部分。

---

结论

我认为这令人印象深刻地表明现代正则表达式不仅能够解析非常规语法，而且甚至可以解析非上下文无关语法。希望这能平息“你不能用正则表达式做 X，因为 X 不规则”的无休止的鹦鹉学舌