编译原理-第4章.ppt

③ 取这些项目集作为各状态，并画出识别文法Ｇ′的有穷自动机 ④ 用SＬＲ方法解决“移进---归约”冲突。 在十二个项目集中，Ｉ１、Ｉ２和Ｉ９都含有“移进---归约”冲突，其解决办法是： ● 对于项目集Ｉ1＝｛S′∷＝Ｅ·，Ｅ ∷＝Ｅ·＋Ｔ｝，由于集合ＦＯＬＬＯＷ（S′）＝｛＃｝与集合｛＋｝不相交，所以当状态为１时，面临着输入符号为＋时便移进，而面临着输入符号为＃时，则按规则S′∷＝Ｅ归约。 ● 对于项目集Ｉ2＝｛Ｅ∷＝Ｔ·，Ｔ∷＝Ｔ·*Ｆ｝，由于集合ＦＯＬＬＯＷ（Ｅ）＝｛＋，），＃｝与集合｛*｝不相交，因此状态２面临输入符号为*时移进，而面临输入符号为＋或）或＃时，按规则Ｅ∷＝Ｔ归约。 ● 对于项目集Ｉ9＝｛Ｅ ∷＝Ｅ＋Ｔ·，Ｔ ∷＝Ｔ·*Ｆ｝，同样由于FOLLOW（Ｅ)={+,),#}与集合｛*｝不相交，因此状态９面临着输入符号为*时移进，面临着输入符号为＋或）或＃ 时，按规则E∷＝E＋T归约。 ⑤ 根据SLR(１）分析表构造方法构造SLR(１）分析表. 对于冲突项目的状态，如状态1，2，9，按用SＬＲ方法解决构造 SLR(１）分析表. 对于其他状态项目集，只有一个归约项目，也是按照修改后构造SLR(１）分析表方法进行构造 §4.3 自底向上语法分析 四、LR分析法 3、LR(0)分析表的构造 7） LR(0)文法 （1） 冲突项目 如果一个项目集中既有移进项目又含有归约项目，或一个项目 集中有两个以上不同归约项目，则称这些项目是冲突项目。 （2）LR（0）文法 如果一个文法的项目规范族的每个项目集不存在任何冲突项目 ，则称该文法为ＬＲ（０）文法 。 如：上例文法的LR（0）项目集规范族的每个项目集中就不存在冲突项目，所以该文法就是LR（0）文法。 §4.3 自底向上语法分析 四、LR分析法 3、LR(0)分析表的构造 8） LR(0)分析表的构造 为了方便，我们用0，1，2，3，…，n表示状态I0，I1，I2，I3，…In， （1）对于每个项目集Ii中有形如Ａ∷＝β1·Xβ2项目，且Ii状态经过X 到达Ij状态，若X＝a∈VT，则置ACTION［i , a］＝Sj， 若 X∈VN ，则置GOTO[ i , X]=j 如： I0中有E∷=·aA ，而I0经过a到达I2状态，且 a∈VT, 所以置ACTION［0 , a］＝S2 ( 见p125表4.17） I2中有E∷=a·A ， 而I2经过A到达I6状态，且A∈VN 所以置GOTO[ 2，A]=6 ( 见p125表4.17） §4.3 自底向上语法分析 四、LR分析法 3、LR(0)分析表的构造 8） LR(0)分析表的构造 （2）若归约项目Ａ∷＝β·属于Ｉi，设Ａ∷＝β是文法第j个规则，则对任意终结符a和句子右界符#，均置ACTION［i , a或#］＝rj，表示按文法第j条规则将符号栈顶符号串β归约为Ａ。 如： I6有项目E∷=aA· ,其规则E∷=aA 是文法的第一个规则 所以置ACTION[ 6, a ]=ACTION[6 , b]=ACTION[6,c]=ACTION[6,d] =ACTION[6,#]=r1 (见p125表4.17） §4.3 自底向上语法分析 四、LR分析法 3、LR(0)分析表的构造 8） LR(0)分析表的构造 （3）若接受项目S′∷＝S·属于Ｉi，则置ACTION[ｉ,#］＝acc， 表示接受 如： S′∷＝E· 属于I1，所以置ACTION[ 1，# ]=acc (见p125表4.17） （4）分析表中，凡不能用前3个规则填入信息的空白格位置上，均表示出错。 §4.3 自底向上语法分析 四、LR分析法 3、LR(0)分析表的构造 LR(0)分析表的构造小结 (1) 写出给定文法G的拓广文法G’并编号，同时写出全部项目 (2) 写出G’初始状态I0，项目集基本项目S′∷=·S，并由此基本项目 求I0项目集合。 (3) 由I0项目集合，再求出LR（0）项目其它项目集I1 ,I2… (4) 构造识别活前缀的DFA (5) 由DFA根据算法构造LR（0）分析表 §4.3 自底向上语法分析 四、LR分析法 4、SLR(1)分析表的构造 1）问题的提出 LR(0)方法，是从左向右扫描源程序，当到达某规则右部最右符号时，便识