07-LR法分析-kang.ppt

1、编译原理,第7章分析,一起交流 共同进步,2,主要内容,本章学习目标 7.1自下而上分析及LR分析概述 7.2LR分析算法 PPT 1-36 7.3SLR(1) 分析 7.4LR（1）分析 7.5LALR分析 7.6使用二义文法 本章小结 重点习题解析 作业 相关术语的回顾（英文版）,一起交流 共同进步,3,本章学习目标,一学习目标 掌握LR分析器 二课程安排 2学时,本章知识结构,自下而上分析算法 能力强 构造复杂 最常用和最有效的模型-移进归约(动作）,将输入分成两部分：未消化和半消化的,总控程序,output,Input#未消化,半消化的,分析表,产生式表,一起交流 共同进步,6,S E

2、 E T | E + T T int | (E),Reduce: 如能找到一产生式 A w 且栈中的内容是 qw (q 可能为空), 则可以将其归约为 qA.即倒过来用这个产生式. 如上例, 若栈中内容是 (int ，我们使用产生式 T int柄把栈中内容归约为(T Shift: 如不能执行一个归约且在未消化的输入中还有 token ，就把它从输入移到栈中. 如上例,假定栈中内容是 ( ,输入中还有 int+int)#.不能对( 执行一个归约，因为它不和任何产生式的右端匹配.所以把输入的第一个符号移到栈中,于是栈中内容是 (int ，而余留的输入是 +int)# .,一起交流 共同进步,7,R

3、educe的一个特殊情况：栈中的全部内容w归约为开始符号S （即施用 S w） ，且没有余留输入了，意味着已成功分析了整个输入串. 移进归约分析中还会出现一种情况，就是出错，比如当前的token不能构成一个合法句子的一部分，例如上面的文法，试分析 int+)时就会发生错误.,STACK REMAINING INPUT PARSER ACTION 1 (int + int)# Shift 2 ( int + int)# Shift 3 (int + int)# Reduce: T int 4 (T + int)# Reduce: E T 5 (E + int)# Shift 6 (E + int

4、)# Shift 7 (E + int )# Reduce: T int 8 (E + T )# Reduce: E E + T 9 (E )# Shift 10 (E) # Reduce: T (E) 11 T # Reduce: E T 12 E # Reduce: S E 13 S #,一起交流 共同进步,9,冲突,(E + T )# Reduce:E E + T why?不用 E T (E ) # 若使用了E T，在栈中形成的(E+E不是规范句型的活前缀（viable prefixes） （E+E不能和任何产生式的右端匹配 （E+E）不是规范句型 活前缀 是规范句型（右句型）的前缀，但

5、不超过句柄 移进归约分析的栈中出现的内容加上余留输入构成规范句型,一起交流 共同进步,10,冲突及解决方法,冲突： 移进-归约 冲突 归约-归约 冲突 解决方法： Conflict Solutions 改写文法 根据产生式出现的顺序来选择 根据算符的优先级 特定的一种shift-reduce实现技术（分析） L 从左到右扫描输入串 R 最右推导的逆过程 能力强 几乎所有CFG的语言结构都能用LR分析 不需要对文法附加条件,一起交流 共同进步,11,规范推导 规范句型 规范归约,最右推导：在推导的任何一步，其中、是句型，都是对中的最右非终结符进行替换 最右推导被称为规范推导。由规范推导所得的句型

6、称为规范句型。 GS： SE EE+T|T T(E)|intSE T (E) (E+T) (E+int) (T+int) (int+int) 规范归约 假定是G的一个句子，称序列n ,n-1 ,0是 的一个规范归约 如果该序列满足： （1） n = （2）0为文法的开始符号 （3）对任何j,0j=n, j-1是从j经把句柄替换为相应产生式的左部而得到的,一起交流 共同进步,12,LR分析法及基本思想 分析器模型和分析算法 LR分析特征讨论,7.1 分析器,LR分析法,LR分析法是一种自下而上进行规范归约的语法分析方法。,这里L是指从左到右扫描输入符号串。R是指构造最右推导的逆过程。,这种分析法

7、比递归下降分析法、预测分析法和算符优先分析法对文法的限制要少得多。,LR分析法的基本思想:,LR分析法是一种规范归约分析法。,规范归约分析法的关键是在分析过程中如何确定分析栈栈顶的符号串是否形成句柄。,LR分析法的基本思想,一起交流 共同进步,15,分析器模型,LR分析器由3部分组成：总控程序、分析表、分析栈。,一起交流 共同进步,16,LR分析器的工作过程, 在总控程序的控制下，自左向右扫视输入串的各个字符； 按分析表的指示（动作，状态转移）完成相应的分析工作； 分析栈记录的是从开始到目前为止的整个历程； 对当前可能遇到的输入符号进行预测。 分析表是LR分析器的核心，栈顶状态和输入符号是唯一

8、确定的。,一起交流 共同进步,17,LR分析表 GS: (1)S a A c B e (2)A b (3)A Ab (4)B d,一起交流 共同进步,18,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时，要放到栈顶的新状态,一起交流 共同进步,19,分析,GS: (1)S a A c B e (2)A b (3)A Ab (4)

9、B d w=abbcde#,Step states. The rest of inputaction goto 1 0 abbcde# s2 2 02 bbcde# s4 3 024 bcde# r2 goto(3,A) 4 023 bcde# s6 5 0236 cde# r3 goto(3,A) 6 023 cde# s5 7 0235 de# s8 8 02358 e# r4 goto(7,B) 9 02357 e# s9 10 023579 # r1 goto(1,S) 11 01 # acc,GS: (1)S a A c B e (2)A b (3)A Ab (4)Bd w=abbc

10、de#,1) E E + T2) E T 3) T (E)4) T id,一起交流 共同进步,22,id + (id),7.2 LR分析算法,置ip指向输入串w的第一个符号 令S为栈顶状态 a是ip指向的符号 重复 begin if ACTIONS,a=Sj then begin PUSH j,a(进栈) ip 前进(指向下一输入符号) end else if ACTIONS,a=rj (第j条产生式为A) then begin pop | 项 令当前栈顶状态为S push GOTOS,A和A(进栈) end else if ACTIONs,a=acc then return (成功） els

11、e error end.重复,一起交流 共同进步,24,分析程序,例: GS: S a A c B e 1 A b 2 A Ab 3 B d 4 w=abbcde#,一起交流 共同进步,25,文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B d,a,b,b,c,d,e,步骤,符号栈,输入符号串,动作,1） # abbcde# 移进,2） #a bbcde# 移进,4） #aA bcde# 移进,6） #aA cde# 移进,7） #aAc de# 移进,9） #aAcB e# 移进,11） #S # 接受,符号串abbcde是否是GS的子,对输入串abbcde#的移进-

12、规约分析过程,步骤,符号栈,输入符号串,动作,1） # abbcde# 移进 0 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 3,5） #aAb cde# 归约(AAb) 0236 r3 3,8） # aAcd e# 归约(Bd) 02358 r4 7,10） #aAcBe #

13、归约(SaAcBe) 023579 r1 1,状态栈,ACTION,GOTO,文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B d,Si:移进，将状态i和输入符进栈 ri:归约，用第i个产生式归约，同时状态栈与符号栈退出相应个符号，并把GOTO表相应状态和第i个产生式的左部非终结符入栈。,一起交流 共同进步,27,Question,LR分析表是如何构造的？,一起交流 共同进步,28,LR分析表是如何构造的？,Review ：LR分析器的关键部分是分析表的构造。 从给定的上下文无关文法直接构造识别文法所有规范句型活前缀的DFA，然后再将DFA转换成一张LR分析表。,一起交

14、流 共同进步,29,LR分析表是如何构造的？,为了给出构造LR分析表的算法，需要定义一些重要的概念和术语。 文法规范句型的活前缀 1.字符串的前缀是指字符串的任意首部。例如，字符串abc的前缀有：,a,ab,abc。 2. 规范句型活前缀是指规范句型的前缀, 这种前缀不包含句柄右边的任何符号。,一起交流 共同进步,30,活前缀,活前缀 G=(Vn,Vt,P,S),若有S A , 符号串是的前缀,则称是文法G的活前缀. 其中S是对原文法扩充(SS)增加的非终结符. S不出现在任何产生式的右部. 如G=(S,a,SSa,Sa,S),R,一起交流 共同进步,31,Example,推导过程 S aAc

15、Be1 aAcd4e1 aAb3cd4e1 ab2b3cd4e1 可归前缀 活前缀可归前缀 规约时在栈里的句型的前缀规约前可在栈里的规范句型(不含句柄)的前缀 ab2a aAb3a,aA aAcd4a,aA,aAc aAcBe1a,aA,aAc,aAcB,一起交流 共同进步,32,x,5,9,2,14,3,0,6,7,10,11,12,16,15,17,18,S,a,a,a,a,A,A,A,b,c,c,b,d,e,B,图7.3 识别可归前缀的NFA,一起交流 共同进步,33,图7.4 识别可归前缀的DFA,x,2,3,5,7,A,b,a,S,b,c,B,e,d,结论：只要能构造出CFC文法的识

16、别可归前缀的DFA，就可以构造出相应的分析表(Action和Goto表),文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B d,一起交流 共同进步,34,构造文法活前缀DFA的三种方法,根据形式定义求出活前缀的正规表达式，然后由此正规表达式构造NFADFA 求出文法的所有项目，按照一定规则构造识别机活前缀的NFADFA P134：把拓广文法的第一个项目作为初态集的核，通过求核的闭包和转换函数，求出LR（0）项目集规范簇，再由转换函数建立状态之间的链接关系得到识别或前缀的DFA。,一起交流 共同进步,35,分析程序,LR 文法 对于一个cfg 文法, 如果能够构造一张 L

17、R 分析表, 使得它的每一个入口均是唯一的（Sj,rj,acc,空白），则称该 cfg 是LR 文法,一起交流 共同进步,36,分析,特征: 规范的 符号栈中的符号是规范句型的前缀，且不含句柄以后的任何符号(活前缀) 分析决策依据栈顶状态和现行输入符号？识别活前缀的 DFA. 四种技术 LR(0) SLR(1) LR(1) LALR(1),一起交流 共同进步,37,LR(0) 分析,LR(0)文法 能力最弱，理论上最重要 存在FA 识别活前缀 识别活前缀的DFA如何构造 （LR(0)项目集规范族的构造） LR(0)分析表的构造,一起交流 共同进步,38,识别活前缀的DFA,启示:LR分析使用的

18、信息之一是句柄左部的内容. 定义(非终结符的左文)计算可归前缀的基础 LC(A)= | SA, V*, Vt*, 对拓广文法的开始符号S: LC(S)= 若BA 则:LC(A)LC(B). 注：LC(A)表明了在规范推导中在非终结符A左边的符号串的集合。,一起交流 共同进步,39,GS: (0) SS (1) S a A c B e (2)A b (3) A Ab (4)B d,每个非终结符的左文方程组 LC(S)= LC(S)=LC(S). LC(A)=LC(S).a LC(A) LC(B)=LC(S).aAc 化简为： S= S=S A=Sa+A B=SaAc,用代入法求解得： S= S=

19、 A=a+A B=aAc 令 =S，S，A， B，a，A,c 则方程两边都是上的正规式 而A=a+A 即为 A=a | A 由正规式所表示的正规集 得： A=a,一起交流 共同进步,40,GS: (0) SS (1) S a A c B e (2)A b (3) A Ab (4)B d,定义(产生式的LR(0)左文) LR(0)LC(A)=| =且SA , Vt* 有推论：LR(0)LC(A )=LC(A). 则有: LR(0)LC(SS)=S LR(0)(LC(SaAcBe)=aAcBe LR(0)LC(Ab)=ab LR(0)LC(AAb)=aAb LR(0)LC(Bd)=aAcd ( =

20、VnVt)上的正规式,R,一起交流 共同进步,41,构造LR(0)项目集规范族,LR(0)项目集规范族(构成识别一个文法的活前缀的DFA的状态的全体) 。 LR（0）项目或配置（ item or configuration）. 文法每一个产生式的右部添加一个圆点指示识别的位置，圆点右移一位代表LR（0）的一个项目（一个产生式项目的个数为右部符号个数+1）。 A xyz A.xyz Ax.yz Axy.z Axyz. 如：SaAd S.aAd Sa .Ad SaA .d SaAd .,一起交流 共同进步,42,项目的分类,根据圆点所在的位置和圆点后是终结符还是非终结符或为空把项目分为以下几种：

21、归约项目：A 移进项目：Aa，aVT (a是终结符), , V* 以下同 待约项目: AB, BVN 接受项目：S S , S为文法开始符号 形如 A的LR(0)项目只有A 是归约项目,一起交流 共同进步,43,例 GS为: S a A c B e A b A Ab B d 1)构造识别活前缀的DFA 2)构造它的LR(0)分析表。 3)分别给出对输入符号串abbcde和 Abbbce的LR(0)分析步骤。,一起交流 共同进步,44,GS拓广为: S S S a A c B e A b A Ab B d,I0 : S S S a A c B e,I1 : S S ,I2 : S a A c B

22、 e A b A Ab,I3 : S a A c B e A A b,I4 : A b ,I5 : S a A c B e B d,I7 : S a A c B e,I8 : B d ,I9 : S a A c B e ,I6 : A A b ,S,a,A,b,b,c,B,e,d,GL= ab+ cde,一起交流 共同进步,45,活前缀与句柄的关系：,GS: 若S = A = r是的前缀，则称r 是G的一个活前缀 1.活前缀已含有句柄的全部符号，表明产生式A的 右部已出现在栈顶 2.活前缀只含句柄的一部分符号表明A12的右部子串1已出现在栈顶，期待从输入串中看到2推出的符号 3. 活前缀不含有

23、句柄的任何符号，此时期望A的右部所推出的符号串,R,一起交流 共同进步,46,活前缀,与句柄 ,与 LR(0)项目,为刻划这种分析过程中的文法G的每一个产生式的右部符号已有多大一部分被识别（出现在栈顶）的情况，分别用标有圆点的产生式来指示位置。 A刻划产生式A的 右部已出现在栈顶 A12 刻划A12的右部子串1已出现在栈顶，期待从输入串中看到2推出的符号 A 刻划没有句柄的任何符号在栈顶，此时期望A的右部所推出的符号串 对于A的LR(0)项目只有A,一起交流 共同进步,47,构造识别活前缀的DFA,LR（0） 项目集的闭包LOSURE, GO 函数， function CLOSURE (I);

24、 /* I 是项目集*/ J:= I; repeat for J 中的每个项目A .B 和产生式 B ，若B . 不在J中 do 将 B . 加到J中 until 再没有项目加到J中 return J ; GO (I,x) = CLOSURE(J) ; 其中， I:项目集，x: 文法符号， J=任何形如A x. 的项目|A .x I,一起交流 共同进步,48,LR（0） 项目集的闭包LOSURE,若当前处于A XYZ刻划的情况，期望移进 First(Y)中的某些符号，假如有产生式 Y u | w . 那么Y u和Y w这两个项目便是刻划期望移进 First(Y)中的某些符号的情况. A XYZ

25、 Y u Y w 这三个项目对应移进归约分析的同一个状态,这三个项目构成一个配置集, 对应每个配置集，分析表将有一个状态.,一起交流 共同进步,49,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 不再增大 End;,一起交流 共同进步,50,例：文法G: （0）SE (1) EaA (2) EbB (3)

26、AcA (4) Ad (5) BcB (7) Bd LR(0) 项目集规范族（识别G的活前缀的DFA)： I0: SE I1: SE I2: EaA EaA A.cA EbB Ad,一起交流 共同进步,51,I3: EbB I4: Ac.A I5: BcB AcA BcB Bd A .d BcB Bd I6: I7: I8: EaA EbB AcA I9: BcB I10: Ad I11: BcB,一起交流 共同进步,52,LR(0)分析表的构造,假定C=I0, I1,，In，令每个项目集Ik的下标k 为分析器的一个状态，因此，G 的LR(0)分析表含有状态0，1，n。令那个含有项目SS的Ik

27、的下标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, 则置ACTIONk, #为“接受”，简记为“acc”; 若GO (Ik, A)= Ij, A为非终结符，则置GOTO(k, A)=j; 分析表中凡不能用规则1至4填入信息的空白格均置上“出错标志”。,一起交流 共同进步,53,按上述算法构

28、造的含有ACTION和GOTO两部分的分析表，如果每个入口不含多重定义，则称它为文法G的一张LR(0)表。具有LR(0)表的文法G称为一个LR（0）文法。 LR(0)文法是无二义的。,一起交流 共同进步,54,例 文法G:（0）SE (1) EaA (2) EbB (3) AcA (4) Ad (5) BcB (6) Bd,一起交流 共同进步,55,例：（0）SS (1)SrD (2) DD,i (3) DI Real x,y, 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.

29、 Di,一起交流 共同进步,56,NFA,1,3,10,7,8,i,S,r,r,D,4,6,D,一起交流 共同进步,57,例： (0) SS (1)SrD (2) DD,i (3) Di LR（0）项目集规范族 I0: SS I3: Sr D Sr D DDi I1: SS I4: Di I2: SrD I5: DDi DD i I6: DDi Di 其中I3中含有移进/归约冲突 文法不是LR(0)的，如何解决？,一起交流 共同进步,58,SLR(1)技术,若 LR(0) 项目集规范族中有项目集IK含 移进/归约 归约/归约 冲突： IK : .A.b , P . , Q . , 若FOLLO

30、W(Q) FOLLOW(P) = FOLLOWP(P) b = FOLLOW(Q) b = 则解决冲突的SLR(1)技术： action k,b = 移进 对a FOLLOW (P) 则 action k,a =用 P 归约 对a FOLLOW (Q) 则 action k,a =用 Q 归约 能用SLR(1)技术解决冲突的文法称为SLR(1)文法。 SLR(1)文法是无二义的。,一起交流 共同进步,59,SLR表,假定C=I0, I1,，In，令每个项目集Ik的下标k 为分析器的一个状态，因此，G 的SLR分析表含有状态0，1，n。令那个含有项目SS的Ik的下标k为初态。函数ACTION和G

31、OTO可按如下方法构造： 若项目Aa属于Ik且GO (Ik, a)= Ij, a为终结符，则置ACTIONk, a为“把状态j和符号a移进栈”，简记为“sj”; 若项目A属于Ik, 那么，对任何输入符号a, aFOLLOW(A),置ACTIONk, a为“用产生式A进行规约”，简记为“rj”;其中，假定A为文法G的第j个产生式； 若项目SS属于Ik, 则置ACTIONk, #为“接受”，简记为“acc”; 若GO (Ik, A)= Ij, A为非终结符，则置GOTO(k, A)=j; 分析表中凡不能用规则1至4填入信息的空白格均置上“出错标志”。 按上述算法构造的含有ACTION和GOTO两部

32、分的分析表，如果每个入口不含多重定义，则称它为文法G的一张SLR表。具有SLR表的文法G称为一个SLR（1）文法。数字1的意思是，在分析过程中顶多只要向前看一个符号。,一起交流 共同进步,60,实数说明文法的SLR（1）分析表 状态 ACTION GOTO r , i # S D 0 S2 1 1 acc 2 S4 3 3 r1 S5 r1 r1 4 r3 r3 r3 r3 5 S6 6 r2 r2 r2 r2,一起交流 共同进步,61,? SLR,例：文法G: （0）SS (1) SaAd (2) SbAc (3) Saec (4) Sbed (5) Ae LR(0) 项目集规范族（识别G的

33、活前缀的DFA)： I0: SS I1: SS I2: SaAd SaAd Saec SbAc Ae Saec Sbed,一起交流 共同进步,62,? SLR,I3: SbAc I4: I5: Sbed SaAd Saec Ae Ae I6: I7: I8: SbAc Sbed SaAd Ae I9: Saec I10: SbAc I11: Sbed,一起交流 共同进步,63,一起交流 共同进步,64,?,I5: S aec A e S=S=aAd=aed S=S=aec I7: S bed A e S=S=bAc=bec S=S=bed ？信息 哪些输入符号能跟在句柄之后,R,R,R,R,R

34、,R,R,R,R,R,一起交流 共同进步,65,Another example （P142）,GS: (0) SS (1) SL=R (2) SR (3) L *R (4) Li (5) RL LR(0)项目集规范族和G0函数 I1 S S. I6 I0 SS I2 SL=R S L=.R L .*R SL=R R L. R .L L .i SR L*R I3 Li SR RL I4 L* R I7 I5 RL L*R Li L*R L .i I8 RL,一起交流 共同进步,66,(1)不是LR(0)文法 I2 SL=R R L.中存在移进/归约冲突 （2） SLR能否解决I2中的冲突 FOL

35、LOW（R）=#,=与=交不为空 不是SLR（1）文法 SL.=R RL. 若用 RL 归约 则形成 R= 而 R=不是活前缀 ?早知此信息 向前搜索符 LR（1）方法 若 A .B I 则 B . （ B 是一产生式） I 把FIRST（B）中的符号作为用B 归约的搜索符,一起交流 共同进步,67,LR（1）项目 A . ， a LR（K）项目 A . ， a1 a2 aK ,一起交流 共同进步,68,构造LR(1)项目集规范族和G0函数,closure(I)按如下方式构造 (1) I的任何项目属closure(I)； (2)若A1B2，aclosure(I)，B是一产生式，那么对于FIRS

36、T(2a)中的每个终结符b，如果B,b不在closure(I)中，则把它加进去； (3)重复（1）（2），直至closure(I)不再增大。,一起交流 共同进步,69,GO函数： 若I是一个项目集，X是一个文法符号 GO(I, X)= closure(J) 其中 J= 任何形如AX,a的项目A.X,aI LR(I)项目规范族C的构造算法类同LR(0)的，只是初始时： C= closure(SS,#);,一起交流 共同进步,70,LR(1)项目集规范族,I0: SS, # I5: S aec,# S aAd, # A e,d S bAc, # I6: S bAc, # S aec, # I7:

37、S bed, # S bed, # A e,c I1: S S,# I8: S aAd, # I2: S aAd, # I9: S aec, # S aec, # I10: S bAc, # A e, d I11: S bed, # I3: S bAc, # S bed, # Ae,c I4: S aAd, #,一起交流 共同进步,71,LR(1)项目集规范族,I1: SS,# I9 :S L=R. ,# I2: I6: SL=R,# I0: SS,# SL=R,# RL,# SL=R,# RL,# L*R,# SR,# I3: Li,# L*R,=/# SR,# Li,=/# I4: I11

38、: RL,# L*R,=/# L*R,# L*R,=/# RL,# I5: Li,=/# Li,=/# L*R,# RL,=/# Li,# I7 L*R ,=/# I8 RL,#/= I10 I13 I12: Li. RL,# L*R,#,一起交流 共同进步,72,LR(1)分析表的构造,若项目AA属于Ik, 那么 置 ACTIONk, a为“用产生式A进行规约”，简记为“rj”;其中，假定A为文法G的第j个产生式；,一起交流 共同进步,73,规范的LR(1)分析表的构造,假定LR(1)项目集规范族C=I0, I1,，In，令每个项目集Ik的下标k 为分析器的一个状态，G 的LR（1）分析表含

39、有状态0，1，n。 1.令那个含有项目SS ，#的Ik的下标k为状态0（初态）.ACTION表和GOTO表可按如下方法构造 2.若项目A,b属于Ik, 那么置ACTIONk, b为“用产生式A进行规约”，简记为“rj”;(假定A为文法G的第j个产生式) 3.若项目Aa,b属于Ik且GO (Ik, a)= Ij,则置ACTIONk, a为“把状态j和符号a移进栈”，简记为“sj”; 4.若项目SS,#属于Ik, 则置ACTIONk, #为“接受”，简记为“acc”; 5.若GO (Ik, A)= Ij, A为非终结符，则置GOTO(k, A)=j; 分析表中凡不能用规则1至5填入信息的空白格均置

40、上“出错标志”。 按上述算法构造的含有ACTION和GOTO两部分的分析表，如果每个入口不含多重定义，则称它为文法G的一张规范的LR(1)分析表。具有规范的LR(1)表的文法G称为一个LR（1）文法。,一起交流 共同进步,74,LR(1) 文法满足下面两个条件 1.如果一个项目集里有项目 A uxv , a ， x是终结符，那就不会有项目B u, x 2.项目集里所有归约项目 的向前搜索符不相交，即不能同时含有项目 A u, a 和B v , a,一起交流 共同进步,75,LR（K）分析,LR（K）项目 A . ， a1 a2 aK a1 a2 aK 向前搜索符串 移进项目 A . a， a1

41、 a2 aK 待约项目 A . B， a1 a2 aK 归约项目 A . ， a1 a2 aK ,一起交流 共同进步,76,LR(1)比SLR（1）能力强,例2 (0) SS (1)SL=R (2)SR (3)L *R (4)Lid (5)RL不能用SLR（1）技术解决，但能用LR（1）,一起交流 共同进步,77,I1:SS ,#,I5:Li ,=/#,I7:L*R ,=/#,I8:RL ,=/#,I9:SL=R ,#,I3:SR ,#,I12:Li ,#,I10:RL ,#,I13:L*R ,#,I0:S S,# S L=R,# S R,# L *R,=/# L i,=/# R L,#,I4

42、: L *R,=/# R L,=/# L i,=/# L *R,=/#,I6:S L= R,# R L,# L *R,# L i,#,I11:L * R,# R L,# L *R,# L i,#,I2:S L =R,# R L,#,s,R,=,L,R,i,i,*,i,i,R,L,L,R,L,*,*,*,例2的 LR(1)项目集及转换函数,一起交流 共同进步,78,每个SLR（1）文法都是LR（1）的，一个SLR（1）文法的规范LR分析器比其SLR（1）分析器的状态要多。,例 G(S):S BB BaB B b I0:S.S S .BB B .aB B .b I1:S S. I2:S B.B B

43、.aB B.b I3:Ba.B B.aB B.b I4:BaB. I5: Bb. I6: SBB.,一起交流 共同进步,79,I0:S S,# S BB,# B aB,a/b B b,a/b,I1:S S,#,I2:S BB,# B aB,# B b,#,I5:S BB,#,I6:BaB,# B aB,# B b,#,I3:B aB,a/b B aB,a/b B b,a/b,I4:B b,a/b,I7:B b,#,I9:B aB,#,I8:B aB,a/b,s,B,B,a,b,b,b,B,B,a,a,a,LR(1)项目集规范族和转换函数,b,一起交流 共同进步,80,LALR在SLR（1）和L

44、R（1）间寻找折衷办法（状态数目，分析能力）,LALR (lookahead LR) 合并LR（1）项目集规范族的同心集I36 I47 I89（除搜索符外两个集合是相同的）.,I3:B aB,a/b B aB,a/b B b,a/b,I6:B aB,# B aB,# B b,#,I4:B b,a/b,I7:B b,#,I8:B aB,a/b,I9:B aB,#,一起交流 共同进步,81,构造 LALR(1)分析表.方法1-“brute-force”,1.构造文法G的规范 LR(1) 状态. 2.合并同心集的状态. 3.新 LALR(1) 状态的GO函数是合并的同心集状态的GO函数的并. 4. LALR(1)分析表的ACTION 和 GOTO 登录