是否有正规的语言来表示正则表达式?(Is there a regular language to r

2019-10-18 20:08发布

具体而言,我注意到,正则表达式本身的语言是没有规律的。 所以,我不能使用正则表达式来分析给定的正则表达式。 我需要使用一个分析器,因为正则表达式本身的语言是免费的上下文。

有什么办法正则表达式可以在结果字符串可以使用正则表达式解析的方式来表示?

注:我的问题不是是否有一个正则表达式匹配的正则表达式的当前语法,但是否存在正则表达式是“三个代表”为我们今天所知道(也许不是一个整洁的东西我们知道他们是今天)可以使用正则表达式进行解析。 另外,请可能有人删除DUP,因为它不是一个DUP。 我要问的东西完全不同。 我已经知道,正则表达式的当前语言不是正规(这是我开始了我原来的问题)。

Answer 1:

答案可能是否定的。

正如你所指出的那样,将所有可能的正则表达式本身就不是一个普通组。 任何TRUE的正则表达式(而不是那些扩展)可被转换成有限自动机(FA)。 如果正则表达式可以在可以由自身进行解析的形式来表示,则FA可以通过正则表达式,以及解析。

但是,这是不可能的,因为据我所知。 RE本身可以减少为三个基本操作(根据本龙书):

  1. 串联:如ab
  2. 交替:如a|b
  3. KLEEN封:如a*

该KLEEN闭合可以匹配的字符数限制的,但它无法知道有多少个字符相匹配。 试想这样的情况:你想匹配连续3 a秒。 然后相应的正则表达式/aaa/ 。 但是,如果你想要的东西匹配4,5,6个... a S' 解析器只有一个RE无法知道确切的数字a秒。 因此,它不能给予匹配任意表达式的权利。 然而,RE解析器来匹配无限不同形式的RE。 根据你的表达, 正则表达式无法比拟的一切准备。

好了,RE解析器的唯一区别是,它并不需要一个标记。(也许这就是为什么RE在词法分析中使用)的RE的每个字符是(不包括逃生charcters)的令牌。 但是解析RE,不管它是转化,一个不得不面对了NFA / DFA /树......不能重新本身解析所有等效结构。



文章来源: Is there a regular language to represent regular expressions?