[音乐]
Hi,欢迎回来,接下来我们来看看关于正则的一切。
我们在最最早的时候学到了这个正则表达式,然后说正则表达式它所对应的这个集合,
正则上称作一个正则集合,后来我们在进行语法分类的时候,我们分出一类的这个语法, 称作为正则语法。
那么正则语法所产生的语言,叫做正则语言。
那么这 两个体系它们都是有正则这么一个意味的, 都有这么一个术语。
那么到底由正则表达式所 产生的正则集合和正则语法所产生的正则语言
那么这两个体系之间它们有什么样的一个关系呢?我们来看看这个定理,它就说明了这么一- 个关系。
这个定理说S是一个有限集合,这个L呢是
S*的一个子集,那么也就是说S是一个终结符,它只包含一些 终结符作为这个字符。
那么S*呢就是所有的由终结符所构成的大大小小的字符串的所有的集合。
那么L呢是S*的一个子集,那么也就表示了L它是一个语言,
那么它说L是一个正则集合, 那正则集合呢那它肯定就会对应某一个正则表达式对吧?
那么正则集合呢当且仅当说对于某一个正则语法G来说, 有这个L=L(G)。
这个L(G)呢是由 正则语法所产生的语言,那么这个L呢是正则表达式
所对应的正则集合。
那这个定理呢就把它们这两者建立了一个一一对应的关系。
它所以它是用当且仅当,对吧?那我们在接下来呢
试图来说明一下,并不是严格地证明,说明一下它为什么可以这样?
那实际上呢我们可以从这个正则语法G所构造
构造出对应的正则集合和它的这个正则表达式,也就是说我有了这个正则语法,
我可以把这个语法构造出这个正则表达式来的话,那么它不就建立了一个一一对应的关系了嘛?
那么好,我们就把这个G的这个语法,它不是有产生式,
那么产生式呢都可以表达式为这个语法图,它可以用语法图的形式来表达。
那么刚刚我们也发现了语法图呢它可以进行化简,
那所谓的化简呢,就可以把几个图合并成一个大图, 那么再把所有的产生式通通都合并了以后,
这个大图里边只包含什么呢?只包含v0这么一个非终结符,也就是它的一个替换的一个起点。
那么对于,那么其他所有的全都是圆框,没有一个方框。
那么其他所有的都是终结符,那么我们就把这样的图叫做 主导图,叫做master diagram,叫做主导图。
那么接下来呢我们说这个语法图,语法图当中这个终结符
就对应这个正则表达式当中的终结符,它们字符都是一样的嘛。
现在的我们说如何把这个由 语法产生式最后呢经过对应到
语法图,然后经过化简,经过合并,变成了一个大图,主导图。
如何把它翻译成正则表达式呢?我们就来分析这个 主导图它的结构,对它的结构进行分析。
那么结构呢也正是这三大结构,一个是串联的结构。
那么也就是说它会是一个串联子图,当然我们看到有一群的一个图,
另外一群的图它们是一个串联关系的话,那么这就是一个串联子图。
那每一个子图,比如一个子图叫D1,一个子图是D2,那么D1,D2它可能都里面会包含- 很多更复杂的
那么只要是大致是这么一个大的结构的话, 我们就把它对应这个子表达式是α1α2.。
D1所对应的是α1,D2所对应的是α2。
那么这个呢就是一个正则表达式的 一个中间的一个定义了。
如果它 分析出来是一个并联方式,D1,D2呢是可选的,好
我们对应这个正则表达式的子表达式呢就是α1|α2。
那么我们在正则表达式的定义里面呢是有|这么一个的。
如果我们发现了一个回路的子图,它是一个不同的循环的话,
那么我们就对应的这个子表达式是α*, α*,然后呢再对这个每一个子图里面,
再嵌套地去分析是串联,还是并联,还是回路。
那么最终呢就能够得到这个完整的一个正则 表达式了,而这个正则表达式里头只包含有这个终结符。
所以这个呢是一个大致的一个过程,那么这个过程具体怎么做,我们来看看一个例子。
先看这个最上面这个例子,那我们最上面也是a,b,c,然后有个循环。
我们首先分析呢它是一个分支,是一个并联结构,对吧?
所以呢它会用竖杠隔开,然后呢有a竖杠,b然后再竖杠。
然后在第三个分支,我们发现了一个回路结构,所以呢就是c*,所以最终呢它得到了一个
正则表达式,就是a|b|c*。
那么第二个图, 我们首先呢看到它是一个串联的,
那么就是三个结构的串联,由并联结构和单个的终结符,以及一个回路结构的串联。
那么很明显地,就是变成了(a|b)这样的一个并联结构。
串联上c,然后在串联上d*这么一个回路结构,所以呢它也
这样的一个主导图也直接翻译成正则表达式了。
那么第三个呢它就大的结构,第一层次就是一个回路,所以呢最外面它是应该是一个*。
然后里边呢它是一个并联的分支, 那么里边呢应该是一个树干,那树干呢就是a树干上bc,
所以呢最终翻译成这个正则表达式,它就应该是(a|bc), 然后呢最外面再加一个*。
这样呢我们通过这么一个几个例子, 以及这个对于主导图结构的分析,
我们就让这个正则表达式所对应的这个正则集
和这个正则文法所对应的这个正则语言,它们之间建立了一个 等价的一个关系。
那好,我们从现在开始呢,我们就知道 所有带正则的东西,它们都是一回事。