当前课程知识点:编译技术 > 第三章 语法分析 > 3.5 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 编译技术绪论
--编译原理介绍--作业
-2.1 词法记号 串和语言
--2.1 词法记号 串和语言--作业
-2.2 正规式 状态转换图
--2.2 正规式 状态转换图--作业
-2.3 有限自动机
--2.3 有限自动机--作业
-2.4 DFA构建 子集构造法 DAF化简
-2.5 Lex
-3.1 上下文无关文法
--3.1.3 推导
-3.2 自上而分析中的文法
--3.2 上下文无关文法--作业
--3.2.3 语言和文法--作业
-3.3 自上而下分析
-3.4 自下而上分析
--3.4 自下而上分析--作业
-3.5 LR分析器
-4.1 语法制导的定义
--4.1 语法制导的定义--作业
-4.2 S属性的自下而上计算
-4.3 L属性定义
--4.3 L属性定义--作业
-4.4 L属性的自下而上计算
--4.4 L属性的自下而上计算--作业
-5.1 概述
--5.1 概述
--概述-作业
-5.2 全局栈式存储分配
-5.3 调用序列
--5.3 调用序列
-5.4 非局部名字的访问
--5.4 非局部名字的访问--作业
-6.1 中间代码生成
-6.2 作用域信息的保存
-7.1 代码生成器设计中的问题
-7.2 目标机器
--7.2 目标机器
--7.2 目标机器--作业
-7.3 基本块和流图
-7.4 一个简单的代码生成器
-8.1 基于Python的编译器框架演示视频和代码
-8.2 代码介绍
--8.2.4 SA
-8.3 SimpleJava