python - 相互匹配两个正则表达式

Question

我想比较 Python 中的两个正则表达式。

基本上，我需要测试一个表达式是否包含在另一个表达式中。

例如，[AB]D是否包含在[AB][CD]中。或者是...K.. 包含在...[KR]..

我尝试了类似下面的方法，但它不起作用:

re.finditer(r"[AB][DF]",r"[AB]D")
re.finditer(r"[AB]D",r"[AB][CD]")

我的表达式可以有不同的大小，但具有相同大小表达式的解决方案会很棒。

编辑

我所有的正则表达式都非常简单。

它们只包含“points”、“square braquets”和“^”。

.意思是“任何东西”(就像真正的正则表达式中的 *)
[AB]表示“A或B”
[^P]表示“不是P”

编辑 2

感谢您的回答和评论，我想我将从一个正则表达式生成一组所有字符串并用第二个正则表达式测试它们。

Answer 1

你可以做到，但你必须自己做。这是一项繁重的工作，您可能会认为不值得为此付出努力。您可以通过以下方式做到这一点:

1. 将正则表达式 A 和 B 转换为 NFA。

2. 让 (a, b) 成为 NFA 形式的两个正则表达式的初始状态集。

3. 取两个集合的 epsilon 闭包，(e(a), e(b))。

4. 对于每个符号，遵循从 e(a) 到 e(b) 的所有转换，沿着该符号形成一个新状态， (a', b')。

5. 回到第三步。

最终，您将对两个正则表达式的所有可能状态集进行递归。如果在任何一点 e(b) 包含最终状态但 e(a) 不包含，则 B 不包含在 A 中。

这保证会终止，因为状态集的数量是有限的。此技术不适用于反向引用。 技术上如果您使用反向引用，那么它们就不再是正则表达式，至少从形式语言的角度来看是这样。