当前课程知识点:编译原理 >  第5章 自底向上的语法分析 >  5.3 活前缀和LR(0)项目 >  活前缀和LR(0)项目

返回《编译原理》慕课在线视频课程列表

活前缀和LR(0)项目在线视频

下一节:活前缀和LR(0)项目

返回《编译原理》慕课在线视频列表

活前缀和LR(0)项目课程教案、知识点、字幕

大家好

在上一节我们对LR分析器工作过程的解读当中

我们发现LR分析过程的每次规约的

总是规约当前句型的句柄

那么因此它是规范归约

对于分析的每一步

栈内符号串与输入串的剩余部分

可以拼接出一个规范的句型

那么如果已经被扫描的输入串

没有语法错误的话

那么栈内的符号串应该是

某一个规范句型它的活前缀

也就是说不含句柄之右的任何符号

这里边有一个新的概念就是活前缀

那么什么是活前缀呢

我们先来看一个文法

对于输入串abbcde

它的最右推导序列是这样的

根据1号产生式S=>aAcBe

根据4号产生式接着可以

把最右边的B用d替换掉

那么推导出aAcde

下面呢就是将最右边的非终结符A

按照3号产生式用Ab替换掉

那么推导出aAbcde

最后呢A按照

2号产生式被b替换掉

得到的是和输入串一样的字符串

abbcde

规约的过程呢

正好是刚才最右推导它的逆过程

大家来看

首先是按照2号产生式

将最左边的b规约成A

接下来将Ab

按照3号产生式规约为A

然后呢依照4号产生式

将d规约为B

最后呢按照1号产生式

将aAcBe规约为文法的开始符号S

我们发现在这个例子当中

每次归约前那么对应的句型

它的前面的部分是什么呢

分别是ab

aAb

aAcd

aAcBe

其实它们就是可规约前缀

我们仔细观察这些前缀当中的红色部分

大家发现是不是句柄呢

而且都出现在

这些前缀的最右边

如果某个前缀已经含有句柄

但是不含有句柄之后的任何符号

我们可以称之为可归约前缀

之所以称它为可规约前缀

是因为一旦句型当中的句柄

在符号栈的栈顶形成了

那么将会立即被归约的缘故

实际上

它们恰好是符号栈栈顶形成句柄的时候

符号栈里的内容

而句柄呢就在栈顶

在刚才的例子当中我们来看一看

那些可规约前缀的前缀都有什么

这里呢有一个比较有趣的现象

大家发现了吗

就是前缀a

aA还有aAc

同时是多个规范句型它的前缀

我们可以把形成可归前缀之前

和形成可归前缀时

所有的规范句型它的前缀

称为活前缀

活前缀呢就是可归前缀的任意首部

特指那些在分析过程当中

对于在栈顶形成句柄之前

和恰好形成句柄时

每一步中符号栈当中

那些符号组成的符号串

在前面对输入串

abbcde归约分析过程当中

在归约的过程当中的任何时刻

已经分析过的部分

也就是说在符号栈内的符号串

都是规范句型它的活前缀

它表明输入串

当中已经被分析过的部分

是这个文法

某个规范句型当中的一个正确部分

于是呢我们可以给出

活前缀它的形式化定义

如果S'=>αAω=>αβω

那么这个推导呢是文法的一个规范推导

那么如果符号串γ是αβ的前缀

那么γ就是文法G的一个活前缀

其实换一个比较通俗的说法来说

活前缀就是可归前缀的前缀

就是规范句型的活前缀

LR分析法它的实质就是在寻找句柄

如果能通过产生规范句型的活前缀

也就是说让栈内的符号串始终是活前缀

再通过继续扫描余留的输入串

进而去构成最长的活前缀

那么它的右端恰好包含句柄

这个时候呢在栈顶就形成了句柄

我们就可以进行立即归约了

于是我们可以把句柄识别的过程

分成若干个状态

每个状态呢都是从左向右

识别句柄当中的一个符号

若干状态就可以识别

句柄左端的一部分符号

识别了句柄的这部分符号就相当于

识别了当前规范句型它的活前缀

这与我们上一节讨论LR分析器时

它的思路不谋而合

那么LR分析程序实质上呢就是利用

FA来识别所有规范句型的活前缀

所以LR分析的核心

就是来构造识别活前缀的FA

根据活前缀它的定义

一个规范句型它的活前缀是不

包含句柄右边的符号

那么因此句柄和活前缀之间存在三种关系

其一活前缀当中呢含有句柄的全部符号

那么这就是一个最长的活前缀

可以构成可归约前缀

表明在栈顶已经形成了某个产生式

它的候选式可以进行规约

其二活前缀当中含有句柄的部分符号

表示的是某些候选式

它的子串已出现在栈顶了

但是还需要继续去读入剩下的一些符号

其三活前缀中不含有句柄的任一符号

那么这三种情况呢我们可以用

LR(0)项目来进行描述

在文法G

它的每个产生式的右部也就是候选式

它的任意一个位置添加一个小圆点

所构成的

每个产生式称为LR(0)项目

我们做一个特殊的约定

如果产生式是A→ε

那么其LR(0)项目为A→·

例如如果有产生式S→aAcBe

那么产生式的右边有5个字符

那么根据圆点的位置我们就可以得到

下面这六个项目了

下面我们根据圆点的位置

对项目呢做进一步的分类

首先是归约项目A→α·

圆点在产生式最右端

表示句柄α恰好包含在栈中

也就是说当前栈顶的部分

已经构成了所期望的

刚好含有句柄的活前缀

那么应该按照A→α进行归约

其次是接受项目S'→α·

其中S' 是文法唯一的开始符号

这是特殊的归约项目

表示的是分析栈当中恰好含有α

那么

在栈顶出现的这个α

就可以按照S'→α来进行规约了

那么整个分析是成功的

第三是移进项目

A→α·aβ

其中

圆点后面的a它是一个终结符

表示的是分析栈当中是

不完全包含句柄的活前缀的

那么为了构成恰好包含句柄的活前缀

那么需要将a移到分析栈当中去

最后是一个待约项目

A→α·Bβ

这个小圆点后面的这个B呢是非终结符

表示的是分析栈当中

是不完全包含句柄的活前缀的

那么为了构造恰好有句柄的这个活前缀

应该首先把当前输入字符串当中的

相应的内容先归约为B

通俗地来讲

一个项目呢指明了

在分析的过程当中某个时刻

我们所看到的

是产生式的多大的一部分

大家来看

在我们表达式文法当中我们来看

对于规则S→E

那么右部呢只有一个符号

因为圆点的位置不同的话

我们就可以得到两个项目

分别是S→. E S→E.

那么对于另外一个规则T→ ( E )

因为右部呢有三个符号

所以说它有下面的这四个项目

接下来根据圆点所在的位置

以及圆点后面它是终结符还是非终结符

或是空我们可以把这个项目呢

分成下面这几种

T→ (E.)

那么圆点后面的)是VT

所以这是一个移进项目

T→ (.E)

圆点后面的E是VN

所以它是一个待归约的项目

T→ (E).

圆点恰好在这个产生式的最右边

所以它是属于一个归约项目

那么S→E.

这是一个特殊的项目就是一个接受项目

但是他们都是LR(0)的项

下面我们来总结一下活前缀

与句柄与 LR(0)项目之间的关系

首先移进项目或者是待归约项目

A→.β

刻划的是没有句柄的任何符号在栈顶

这个时候呢就期望

A→β

它的右部所推出的符号串

那么活前缀是不包含句柄的任何符号

第二个是移进项目或者叫待归约项目

A→β1.β2

那么刻划的是A→β1β2

它的右部的子串β1已经在栈顶了

那么期待的是

从输入串当中可以看到β2

推导出来的这个符号

活前缀只含句柄的一部分符号

归约项目A→β.

刻划的是产生式A→β

它的右部β这个字符串已经出现在栈顶了

那么活前缀已经包含句柄的全部符号

这一节课我们分析了在栈顶出现句柄的时候

符号栈内的符号串它的特点

这些符号串我们称之为

规范句型的可规约前缀

还有可规约前缀的前缀就是活前缀

发现了

其实寻找句柄的过程

也是利用FA识别所有

规范句型活前缀的过程

那么识别句柄的状态

其实可以用LR(0)的项目来描述

今天的课就到这里

谢谢大家

编译原理课程列表:

第1章 编译原理概述

-1.1 什么是编译原理

--什么是编译原理

--什么是编译程序

--讨论:翻译程序、汇编程序、编译程序、解释程序的区别和联系。

--练习1

-1.2 编译的基本过程

--编译的基本过程

--编译的基本过程

--讨论:表格管理和出错处理

--练习2

-1.3 编译程序的组织

--编译程序的组织

--编译程序的组织

--练习3

-编译原理概述

第2章 编译理论基础

-2.1 文法与语言

--文法与语言

--文法与语言

-2.2 文法和语言的形式定义

--文法和语言的形式化定义

--文法和语言的形式化定义

--讨论:高级语言的一般特点

--练习1

-2.3 文法的类型

--文法的类型

--文法的类型

--练习2

-2.4 上下文无关文法及语法树

--上下文无关文法及语法树

--上下文无关文法及语法树

--练习3

-2.5 上下文无关文法的句型分析

--上下文无关文法的句型分析

--上下文无关文法的句型分析

--练习4

-编译理论基础作业

-讨论:识别不同文法的实验方法

第3章 词法分析

-3.1 词法分析概述

--词法分析概述

--词法分析概述

--练习1

-3.2 正规文法和状态转换图

--正规文法和状态转换图

--正规文法和状态转换图

--练习2

-3.3 有限状态自动机

--有限状态自动机

--有限状态自动机

--讨论:有限状态自动机的应用

--练习3

-3.4 NFA与DFA的等价性

--NFA与DFA的等价性(上)

--NFA与DFA的等价性(下)

--NFA与DFA的等价性

--练习4

-3.5 正规表达式与正规集

--正规表达式与正规集

--正规表达式与正规集

--讨论:正规式的应用

--练习5

-3.6 正规文法与正规式

--正规文法与正规式

--正规文法与正规式

--练习6

-3.7 正规式与FA

--正规式与FA

--正规式与FA

--练习7

-词法分析作业

-讨论:如何实现词法分析器

第4章 自顶向下的语法分析

-4.1 自顶向下语法分析及其面临的问题

-- 自顶向下语法分析及其面临的问题

--自顶向下语法分析及其面临的问题

--自上而下语法分析中面临的问题

--练习1

-4.2 文法的等价转化

--文法的等价转化

--文法的等价转化

--讨论:什么样的文法才是等价的?

--练习2

-4.3 LL(1)文法与递归下降分析法

--LL(1)文法与递归下降分析法

--LL(1)文法与递归下降分析法

--LL(1)分析法和递归下降法的异同

--练习3

-4.4 构建FIRST集合FOLLOW集合

--构建FIRST集合FOLLOW集合

--构建FIRST集合FOLLOW集合

--讨论:FIRST集合FOLLOW集合的关系

--练习4

-4.5 LL(1)分析器工作原理

-- LL(1)分析器工作原理

--LL(1)分析器工作原理

-4.6 LL(1)分析表构造算法

--LL(1)分析表构造算法

--LL(1)分析表构造算法

--练习5

-讨论:自顶向下语法分析算法的实现方式

第5章 自底向上的语法分析

-5.1 自底向上的语法分析及优先分析

--自底向上的语法分析及优先分析

--自底向上的语法分析及优先分析

--练习1

-5.2 LR分析器

--LR分析器

--LR分析器

--练习2

-5.3 活前缀和LR(0)项目

-- 活前缀和LR(0)项目

--活前缀和LR(0)项目

--练习3

-5.4 构造识别活前缀的FA

--构造识别活前缀的FA

--构造识别活前缀的FA

--练习4

-5.5 LR(0)分析表构造算法

--LR(0)分析表构造算法

--LR(0)分析表构造算法

--练习5

-5.6 SLR(1)分析法

--SLR(1)分析法

--SLR(1)分析法

--练习6

-5.7 LR(1)分析法与LALR分析法

--LR(1)分析法与LALR分析法(上)

--LR(1)分析法与LALR分析法(下)

--LR(1)分析法与LALR分析法

--练习7

-讨论:比较四种LR分析法

第6章 语法制导翻译和中间代码生成

-6.1 语义分析和语法制导翻译概述

--语义分析和语法制导翻译概述

--语义分析和语法制导翻译概述

--练习1

-6.2 常见中间语言简介

--常见中间语言简介

--常见中间语言简介

--讨论:为什么要引入中间代码

--练习2

-6.3 简单算术表达式和赋值语句翻译

--简单算术表达式和赋值语句翻译

--简单算术表达式和赋值语句翻译

--练习3

-6.4 布尔表达式和复制语句翻译

--布尔表达式和复制语句翻译

--布尔表达式和复制语句翻译

-6.5 拉链和回填

--拉链与回填

--拉链与回填

--练习4

-6.6 程序控制语句翻译

--程序控制语句翻译

--程序控制语句翻译举例

--程序控制语句翻译

--练习5

-6.7 for循环语句的翻译

--for循环语句的翻译

--for循环语句的翻译

-6.8 GOTO语句和情况语句的翻译

--GOTO语句和情况语句的翻译

--GOTO语句和情况语句的翻译

--练习6

-6.9 含数组元素的算术表达式的翻译

--含数组元素的算术表达式的翻译

--含数组元素的算术表达式的翻译

--练习7

-6.10 数组元素赋值语句的翻译

--数组元素赋值语句的翻译

--数组元素赋值语句的翻译

--练习8

-讨论:三元式和四元式

第7章 符号表

-7.1 符号表概述

--符号表概述

--符号表概述

--练习1

-7.2 符号表的建立

--符号表的建立

-- 符号表的建立

--练习2

-讨论:符号表

第8章 运行时存储空间组织

-8.1 运行时存储空间组织概述

--运行时存储空间组织概述

--运行时存储空间组织概述

-8.2 运行时分配策略

--运行时分配策略

--运行时分配策略

--练习

第9章 中间代码优化

-9.1 线性窥孔优化

--线性窥孔优化

--线性窥孔优化

-9.2 基本块及其优化方法

--基本块及其优化方法

--基本块及其优化方法

-9.3 循环概念

--循环概念

--循环概念

-9.4 循环优化

--循环优化

--循环优化

-代码优化作业

-讨论:代码优化

活前缀和LR(0)项目笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。