当前课程知识点:Compilers Techniques > 3 Syntax Analysis > 3.1 Context-free Grammars > 3.1.4 Ambiguity
返回《Compilers Techniques》慕课在线视频课程列表
返回《Compilers Techniques》慕课在线视频列表
各位同学大家好
欢迎大家来学习语法分析这一课
那么接下来
我们来说一下二义性的问题
二义性是我们在文法设计当中常见的
也是我们最需要避免的一个问题
文法的二义性指的是什么呢
是说对于符合文法规则的
同一个句子
可能存在着两种可能的分析树
我们观察一下
之前我们碰到的问题
如果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 Overview of Compilers Techniques
--Chapter 1 Overview of Compilers Techniques
--Overview of Compilers Techniques
-2.1 Lexical Tokens, Strings and Language
--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.1 Context-free Grammars
--3.1.1 The Role of the Parser
--3.1.2 The Formal Definition of a Context-free Grammar
-3.2 Writing a Grammar
--3.2.1 Elimination of Left Recursion
--3.2 Top-Down Parsing
-3.3 Languages and Grammars
--3.3 Language and Grammars
-3.4 Top-Down Parsing
--3.4.3 Recursive Descent Analysis
--3.4.4 Nonrecursive Descent Analysis
-3.5 Bottom-up Parsing
--Bottom-up Parsing
-3.6 LR Parsing
--3.6.6 Characteristics of LR Parsing
--3.6.7 Non Ambiguous and Not LR Context-Free Grammars
-4.1 Syntax-Directed Definitions
--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.3 L-Attributed Definitions
--4.3.1 L-Attributed Definitions
--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.1 Overview
--Overview
-5.2 Global Stack Storage
-5.3 Calling Sequences
-5.4 Non Local Names
--5.4 Non Local Names and dynamic scope
--Non Local Name
-6.1 Overview of Intermediate Code Generation
--6.1 Overview of Intermediate Code Generation
-6.2 Declaration Statements
-7.1 Issues in the Design of Code Generator
--7.1 Issues in the Design of Code Generator
-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
-8.1 Demonstration of Compiler Framework based on Python
--8.1 Demonstration of Compiler Framework based on Python
-8.2 Basic
--8.2.4 SA
-8.3 SimpleJava