当前课程知识点:Compilers Techniques > 3 Syntax Analysis > 3.5 Bottom-up Parsing > 3.5.1 Reductions and Handle
返回《Compilers Techniques》慕课在线视频课程列表
返回《Compilers Techniques》慕课在线视频列表
各位同学大家好
我们继续来学习语法分析部分
我们来看一下
之前我们已经学习了自上而下的分析
从这节课开始
我们来学习自下而上的分析
在自上而下的分析中
我们一直使用的是最左推导
那么在自下而上的分析中
我们是不是应该用最右推导呢?
我们先来看一个例子
在自上而下分析中
我们用最左推导来构造语法树
根据这个文法
假设我们的输入是id×id
从产生式的开始符号E开始
我们将E推导为TE'
然后T推导为FT'
我们将F推导为id
T'推导为*FT'
然后F推导为id
T'推导为ε
E'推导为ε
这样我们就完成了自上而下的语法树的构建
接下来的问题就是
我们在进行自上而下的分析中
我们可以用最右推导吗?
我们其实可以发现
我们在进行分析输入的时候
我们是从左到右来读取我们的输入符号
却要进行最右推导
这也就是说
我们每一次希望利用最左边的字符
来决定右边的符号的动作
这样其实是非常困难的
也就是说
在自上而下的分析过程中
适用的是最左推导
没法使用最右推导
但是我们在自下而上的分析中
我们发现
我们要做的是从句子开始
将它进行归结为文法的开始符号
后面我们会看到
最右推导用于自下而上的分析
对应的实际上是最右推导的逆过程
首先我们给大家介绍一个新的概念 叫做归约
归约实际上是最右推导的逆过程
也就是我们有一个输入id+id×id
我们将它归约为产生式的开始符号E
在进行自下而上分析中
我们引入两个重要的概念
一个是归约,另一个是句柄
我们首先来学习一下'归约'这个概念
归约是自下而上分析中的一个重要动作
它对应的是最右推导的逆过程
假设我们有一个文法
S可以产生aABe
A可以产生Abc或者b
B可以产生d
我们有一个输入串abbcde
这个输入串如何把它归约为我们想要的开始符号S
我们将这个符号串写在这
我们使用最右推导的逆过程
也就是归约,来完成自下而上的分析
我们首先可以看到
a没有办法进行归约
而第1个b可以归约为A
我们将它归约为A
然后我们发现Abc可以归约为A
接下来我们将d归约为B
最后我们就可以根据aABe得到S
也就是完成了自下而上的构建
我们再来完整的看一下分析的过程
实际上
我们在进行归约动作的时候
是从左到右去读取输入
发现第1个符号a 没有办法进行归约
然后我们读取到第1个b
它是一个产生式A产生b的右半部
所以这个小B可以归为A
接下来我们的符号串就变成了aAbcd
我们观察到Abc
它仍然是作为一个产生式的右部A产生Abc
所以我们将Abc归约为A
接下来我们观察到
我们的输入符号串变成了aAde
而其中的d其实是一个产生式的右部
也就是B可以产生d
d可以来进行归约
我们将d归约为B
在归约完成之后
输入的符号串就变成了aABe
那么输入的符号串aABe
仍然是作为一个产生式的右部
S可以产生aABe
所以我们将符号串归约为S
我们整个的输入串就完成了自下而上的分析
构造出了语法树 得到了开始符号S
接下来我们
来学习句柄这个概念
我们看到在归约的过程中
每一次和一个产生式右部符号
如果匹配上了
我们就可以将这个符号串变成产生式的左部
也就是把它归约过去
而实际上和一个产生式右部匹配的一个子串
我们给它一个名字叫做句柄
也就是在刚才的分析过程中
b就是句柄
因为我们将b归约为A
而在这一步Abc,我们将它归为A
所以在这一步,Abc就是句柄
而在下一步
由于d归约为B,所以d是句柄
那么在最后一步aABe归约成S
所以它是句柄
总结一下
句柄是句型的一个子串
我们把句柄归为非终结符的这一步
实际上代表的是
最右推导的逆过程
也就是这个归约的步骤
最终可以得到产生式的开始符号S
接下来我们学习一下句柄的性质
我们可以看到
对于我们之前所标注出来的
几个句柄的右侧
它只含有终结符
这是句柄本身的特点所决定的
因为句柄是用来进行归约
所以它在(产生式的)右边,肯定只含有终结符
如果文法是二义性的
那么句柄可能不唯一
我们可以来看一个例子
比如说有一个文法
E可以产生E+E或者E×E或者(E)或者id
我们有一个输入id1×id2+id3
我们在进行推导的过程中
假设使用最右推导
我们会观察到
这两种情况
第1种情况
我们首先将E推导为E×E
然后按照最右推导的原则
我们将右边的E推导为E+E
然后再将最右侧的E推导为id3
我们观察到在这一步
E推导为id3,所以id3是句柄
而在右边的情况中
E 我们首先将它展开为E+E
我们将最右侧的E推导为id3
然后下一步
再将左边的E推导为E×E
所以在这一步当中
仍然是E×E+id3这个串
而此时它的句柄变为E×E
这个问题的原因是
由于这个文法本身是有二义性的
所以在进行推导的过程中
句柄可能不唯一
接下来我们看一下
句柄的非形式化定义
对一个句型的句柄
是指我们在一个和产生式的右部相匹配的一个字符串
我们观察一下
对于这个文法来说
在最右推导的过程中
可能和产生式的右部相匹配的串有哪些呢?
其实也就是产生式的右部的串有哪些?
也就包括aABe、Abc、b和d
也就是所有产生式的右部都是可以和它相匹配的串
接下来我们来学习
句柄的精确定义
假设有一个右句型γ
它的句柄是一个产生式的右部β
而β在用A进行替换γ中的句柄β之后
我们得到的是最右推导的前一个句型
首先我们来明确一下右句型的含义
右句型是指我们在进行最右推导过程中
所有可能出现的句型
我们可以假设
产生式的开始符号是S
从S开始推导,我们得到了一个右句型γ
然后我们把γ表示为αβω
那么其中γ可以通过产生式A产生β来归约为右句型αAω
也就是说
我们从S进行推导得到γ
我们将γ表示为αAω
然后我们将其中的A推导为β
这个情况下β就是句柄
我们仍然来观察之前的文法
输入的符号是abbcde
我们在进行第1步的归约之后
得到了一个串aAbcde
那么这个b是不是句柄呢?
如果b是句柄,
一定意味着存在这样的一步:aAAcde是一个右句型
而aAAcde我们没有办法继续进行最右推导的逆过程
也就是没有办法继续进行归约,最终得到产生式的开始符号S
所以aAAcde并不是文法的右句型
所以这个b它不是句柄
我们再来看一下句柄形式化的定义
S我们将它推导为αXω
X推导为β
在这种情况下β是句柄
β是αXω的句柄
在移进归约的分析过程中
我们每一次移进或者归约
其实是取决于是否出现了句柄
也就是句柄始终出现在栈底
自下而上的分析中
基于这个句柄是不是能识别出来
如果一个句柄出现,我们就进行归约
如果句柄没有出现,我们就继续移进
我们来看一个例子
假设有一个文法
S可以产生aAcBe
A可以产生b
A可以产生Ab
B可以产生d
我们对这个输入abbcde,使用移进归约分析器来分析它
我们画了一个栈
首先这是输入
我们将a移进栈,输入这边就去掉了a
然后我们来判断是不是出现了句柄
如果出现了句柄,要进行归约
而此时没有出现句柄,所以继续进行移进
我们将输入的b移进栈
移进栈之后
仍然需要去判断是否出现了句柄
第2条产生式A可以产生b
所以我们认为这个b是句柄
我们将b归约为A
归约完成之后
仍然需要去判断栈里是不是出现了句柄
此时我们发现栈里不含有句柄
那么我们就继续进行移进的动作
我们将b移到栈里
这时候仍然需要去判断是不是出现了句柄
我们发现
bA它是一个产生式的右部
也就是第3个产生式A可以产生Ab
如果出现了句柄,我们就进行归约
将它归约为A
然后接下来判断栈里是不是出现了句柄
如果没有出现句柄,继续将输入的c移进栈中
在将C移入栈中之后
继续去判定是否出现了句柄
没有出现句柄
我们就继续将输入的d移入到栈中
继续判断是不是出现了句柄
没有出现句柄,我们就继续移进
如果出现了句柄,我们就来进行归约
d可以根据第4个产生式来进行归约成B
然后我们判断栈里边是不是出现了句柄
如果没有出现句柄
我们继续将输入的e移入到栈里边
这个时候栈里边是第1个产生式的右部
也就是出现了一个句柄
我们将它归为产生式的开始符号S
这个移进归约过程就结束了
这一小节就介绍到这
谢谢大家
-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