当前课程知识点:编译技术 >  第三章 语法分析 >  3.5 LR分析器 >  3.5.6 LR分析方法特点

返回《编译技术》慕课在线视频课程列表

3.5.6 LR分析方法特点在线视频

下一节:3.5.7 非二义且非LR的上下文无关文法

返回《编译技术》慕课在线视频列表

3.5.6 LR分析方法特点课程教案、知识点、字幕

各位同学大家好

这节课

我们继续来学习语法分析方法

我们来学习 LL 分析方法和LR分析的特点

也就是将这两种分析方法来进行对比

我们首先看一下 LR分析方法

我们知道

在进行移进归约的过程中

栈中的文法符号总是形成一个活前缀

比如说我们给出一个最右推导的过程

我们观察到

在移进归约的分析中栈里边

它一定是形成了一个活前缀

因为移进归约分析是最右推导的逆过程

我们可以通过这个分析表来分析一下

这边是输入

第1列是栈

那么栈里的符号串

总是我们标记的这些红色的部分

也就是它始终形成一个活前缀

第2个特点

分析表的转移函数

实际上是识别活前缀的DFA

我们看到这个是动作表

这边是转移表

转移表才是对应识别活前缀的DFA

第3个特点

栈里边这个状态符号

包含了确定句柄所需要的一切的信息

那么我们为什么还要放文法符号呢?

栈里放文法符号

是为了方便大家的理解

实际上文法符号是可以省略的

可以只写状态符号

下一个特点是:

LR分析方法

是已知的最一般的没有回溯的移进归约分析方法

此外它所能分析的文法

是预测分析方法所能分析文法的真超集

还有它可以及时发现错误

但是缺点我们也知道,是很明显的

手工来构造这张分析表的工作量非常大

我们再将 LL分析方法和LR的方法进行对比

首先是建立分析树的方式

LR分析方法是自下而上建立分析树进行归约

LL分析方法是自上而下来建立分析树进行推导

那么LR分析方法用的是规范归约

也就是最右推导的逆过程

LL分析方法用的是最左推导

我们再来看第3个对比方法

也就是决定使用产生式的时机

LR分析方法当中

它在看到了整个产生式的右部之后

再决定使用哪个产生式进行归约

而LL分析方法中

它只是看到产生式的第1个终结符

就决定接下来使用哪一个产生式

我们可以看一下推导的过程

假设从S开始进行推导

我们得到 γAbω

接下来我们将A推导为 lβ

那么如果在自上而下的分析中

LL分析方法决定使用产生式的位置

是在看到 l 之后就决定是由哪个产生式

而使用自下而上的LR分析法

我们是在看见了b之后才决定

将 lβ 归约为A

当然看得越多越准确

所以LR分析方法

它能分析的文法是更多

选择的时机是更好的、更准确的

再一个是对本法的限制

我们在学LL(1)文法的时候

学习了提取左因子、消除左递归

是因为LL这种分析方法

它不允许有左递归存在

而且也不允许有公共左因子存在

那么LR分析方法中我们发现

其实对文法没有明显的限制

下一个是分析表的比较

LR分析表(的大小)是状态数目乘以文法符号的数目

也就是状态数乘以终结符和非终结符个数的总和

分析表比较大

而LL分析表

是非终结符的个数乘以终结符的个数

分析表比较小

最后我们来比较一下分析栈

LR分析方法的栈是一个状态栈

当然我们也可以把符号放入其中

但是通常状态比文法符号包含的信息更多

而LL分析方法中它是文法的符号栈

接下来我们再看一下句柄

在LL分析方法中没有句柄的概念

在LR分析方法中

我们每次根据栈顶的状态和下一个符号

决定是不是有句柄出现

以及我们要进行归约

应该使用哪一个产生式

还有关于语法错误这一部分

对于LA分析方法来说

绝对不会将出错点之后的符号移入到栈中

LL分析方法和LR分析一样

绝不会读过出错点而不会报错

也就是它一定会报错

这一小节就到这

谢谢大家

编译技术课程列表:

第一章 绪论

-1.1 编译技术绪论

--1.1 编译技术绪论

--编译原理介绍--作业

第二章 词法分析

-2.1  词法记号 串和语言

--2.1 词法记号 串和语言

--2.1  词法记号 串和语言--作业

-2.2  正规式 状态转换图

--2.2 正规式 状态转换图

--2.2  正规式 状态转换图--作业

-2.3  有限自动机

--2.3 有限自动机

--2.3  有限自动机--作业

-2.4  DFA构建 子集构造法 DAF化简

--2.4 DFA构建

-2.5 Lex

--2.5 词法分析工具Lex

第三章 语法分析

-3.1 上下文无关文法

--3.1.1 语法分析概述

--3.1.2 上下文无关文法定义

--3.1.3 推导

--3.1.4 二义性

-3.2 自上而分析中的文法

--3.2.1 消除左递归

--3.2.2 提取左因子

--3.2 上下文无关文法--作业

--3.2.3 语言和文法

--3.2.3 语言和文法--作业

-3.3 自上而下分析

--3.3.1 first follow

--3.3.2 LL(1)文法

--3.3.3 递归下降分析

--3.3.4 非递归下降分析的预测分析器

-3.4 自下而上分析

--3.4.1 归约句柄

--3.4.2 移进归约分析过程

--3.4 自下而上分析--作业

-3.5 LR分析器

--3.5.1 LR分析器

--3.5.2 活前缀

--3.5.3 SLR分析方法

--3.5.4 规范的LR分析方法

--3.5.5 LALR分析方法

--3.5.6 LR分析方法特点

--3.5.7 非二义且非LR的上下文无关文法

第四章 语法指导的翻译

-4.1 语法制导的定义

--4.1.1 属性文法

--4.1.2 属性依赖图和计算次序

--4.1 语法制导的定义--作业

-4.2 S属性的自下而上计算

--4.2.1 S属性的自下而上计算

--4.2.2 栈代码

-4.3 L属性定义

--4.3.1 L属性定义

--4.3.2 翻译方案

--4.3.3 预测翻译器的设计

--4.3 L属性定义--作业

-4.4 L属性的自下而上计算

--4.4.1 L属性的自下而上计算

--4.4.2 模拟继承属性的计算

--4.4 L属性的自下而上计算--作业

第五章 运行时存储空间的组织与管理

-5.1  概述

--5.1 概述

--概述-作业

-5.2  全局栈式存储分配

--5.2 全局栈式存储

-5.3  调用序列

--5.3 调用序列

-5.4 非局部名字的访问

--5.4 非局部名字

--5.4 非局部名字的访问--作业

第六章 中间代码生成

-6.1 中间代码生成

--6.1 中间代码生成概述

-6.2 作用域信息的保存

--6.2 声明语句-作用域信息的保存

第七章 代码生成

-7.1 代码生成器设计中的问题

--7.1 代码生成器的设计中的问题

-7.2 目标机器

--7.2 目标机器

--7.2  目标机器--作业

-7.3 基本块和流图

--7.3 基本块和流图

-7.4 一个简单的代码生成器

--7.4 一个简单的代码生成器

第八章 基于Python的编译器框架实现

-8.1 基于Python的编译器框架演示视频和代码

--8.1 基于Python的编译器框架演示

-8.2 代码介绍

--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.6 LR分析方法特点笔记与讨论

也许你还感兴趣的课程:

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