当前课程知识点：编译原理 > 第5章 自底向上的语法分析 > 5.5 LR(0)分析表构造算法 > LR(0)分析表构造算法
大家好
在上一节课我们讨论了
LR(0)项目集它的构造
有的时候呢
在识别活前缀的DFA某一状态当中呢
可能会出现这样的两种情况
第一种情况
如果这个项目集当中既含有移进的项目
又含有归约项目
那么这个项目
就存在移进和归约的冲突
其二如果这个项目含有两个或两个以上
圆点在最后的这样的归约项目
那么这个项目集就存在
归约和归约的冲突
要注意
冲突的情况都是和归约的动作相关的
反过来如果这个项目集满足
没有移进项目和归约项目并存
也没有多个归约项目并存这两个条件的话
我们称这样的项目集
是相容的项目集
例如有这样的项目是这样子的
｛A→α·β
B→α·｝
那么如果这个时候
栈顶是α
项目集当中呢还有一个移进项目
然后一个规约项目
那么就无法确定
到底是移进呢还是归约
那么因此呢这个项目集
是不相容的
如果一个文法G的识别
活前缀的DFA
它的每一个项目都不存在
既包含移进项目又包含归约项目
或者说含有二个以上的归约项目
也就是说呢
LR(0)项目集规范族是不存在
移进和归约的冲突
还有归约和归约的冲突
那么每一个项目他都是相容的
这样的文法
就是一个LR(0)文法
显然呢
LR(0)文法它的每一个项目集当中呢
不包含任何的冲突项目
但是呢从另外一个角度来看
LR(0)文法它的能力还是比较弱的
甚至连我们经常讨论的
表达式文法也不属于LR(0)文法
我们一直强调
LR(0)分析它的关键
是构造LR(0)分析表
那么接下来就让我们来重温一下
LR(0)分析表它的结构
大家看到
列标题实际上是项目集Ii它的编号
行标题呢是所有的文法符号
只不过在ACTION子表当中呢是终结符号
而GOTO子表当中呢是非终结符
ACTION子表当中的每一项
表示的是当前状态
面临输入符号时
应该采取的是移进还是规约操作
GOTO子表中的每一项
表示的当前状态
面临文法符号的时候
应该进入到下面的哪一个状态
接下来是我们来看一下
LR(0)分析表它的构造算法
前提是这个文法呢一定是LR(0)文法
输入的呢是一个拓广文法G'
输出的是 G’
它的LR(0)分析表当中的
action子表和goto子表
方法是这样子的
首先构造G’
它的LR(0)项目集规范族
也就说呢我们来构造
识别活前缀的DFA
接下来对状态 k进行分析动作
那么在这个分析表当中呢
我们是用状态Ik
它的下标k来代替对应状态的
第一种情况是
如果A→α·aβ
属于状态K的话
而且状态转移函数
GO(Ik a)=Ij
而且a为终结符号
那么就将action这个词表当中
的k行a列设置为Sj
表示的是shift j
对应的状态转换关系就是状态K
面临输入符号a的时候
会转移到状态j
第二种情况是
如果A→α·
属于K状态的话
那么对于所有的终结符a还有#号
那么将action这个表当中的
k行a列设置为rj
也就是说按照j号产生式
A→α进行规约
要注意此处A并不是S’
这个文法的开始符号
这里就体现出了LR(0)的特点
也就是说我无须向前查看输入符号
不管是任何的终结符
还是#号也好
那么我进行的是统一操作
对应的状态是一个终态
圆点呢是在α的最右边
第三种情况
如果转换函数go(Ik A)=Ij
A是非终结符号
那么就将goto表当中的
k行A列设置为j
对应的状态转换是k状态下面
如果面临的符号
是规约之后的一个非终结符的话
那么状态转移到j
第四种情况
如果S’→S·
属于这个状态集的话
那么就将action表当中的
k行#列置为acc
表示这是一个接受状态
第五种情况
分析表当中凡是不能够用上面的规则
填入信息的
空白格上面
均置上出错标志error
接下来我们就来尝试为这个文法G[S]
构建LR(0)的分析表
首先拓广文法
增加一个新的开始符号S’
并且为每一个产生式进行编号
接下来以S’→.A为核心项目
去求得初始状态
并且利用状态转化函数
求得其他的状态
也就是求得项目集规范族
大家也看到了
那么在这个项目集规范族当中
I1 I3和I4呢
是规约态也就是终态
那么下面的话呢我们可以一边
来构造识别活前缀的DFA
一边来填充我们的LR(0)分析表
LR(0)分析表它的行号
刚才我们说了我们用的
是项目集它的编号
初态I0
面临的输入如果是A的话
那么转向项目集I1
所以Goto表当中0行A列就设置为1
初态I0
面临的输入如果是a的话
那么
转向项目集I2
就将Action这个表当中的
0行a列设置为S2
初态I0如果面临输入的是b的话
那么转向项目集I3
所以将Action这个表当中的0行b列
设置为S3
接下来来看一下项目集I1
项目集I1呢它里边有S＇→A·
那么就将
Action表当中的1行当中的#这一列
设置为acc
项目集I2
如果面临的输入是a的话
那么转向的项目集是I2
于是就将Action这个表当中的
2行a列设置为S2
项目集I2如果面临的输入是b的话
那么转向项目集I3
所以就将Action这个表当中的2行b列
设置为S3
接下来来看一下项目集I3
I3呢是规约态
那么就将Action表当中的3行当中的
所有的终结符
和#号列置为r3
也就是说可以将栈顶的符号b
规约为A了
项目集I4也是规约态
那么就将Action表当中的第4行
所有的终结符
以及#号这一列设置为r2
意思就是可以将栈顶的符号串
aA规约为A了
那么这样的话我们就完成了LR(0)
分析表它的构建工作
在这一节课当中呢我们讨论了
项目集当中的冲突问题
如果不存在移进和归约的冲突
或者是归约和归约冲突的话
那么这样的文法就属于LR(0)文法
我们可以为其构造LR(0)分析表了
显然LR(0)文法当中的每一个项目
集呢都是不包含任何冲突的
但是呢
我们也要承认LR(0)文法它的能力很弱
连表达式文法也不属于LR(0)文法
这节课呢就到这里
谢谢大家
-1.1 什么是编译原理
--什么是编译原理
--什么是编译程序
--讨论：翻译程序、汇编程序、编译程序、解释程序的区别和联系。
--练习1
-1.2 编译的基本过程
--编译的基本过程
--编译的基本过程
--练习2
-1.3 编译程序的组织
--编译程序的组织
--编译程序的组织
--练习3
-编译原理概述
-2.1 文法与语言
--文法与语言
--文法与语言
-2.2 文法和语言的形式定义
--练习1
-2.3 文法的类型
--文法的类型
--文法的类型
--练习2
-2.4 上下文无关文法及语法树
--练习3
-2.5 上下文无关文法的句型分析
--练习4
-编译理论基础作业
-3.1 词法分析概述
--词法分析概述
--词法分析概述
--练习1
-3.2 正规文法和状态转换图
--练习2
-3.3 有限状态自动机
--有限状态自动机
--有限状态自动机
--练习3
-3.4 NFA与DFA的等价性
--练习4
-3.5 正规表达式与正规集
--练习5
-3.6 正规文法与正规式
--正规文法与正规式
--正规文法与正规式
--练习6
-3.7 正规式与FA
--正规式与FA
--正规式与FA
--练习7
-词法分析作业
-4.1 自顶向下语法分析及其面临的问题
--练习1
-4.2 文法的等价转化
--文法的等价转化
--文法的等价转化
--练习2
-4.3 LL(1)文法与递归下降分析法
--练习3
-4.4 构建FIRST集合FOLLOW集合
--练习4
-4.5 LL(1)分析器工作原理
-- LL(1)分析器工作原理
-4.6 LL(1)分析表构造算法
--练习5
-5.1 自底向上的语法分析及优先分析
--练习1
-5.2 LR分析器
--LR分析器
--LR分析器
--练习2
-5.3 活前缀和LR(0)项目
-- 活前缀和LR(0)项目
--练习3
-5.4 构造识别活前缀的FA
--练习4
-5.5 LR(0)分析表构造算法
--练习5
-5.6 SLR(1)分析法
--练习6
-5.7 LR(1)分析法与LALR分析法
--练习7
-6.1 语义分析和语法制导翻译概述
--练习1
-6.2 常见中间语言简介
--常见中间语言简介
--常见中间语言简介
--练习2
-6.3 简单算术表达式和赋值语句翻译
--练习3
-6.4 布尔表达式和复制语句翻译
-6.5 拉链和回填
--拉链与回填
--拉链与回填
--练习4
-6.6 程序控制语句翻译
--程序控制语句翻译
--程序控制语句翻译
--练习5
-6.7 for循环语句的翻译
-6.8 GOTO语句和情况语句的翻译
--练习6
-6.9 含数组元素的算术表达式的翻译
--练习7
-6.10 数组元素赋值语句的翻译
--练习8
-7.1 符号表概述
--符号表概述
--符号表概述
--练习1
-7.2 符号表的建立
--符号表的建立
-- 符号表的建立
--练习2
-8.1 运行时存储空间组织概述
-8.2 运行时分配策略
--运行时分配策略
--运行时分配策略
--练习
-9.1 线性窥孔优化
--线性窥孔优化
--线性窥孔优化
-9.2 基本块及其优化方法
-9.3 循环概念
--循环概念
--循环概念
-9.4 循环优化
--循环优化
--循环优化
-代码优化作业
