有这样的东西吗?
例如,S -> aSb | ^(可能的词:^、ab、aabb、aaabbb、aaaabbbb、...)
据我所知,唯一与上述语法密切匹配的正则表达式是:a*b*
但是正则表达式可以生成 aab、abb 等单词,其中 a 和 b 不相等。
有解决办法吗?类似于:a*b* if#a = #b
编辑:我认为没有解决办法。
正确的解释是什么?这实际上是我作业的一个片段,我真的不知道该回答什么,因为没有将语法转换为正则表达式的解决方案。
最佳答案
如果您在谈论形式语言理论,那么当然所有非常规语法(如您的示例中)都不能用正则表达式(根据定义)来表达。
但是如果您想知道不同的正则表达式风格(在编程语言/正则表达式库中)可以做什么,那么您可以匹配所有类型的非常规语法/语言。
例如,在 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)
关于regex - "Untranslatable"正则表达式语法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14713075/