regex - "Untranslatable"正则表达式语法

Question

有这样的东西吗？

例如，S -> aSb | ^(可能的词:^、ab、aabb、aaabbb、aaaabbbb、...)

据我所知，唯一与上述语法密切匹配的正则表达式是:a*b*

但是正则表达式可以生成 aab、abb 等单词，其中 a 和 b 不相等。

有解决办法吗？类似于:a*b* if#a = #b

编辑:我认为没有解决办法。

正确的解释是什么？这实际上是我作业的一个片段，我真的不知道该回答什么，因为没有将语法转换为正则表达式的解决方案。

Answer 1

如果您在谈论形式语言理论，那么当然所有非常规语法(如您的示例中)都不能用正则表达式(根据定义)来表达。

但是如果您想知道不同的正则表达式风格(在编程语言/正则表达式库中)可以做什么，那么您可以匹配所有类型的非常规语法/语言。

例如，在 Perl/PCRE 中，您可以将您的示例语言与以下任何一种相匹配:

• 使用递归/子模式调用:

  ^(a(?1)b)$

• 使用反向引用(带条件):

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

您可能对此问答感兴趣:Match a^n b^n c^n (e.g. "aaabbbccc") using regular expressions (PCRE)