正则表达式本身能否用正则表达式进行解析？

Question

我正在阅读正则表达式解析器的代码，开始想知道正则表达式的语法是否本身就是规则的，并且能否用另一个（相当复杂的）正则表达式来表示？

rere = "" # the regular expression of regular language
match1 = re.match(rere, "[a-z]+@[a-z]+.com") # True
match2 = re.match(rere, ")az[") # False 

我在正则表达式语法中没有看到任何递归结构，所以我认为这可能是可以做到的？

如果可以，这个表达式长什么样？ 如果不行，为什么？

- NeoWang

---

需要使用无上下文语法来解析正则表达式。嵌套的括号不能通过（理论上的）正则表达式进行解析。 - nhahtdh

是的，嵌套括号。我忘了这个。但如果我不支持组内嵌套，答案会不同吗？ - NeoWang

@NeoWang：那么你所拥有的比正则表达式要弱。也就是说，有些语言可以用正则表达式/正则文法来描述，但不能用你的文法来描述。 - nhahtdh

实际上，您可以使用正则表达式匹配嵌套的括号，但只有某些正则表达式风格支持。您的示例代码是Python，其正则表达式引擎不支持递归行为/平衡结构。然而，并不存在一个神奇的正则表达式可以“解析它们所有”。 - Wiktor Stribiżew

@stribizhev：从理论上讲，这些“flavor”并不严格符合“正则表达式”的定义，但如果问题特别指的是现实世界中的“regex”引擎，那么我想对于某些“flavor”来说是可能的。 - nhahtdh

这可能与主题无关...为什么大多数正则表达式解析器都是手写的？为什么不编写它的上下文无关语法并使用解析器生成器？ - NeoWang

Answer 1

你无法使用正则表达式解析嵌套的括号，因为你需要无限状态来这样做。所以答案是否定的。你要寻找的是被称为上下文无关文法的内容。

- Emil Vikström