7.3 SLR()分析.ppt

7.3 SLR(1)分析 例1：已知拓展文法G’[S’]: (实数说明文法) (0)S’→S (1)S→rD (2)D→D, i (3)D→i 构造文法G’的分析表 7.3 SLR(1)分析 7.3 SLR(1)分析 冲突如何解决 ？ SLR(1)中冲突的解决方法 假定一个LR(0)规范族中含有如下的项目集 I　　I={X→α·bβ,A→γ·,B→δ·} 在该项目集中含有移进-归约冲突和归约-归约冲突。 其中α,β,γ,δ为文法符号串，b为终结符。只要在所有含有A或B的句型中满足 FOLLOW(A)∩FOLLOW(B)∩{b}= SLR(1)中冲突的解决方法 概 念 例题：判断算术表达式文法是否是SLR(1)文法 解：将表达式文法拓广为 (0)S’→E (1)E→E+T (2)E→T (3)T→T*F (4)T→F (5)F→(E) (6)F→i 首先构造该文法的LR(0)项目集规范族 表达式拓广文法：(0)S’→E (1)E→E+T (2)E→T (3)T→T*F (4)T→F (5) F→(E) (6)F→i 表达式拓广文法：(0)S’→E (1)E→E+T (2)E→T (3)T→T*F (4)T→F (5) F→(E) (6)F→i SLR(1)分析表的构造 SLR(1)分析表的构造与LR(0)分析表的构造类似，仅在含有冲突的项目集中分别进行处理。 SLR(1)分析表的构造 改进：对所有归约项目都采取SLR(1)的处理思想,凡是归约项目仅当面临输入符号包含在该归约项目左部非终结符的FOLLOW集合中，才采取用该产生式归约的动作。 改进的SLR(1)分析表的构造方法如下： 假设已构造出文法的LR(0)项目集规范族C={I0,I1,…,In},令包含S’→·S项目的集合Ik的下标k为分析器初态，求出所有非终结符的FOLLOW集。则SLR(1)分析表构造步骤为 SLR(1)分析表的构造 a) 若项目A→α·aβ属于Ik ，且转换函数GO(Ik , a)= Ij，当a为终结符时，则置ACTION[k,a]为Sj。b) 若项目A→α·属于Ik，则对a为任何终结符或‘#’，且满足a∈FOLLOW(A)时，置ACTION[Ik,a]= rj，j为产生式A→α在文法G’中的编号。c) 若GO(Ik ,A)= Ij，则置GOTO[k,A]=j，其中A为非终结符，j为某一状态号。d) 若项目S’→S·属于Ik,则置ACTION[k,#]=acc,表示接受。e) 凡不能用上述方法填入的分析表的元素，均应填上“报错标 志”，在表中用空白表示。 SLR(1)分析表的构造 采用表7.8的SLR(1)分析表，对符号串i+i*i # 进行分析 SLR(1)分析器存在的问题 SLR(1)方法仍存在无效规约。 仍有许多LR(0)项目集规范族存在的动作冲突不能用SLR(1)规则解决。 SLR(1)分析器存在的问题 SLR(1)分析器存在的问题 SLR(1)分析器存在的问题 例如文法G’为： 　　(0) S’→S 　　(1) S→aAd 　　(2) S→bAc 　　(3) S→aec 　　(4) S→bed (5) A→ e 首先用S’→?S作为初态集的项目，然后用闭包函数和转换函数构造识别文法G’的识别活前缀的DFA如图7.11所示。 G’:(0)S’→S (1)S→aAd (2)S→bAc (3)S→aec (4)S→bed (5)A→ e I5：S→ae·c ； A→e·因 S’ =R S =R aAd =R aed； S’ =R S =R aec这两个最右推导已包括了活前缀为a的所有句型，因此对活前缀ae来说，当面临输入符号为c时应移进，面临d时应用产生式A→e归约。因为S’ =R S≠R aAc 所以aAc 不是该文法的规范句型。 I7: S→be·d； A→e· S’ =R S =R bAc =R bec ;　S’ =R S =R bed 上述两个推导，包含了活前缀为b的所有规范句型，因此 FOLLOW(A)中的c只能跟在句型bAc中A的后面，这样在I7中当面临输入符为c时才能归约。 7.4 LR(1)分析 LR(1)处理方法： 若[A→α·Bβ]∈项目集I，则[B→·γ]也∈I ，不妨把FIRST(β)作为用产生式B→γ归约的向前有哪些信誉好的足球投注网站符，归约时用该符号集合替代SLR(1)分析中的FOLLOW集，并把此有哪些信誉好的足球投注网站符号的集合也放在相应项目的后面，这种处理方法称为LR(1)方法。 7.4 LR(1)分析 7.4 LR(1)分析 7.4.1 LR(1)项目集族的构造 (续) (2) 转换函数的构造 LR(1)转换函数的构造与