当前课程知识点:Compilers Techniques > 3 Syntax Analysis > 3.5 Bottom-up Parsing > 3.5.2 Shift- Reduce Parsing
返回《Compilers Techniques》慕课在线视频课程列表
返回《Compilers Techniques》慕课在线视频列表
各位同学大家好
这节课
我们来学习语法分析中自下而上的分析
在语法分析中
自下而上的分析我们使用移进归约分析器
我们来看一下这个图
移进归约分析程序
在整个分析器的中间位置
移进归约分析程序
依靠分析表来决定下一步的动作
分析表用来驱动整个移进归约分析程序的动作
来决定下一步的动作是移进还是归约
分析程序的最左边是移进归约分析栈
在栈底,我们看到放置的是标志符$符号
输入在最上部
输入的指针
每一次指向当前的第1个输入符号
同样的,在输入的末尾
我们也放置了$符号
用来表示整个输入的结束
我们来观察一下
如何用栈来实现移进归约分析程序
也就是说,这个分析器一共具备四种动作
首先是移进
根据栈顶的符号和输入的符号
我们去查分析表
如果分析表里写着这一步应该“移进”
那么我们就进行移进的动作
也就是把输入的一个符号压入到栈中去
如果查表的时候发现表里写的是“归约”
我们就需要参照分析表所指定的那个产生式来进行归约
也就是从栈中弹出一定的符号
然后将产生式的左部压入栈中
然后我们再根据分析表
把我们需要的动作
继续往下进行
还有一个状态是成功结束的状态
也就是,我们根据栈顶元素和输入符号去查表
发现在这一步表里写的是“成功结束”
那么也就是整个的分析完成
输入的符号刚好处理完成
栈里只剩下文法的开始符号和$
此外还有一种情况是
我们在查表的时候发现表里边写的是一个空白
也就是没有任何的移进归约输出动作或者是成功的状态
那么这种情况
我们可以认为是出错了
也就是最后一个分析器的动作
报错的动作
如果碰到报错
就说明我们的输入这个串
不是当前文法所接受的串
接下来我们来看一个例子
我们用移进归约分析器来实现 id1×id2+id3
查看一下它的动作序列
来了解一下移进归约分析器的动作
我们处理的对象是由终结符组成的句子
也就是 id1×id2+id3
我们从id1开始处理
我们知道
对于移进归约分析器来说
它是从左到右去读取句子
也就是首先读取 id1,然后读取乘号
然后读取 id2
然后再读取加号
最后读取 id3 这个符号
我们把栈横过来
这样方便我们来看到
整个移进归约分析器的动作
首先我们将文法写在这个位置
然后我们看到在栈里边,栈底只有一个符号$
而我们的输入指针是指在A第一的
我们的初始状态
栈里只有一个$符号
这个时候我们需要去查表决定下一步的动作
当前表里边的动作
写的是需要移进一个符号
所以我们将id1移入到栈中
移入到栈中之后
我们仍然根据栈顶元素和下一个符号
来决定下一步的动作
目前的状态是 栈里边是我们移入的串id1
这个时候
我们去观察一下表达式的文法
来决定下一步的动作
那么下一步的动作
也就是来判断一下
有没有形成句柄
我们发现有一个产生式 E产生id
也就是说当前的id是一个句柄
如果id是一个句柄,出现在栈里边
我们可以利用E产生id这个产生式来进行归约
归约之后,栈里边的id1移出栈
我们将产生式的左部E移入栈中
栈里边是E的情况下
输入是乘号
那么E本身不是句柄
所以我们需要进行移进
也就是将乘号移入到栈中
我们把乘号移入到栈中
仍然进行上述的判断
栈顶的符号是乘号,输入是id2
我们去查表
发现这个时候没有形成句柄
“E×”如果不是句柄的话
我们仍然进行移进的动作
我们将id2移入到栈中去
id2移入栈中之后
仍然去进行判断是否形成了句柄
栈里边是我们当前已经识别出来的串
E×id2
有没有句柄出现呢?
我们发现id2其实可以是句柄
所以此时
我们如果判断id2是句柄
我们仍然利用E产生id来进行归约
也就是将id2弹出栈
然后将产生式的左部E移入到栈中
这个时候栈里边的串是E×E
输入是加号
仍然需要去判断是不是形成了句柄
栈里边是E×E的情况下
我们发现此时
它可以作为句柄出现
也就是存在着产生式E产生E×E
但是我们在这一步
由于文法本身是二义的
也可以选择进行移进
当栈顶出现句柄的时候
可以选择归约,也可移进行移进
怎么选择呢?
我们在后面会解释这个问题
接下来假设我们选择的动作是移进
我们就将输入的加号移入到栈中
在记号移入到栈中之后
我们仍然去判断
是不是形成了句柄
我们发现这个时候没有句柄出现
所以继续进行移进
我们将最后一个符号id3移入到栈里
然后我们仍然根据栈顶元素和输入
来决定下一步的动作
继续去判断一下
是不是有句柄出现
我们发现id3可以作为句柄
所以我们利用产生式E产生id来进行归约
所以将id3移出栈中
将E移入到栈中
然后继续判断整个的栈里边
有没有形成句柄
我们发现这个时候栈里边是E×E+E
根据产生式的文法
我们发现已经形成了句柄
所以我们利用产生式E→E+E来进行归约
也就是将E+E弹出栈
然后将E移入到栈中
然后继续去判断
整个栈里边有没有形成句柄
栈里边的串是E×E
这个时候是有句柄出现的
我们利用产生式E→E×E进行归约
也就是将E×E移出栈
将E移入到栈中
这个时候我们观察到
我们的输入已经全部处理完成
而栈里边是整个文法的开始符号E
也就是说我们当前已经成功结束
将输入的串归约为产生式的开始符号E
我们发现
使用移进归约分析的方法
即使我们知道了每一步的动作
我们其实还有两个问题需要去解决
一个是我们需要去确定右句型当中
需要归约的子串是哪些
另一个问题是
我们需要去确定
选择哪一个产生式来进行归约
我们看一下这两个问题
实际上对应的是两个冲突问题
第1个我们将它称为移进归约冲突
我们来看一个例子
假设有一个if else的文法
是我们常见的if else文法
那么根据文法
我们在进行分析的时候
假设栈里边处于当前的状态
栈中是 if expr then stmt 这样的状态
而输入已经到else
那么我们其实可以根据第1条产生式来进行归约
也可以参照第2个产生式来自来继续移进
所以到底是进行归约还是进行移进呢?
这其实是一个不容易作出选择的
也就是说
因为当前存在着移进归约冲突
导致这种状态的出现
我们将这种情况称之为移进归约分析的冲突
第2类的冲突
我们将它称为归约归约冲突
我们观察一下文法
对于第3行产生式来说
参数它可以产生id
而第四行的产生式当中expr表达式
也可以产生id
这样就导致
我们在分析的时候如果栈中刚好是 id ( id 这样的状态
而输入是 , id
那么我们就需要判断栈顶的符号id
如果它作为句柄的话
我们应该参照哪一个产生式来进行归约呢?
我们可以将id归约为参数
也可以将它归为一个表达式
到底参照哪个产生式来进行归约
其实仍然是一个不容易作出选择的
那么出现这个问题的原因
是因为我们文法本身
它包含着一个归约归约冲突
这一小节就到这
谢谢大家
-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