当前课程知识点:编译技术 >  第三章 语法分析 >  3.1 上下文无关文法 >  3.1.4 二义性

返回《编译技术》慕课在线视频课程列表

3.1.4 二义性在线视频

下一节:3.2.1 消除左递归

返回《编译技术》慕课在线视频列表

3.1.4 二义性课程教案、知识点、字幕

各位同学大家好

欢迎大家来学习语法分析这一课

那么接下来

我们来说一下二义性的问题

二义性是我们在文法设计当中

常见的

也是我们最需要避免的一个问题

文法的二义性指的是什么呢

是说对于符合文法规则的

同一个句子

可能存在着两种可能的分析树

我们观察一下

之前我们碰到的问题

如果E

可以推导出id*id+id

其实它就对应着两棵分析树

大家观察左边

我们先来把 E 推导成 E* E

然后右边的E

再推导成E+E

最终我们会得到id*id+id

然后在右侧的这颗分析树

我们先把 E 推导成 E+E

然后左侧E在推导成 E*E

最终每一个 E 推导为id

那么我们看

这个就出现了二义性

针对id*id+id

这样的同一个串

有两棵不一样的语法树

那么就是二义性

然后我们再想一想

哪一棵树是符合我们的要求

符合我们最基本的认知呢?

大家想按照左边的这棵树的方式

3*4+5

我们要先计算4+5

然后再来计算3*9

大家觉得是符合我们

常用的四则运算的方法吗?

好像不是的

所以我们觉得这是不对的

那么针对右边来说

我们要先计算乘法

所以3*4+5

最终我们会得到正确的结果

17

我们再来看一下表达式二义性

产生的原因是什么呢?

文法产生二义性的原因

我们观察到是因为E+E和E*E

它们两个其实是有优先级别的

大家知道

在我们的四则运算中

乘法的优先级别高于加法

可是在文法当中

优先级没有体现出来

它们有不同的优先级

但是文法中没有体现出来

没体现出来

就导致它出现了二义性

那么如果我们想消除二义性

怎么办

我们需要用一种层次的观点

去看待表达式

也就是在这里边

其实它是隐含着优先级

像我们底下画这个

如果你想先计算id+id

那么你需要把它用括号括起来

它才会先计算id+id

那么我们看一下

如果采取适当的表达式文法

我们采取层次的观点

去看待它

我们发现

乘法的优先级别

是高于加法的

所以你需要把E→E+E

从不同的E扩展得到的树

需要用括号括起来

所以怎么办

可以改写本法

我们引入了新的符号

T和F

E→E+T | T

而这个T →T*F | F

F→id | (E)

这样的话

我们就把优先级别

体现在文法当中了

一定是先计算完乘法

再去计算加法

就消除了文法的二义性

但是我们又会觉得

如果消除了文法的二义性的话

文法看起来就没有那么的直观了

这只是加法和乘法

如果我们再加上减法和除法的话

它这个文法写起来

就比较的复杂、不直观

有二义性的文法写起来

其实是非常直观的

贴近我们的认识

我们在这里

根据算符

不同的优先级别

引入了新的非终结符T和F

从而消除了文法的二义性

我们看一下

消除文法二义性之后

它的分析树 id*id*id

这个分析树

会变成 E→T

T→T*F

然后 T →T*F

T再推导出F

然后每个F推导为id

而在id+id*id的分析树

我们就看到E

它会先推导成 E+T

然后 E 推导成 T

再推导成F

再推导成id

而 T 会推导成 T*F

T 再推导成 F

F 推导成 id

最后的F推导成 id

那么这样的话

乘法的优先级别就高于加法

从而消除了文法的二义性

我们再来看一下

if else这个语句

它写成了上下文无关文法之后是什么样的

stmt → if expr then stmt

| if expr then stmt else stmt

| other

也就是在这里边

你可以是 if then 的形式

也可以是 if then else 的形式

所以我们把它叫做悬空else文法

那么大家想

这个文法有没有二义性呢

如果有二义性

我们该如何去消除这种二义性?

那么很显然

这是一个有二义性的文法

因为大家都知道

我们在写程序的时候

老师介绍过

if then else 这种文法

我们是利用就近原则

去消除二义性

比如说我们有一个语句

if expr then if expr then stmt else stmt

请问这里边 else 是跟第一个

if 来配对

还是跟第二个 if 来配对呢

如果你学过

就近原则

你知道

它应该跟第二个来配对

但是从文法上来说

它跟第一个来配对

或者跟第二个来配对

其实都是可以的

我们可以把它的最左推导写出来

大家看这里边有两个

第一个是stmt

先可以推导成 if then 的形式

然后我们按照就近原则

这是符合我们一般的认知的

后边的stmt

把它推导成 if then else 的形式

那么这个else

就是和第二个if来配对

但是你再看第二个推导

stmt

如果一开始就推导成

if then else 的形式

然后其中的 stmt

再推导成 if then 的形式

那么这个时候

else 就是在跟第一个 if 来配对

所以上边的句型

其实是有二义性的

也就是 if else 语句

是天然地存在二义性的

这样的一个文法

我们常用的解决方法

就是告诉你是有就近原则的

我们在解析的时候

去构建语法树的时候

也按照就近原则

去解决这样的一个问题

那么大家会问说

老师为什么不用

没有二义性的文法呢

这是因为没有二义性的文法

写起来就很难理解

比如说

我们把它改写成

没有二义性的文法

大家看一下

stmt → matched_stmt

| unmatched_stmt

matched_stmt的语句就是if then else

而且 if 当中 then 的后边

跟的是一个matched_stmt的语句

而 else 后边跟着的

也是一个matched_stmt的语句

或者 other

unmatched_stmt 的语句当中

我们写成 if expr then stmt

| if expr then matched_stmt else unmatched_stmt

这样的话

我们就看起来感觉非常的复杂

学习起来也感觉很困难

这就是为什么

保留了二义性

而让大家写程序更容易

这一讲就介绍到这

谢谢大家

编译技术课程列表:

第一章 绪论

-1.1 编译技术绪论

--1.1 编译技术绪论

--编译原理介绍--作业

第二章 词法分析

-2.1  词法记号 串和语言

--2.1 词法记号 串和语言

--2.1  词法记号 串和语言--作业

-2.2  正规式 状态转换图

--2.2 正规式 状态转换图

--2.2  正规式 状态转换图--作业

-2.3  有限自动机

--2.3 有限自动机

--2.3  有限自动机--作业

-2.4  DFA构建 子集构造法 DAF化简

--2.4 DFA构建

-2.5 Lex

--2.5 词法分析工具Lex

第三章 语法分析

-3.1 上下文无关文法

--3.1.1 语法分析概述

--3.1.2 上下文无关文法定义

--3.1.3 推导

--3.1.4 二义性

-3.2 自上而分析中的文法

--3.2.1 消除左递归

--3.2.2 提取左因子

--3.2 上下文无关文法--作业

--3.2.3 语言和文法

--3.2.3 语言和文法--作业

-3.3 自上而下分析

--3.3.1 first follow

--3.3.2 LL(1)文法

--3.3.3 递归下降分析

--3.3.4 非递归下降分析的预测分析器

-3.4 自下而上分析

--3.4.1 归约句柄

--3.4.2 移进归约分析过程

--3.4 自下而上分析--作业

-3.5 LR分析器

--3.5.1 LR分析器

--3.5.2 活前缀

--3.5.3 SLR分析方法

--3.5.4 规范的LR分析方法

--3.5.5 LALR分析方法

--3.5.6 LR分析方法特点

--3.5.7 非二义且非LR的上下文无关文法

第四章 语法指导的翻译

-4.1 语法制导的定义

--4.1.1 属性文法

--4.1.2 属性依赖图和计算次序

--4.1 语法制导的定义--作业

-4.2 S属性的自下而上计算

--4.2.1 S属性的自下而上计算

--4.2.2 栈代码

-4.3 L属性定义

--4.3.1 L属性定义

--4.3.2 翻译方案

--4.3.3 预测翻译器的设计

--4.3 L属性定义--作业

-4.4 L属性的自下而上计算

--4.4.1 L属性的自下而上计算

--4.4.2 模拟继承属性的计算

--4.4 L属性的自下而上计算--作业

第五章 运行时存储空间的组织与管理

-5.1  概述

--5.1 概述

--概述-作业

-5.2  全局栈式存储分配

--5.2 全局栈式存储

-5.3  调用序列

--5.3 调用序列

-5.4 非局部名字的访问

--5.4 非局部名字

--5.4 非局部名字的访问--作业

第六章 中间代码生成

-6.1 中间代码生成

--6.1 中间代码生成概述

-6.2 作用域信息的保存

--6.2 声明语句-作用域信息的保存

第七章 代码生成

-7.1 代码生成器设计中的问题

--7.1 代码生成器的设计中的问题

-7.2 目标机器

--7.2 目标机器

--7.2  目标机器--作业

-7.3 基本块和流图

--7.3 基本块和流图

-7.4 一个简单的代码生成器

--7.4 一个简单的代码生成器

第八章 基于Python的编译器框架实现

-8.1 基于Python的编译器框架演示视频和代码

--8.1 基于Python的编译器框架演示

-8.2 代码介绍

--8.2.1 Scanner

--8.2.2 Parser -1LRItem

--8.2.3 Parser-2ActionGoto

--8.2.4 SA

-8.3 SimpleJava

--8.3 SimpleJava

3.1.4 二义性笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。