3.1.4 Ambiguity慕课视频播放-Compilers Techniques-MOOC慕课视频教程-柠檬大学

各位同学大家好

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

那么接下来

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

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

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

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

是说对于符合文法规则的

同一个句子

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

我们观察一下

之前我们碰到的问题

如果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

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

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

产生的原因是什么呢？

文法产生二义性的原因

我们观察到是因为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

这样的话

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

学习起来也感觉很困难

这就是为什么

保留了二义性

而让大家写程序更容易

这一讲就介绍到这

谢谢大家

Compilers Techniques课程列表：

1 Overview of Compilers Techniques

-1.1 Overview of Compilers Techniques

--Chapter 1 Overview of Compilers Techniques

--Overview of Compilers Techniques

2 Lexical Analysis

-2.1 Lexical Tokens, Strings and Language

--2.1 Lexical Tokens, Strings and Language

-2.2 Regular form

--2.2 Regular form

-2.3 Finite automata

--2.3 Finite automata

-2.4 DFA construction, Subset construction, Simpleset DFA

--2.4 DFA construction, Subset construction, Simpleset DFA

-2.5 Lex

--2.5 Lex

3 Syntax Analysis

-3.1 Context-free Grammars

--3.1.1 The Role of the Parser

--3.1.2 The Formal Definition of a Context-free Grammar

--3.1.3 Derivations

--3.1.4 Ambiguity

-3.2 Writing a Grammar

--3.2.1 Elimination of Left Recursion

--3.2.2 Left Factoring

--3.2 Top-Down Parsing

-3.3 Languages and Grammars

--3.3 Languages and Grammars

--3.3 Language and Grammars

-3.4 Top-Down Parsing

--3.4.1 First and Follow

--3.4.2 LL(1) Grammers

--3.4.3 Recursive Descent Analysis

--3.4.4 Nonrecursive Descent Analysis

-3.5 Bottom-up Parsing

--3.5.1 Reductions and Handle

--3.5.2 Shift- Reduce Parsing

--Bottom-up Parsing

-3.6 LR Parsing

--3.6.1 LR Parsing

--3.6.2 Viable Prefixes

--3.6.3 Simple LR

--3.6.4 LR(1)

--3.6.5 LALR

--3.6.6 Characteristics of LR Parsing

--3.6.7 Non Ambiguous and Not LR Context-Free Grammars

4 Syntax-Directed Translation

-4.1 Syntax-Directed Definitions

--4.1.1 Attribute Grammars

--4.1.2 Attribute Dependency Graphs and Ordering the Evaluation of Attributes

--Syntax-Directed Definitions

-4.2 Bottom-Up Calculation of S Attribute

--4.2.1 Bottom-Up Calculation of S-Attributed

--4.2.2 Stack Code

-4.3 L-Attributed Definitions

--4.3.1 L-Attributed Definitions

--4.3.2 Translation Schemes

--4.3.3 Design of Predictive Translator

--L-Attributed Definitions

-4.4 Bottom-Up Parsing of L-Attributed Translation

--4.4.1 Bottom-Up Parsing of L-Attributed Translation

--4.4.2 Simulate the Parsing of Inherited Properties

--Bottom-Up Parsing of L-Attributed Translation

5 Organization and Management of Run-Time Storage Space

-5.1 Overview

--5.1 Overview

--Overview

-5.2 Global Stack Storage

--5.2 Global Stack Storage

-5.3 Calling Sequences

--5.3 Calling Sequences

-5.4 Non Local Names

--5.4 Non Local Names and dynamic scope

--Non Local Name

6 Intermediate Code Generation

-6.1 Overview of Intermediate Code Generation

--6.1 Overview of Intermediate Code Generation

-6.2 Declaration Statements

--6.2 Declaration Statements

7 Code Generation

-7.1 Issues in the Design of Code Generator

--7.1 Issues in the Design of Code Generator

-7.2 Target Machine

--7.2 Target Machine

--Target Machine

-7.3 Basic Blocks and Flow Graphs

--7.3 Basic Blocks and Flow Graphs

-7.4 A Simple Code Generator

--7.4 A Simple Code Generator

8 Design and Implementation of a Simple Compiler

-8.1 Demonstration of Compiler Framework based on Python

--8.1 Demonstration of Compiler Framework based on Python

-8.2 Basic

--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 Ambiguity在线视频

3.1.4 Ambiguity课程教案、知识点、字幕