regex - “不可翻译”的语法到正则表达式

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^nb^nc^n (eg "aaabbbccc") using regular expressions (PCRE)

Answer 2

在形式语言理论中，可以使用称为“抽水引理”的东西来证明某些句子（语言）集不能用正则表达式来描述。参见维基百科http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages。您从要描述的语言开始，并使用抽水引理来找到矛盾。您的示例的证明实际上在该维基百科页面上。

上下文无关语言也存在类似的理论。有些语言不能用上下文无关的语法来描述。