编译原理 之 LR分析程序及其构造.ppt

1、第7章分析程序及其构造,自下而上分析及其LR分析概述 LR (0) 分析 SLR(1) 分析 LR（1）分析 LALR分析 使用二义文法,自底向上分析方法是一种移进-归约过程. 分析栈的栈顶符号形成句柄时-归约. 自底向上分析方法的关键问题-确定句柄. LR分析的归约过程是规范（最右）推导的逆过程. LR分析过程是一种规范（最左）归约过程. LR分析方法对文法的限制少，速度快. LR分析器的构造工作量大.,7.1 自下而上的语法分析概述,例：文法G： S cAd A ab A a识别输入串w=cabd是否该文法的句子,S AA c a b d c a b d c d 归约过程构造的推导： cA

2、d cabd S cAd,(1) S cAd (2) A ab (3)A a识别输入串w=cabd是否为该文法的句子自下而上的语法分析,对串cabd的分析中，如果不是选择ab用产生式(2),而是选择a用产生式(3)将a归约到了A，那么在cAbd中无法找到一个可归约串了，最终就达不到归约到S的结果，因而也无从知道cabd是一个句子. 在自下而上的分析方法中如何识别可归约串？ 在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”,c A b d a,文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B d,a,b,b,c,d,e,

3、步骤,栈,余留输入符号串,动作,1） # abbcde# 移进,2） #a bbcde# 移进,4） #aA bcde# 移进,6） #aA cde# 移进,7） #aAc de# 移进,9） #aAcB e# 移进,11） #S # 接受,符号串abbcde是否是GS的句子,对输入串abbcde#的移进-归约分析过程,刻画“可归约串”,文法GS 句型的短语 S A且 A ，则称是句型相对于非终结符A的短语 句型的直接短语 若有A ，则称是句型相对于非终结符A 的直接短语 句型的句柄 一个句型的最左直接短语称为该句型的句柄,例 ：i*i+i 的短语、直接短语和句柄,E E + T T F T

4、* F i3 短语：i1* i2+ i3， i1* i2 ， F i2 i1 ， i2 ， i3 。 i1 直接短语： i1 ， i2 ， i3 。句柄： i1,GE：EE+T|T TT*F|F F(E)|i 句型：i*i+i,自下而上的语法分析在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”,算符优先选择“可归约串”是最左素短语（至少含有一个终结符的最左边的短语，且这个短语不包含别的短语） 规范归约选择“可归约串”是句型的句柄,GE：EE+T|T TT*F|F F(E)|i,句型 i*i+i 的自下而上分析，总是归约当前句型的句柄形成的规范

5、推导序列： EE+TE+FE+iT+iT*F+iT*i+iF*i+i i*i+i 句型 i*i+i 的自下而上分析总是归约当前句型的最左素短语形成的推导： ET+FT+iF*F+iF*i+i i*i+i,分析器模型,总控程序,output,Input #,Sn,Xm, S1, X1,S0,#,栈,状态,文法符号,ACTION,GOTO,LR分析表,产生式表,LR分析使用两张表,ACTION表 告诉分析器：栈顶状态为S, 当前输入符号是a时做什么: 1. ACTIONS,a= Sj 2. ACTIONS,a=rj (第j条产生式为A) 3. ACTIONS,a=acc 4. ACTIONS,a=

6、 error GOTO表 GOTOS,A栈顶状态为S，归约之后的非终结符為A时，要放到栈顶的新状态,步骤,符号栈,输入符号串,动作,1） # abbcde# 移进 0 action0,a=S2,2） #a bbcde# 移进 02 S4,4） #aA bcde# 移进 023 S6,6） #aA cde# 移进 023 S5,7） #aAc de# 移进 0235 S8,9） #aAcB e# 移进 02357 S9,11） #S # 接受 01 acc,对输入串abbcde#的LR分析过程,3） #ab bcde# 归约(Ab) 024 r2 goto2,A=3,5） #aAb cde# 归

7、约(AAb) 0236 r3 goto2,A= 3,8） #aAcd e# 归约(Bd) 02358 r4 goto5,B= 7,10） #aAcBe # 归约(SaAcBe) 023579 r1 goto0,S= 1,状态栈,ACTION,GOTO,文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B d,Si:移进，将状态i和输入符进栈 ri:归约，用第i个产生式归约，同时状态栈与符号栈退出相应个符号，并把GOTO表相应状态和第i个产生式的左部非终结符入栈。,7.2 LR(0) 分析,构造DFA识别规范句型特定前缀(就到句柄为止). LR(0)项目集规范族的构造 LR(

8、0)分析表的构造 LR(0)语法分析过程,7.2.1可归前缀、活前缀,例: GS: S aAcBe 1 A b2 A Ab3 B d4 w=abbcde#,推导过程 S aAcBe1 aAcd4e1 aAb3cd4e1 ab2b3cd4e1 每次归约前句型的前部分依次为: ab2 aAb3 aAcd4 aAcBe1 把规范句型的这种前部分串称为可归前缀。,句柄位于可归前缀之中 每次归约前句型的所有前缀 , a, ab2 , a, aA, aAb3 , a, aA, aAc, aAcd4 , a, aA, aAc, aAcB, aAcBe1 规范句型中形成可归前缀之前（包括可归前缀）的所有前缀都

9、称为活前缀。 规范归约中已分析的部分（LR）都是规范句型的活前缀（规范句型正确部分）,7.2.2构造识别活前缀的DFA,为刻划这种分析过程中的文法G的每一个产生式的右部符号已有多大一部分被识别（出现在栈顶）的情况，分别用标有圆点的产生式来指示位置。 A刻划产生式A的右部已出现在栈顶 A12 刻划A12的右部子串1已出现在栈顶，期待从输入串中看到2推出的符号 A 刻划没有句柄的任何符号在栈顶，此时期望A的右部所推出的符号串,LR(0)项目,LR（0）项目或配置（ item or configuration）. 右端某一位置有圆点的G的产生式 对A xyz 则有 A xyz Axyz Axyz A

10、xyz 如：SaAd SaAd SaAd SaAd SaAd 对于 A LR(0)项目只有A,LR(0)项目集,若当前处于A XYZ的情况，期望移进 First(Y)中的某些符号，假如有产生式 Y u | w, 那么Y u和Y w这两个项目便是刻划期望移进 First(Y)中的某些符号的情况. A XYZ Y u Y w 这三个项目对应移进归约LR分析的同一个状态,这三个项目构成一个项目集, 对应每个项目集，分析表将有一个状态。,LR(0) 项目集的闭包CLOSURE,CLOSURE (I); /* I 是项目集*/ Repeat 对I中每个形如AB的项目，将项目B加入CLOSURE (I)

11、until 再没有项目加到CLOSURE (I)中 ;,GO 函数状态转换函数,GO (I, x) = CLOSURE(J) ; 其中， I: 包含每个项目集的状态， x: 文法符号，x VNVT J=任何形如Ax的项目|Ax I， J称为“核”.,LR(0)项目集规范族,计算LR(0)项目集规范族 C=I0, I1, . , In Procedure itemsets(G); Begin C := CLOSURE (S S) Repeat For C 中每一项目集I和每一文法符号x Do if GO(I,x) 非空且不属于C Then 把 GO(I,x) 放入C中 Until C 不再增大

12、End;,构造识别一个文法的活前缀的DFALR(0)项目集规范族的构造,文法G: (0) SE (1) EaA (2) EbB (3) AcA (4) Ad (5) BcB (6) Bd,该文法的项目有： 1 SE 10 Ad 2 SE 11 EbB 3 EaA 12 EbB 4 EaA 13 EbB 5 EaA 14 BcB 6 AcA 15 BcB 7 AcA 16 BcB 8 AcA 17 Bd 9 Ad 18 Bd,LR(0)项目集规范族的构造步骤,置项目SS为初态集的核，然后对核求闭包CLOSURE(SS) 得到初态集的项目集. 对初态集或其它所构造的项目集应用转换函数GO(I,X)

13、=CLOSURE(J)求出新的状态J的项目集. 重复直到不出现新的项目集为止.,该文法的项目有： 1 SE 10 Ad. 2 SE 11 EbB 3 EaA 12 EbB 4 EaA 13 EbB 5 EaA 14 BcB 6 AcA 15 BcB 7 AcA 16 BcB 8 AcA 17 Bd 9 Ad 18 Bd,I5: BcB BcB Bd,I6: EaA,I7 : EbB,I8: AcA,I9 : BcB,I10: Ad,I11 : Bd,I3: EbB BcB Bd,I4: AcA AcA A d,I0 : SE EaA EbB,I1: SE,I2: EaA AcA Ad,E,b,

14、c,B,c,B,d,d,A,d,d,A,a,c,c,LR(0)分析表的构造,假定C=I0, I1, ，In，令每个项目集Ik的下标k 为分析器的一个状态，因此，G的LR(0)分析表含有状态0，1，n。令那个含有项目SS的Ik的下标k为初态。ACTION和GOTO可按如下方法构造： 若项目Aa属于Ik且GO (Ik, a)= Ij, a为终结符，则置ACTIONk, a为“把状态j和符号a移进栈”，简记为“Sj”; 若项目A属于Ik, 那么，对任何终结符a, 置ACTIONk, a为“用产生式A进行规约”，简记为“rj”;其中，假定A为文法G的第j个产生式； 若项目SS属于Ik, 则置ACTIO

15、Nk, #为“接受”，简记为“acc”; 若GO (Ik, A)= Ij, A为非终结符，则置GOTO(k, A)=j; 分析表中凡不能用规则1至4填入信息的空白格均置上“出错标志”。,例 文法G: (0) S E (1) EaA (2) EbB (3) AcA (4) Ad (5) BcB (6) Bd ACTION GOTO a c b d # E A B 0 S2 S3 1 1 acc 2 S4 S10 6 3 S5 S11 7 4 S4 S10 8 5 S5 S11 9 6 r1 r1 r1 r1 r1 7 r2 r2 r2 r2 r2 8 r3 r3 r3 r3 r3 9 r5 r5

16、 r5 r5 r5 10 r4 r4 r4 r4 r4 11 r6 r6 r6 r6 r6,I5: BcB BcB Bd,I6: EaA,I7 : EbB,I8: AcA,I9 : BcB,I10: Ad,I11 : Bd,I3: EbB BcB Bd,I4: AcA AcA A d,I0 : SE EaA EbB,I1: SE,I2: EaA AcA Ad,E,b,c,B,c,B,d,d,A,d,d,A,a,c,c,LR(0)文法,按上述算法构造的含有ACTION和GOTO两部分的分析表，如果每个入口不含多重定义（每个单元格的元素是惟一的），则称它为文法G的一张LR(0)表。具有LR(0)表

17、的文法G称为LR(0)文法. LR(0)文法是无二义的.,LR分析使用两张表,ACTION表 告诉分析器：栈顶状态为S, 当前输入符号是a时做什么: 1. ACTIONS,a= Sj 2. ACTIONS,a=rj (第j条产生式为A) 3. ACTIONS,a=acc 4. ACTIONS,a= error GOTO表 GOTOS,A栈顶状态为S，归约之后的非终结符為A时，要放到栈顶的新状态,LR分析算法,置ip指向输入串w的第一个符号 令S为栈顶状态 a是ip指向的符号 重复 begin if ACTIONS,a=Sj then begin PUSH j(进栈) ip 前进(指向下一输入符

18、号) end else if ACTIONS,a=rj (第j条产生式为A),LR分析算法(continue),then begin pop | 项 令当前栈顶状态为S push GOTOS,A end else if ACTIONs,a=acc then return (成功） else error end.重复,步骤,符号栈,输入符号串,动作,1） # abbcde# 移进 0 action0,a=S2,2） #a bbcde# 移进 02 S4,4） #aA bcde# 移进 023 S6,6） #aA cde# 移进 023 S5,7） #aAc de# 移进 0235 S8,9） #

19、aAcB e# 移进 02357 S9,11） #S # 接受 01 acc,对输入串abbcde#的LR分析过程,3） #ab bcde# 归约(Ab) 024 r2 goto2,A=3,5） #aAb cde# 归约(AAb) 0236 r3 3,8） # aAcd e# 归约(Bd) 02358 r4 7,10） #aAcBe # 归约(SaAcBe) 023579 r1 1,状态栈,ACTION,GOTO,文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B d,Si:移进，将状态i和输入符进栈 ri:归约，用第i个产生式归约，同时状态栈与符号栈退出相应个符号，并把

20、GOTO表相应状态和第i个产生式的左部非终结符入栈。,LR(0)项目分类,根据圆点所在的位置和圆点后是终结符还是非终结符或为空把项目分为以下几种： 移进项目，形如 A a a是终结符, , V* 待约项目，形如 A B 归约项目，形如 A 接受项目，形如 S S A的LR(0)项目只有A 是归约项目,项目集中的两种冲突,移近-归约冲突 A a, a是终结符 B 归约-归约冲突 A B,例：对文法GS的LR分析,GS为: S aAcBe A b A Ab B d 1)构造识别活前缀的DFA 2)构造它的LR(0)分析表。 3)分别给出对输入符号串abbcde和 Abbbce的LR(0)分析步骤。

21、,GS拓广为: S S S aAcBe A b A Ab B d,I0 : S S S aAcBe,I1 : S S ,I2 : S a AcBe A b A Ab,I3 : S aA cBe A A b,I4 : A b ,I5 : S aAcBe B d,I7 : S aAcB e,I8 : B d ,I9 : S aAcBe ,I6 : A Ab ,S,a,A,b,b,c,B,e,d,GL= ab+ cde,例 GS的LR(0)分析表,Step states. Syms. The rest of inputaction goto 1 0 # abbcde# s2 2 02 #a bbcd

22、e# s4 3 024 #ab bcde# r2 3 4 023 #aA bcde# s6 5 0236 #aAb cde# r3 3 6 023 #aA cde# s5 7 0235 #aAc de# s8 8 02358 #aAcd e# r4 7 9 02357 #aAcB e# s9 10 023579 #aAcBe # r1 1 11 01 #S # acc,对输入串abbcde#的分析过程,Step states. Syms. The rest of inputaction goto 1 0 # abbce# s2 2 02 #a bbce# s4 3 024 #ab bce# r

23、2 3 4 023 #aA bce# s6 5 0236 #aAb ce# r3 3 6 023 #aA ce# s5 7 0235 #aAc e# 出错 说明abbce#不是 文法 GS的句子,对输入串abbce#的分析过程,7.3 SLR(1)分析技术,例1： (0) SS (1) SrD (2) DD,i (3) Di LR（0）项目 1) SS 2) SS 3) SrD 4) SrD 5) SrD 6) DD,i 7) DD,i 8) DD,i 9) DD,i 10) Di 11) Di,LR（0）项目集规范族,I0: SS I3: SrD SrD DD,i I1: SS I4: Di

24、 I2: SrD I5: DD,i DD,i I6: DD,i DI I3: SrD 归约项目 DD,i 移进项目,I3: SrD DD,i例1文法的LR(0)分析表有多重入口,状态 ACTION GOTO r , i # S D 0 S2 1 1 acc 2 S4 3 3 r1 S5 r1 r1 r1 4 r3 r3 r3 r3 5 S6 6 r2 r2 r2 r2,I3: SrD DD,i 其中I3中含有移进/归约冲突 文法不是LR(0)的，如何解决？ 当用句柄rD归约成S时，S的后跟符号集合中不包含当前所有移进项目的移进符号的集合时，则这种移进/归约冲突便可解决.例中S的后跟符号集#,移进项目只有一个”,”，这样在状态I3,当遇到”#”时归约，遇到”,”时移进.,如果 LR(0) 项目集规范族中某个项目集IK含 移进/归约， 归约/归约冲突： IK : .A.b , P . , Q . , 若FOLLOW(Q) FOLLOW(P) = FOLLOW(P) b = FOLLOW(Q) b = 则解决冲突的方法： action k,b = 移进 对a FOLLOW (P) 则 action k,a =用 P 归约 对c FOLLOW (Q) 则 action k,c =用 Q 归约,一般地，当在状态I含有m