Video在线视频

欢迎同学们来到《软件理论基础》的MOOC课堂

我是清华大学的教师罗贵明

现在介绍第十章 上下无关文法的化简与规范

我们的内容包括消除无用符号

消除ε产生式

消除单一产生式

最后介绍上下无关文法的化简

与Chomsky范式

首先我们介绍消除无用符号

在我们前面介绍自动机的时候

我们曾经碰到这个问题

同样一个语言

有很多不同的自动机来表示这个语言

自动机是占有计算机的资源的

就是每一个状态都占资源

我们就希望用较少的状态来表示这个语言

在确定有限自动机我们介绍过DFA的优化

那现在我们介绍上下无关文法

和上下无关语言

那构造这个语言的文法和下推自动机

同样也占有我们的系统资源

那对于同一个语言 用较少的状态

来表示这个下推自动机

这是不是可行的呢

实际上这不一定的

我们曾经证明过

任何一个上下无关语言

都可以用一个状态的PDA来表示这个语言

所以我们减少状态没多大作用

那我们现在只有从文法这个角度

我们尽量用较少的变量或者产生式

去表示这个语言

这就是我们的文法的化简

我们的文法里面

我们首先就怎么去消除无用符号

我们首先介绍有用符号

给了一个上下无关文法

X它可以是变量 也可以是终结符

我们称它是有用的

如果下面这个式成立

就当开始变量推终结符这个串的时候

这个串中间符号X要出现

就一定要αXβ

a和β是任意的一个串

什么是无用符号呢

不是有用符号的它就是无用符号

当然在我们文法里面

我们是希望保持有用符号

消除无用符号

在我们的文法里面

如果一个产生式含有无用符号

我们把这样的产生式称为无用产生式

像这样给的一个文法

后面这个产生式无穷无尽的推导写出

它是推不出终结符的串

这个符号肯定不会是有用的

那包含这个符号的这个a

这样的产生式 它就是无用产生式

那下面我们再看

什么样的倒置出一个符号是无用的

从我们刚才这个特点来看

因为我们说

有用的是开始变量你要推出终结符的串

从这个关系式它是推不出终结符的串

也就是说只要是有这个性质的

它推不出终结符的串的

它肯定不是有用的

所以我们它无用符号的时候

我们首先具有这个特点

那另外

我们再看一个例子

这个例子里面

这个符号B产生bA

从开始变量到这个产生式b

它是没有可达的

也就是说这个从开始变量它是不可到达b的

都是无用符号

我们把这两个特点就定义出一个新的概念

叫产生符号可达符

如果这个X这个符号

它假如在这个文法里面

经过若干次推导能够推导出终结符的串

我们把这个符号叫做产生符

你看第一个例子里面

它是推导不出终结符的串

这样的符号我们很关注

如果推不出的话我们是不关注的

约定一下

终结符本身它也是产生符

我们再看看可达符

如果在这个文法里面

从开始变量能够推出这样一个句型

αXβ

这里面含有X

那X就称为可达符

也就是说从开始变量

能够推导出含有X这种串

那这个X就是可达的

我们也约定一下

这个开始变量是可达符的

那我们介绍了产生符和可达符

这两个符号

它跟有用符号之间有什么关系呢

那根据我们之前定义

因为有用符号

是开始变量经过若干次推导

推导出终结符的串

而在推导的过程当中

必须含有你这个符号X

那X为有用符号

那根据这个定义

我们就发现了有用符号一定是产生符

而且是可达符

反过来它们成立吗

我们说这个结论它不一定成立

大家可以回去去思考思考

产生符和可达符

这是我们在有用符号里面

是非常重要的概念

消除无用符号必须要计算产生符

那产生符怎么计算呢

那下面我们给一个算法

这个算法是一个递归的算法

给了上下无关文法

那我们的产生符是用这样的算法得到的

首先是基础

任何一个终结符它都是产生符

这是我们的归纳基础

接下来

如果有这样的一个产生式

A产生α

而α当中它每一个符号都是产生符

那我们就说a也是产生符

这就是一个归纳的一个算法

通过这个算法

就可以求出所有的这个产生符

而且求出符号一定是产生符

也就是说得到这个定理

这个算法恰好求得这个文法集的

所有的产生符

也就是说我们刚才说的那两个方面

一方面所得的符号一定是产生符

任何一个产生符

它都可以通过这个算法得到

这是产生符的它的算法

下面我们再看可达符的算法

可达符的算法它也可以由归纳得到

得到这个上下无关文法

首先基础是开始变量是可达符

接下来假如A是一个可达符

A可以产生这个α

它任何一个符号都是可达符

这也是递归的

这里得到的这个算法

恰好得到这个文法集的所有的可达符

恰好得到所有的

那也就是

一方面它得到的符号都是可达的

另外任何一个可达符

都可以通过这个算法得到

已经算出了可达符 产生符

那我们怎么去消除无用符号

接下来我们给出消除无用符号的

它的三个步骤

假设这给了一个上下无关文法

消除非产生符

因为我们计算出产生符了

把不是产生符的 就是非产生符 都消除

消除之后

我们得到了这个文法记为加

它也是个上下无关文法

它只是消除了非产生符

以及包含这个非产生符的这些产生式

得到的文法

所以它的语言是跟原来的语言是相同的

接下来我们在消除非可达符

也就是在这个文法加2里面

我消除不可达的

也就是在这个加这个文法里面

消除它的不可达符

以及包含这些不可达符的产生式

我们得到的这个文法把它记为G1

它跟G2实际上语言也是相同的

算法的步骤是按这个步骤来给的

首先要消除非产生符

然后再消除不可达符

这个算法的次序一定不能搞混淆了

只要按这种方式得到的

我们就说你这个文法里面

就再不含有非产生符和不可达符

那也就是我们得到这个文法里面

再不含有有用符号

所以我们把刚才的方法总结一下

得到这样的一个定理

根据上面的算法得到的文法G1

就是剩下的符号都是有用的

新的文法 语言的文法 是等价的

这个要证明它 一方面证明了

我们这个文法G1里面它没有无用符号

在这里面它们的语言是相等的

这个我们书上有

大家可以到底下去看看

我们把消除无用符号这个步骤

把它归纳下

步骤1就是计算你这个文法里面

所有的产生符

只要是把产生符计算出来之后

接下来就消除非产生符

然后计算可达符这个集合

计算了可达符

把那些非可达符就消除

按这个步骤我们就消除文法里面

所有的有用符号

下面我们看个例子

给了这个文法

这个文法它的产生式是这样的

那我们现在要消除它的无用符号

那按刚才你要计算它的产生符

这个文法里面它的哪些是产生符呢

终结符 终结符A

以及从这里能够推出终结符的这个串

按刚才的我们就得到a，b，A，B

我们第一轮就得到这些符号

我们前面定义的它是产生符

接下来我们再看这里面S产生a

因为a是它的产生符

根据前面的归纳

归纳那我们就得到这些也是产生符

得到第二轮就把所有的产生符就得到了

那我们就消除它的

非产生符的变量的一些产生式

那我们消除那些C还有这里的产生式

那就得到这个文法就是这样的文法

然后我们再消除非可达符

非可达符可以类似于前面的

正则文法里面把它的依赖图画出来

就发现就是开始变量不能到达的变量吧

这个是不可达符的

消除这个变量以及它的产生式

得到等价的文法就是这样

这其实消除了无用符号

我们得到的等价的文法

就比原来的变量减少了

它的产生式减少了

下面我们再看一个例子

这个例子是我们在上一章里面介绍

下推自动机转上下无关文法的一个例子

当时 这个下推自动机它构造的

上下无关文法是这样的

这是文法的变量

这是文法的变量的产生式

有多少个变量呢

大家可以数数

一共有19个变量

产生式有24个

这里面是不是都是有用的呢

我们按刚才的方法

把这些变量和产生式里面

我们把它的产生符把它给出来

这个产生符 终结符包括0，1

变量非终结符只包含这几个

那我们在这个文法里面

就消除非产生符以及对应的产生式

那我们就得到一个记号问题

我们可以把这些变量换成另外一种形式

记q0、Z0、q2为q0Xq1为B

q1Xq1为C

q1Z0q2为D

做了这个记法之后

这个文法实际上就可以表示成

这么一个简单的形式

消除它的非产生符

原来是19个变量 24个产生式

把这个文法就简化为只有6个产生式

只有4个变量

就说明用这种方法是很有效的

接下来我们再计算它的可达符

这些符号S、A、B、C、D

这些符号都是可达的

因此这里面就没有不可达符

那得到的文法实际上还是这些

这节里面我们介绍了上下无关文法

怎么去消除它的无用符号

从前面介绍的例子里看

这个方法可以有效的减少

文法里面的变量和产生式

好 这节内容介绍完毕

谢谢大家