目录
构造LR(0)分析表的步骤如下:
拓广文法--->列项目--->项目集规范簇--->分析表
拓广文法是一种用于描述上下文无关文法的元语法表示法,通过引入了一些扩展的符号和表示方式,以使得语法的描述更加直观
看下面的拓广文法,这里的(0)E'-->E:表示通过E'指向开始文法
列项目:
①首先将每个产生式的右部加“点”
②将通过不同符号的类列举出来
③若列举出来的语句中“点”后面是非终结符,那么需要将该非终结符所属的类都写下来,除了E'->E?。例如 E-->"点"E+T,"点"后面是E,所以将 E->"点" E +T 和 E-> "点" T 写下来,不写E'-->“点” E
接下来分析I0:
由于E'--->E"点"中的"点"已经到最后了,不需要进一步分析
同理可得:
分析表:
列出这样的表,0~8分别表示I0~I8:
第一行表示从I0出发,经过一个E,到达状态1,I0输入T,到达状态2,I0输入a,到达状态5,I0输入"(",到达状态3
以此类推:
若"点"已经在最后了, 表示这个项目已经结束,用”r“表示,在拓广文法中找到相同的项目,填入序号。例如这里的T2:E-->T,在拓广文法中对应(2)
最后,状态1包含"E'-->E",所以在状态1的“#”列表明all
SLR(1)步骤和LR(0)相同,只是多求了一部FOLLOW集
点在不同位置,代表的项目不同:
归约项目(A-->?):?在最后
移进项目(A-->?xB):?后面是终结符接受项目(S--->?):开始文法对应的
待约项目(A--->?XB):?后面是是非终结符
来看以下例子:
通过DFA得到的表如下图所示,但是这里先不用填“r”,表示终结
接下来我们求非终结符的FOLLOW集合:
将Follow集的终结符,写在"r"的位置,例如,拓广文法中(2)E-->T,那么E的FOLLOW集={+,),#}
以此类推,得到:
SLR(1)的出现其实是为了解决LR(0)的两个矛盾,即同一个项目中会产生矛盾:移进---归约????????归约---归约
(1)归约---归约
A--->a?
B--->a?
以上就出现了(归约---归约)错误,A的follow集/B的follow集不知是用"A--->a?"还是"B--->a?"
归约
(2)移进---归约(?后面是终结符---?在最后):
表中划圈部分满足,即I1和I3都存在移进---归约错误:
在I1中,我们将?后面的终结符“+”与该项目的开始符“ S’ ”的Follow集相交
I3同理:
得出的两个交集皆为(空),那么说明LR(0)文法也满足SLR(1)文法的要求,是SLR(1)文法。
若不存在冲突项目,那么既是LR(0)文法,也是SLR(1)文法
若存在冲入项目,且满足Follow集为(空)的条件,那么就是SLR(1)文法,如果也不满足那么就既不是LR(0)文法,也不是SLR(1)文法
也就是说SLR(0)包含不冲突的项目,也包含符合条件的冲突项目:
SLR(0)LR(0)