Video在线视频

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

现在介绍第七章 第二节

规约和推导

在上一节里面我们介绍了

上下文无关文法

以及上下文无法文法的表示形式

这里我们要介绍上下文无关文法

它怎么样去操作的

一个字符串是不是属于文法的语言

我们在上一节的例子里面

会看到它可以推导

那怎么推导呢

我们推导有两种方法

一种是规约 一种是推理

规约是自下而上的一种推理

也就是从下面往上面

来进行推理的一个过程

我们也叫递归推理

另外还有一个是自上而下地推理

我们叫推导

规约的过程

它是把它的产生式的右边

替换为产生式的左边

而推导的过程 它跟它是相反的

是把产生式的左边

也就是它的head替换产生式的右边

那下面我们看这个规约过程的举例

我们还是给出之前的上下文法

这个文法 它的变量 终结符

以及开始变量 产生式

大家前面已经看过了

下面我们要用递归推理

要推这么一个字符串

（v+d）×d

看这里是不是可以通过这个文法

把它归结出来

如果能够归结到开始变量E

那说明这个串是由这个文法产生的

那下面我们给出这个串

首先用第六个产生式 把×规约成O

然后用第五个产生式 把+规约成O

再用第四个产生式 把d 规约成E

这个d规约成E

再用第四个产生式

就把这个d规约成E

然后再用第三个产生式 把v规约成E

再用第一个产生式把EOE规约成E

再用第二个产生式把这个（E）规约成E

最后用第一个产生式

把EOE规约成开始变量E

你看这个过程

是首先我们给出了这个字符串

也是最下一层的

在这个文法里面

我们就用递归推理或者规约

它的右边替换左边

最后得到了它的开始变量E

这是我们的规约过程

下面我们再看一个它的推导过程

我们还是用这个文法

还是用这样的字符串

那跟刚才不同的是

我们现在是希望在这个文法里面

是自上而下把这个字符串推出来的

那上最开始是什么呢

最开始是从开始符 开始变量E

在这个文法里面

我们能不能推出这个字符串

如果能够推出出来

说明这个字符串是由这个文法产生的

那么我们下面根据开始给了开始变量E

因为第一个产生式E产生EOE

再用第二个产生式E产生（E）

然后再用第一个产生式这个E产生EOE

再用第三个产生式把这个E产生V

再用第四个产生式把E产生这个d

再用第四个产生式把这个E产生这个d

再第五个产生式把这个O产生+

再用第六个产生式 把这个O产生×

最后得到的是这个终结符串

这是从开始变量在这个文法里面

把它这样推出来的

这是自上而下推出来的

给了这样的文法

那我们的推导实际上始终是（06：02）产生式的

假如有这么一个串 αAβ

A是这个文法当中的一个变量

那如果A有一个A产生γ

那我们怎么样利用这个串

得到后面的串呢

实际上我们就是把这个A就替换成γ

这个推导跟产生式不同的就是

这是这样一个箭头 这是双的

也就是在这个串当中

它运用了这个产生式

把这个α会看作A的它的上文

把β看作A的下文

那整个这个串从它变到它

实际上是用了这个产生式

而跟它的上文和下文是没有关系的

所以我们这个文法是上下文无关文法

如果在这个文法里面推导

我们对这个文法记忆很清楚

我们也可以在这个推导里面

把这个G 就把它省略掉

另外在这个推导里面

用到一个叫传递闭包

我们假如在整个推导过程当中

我们只关心结果

不大关心中间的推导步数

这跟我们之前讲的那个状态转移

实际上有状态转移闭包是很类似的

我们定义是这样的

在这个文法里面

我们定义这个推导闭包

我们用G这个箭头上面给*来表示

我们是用归纳定义的

首先对这里面任何一个串α

α它不需要做任何变动

自己到自己也是一个*来推导它

那另外假如有α、β、γ是这么一个串

α若干步在这个文法里面可以推导出β

而β在这个文法里面

它一步可以推导出γ

这样这就是一个关联假设

那我们就可以推出来α在这个文法里面

它有若干步也能够推出γ

你看我们只关心它最后的结果

不关心它的步骤

那通过这个归纳定义

我们得出任意的

这个传递闭包的它的推导

这个定义在我们后面的

语言里面的定义非常重要

在前面我们讲的推导的时候

我们举的几个例子大家就会看出

从开始变量能够推出终结符串

我们在文法里面用产生式进行推导

这个推导可能有的同学这里也问

你在这个文法里面

这个串里面 有这么多这个变量

你该用哪个变量

用哪个产生式进行推导呢

这里在一般情况下

我们觉得它是没有规律可行的话

你推导也是杂乱无章的

所以下面我们讲一个叫最左推导

最左推导是这样的

就在你的推导过程当中

你如果是总是在这个串里面

最左边的一个变量

引用文法里面进行推导

这样我们用一个记号叫IM

也是left most这个记号

如果是传递闭包里面的

它的最左推导的传递闭包

就用IM上面摆个*

下面我们看个例子

这还是我们前面的上下文法

还是这样的串

我们对这样的文法最左推导

要推导出这个串

那我们在开始例子里面

我们也讲过推导

那里面推导的是开始变量

后面的推导是任意的

它的变量进行推导的

而我们现在是每次

都是在这个串当中最左边的一个变量

下面看开始变量E

我用第一个产生式

这是因为是最左边的 它只有一个符号

那就推导出EOE

EOE这个串里面最左边的一个变量是E

E我用第二个产生式就推出（E）左括号

就得到这个串

这个串里面

现在最左边一个变量是E

我再用第一个产生式

E产生EOE得到这样

这里最左边变量是这个E

我再用第三个产生式E产生V

得出这个关系式

那下面在这个串里面最左边是一个O

再用第五个产生式O产生+

那接下来最左边那个变量是E

E用第四个产生式E产生d 得到这样的

那接下来最左边一个变量是O

再用第六个产生式O产生×

到了这个串

最左边每个变量是E

再用第四个产生式E产生d

最后推出了（v+d）×d

整个推导过程

都是每一次都是

最左边的一个变量进行推导的

这是这一组推导

那下面我们再看另外一个推导

叫最右推导

最右推导跟刚才的方法它是很类似的

我们在推导过程当中

每一步总是在这个串当中

最右边一个变量进行推导

就用rm right most这个来表示的

所有这个最右推导里面的传递闭包

我们就用rm上面给个*表示的

我们下面也看这个例子

这个例子也是上下文法

对这个串我们采用最右推导

整个的推导

跟刚才的这种推导是很类似的

每次推导都是以右边的一个变量

右边的一个变量 右边的一个变量

对它进行推导的

最后得到这个终结符的串

这是最右推倒

在我们上下文无关文法里面

这个串里面

它可能包含有变量和终结符

我们把这样的串

给它命一个名字叫做句型

也就是说句型是一个字符串

它包含有终结符和包含有非终结符

如果从开始变量 用最左推导出的一个句型α

我们叫做左句型

那如果从开始变量用最右推导

推导出来的句型α

我们把α叫做一个右句型

如果这个串里面

全部都是终结符构成的

我们把这样的串叫做一个句子

实际上文法的语言

它都是由这个句子构成的

这节里面我们介绍了

上下文无关文法的推导

包括递归推理

也是归右或推导

我们还介绍了最左推导和最右推导

这些推导是为我们下面

怎么去用文法推导一些句子

或者推导我们的语言来做准备的

好 这节内容介绍完毕

谢谢大家