pcre - 构造一个简单的正则表达式，只有 +、*、() 和 |

Question

让我们{a,b,c}成为字母表。我必须构造一个匹配这个字母表上任何输入的正则表达式，如果aa出现在输入中，那么cc也必须出现（在输入中的某个地方）。

没有向前看，没有向后看，没有反向引用，只需使用量词 + 和 *，通过括号分组和通过|.

问题是我不知道如何解决这个问题。例如，这些输入必须匹配：

以下内容不得匹配：

我怎样才能构建这样的正则表达式，只使用这些工具？

更新

我想过

((cc(b|c)*aa)|(aa(b|c)*cc))+|(ab|ba|ca|ca|bb|bc|cc)*

你怎么看，这是否符合规范？

score 3 · Accepted Answer

(b|c|a(b|c))*(a|)|(a|b|c)*(aa(a|b|c)*cc|cc(a|b|c)*aa)(a|b|c)*

将匹配：

任意数量的bs 或cs（甚至为零），或aif 后跟一个bor c，再加上一个可选的无伴奏a结尾。这些规则共同确保两个as 始终由bor分隔c，并且还将匹配空字符串和单个字符。
一个字符串，在某处包含一个 aa，最后是一个 cc
一个字符串，在某处包含一个 cc，最后跟一个 aa

（作为参考，如果您需要每个都aa与 a 匹配cc，那您有点搞砸了。这不再是常规的。像这样的字符串需要计算到目前为止已经看到ccccaaaa了多少s，而 FSA 无法计算。）cc

score 2 · Accepted Answer

我想，对于给定的一组参数来说，这更简单：

/^((b|c|ab|ac|a$)*|(a|b|c)*(cc(a|b|c)*aa|aa(a|b|c)*cc)(a|b|c)*)$/;

说明：显然你需要在这里匹配三种情况：

/^(b|c|ab|ac|a$)*$/

...即：“匹配字符串末尾的任意数量的b和c符号ab、、ac序列或单个项目的任意组合”。a

整个字符串确实包含'aa'序列，后跟（某处）'cc'序列 - 它仍然[abc]仅由范围组成：

/^(a|b|c)* aa(a|b|c)* cc(a|b|c)* $/

（不知何故，即使在该部分中，没有空格*也被视为斜体文本标记<code>；您显然不需要在正则表达式中使用它）

整个字符串确实包含 'aa' 序列，前面（某处）有 'cc' 序列 - 它仍然[abc]仅由范围组成：

/^(a|b|c)* cc(a|b|c)* aa(a|b|c)* $/

现在你有了正则表达式的三个部分，我想很容易将它组合成简单的模式。

2 回答 2