编译原理精品教学课件（华南理工大学）第六章LR分析法.pptVIP

6.3 SLR(1)分析(Simple LR(1)) 项目集中的冲突 一个项目集中存在下列情况称为项目冲突： 移进—归约冲突 移进项目A→α?aβ和归约项目B→r?同在一个项目集中，当面临输入符a时，不能确定移进a还是把r归约为B； 归约—归约冲突 归约项目A→β?和归约项目B→r?同在一个项目集中，不管面临什么输入符都不能确定把β归约为A还是把r归约为B。 一个文法的LR(0)项目集规范族中的项目集不存在移进—归约冲突，也不存在归约—归约冲突时，称该文法为LR(0)文法。 例：文法G’ (0) S’→S (1) S→rD (2) D→D,i (3) D→i 识别文法活前缀的DFA： S’→?S S’→S? S→r?D r S S→rD? D→D?,i D D→i? D→D,?i , i S→?rD I0 I1 I2 I3 I4 I5 D→?D,i D→?i D→D,i? i I6 在项目集I3中S→rD?为归约项目，D→D?,i为移进项目， 存在移进－归约冲突，该文法不是LR(0)文法 2. 解决冲突的SLR(1)方法 基本思想： 对于LR(0)有冲突的项目集用向前查看输入符号串的一个符号的办法加以解决 解决方法： 对归约项目A→r?, 只有当输入符号a∈FOLLOW(A)才进行归约，缩小归约范围，有可能解决冲突。 例：文法G’ (0) S’→S (1) S→rD (2) D→D,i (3) D→i 识别文法活前缀的DFA： S’→?S S’→S? S→r?D r S S→rD? D→D?,i D D→i? D→D,?i , i S→?rD I0 I1 I2 I3 I4 I5 D→?D,i D→?i D→D,i? i I6 Follow集 S’ # S # D # , 对项目集I3，若当前输入符为‘#’时，进行归约，若当前输入符为‘,’，进行移进操作，冲突得以解决 SLR(1)可解决冲突的情况： 例：一个LR(0)规范族中项目集I含有冲突项目I={X→α?bβ?Α→r??Β→δ?}, 其中b∈VT， 如果FOLLOW(A)和FOLLOW(B)互不相交，且不含b，则当状态I面临某输入符a时，可采用下列动作： 若a=b，则移进； 若a∈FOLLOW(A)，则用产生式A→r归约； 若a∈FOLLOW(B)，则用产生式B→δ归约； 此外，报错。 如果一个文法的LR(0)项目集规范族中某些项目集所含有的动作冲突都能用SLR(1)方法解决，则称这个文法为SLR(1)文法 SLR(1)分析表的构造算法 与LR(0)分析表的构造类似，仅在含有冲突的项目集中分别进行处理。 改进的SLR(1)方法： 对所有的归约项目仅对当前输入符号包含在该归约项目左部非终结符的FOLLOW集中，才采取归约动作。 改进的SLR(1)分析表的构造方法： 设已构造出以LR(0)项目集为状态的DFA，DFA的每个状态对应成为分析表的状态，含S’→?S项目的状态为初始状态 1 分析表的ACTION部分的构造： 若项目A→α?aβ∈k， a∈VT，且GO(k,a)=j， 则置ACTION[k,a]=‘Sj’； 若项目A→α?∈k，且产生式A→α的编号为j， 则对任何a∈FOLLOW(A)，置ACTION[k,a]=‘rj’； 若项目S’→S?∈k，则置ACTION[k,#]=‘acc’； 2 分析表的GOTO部分的构造 若项目A→α?Bβ∈k， B∈VN，且GO(k,B)=j， 则置GOTO[k,B]=‘j’； 例 文法G’：(0) S’→S (1) S→rD (2) D→D, i (3) D→i FOLLOW(S’)={#} FOLLOW(S)={#} FOLLOW(D)={# ，} S’→?S S’→S? S→r?D r S S→rD? D→D?,i D→i? D→D,?i , i S→?rD I0 I1 I2 I3 I4 I5 D→?D,i D→?i D→D,i? i I6 D 状态 ACTION GOTO r , i # S D 0 S2 ? ? ? 1 ?1 ? ? acc 2 ? S4 ? 3 3 S5 ? r1 4 r3 ? r3 5 ? S6 ? 6? r2 ? r2 6.4 LR(1)、LALR(1)分析思想 仍有许多文法构造的以LR(