Video在线视频

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

现在介绍上下无关文法应用

与文法二义性的第四部分

二义性的消除方法

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

有的文法它有二义性

而二义性它带来的这个软件

可能是很大的错误

我们不希望在文法里面

有这样的二义性出现

那怎么样去消除二义性呢

对于一般的上下无关文法来说

你找不到通用的消除文法的二义性

但对一些特定的文法

我们还是可以找到一些

消除二义性的方法

看看前面介绍的那个算术文法

它这个文法是具有二义性的

发现了v+v×d

它有两个不同的文法分析树

产生这个两个不同的文法分析树的原因

在数学里面加和乘 它是两个运算符号

但是它们的运算的

它们的级别或者优先 它们是不一样的

我们从小学就知道 先乘除后加减

在这个串里面

之所以产生了二义性

是因为这个加或乘它们没有优先性

所以就造成了有两个不同的语法分析树

那为了克服这一点

我们就采用了计算的优先性

我们先乘后加

那对这个文法我们就进行改进了

原来的加或乘都用O表示

那现在加用A表示 乘用N表示

那我们乘是优先的

也就是在这个里面它的产生式

只要一进入到乘

这个乘它就一直都把它做完

就是保证了先乘后加

对这样的文法我们再看看这个字符串

那它只有唯一的一个语法分析树

那这样的文法

是不是再没有二义呢 对这个文法

我们再看这个字符串 v+v+d

这个文法生成这个字符串

我们发现了也有两个不同的语法分析树

或者有两个不同的最左推导

只要找到一个字符串 就是这里

我们就说这个文法是具有二义的

你虽然这个文法克服了

刚才的那个加和乘的二义性

但对这个字符串它还是具有二义的

也就是说这个文法是二义的

那下面我们分析产生这个二义的原因

因为我们这个v+v+d

对加法来说它可以是前面相加

也可以先后面相加

这样得到的它的结果是

语法分析树是不一样的

为了改进这一点

我们在小学里面

我们学算术的时候 我们知道

加法运算或者乘法运算里面

它应该用结合律

所以我们就采用左结合的方法

来消除它这个二义性

我们对加法来说

我采用左结合律

那同样对乘法来说

这里也成了这样类似的问题

我们两个同样的一起来解决

那我们修正这个文法

就得到下面这个文法

EAT和TMF

这个文法描述了

它是用了加或乘都是左结合律

在这种文法下面

这样的字符串

它只有唯一的一个语法分析树

我们可以检验它就是再没有二义了

下面我们介绍另外一个例子

叫悬挂的else二义性

有一个叫控制判断程序

它是有if、else来描述

就是如果 另外

你要用else之前必须要用if

如果有if 后面可以不用else

那怎么样去描述这个文法

下面我们用这个文法来表示

else产生空串

else产生if

if我们用i表示 is

else产生is

e e表示s 再s

这个文法就描述了刚才的判断语句

首先有if 再有else

或者是只有if 没有else

那这样给的这个文法

它是不是无二义的

我们下面看这个字符串

if，if，else

从这个文法生成这个字符串

实际上它有两种生成方法

首先我用s产生ises 得到这样的

然后再用s产生is

最后你用s产生空串 s产生空串

这里面得到的产物就是iie

得到这个字符串

那同样通过这个文法

我们看另外一种产生方式

首先你用这个产生式

s产生is

然后采用s产生ises

s产生ises

再之后你用s产生空串 s产生空串

这个语法分析树 它的产物也是iie

这两个语法分析树它们是不同的

但是它们产生的产物或者句子都是二义的

这说明这个文法它是具有二义的

那我们要消除这个二义性

就采用最临近的嵌套方法

来消除这个二义性

就把这个文法改成一种imes

然后写成m产生它

这个文法再产生这个判断语句

它满足了条件

而且iie它只有唯一的一个语法分析树

这个语法分析树就是这样的

但有的文法里面它是没有二义的

有的文法它是有二义的

如果是这个语言它对应的文法

有的是有二义的 有的是没有二义的

我们肯定是选取那个没二义的

如果是有二义的

利用我们的一些知识 利用我们的经验

去消除二义性

但是也有这样的语言

只要产生这个语言

它的文法是一定有二义的

这就是固有二义

这个上下无关文法语言

只要生成这个语言的文法

它一定是有二义的

什么样的语言是固有二义的

下面我们看这个例子

L等于a的n次方

b的n次方 c的m次方

或者是a的n次方

b的m次方 c的m次方

生成这个语言的文法采用这个文法

生成这个语言的文法

我们可以采用这个上下无关文法

而生成这个语言L

也就是这两个语言的并

我们只需要增加

这样的一个产生式就OK了

这里就是生成

这个语言的一个上下无关文法

那我们考虑这么一个串

a的n次方 b的n次方 c的n次方

像这个串里面

它可以用第一个文法生成

也可以用第二个文法生成

它们这两个语法分析树 大家看

它们是完全不一样的

对于刚才这个语言

有的同学说你是用的那个文法

我可以去找其他的一个

没有两个语法分析树 最后生成这样的

我们说你是找不出来的

因为你的这个语法分析树

它要么属于前面的一个文法

要么属于后面的一个文法

它这两个文法里面

它的结构是不一样的

所以它要生成这个a的n次方

b的n次方 c的n次方

它必然有两个不同的语法分析树

这样的语言是一个固有二义的语言

这个语言你要改进它 是改进不了的

这节里面我们介绍了

对一些二义的上下无关文法

我们凭自己的经验可以消除它的二义性

当然我们说也有一些语言

连二义性都消除不了的

你像这个固有二义的语言

好 这节内容介绍完毕

谢谢大家