是否有常规语言来表示正则表达式？

具体来说，我注意到正则表达式本身的语言并不经常。所以，我不能使用正则表达式来解析给定的正则表达式。由于正则表达式本身的语言没有上下文，因此我需要使用解析器。是否有常规语言来表示正则表达式？

是否有任何方式可以表示正则表达式的方式，结果字符串可以使用正则表达式进行分析？

注意：我的问题不是关于是否有正则表达式来匹配正则表达式的当前语法，而是正如我们现在所知道的那样是否存在正则表达式的“表示”（可能并不像我们所知他们如今天），可以使用正则表达式进行分析。另外，请有人删除dup，因为它不是dup。我在问完全不同的东西。我已经知道当前正则表达式的语言是不正规的（这是我如何开始我的原始问题）。

来源

2013-10-23 dhruvbird

先写* *“所有可能的正则表达式集”*（这是你的输入语言）。 **否**，在正式语言中，您无法编写正则表达式来验证“正则表达式”。因为“所有可能的正则表达式的集合”都是完整的CFL，所以我们不能为CFL编写正则表达式。 –

我的问题不是关于是否有正则表达式来匹配正则表达式的当前语法，而是正如我们今天所知道的那样是否存在正则表达式的“表示”（可能不像我们今天所了解的那样整齐）可以使用正则表达式进行分析。另外，请有人删除dup，因为它不是dup。我在问完全不同的东西。 – dhruvbird

是的，您可以将问题标记为请求重新打开。（如果你注意到还有重新打开的按钮） –

答案可能是NO。

正如您已经指出的那样，所有可能的正则表达式本身并不是一个常规集合。任何TRUE正则表达式（不扩展）可以转换为有限自动机（FA）。如果正则表达式可以用自己可以解析的形式表示，那么FA也可以通过正则表达式进行解析。

但据我所知，这是不可能的。 RE本身可以简化为三种基本操作（根据Dragon Book）：

级联： ab
交替：例如， a|b
kleen closure：例如a*

的KLEEN闭合可以匹配的字符数限制的，但它无法知道多少字符相匹配。只是想这样的情况：你想连续匹配3个a s。那么相应的正则表达式是/aaa/。但是如果你想要比赛4,5,6 ... a s？只有一个RE的解析器无法知道a的确切数量。所以它没有给予任意表达式的正确匹配。但是，RE解析器必须匹配无限不同形式的RE。根据你的表情，正则表达式不能匹配所有的可能性。（可能这就是为什么在词法分析中使用RE的原因）RE中的每个字符都是一个标记（不包括那些转义字符）。但是为了解析RE，无论它是如何转换的，都必须面对NFA/DFA/TREE ...... RE本身无法解析的所有等效结构。

来源

2013-10-23 07:17:05

你也可以添加RE使用圆括号，并且使用RE不能验证圆括号的平衡（如果非常conman example = a^n b^n） –

是否有常规语言来表示正则表达式？

回答

相关问题