regex - grep -P 查找包含恰好 n 个 A 后跟恰好 n B 的行

Question

是否可以编写一个grep -P（PCRE）命令来打印仅包含Aand的行，B这样恰好n A后跟n B并且没有其他字符。这样这些是有效的匹配：

AB
AAABBB
AAAAAAABBBBBBB
AAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBB

虽然这些不是：

AAABB
ABBBBBB
BBBA
ABABA
BBBBBBBB

Answer 1

使用普通的正则表达式，您无法做到这一点 - 它们只能匹配常规的上下文无关语言（乔姆斯基语言层次结构中的类型 3），而您要匹配的是类型 2 语言的经典示例。

幸运的是，perl正则表达式在形式语言理论意义上不是很规则。您可以使用递归正则表达式匹配它：

$ perl -ne 'print if /^((?>A(?1)B|))$/' input.txt
AB
AAABBB
AAAAAAABBBBBBB
AAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBB
$ grep -P '^((?>A(?1)B|))$' input.txt  
AB
AAABBB
AAAAAAABBBBBBB
AAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBB

（其中input.txt包含您所有的测试用例）。

这匹配一个空字符串（0 个 A 后跟 0 个 B），或者一个以 A 开头的字符串，该模式与字符串的其余部分（减去第一个和最后一个字符）成功递归匹配，并以 B 结尾。如果B出现在A之前，A出现在B之后，或者A和B的总数不匹配，因此失败。(?>regex)是一种优化，可防止匹配失败后回溯。

如果您想强制执行n >= 1，则将一对 A 和 B 提升到递归部分之外的细微变化：^A((?>A(?1)B|))B$.