1、湖北大学数计学院计科系湖北大学数计学院计科系 2008年年3月月第7章 自下而上的LR(k)分析方法LR(k)分析器是这样一种分析程序：它总是按从左至右方式扫描输入串，并按自下而上方式进行规范归约。在这种分析过程中，它至多只向前查看k个输入符号就能确定当前的动作是移进还是归约；若动作为归约，则它还能唯一地选中一个产生式去归约当前已识别出的句柄（这里称为活前缀）。若该输入串是给定文法的一个句子，则它总可以把这个输入串归约到文法的开始符号；否则报错，指明它不是该文法的一个句子。湖北大学数计学院计科系湖北大学数计学院计科系 2008年年3月月7.1 LR(k)文法和LR(k)分析方法7.2 LR(0
2、)分析表的构造7.3 SLR分析表的构造7.4 规范LR(1)分析表的构造7.5 LALR分析表的构造7.6 无二义性规则的使用7.7 小结湖北大学数计学院计科系湖北大学数计学院计科系 2008年年3月月7.1 LR(k)文法和LR(k)分析器 给定文法G，S是其开始符号。考虑该文法中一个终结符号串w的一个规范推导 S=w1=w2=w 假定 uAv=uxv 是上述推导中的一个推导步。A:=x是用于该推导步的产生式。 对于每一个这样的推导和推导步，仅通过扫描ux和查看v中开始的k个符号就能唯一确定选用产生式A:=x，我们就称G为LR(k)文法。湖北大学数计学院计科系湖北大学数计学院计科系 200
3、8年年3月月 LRLR分析器的逻辑结构分析器的逻辑结构 一个输入、一个输出、一个栈、一个驱动程序和一张分析表。 id+id*id$ SmXmSm-1Xm-1S0LR驱动程序动作 转移action goto输出湖北大学数计学院计科系湖北大学数计学院计科系 2008年年3月月分析动作表（ACTION）： 移进 ai 和s=gotosm,ai进栈actionsm,ai=归约 rj : A:=Xm-r+1Xm-r+2Xm 接收 s=gotosm-r , A 错误处理LR分析器的分析表：分析动作表和goto函数表GOTO函数表：GOTOsi,xj规定了当状态si面临文法符号xj时所应到达的下一状态。湖北
4、大学数计学院计科系湖北大学数计学院计科系 2008年年3月月格局（构形）：（栈中符号序列，剩余输入符号串） 开始：（s0, a1 a2 an$) 中间：（s0 x1s1x2s2xmsm ,aiai+1an$)LR分析器的工作过程1. 若actionsm ,ai=si 则把ai,si=actionsm ,ai推进栈。格局：（s0 x1s1x2s2xmsm aisi , ai+1an$)湖北大学数计学院计科系湖北大学数计学院计科系 2008年年3月月2. 若actionsm ,ai=r (A:=xm-r+1xm-r+2xm) ,则格局：（s0 x1s1x2s2xm-rsm-r As , ai ai
5、+1an$)其中，s=gotosm-r ,A3.若actionsm ，$=accept,则分析结束。4 .若actionsm,ai=error,则转出错处理程序。湖北大学数计学院计科系湖北大学数计学院计科系 2008年年3月月状态ACTIONGOTOid+*()ETF0S5S41231S6acc2R2S7R2R23R4R4R4R44S5S48235R6R6R6R66S5S4937S5S4108S6S119R1S7R1R110R3R3R3R311R5R5R5R51 E:=E+T2 E:=T3 T:=T*F4 T:=F5 F:=(E)6 F:=id湖北大学数计学院计科系湖北大学数计学院计科系 20
6、08年年3月月7.2 LR(0)分析表的构造 LR分析方法的基本原理是：把每个句柄（某个产生式的右部）的识别过程划分为若干状态，每个状态从左至右识别句柄中的一个符号，若干个状态就可识别句柄左端的一部分符号。识别了句柄的这一部分就相当于识别了当前规范句型的左起部分规范句型的活前缀。因而，对句柄的识别就变成了对规范句型活前缀的识别。 LR(0)分析程序，即在分析的每一步，仅根据当前的栈顶状态就能确定应执行何种分析动作，而无须向前查看任何输入符号。湖北大学数计学院计科系湖北大学数计学院计科系 2008年年3月月规范句型的活前缀 活前缀（Viable Prefix）是指规范句型的一个前缀，它不包含该句
7、型的句柄右边的任何符号。活前缀和句柄的关系：1. 活前缀不含有句柄的任何符号， ；2. 活前缀含有句柄的部分符号， 1 ；3. 活前缀已含有句柄的全部符号， 。湖北大学数计学院计科系湖北大学数计学院计科系 2008年年3月月LR(0)项目 用圆点“ ”表示识别一个产生式右部符号到达的位子，若有规则 AXYZ,则有下面四个项目： A XYZ A X YZ A X Y Z A X YZ 另：A, A 以上项目称作LR(0)项目。项目指明在分析过程的某一时刻，已经看到一个产生式的多少。湖北大学数计学院计科系湖北大学数计学院计科系 2008年年3月月文法G的拓广文法 给定文法G，S是其开始符号，我们构
8、造一个与S相关的文法G：它包含整个G，而且外加一个新产生式S:=S。其中，S是G的开始符号，称G为G的拓广文法。A a aVT 移进项目A B BVN 待归约项目A 归约项目SS 接收项目湖北大学数计学院计科系湖北大学数计学院计科系 2008年年3月月CLOSURE(I)函数设I是文法G的一个LR(0)项目集合 closure(I)是从I出发用下面三个规则构造的项目集: 1I中每一个项目都属于closure(I)。 2若项目AB closure(I)且BP 则将B加进closure(I)中。 3重复执行(2)直到closure(I)不再增大为止。 湖北大学数计学院计科系湖北大学数计学院计科系
9、2008年年3月月goto(I,X)函数若I是G的一个LR(0)项目集, X VTVN 则 goto(I,X)=closure(J) 其中, J=AX|当AX I时 goto(I,X)称为转移函数。项目AX称为AX的后继。I:AXJ:AXX湖北大学数计学院计科系湖北大学数计学院计科系 2008年年3月月LR(0)项目集规范族LR(0)项目集规范族的构造 PROCEDURE ITEMS(G ); BEGIN C:=closure( S S) ; REPEAT FOR IC 和 X VT VN 把goto(I,X) 加入到C中 UNTIL C不再增大 END;最后得到的C就是拓广文法G的LR(0)
10、项目集规范族。DFA m=(VTVNS, Q项目集规范族， q0= closureS S,Q,=go(I,X) )它识别文法G的所有活前缀。湖北大学数计学院计科系湖北大学数计学院计科系 2008年年3月月有效项目 一个项目Ax.y称为对某个活前缀ux是有效的，当且仅当存在某个规范推导 S=uAv=uxyv其中，xy是规范句型uxyv的句柄，v是一个终结符号串。* 项目Ax.y对活前缀ux有效的情况可用于判断：当发现ux已呈现于栈顶时，是应该进行归约还是进行移进。湖北大学数计学院计科系湖北大学数计学院计科系 2008年年3月月 一个活前缀w的有效项目集正是从项目集规范族对应的DFA初态出发，经由
11、标记为w的路径所到达的那个项目集。EE+TTT*FTFF(E)Fid对于活前缀wE+T*，从初态I0出发，经过E+T*路径到达状态集I7I7： TT*.F F.(E) F.idE=E=E+T=E+T*F=E+T*id=E+T*F*idE=E=E+T=E+T*F=E+T*(E)E=E=E+T=E+T*F=E+T*id湖北大学数计学院计科系湖北大学数计学院计科系 2008年年3月月I0: S.S S.A A.aAb A.c S.B B.aBb B.dI1: SS.I2: SA.I3: SB.I5: Ac.I6: Bd.I7: AaA.bI8: AaAb.I9: BaB.bI10: BaBb.I4:
12、 Aa.Ab A.aAb A.cBa.Bb B.aBb B.dSABacdcdabABb文法G(S)：SA|BAaAb|cBaBb|d拓广文拓广文G(S)G(S)：0 SS0 SS1 SA1 SA2 SB2 SB3 AaAb3 AaAb4 Ac4 Ac5 BaBb5 BaBb6 Bd6 Bd识别活前缀的DFA湖北大学数计学院计科系湖北大学数计学院计科系 2008年年3月月LR(0)文法 如果文法G的项目集规范族的每个项目集中不存在下述任何冲突项目：移进项目和归约项目并存；多个归约项目并存； 则称文法G为LR(0)文法。 当且仅当一个文法是LR(0)文法时，才能构造出它的不含冲突动作的LR(0)
13、分析表。湖北大学数计学院计科系湖北大学数计学院计科系 2008年年3月月构造LR(0)分析表的算法 设一文法G的项目集规范族CI0,I1,In,令其中每个项目集Ii的下标作为分析器的状态，令包含项目S.S的项目集Ik的下标k为分析器的初态，则构造LR(0)分析表的步骤为： 若项目A.xIi且goto(Ii,x)=Ij,x,则置ACTIONi,x=Si，即“将状态j、符号x移进栈”；但若xVN，则仅置GOTOi,x=j。 若项目A.Ii，对于任何输入符号a($)，则置ACTIONi,a=rj，即“用第j条产生式A进行归约”。 若项目SS.Ik，则置ACTIONk,$=“接收”。 分析表中凡不能用
14、规则填入信息的元素均置上ERROR（用空白表示）。湖北大学数计学院计科系湖北大学数计学院计科系 2008年年3月月构造LR(0)分析表的步骤小结写出给定文法G的拓广文法G；写出文法G的基本LR(0)项目G的LR(0)项目集；利用CLOSURE和GOTO函数，求出相应的LR(0)项目集规范族C；构造识别该文法全部活前缀的DFA；根据算法构造LR(0)分析表。湖北大学数计学院计科系湖北大学数计学院计科系 2008年年3月月7.3 SLR分析表的构造 LR(0)文法所构造出来的识别活前缀的DFA中每个状态（每个项目集）不能包含冲突项目。 许多冲突动作都可以通过考察有关非终结符的FOLLOW集而得到解
15、决，即通过向前查看一个输入符号来协助解决冲突。例如： 冲突项目集合Ii： A.b ,B. ,C.湖北大学数计学院计科系湖北大学数计学院计科系 2008年年3月月 一般，设LR(0)项目集规范族的某个项目集I中含有i个移进项目 A11.a11 A21.a22 Aii.aii 和j个归约项目 B11. B22. Bjj. 若已知集合a1,a2,ai，FOLLOW(B1)，FOLLOW(Bj)两辆不相交，且没有两个FOLLOW集含有$，则I中的冲突动作可通过查看当前输入符号a属于上述j+1个集合中的哪一个集合而获得解决，即 若aa1,a2,ai，则移进a； 若AFOLLOW(Bk），k=1,2,j，
16、则用产生式Bk进行归约； 其它则报错。 这种解决冲突动作的方法成为SLR(1)SLR(1)解决方法解决方法。湖北大学数计学院计科系湖北大学数计学院计科系 2008年年3月月构造SLR(1)分析表的算法 设一文法G的项目集规范族CI0,I1,In,令其中每个项目集Ii的下标作为分析器的状态，令包含项目S.S的项目集Ik的下标k为分析器的初态，则构造SLR(1)分析表的步骤为： 若项目A.xIi且goto(Ii,x)=Ij,x,则置ACTIONi,x=Si，即“将状态j、符号x移进栈”；但若xVN，则仅置GOTOi,x=j。 若项目若项目A.IA.Ii i，对于任何输入符号，对于任何输入符号aFO
17、LLOW(AaFOLLOW(A) )，则置，则置ACTIONi,a=rACTIONi,a=rj j，即，即“用第用第j j条产生式条产生式AA进行归约进行归约”。 若项目SS.Ik，则置ACTIONk,$=“接收”。 分析表中凡不能用规则填入信息的元素均置上ERROR（用空白表示）。能够构造出SLR分析表的文法G称为SLR(1)SLR(1)文法文法湖北大学数计学院计科系湖北大学数计学院计科系 2008年年3月月7.4 规范LR(1)分析表的构造（略） 重新定义项目，使得每个项目包含两个部分，第一部分就是原来的项目本身，第二部分是由一个终结符号（可能为$）组成。重新定义后的项目称为LR(1)LR
18、(1)项目项目，其一般形式为 A.,a 项目中第二部分称为向前看符号向前看符号。 对于的项目A.,a，其作用在于：当相应的状态呈现于栈顶且下一个输入符号为a时，才可选用产生式A，将栈顶的规约到A。湖北大学数计学院计科系湖北大学数计学院计科系 2008年年3月月构造规范LR(1)分析表的算法 设一文法G的LR(1)项目集族CI0,I1,In,令其中每个项目集Ii的下标作为分析器的状态，令包含项目S.S,$的项目集Ik的下标k为分析器的初态，则构造规范LR(1)分析表的步骤为： 若项目A.x,bIi且goto(Ii,x)=Ij,x,则置ACTIONi,x=Si，即“将状态j、符号x移进栈”；但若x
19、VN，则仅置GOTOi,x=j。 若项目若项目A.,aIA.,aIi i，则置，则置ACTIONi,a=rACTIONi,a=rj j，即，即“用第用第j j条产生式条产生式AA进行归约进行归约”。 若项目SS.,$Ik，则置ACTIONk,$=“接收”。 分析表中凡不能用规则填入信息的元素均置上ERROR（用空白表示）。能够构造出规范LR分析表的文法G称为规范规范LR(1)LR(1)文法文法湖北大学数计学院计科系湖北大学数计学院计科系 2008年年3月月7.5 LALR分析表的构造（略） LALR（向前看LR）分析技术是介于规范LR分析器构造法和SLR分析器构造法之间的一种方法。 某些LR(
20、1)项目集称为同心同心，即如果除了向前看符号之外，这些项目集是相同的。在LALR分析方法中，就试图将这些同心项目集合并成一个项目集。湖北大学数计学院计科系湖北大学数计学院计科系 2008年年3月月构造LALR分析表的算法 设一文法G的LR(1)项目集族CI0,I1,In,令其中每个项目集Ii的下标作为分析器的状态，则构造LALR分析表的步骤为： 合并合并C C中的同心集中的同心集，记合并后的项目集族为CJ0,J1,Jm,令其中每个项目集Ji的下标作为分析器的状态，令包含项目S.S,$的项目集Jk的下标k为分析器的初态， 若项目A.x,bJi且goto(Ji,x)=Jj,x,则置ACTIONi,
21、x=Si，即“将状态j、符号x移进栈”；但若xVN，则仅置GOTOi,x=j。 若项目A.,aJi，则置ACTIONi,a=rj，即“用第j条产生式A进行归约”。 若项目SS.Ik，则置ACTIONk,$=“接收”。 分析表中凡不能用规则填入信息的元素均置上ERROR（用空白表示）。能够构造出LALR分析表的文法G称为LALRLALR文法文法湖北大学数计学院计科系湖北大学数计学院计科系 2008年年3月月本章重点LR(0)分析方法SLR(1)分析方法湖北大学数计学院计科系湖北大学数计学院计科系 2008年年3月月练习题： 已知文法G(S)： SaS|bS|a构造该文法的LR(0)项目集规范族；判断该文法是否为SLR(1)文法，若是，构造出SLR(1)分析表。
