使用正则表达式(PCRE)匹配a ^ nb ^ nc ^ n(例如"aaabbbccc")

Question

众所周知,现代正则表达式实现(最值得注意的是PCRE)与常规语法的原始概念几乎没有共同之处.例如,您可以解析无上下文语法的经典示例{a ⁿ b ⁿ ; n> 0}(例如aaabbb)使用此正则表达式(演示):

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

我的问题是:你能走多远？是否也可以使用PCRE 解析上下文敏感的语法 {a ⁿ b ⁿ c ⁿ ; n> 0}(例如aaabbbccc)？

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)$~

这只会检查是否存在任意数量的as,后跟相同数量的bs和cs.

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

结论

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

Answer 2

我的问题是:你能走多远？

为了不创造一个难以理解的标点符号的代码,我将冒险投票并回答一个不同但非常相关的问题:你应该走多远？

正则表达式解析器在您的工具包中是一个很棒的东西,但它们并不是所有的编程.以可读的方式编写解析器的能力在您的工具包中也是一件非常棒的事情.

应该使用正则表达式直到它们开始使代码难以理解.除此之外,他们的价值充其量是可疑的,最糟糕的是破坏性.对于这种特殊情况,而不是使用像hideous这样的东西:

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

(向NikiC道歉),绝大多数人试图维护它要么必须完全替换或花费大量时间阅读和理解,你可能想要考虑像非RE,"适当的 -解析器"解决方案(伪代码):

# Match "aa...abb...bcc...c" where:
# - same character count for each letter; and
# - character count is one or more.

def matchABC (string str):
    # Init string index and character counts.
    index = 0
    dim count['a'..'c'] = 0

    # Process each character in turn.
    for ch in 'a'..'c':
        # Count each character in the subsequence.
        while index < len(str) and str[index] == ch:
            count[ch]++
            index++

    # Failure conditions.
    if index != len(str):        return false # did not finish string.
    if count['a'] < 1:           return false # too few a characters.
    if count['a'] != count['b']: return false # inequality a and b count.
    if count['a'] != count['c']: return false # inequality a and c count.

    # Otherwise, it was okay.
    return true

这将在未来更容易维护.我总是想向人们建议他们应该假设那些跟在他们后面的人(他们必须维护他们写的代码)是那些知道你住在哪里的精神病患者 - 在我的情况下,这可能是对的一半,我不知道你住在哪里:-)

除非你真的需要这种正则表达式(有时候有很好的理由,比如解释语言中的性能),你应该首先优化可读性.

Answer 3

以下是使用.NET正则表达式的平衡组的替代解决方案:

^(?'a'a)+(?'b-a'b)+(?(a)(?!))(?'c-b'c)+(?(b)(?!))$

不是PCRE,但可能有意义.

示例:http://ideone.com/szhuE

编辑:添加了组a的缺失平衡检查和在线示例.

Answer 4

Qtax技巧

未提及的解决方案：

^(?:a(?=a*(\1?+b)b*(\2?+c)))+\1\2$

在正则表达式演示中查看哪些内容匹配，哪些内容失败。

这使用自引用组（@Qtax 在他的垂直正则表达式上使用的想法）。