LR分析方法
# 0x0.总览
# 1.LR分析器逻辑结构
2.LR分析器的工作过程
# 2.重要结论
- 每个LR(0)文法一定是SLR(1)文法,也一定LR(1)文法,反之不然。一个LR(0)文法的状态比LR(1)分析器的状态要少。
- LL(k)文法都是LR(k)文法。
- 存在非LR文法。例:L={wwR | w∈{a,b}*}和G[S]: S→aSa |bSb | 空
# 0x1.LR(0)分析
# 1.活前缀
可以简单理解为:整个分析运算过程所有得到的字符串组成的集合。
# 2.LR(0)项目
# 3.拓广文法
# 4.项目构造NFA:
# 5.直接求DFA
识别活前缀的DFA方法可以直接求:
# 6.LR(0)文法定义
# 7.分析表构造
此处是把所有归约项目都赋值为归约。
例子:
# 8.对输入串的分析过程
# 9.作业
# 0x2.SLR(1)分析
# 1.移进归约冲突、归约归约冲突、接收归约冲突
此文法产生的项目集:
但是在实际运行时就会产生冲突:
除此之外,还有一个接收归约冲突,即I0中既有接收项目,又有归约项目时存在此冲突。
# 2.解决方法-SLR(1)分析
存在上述两种冲突之一时证明文法并不是LR(0)文法,可以尝试构造SLR(1)文法来解决冲突。
# 2.1.SLR(1)文法前提
发生冲突的移进符组成的集合要和归约前面的非终结符的follow集合不相交。
# 3.分析表构造:
和LR(0)不同的是,此处是仅仅把属于前面非终结符follow集合的项目设为归约。
例子:
# 4.分析过程
当归约冲突时,查看符号栈前一个符号的表是去那个状态,便是以哪个归约。
# 5.作业
答案:
# 0x3.LR(1)分析
LR(1)是为了解决SLR(1)文法解决不了的问题创造出来的。
简单理解:
SLR(1)是处理前者的Follow集合,在冲突的前者的follow集合不相交时便可以得解,这是宏观情况;
而LR(1)则是处理冲突时的后者的First集合,并且将每一步的first值一起入栈,使其后者处理时结果唯一。
# 1.SLR问题描述
# 2.LR(k)项目
# 3.LR(1)的有效项目集和转移函数
例子:
# 4.分析表构造
例子:
# 5.分析过程
# 0x4.LALR(1)分析
# 1.介绍说明
LookAhead LR
LALR在SLR(1)和LR(1)的状态数目和分析能力间寻找折中。
简单来说就是将LR(1)文法化简后的文法,但是并不是所有文法都可以化简的。
# 2.分析表构造
1.构造文法G的规范 LR(1) 状态. 2.合并同心集的状态. 3.新 LALR(1) 状态的GO函数是合并的同心集状态的GO函数的并. 4.LALR(1)分析表的ACTION 和 GOTO 登录方法与LR(1)分析表一样. 经上述步骤构造的表若不存在冲突,则称它为文法G的LALR(1)分析表,文法G是LALR(1)文法。
例子:
它的LR(1)项目:
化简之后:
得表:
# 3.分析过程
# 4.不能化简的LR(1)
化简后有冲突时便不能化简,便不是LALR(1)文法,而是LR(1)文法。
# 0x5.作业
除了下面的4题,老师说考试时有可能从第10题里抽题,所以复习时要看下。
我的答案: