当前课程知识点：Compilers Techniques >  3 Syntax Analysis >  3.5 Bottom-up Parsing >  3.5.2 Shift- Reduce Parsing

返回《Compilers Techniques》慕课在线视频课程列表

3.5.2 Shift- Reduce Parsing在线视频

下一节:3.6.1 LR Parsing

返回《Compilers Techniques》慕课在线视频列表

3.5.2 Shift- Reduce Parsing课程教案、知识点、字幕

各位同学大家好

这节课

我们来学习语法分析中自下而上的分析

在语法分析中

自下而上的分析我们使用移进归约分析器

我们来看一下这个图

移进归约分析程序

在整个分析器的中间位置

移进归约分析程序

依靠分析表来决定下一步的动作

分析表用来驱动整个移进归约分析程序的动作

来决定下一步的动作是移进还是归约

分析程序的最左边是移进归约分析栈

在栈底，我们看到放置的是标志符$符号

输入在最上部

输入的指针

每一次指向当前的第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归约为参数

也可以将它归为一个表达式

到底参照哪个产生式来进行归约

其实仍然是一个不容易作出选择的

那么出现这个问题的原因

是因为我们文法本身

它包含着一个归约归约冲突

这一小节就到这

谢谢大家

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.1 Lexical Tokens, Strings and Language

-2.2  Regular form

--2.2 Regular form

--2.2 Regular form

-2.3  Finite automata

--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.5.2 Shift- Reduce Parsing笔记与讨论

也许你还感兴趣的课程:


  1. Compilers Techniques(Round 2)

  2. 细胞生物学和医学遗传学(2021秋)

  3. 商行天下——技术与运营(2021秋)

  4. 中国美术史新解(2021秋)

  5. 生态学实践——森林群落结构与土壤生境篇(2021秋)

  6. 护理教育理论与实践(2021秋)

  7. 2021年中国互联网大会(自主学习)

  8. Практика международной торговли（国际贸易实务）(Round 2)

  9. 面向对象程序设计(2021秋)

  10. Environmentology(Round 2)

  11. 制剂工艺与设计(2021秋)

  12. 速成汉语语法课堂(2021秋)

  13. SQL Server轻松学(2021秋)

  14. 网球第一课(2021秋)

  15. 实验室安全教育(2021秋)

  16. 健康与健康能力(2021秋)

  17. 建筑工程材料与检测(2021秋)

  18. 西医内科学(2021暑假班)

  19. 《中国现代胡琴艺术教学实用教程》(2021秋)

  20. 小儿科，大学问—中医儿科学(2021秋)
© 柠檬大学-慕课导航 课程版权归原始院校所有，
本网站仅通过互联网进行慕课课程索引，不提供在线课程学习和视频，请同学们点击报名到课程提供网站进行学习。