《编译原理课件-(7)》由会员分享，可在线阅读，更多相关《编译原理课件-(7)（30页珍藏版）》请在金锄头文库上搜索。
1、第7章 自下而上的LR(k)分析方法,LR(k)分析器是这样一种分析程序：它总是按从左至右方式扫描输入串，并按自下而上方式进行规范归约。在这种分析过程中，它至多只向前查看k个输入符号就能确定当前的动作是移进还是归约；若动作为归约，则它还能唯一地选中一个产生式去归约当前已识别出的句柄（这里称为活前缀）。若该输入串是给定文法的一个句子，则它总可以把这个输入串归约到文法的开始符号；否则报错，指明它不是该文法的一个句子。,7.1 LR(k)文法和LR(k)分析方法 7.2 LR(0)分析表的构造 7.3 SLR分析表的构造 7.4 规范LR(1)分析表的构造 7.5 LALR分析表的构造 7.6 无二
2、义性规则的使用 7.7 小结,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)文法。,LR分析器的逻辑结构 一个输入、一个输出、一个栈、一个驱动程序和一张分析表。,id+id*id$,Sm Xm Sm-1 Xm-1 S0,LR驱动程序,动作 转移 action goto,输出,分析动作表（ACTION）： 移
3、进 ai 和s=gotosm,ai进栈 actionsm,ai=归约 rj : A:=Xm-r+1Xm-r+2Xm 接收 s=gotosm-r , A 错误处理,LR分析器的分析表：分析动作表和goto函数表,GOTO函数表： GOTOsi,xj规定了当状态si面临文法符号xj时所应到达的下一状态。,格局（构形）：（栈中符号序列，剩余输入符号串） 开始：（s0, a1 a2 an$) 中间：（s0x1s1x2s2xmsm ,aiai+1an$),LR分析器的工作过程,1. 若actionsm ,ai=si 则把ai,si=actionsm ,ai推进栈。 格局：（s0x1s1x2s2xmsm
4、aisi , ai+1an$),2. 若actionsm ,ai=r (A:=xm-r+1xm-r+2xm) ,则 格局：（s0x1s1x2s2xm-rsm-r As , ai ai+1an$) 其中，s=gotosm-r ,A,3.若actionsm ，$=accept,则分析结束。,4 .若actionsm,ai=error,则转出错处理程序。,1 E:=E+T 2 E:=T 3 T:=T*F 4 T:=F 5 F:=(E) 6 F:=id,7.2 LR(0)分析表的构造,LR分析方法的基本原理是：把每个句柄（某个产生式的右部）的识别过程划分为若干状态，每个状态从左至右识别句柄中的一个符号
5、，若干个状态就可识别句柄左端的一部分符号。识别了句柄的这一部分就相当于识别了当前规范句型的左起部分规范句型的活前缀。因而，对句柄的识别就变成了对规范句型活前缀的识别。,LR(0)分析程序，即在分析的每一步，仅根据当前的栈顶状态就能确定应执行何种分析动作，而无须向前查看任何输入符号。,规范句型的活前缀,活前缀（Viable Prefix）是指规范句型的一个前缀，它不包含该句型的句柄右边的任何符号。,活前缀和句柄的关系： 1. 活前缀不含有句柄的任何符号， ； 2. 活前缀含有句柄的部分符号， 1 ； 3. 活前缀已含有句柄的全部符号， 。,LR(0)项目,用圆点“”表示识别一个产生式右部符号到达
6、的位子，若有规则 AXYZ,则有下面四个项目： A XYZ A X YZ A X Y Z A X YZ 另：A, A 以上项目称作LR(0)项目。,项目指明在分析过程的某一时刻，已经看到一个产生式的多少。,文法G的拓广文法,给定文法G，S是其开始符号，我们构造一个与S相关的文法G：它包含整个G，而且外加一个新产生式S:=S。其中，S是G的开始符号，称G为G的拓广文法。,A a aVT 移进项目 A B BVN 待归约项目 A 归约项目 SS 接收项目,CLOSURE(I)函数,设I是文法G的一个LR(0)项目集合 closure(I)是从I出发用下面三个规则构造的项目集: 1I中每一个项目都属
7、于closure(I)。 2若项目AB closure(I)且BP 则将B加进closure(I)中。 3重复执行(2)直到closure(I)不再增大为止。,goto(I,X)函数,若I是G的一个LR(0)项目集, X VTVN 则 goto(I,X)=closure(J) 其中, J=AX|当AX I时 goto(I,X)称为转移函数。 项目AX称为AX的后继。,LR(0)项目集规范族,LR(0)项目集规范族的构造 PROCEDURE ITEMS(G ); BEGIN C:=closure( S S) ; REPEAT FOR IC 和 X VT VN 把goto(I,X) 加入到C中 U
8、NTIL C不再增大 END; 最后得到的C就是拓广文法G的LR(0)项目集规范族。,DFA m=(VTVNS, Q项目集规范族， q0= closureS S,Q,=go(I,X) ) 它识别文法G的所有活前缀。,有效项目,项目Ax.y对活前缀ux有效的情况可用于判断：当发现ux已呈现于栈顶时，是应该进行归约还是进行移进。,一个活前缀w的有效项目集正是从项目集规范族对应的DFA初态出发，经由标记为w的路径所到达的那个项目集。,EE+T TT*F TF F(E) Fid,对于活前缀wE+T*，从初态I0出发，经过E+T*路径到达状态集I7,I7： TT*.F F.(E) F.id,E=E=E+
9、T=E+T*F=E+T*id=E+T*F*id E=E=E+T=E+T*F=E+T*(E) E=E=E+T=E+T*F=E+T*id,文法G(S)： SA|B AaAb|c BaBb|d,拓广文G(S)： 0 SS 1 SA 2 SB 3 AaAb 4 Ac 5 BaBb 6 Bd,识别活前缀的DFA,LR(0)文法,如果文法G的项目集规范族的每个项目集中不存在下述任何冲突项目： 移进项目和归约项目并存； 多个归约项目并存； 则称文法G为LR(0)文法。 当且仅当一个文法是LR(0)文法时，才能构造出它的不含冲突动作的LR(0)分析表。,构造LR(0)分析表的算法,设一文法G的项目集规范族CI
10、0,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,$=“接收”。 分析表中凡不能用规则填入信息的元素均置上ERROR（用空白表示）。,构造LR(0)分析表的步骤小结,写出给定文法G的拓广文法G； 写出文法G的基
11、本LR(0)项目G的LR(0)项目集； 利用CLOSURE和GOTO函数，求出相应的LR(0)项目集规范族C； 构造识别该文法全部活前缀的DFA； 根据算法构造LR(0)分析表。,7.3 SLR分析表的构造,LR(0)文法所构造出来的识别活前缀的DFA中每个状态（每个项目集）不能包含冲突项目。 许多冲突动作都可以通过考察有关非终结符的FOLLOW集而得到解决，即通过向前查看一个输入符号来协助解决冲突。,例如： 冲突项目集合Ii： A.b ,B. ,C.,一般，设LR(0)项目集规范族的某个项目集I中含有i个移进项目 A11.a11 A21.a22 Aii.aii 和j个归约项目 B11. B2
12、2. Bjj. 若已知集合a1,a2,ai，FOLLOW(B1)，FOLLOW(Bj)两辆不相交，且没有两个FOLLOW集含有$，则I中的冲突动作可通过查看当前输入符号a属于上述j+1个集合中的哪一个集合而获得解决，即 若aa1,a2,ai，则移进a； 若AFOLLOW(Bk），k=1,2,j，则用产生式Bk进行归约； 其它则报错。 这种解决冲突动作的方法成为SLR(1)解决方法。,构造SLR(1)分析表的算法,设一文法G的项目集规范族CI0,I1,In,令其中每个项目集Ii的下标作为分析器的状态，令包含项目S.S的项目集Ik的下标k为分析器的初态，则构造SLR(1)分析表的步骤为： 若项目A
13、.xIi且goto(Ii,x)=Ij,x,则置ACTIONi,x=Si，即“将状态j、符号x移进栈”；但若xVN，则仅置GOTOi,x=j。 若项目A.Ii，对于任何输入符号aFOLLOW(A)，则置ACTIONi,a=rj，即“用第j条产生式A进行归约”。 若项目SS.Ik，则置ACTIONk,$=“接收”。 分析表中凡不能用规则填入信息的元素均置上ERROR（用空白表示）。,能够构造出SLR分析表的文法G称为SLR(1)文法,7.4 规范LR(1)分析表的构造（略）,重新定义项目，使得每个项目包含两个部分，第一部分就是原来的项目本身，第二部分是由一个终结符号（可能为$）组成。重新定义后的项
14、目称为LR(1)项目，其一般形式为 A.,a 项目中第二部分称为向前看符号。 对于的项目A.,a，其作用在于：当相应的状态呈现于栈顶且下一个输入符号为a时，才可选用产生式A，将栈顶的规约到A。,构造规范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移进栈”；但若xVN，则仅置GOTOi,x=j。 若项目A.,aIi，则置ACTI
15、ONi,a=rj，即“用第j条产生式A进行归约”。 若项目SS.,$Ik，则置ACTIONk,$=“接收”。 分析表中凡不能用规则填入信息的元素均置上ERROR（用空白表示）。,能够构造出规范LR分析表的文法G称为规范LR(1)文法,7.5 LALR分析表的构造（略）,LALR（向前看LR）分析技术是介于规范LR分析器构造法和SLR分析器构造法之间的一种方法。 某些LR(1)项目集称为同心，即如果除了向前看符号之外，这些项目集是相同的。在LALR分析方法中，就试图将这些同心项目集合并成一个项目集。,构造LALR分析表的算法,设一文法G的LR(1)项目集族CI0,I1,In,令其中每个项目集Ii的下标作为分析器的状态，则构造LALR分析表的步骤为： 合并C中的同心集，记合并后的项目集族为CJ0,J1,
