第六章 LR分析程序及其自动构造.ppt

1、第第6 6章章分析程序及其自动构造分析程序及其自动构造u6.16.1自下而上自下而上分析分析及其及其LRLR分析概述分析概述u6.26.2LR(0)LR(0)分析分析u6.36.3SLR(1)SLR(1)分析分析u6.46.4LRLR（1 1）分析分析u6.56.5LALRLALR分析分析u6.66.6使用二义文法使用二义文法自下而上分析算法 能力强 构造复杂 最常用和最有效的模型-移进归约(动作）总控程序outputInput#栈状态文法符号分析表产生式表将输入分成两部分：未消化和半消化的总控程序outputInput#未消化半消化的分析表产生式表S E E T|E+T T int|(E)R

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

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

4、nt)#Shift7 (E+int )#Reduce:T int8 (E+T )#Reduce:E E+T9 (E )#Shift10(E)#Reduce:T (E)11 T#Reduce:E T12 E#Reduce:S E13 S#8(E+T )#Reduce:E E+T9 why?不用 E T9(E )#若使用了E T，在栈中形成的(E+E不是规范句型的活前缀（viable prefixes）（E+E不能和任何产生式的右端匹配（E+E）不是规范句型 活前缀 是规范句型（右句型）的前缀，但不超过句柄v移进归约分析的栈中出现的内容加上余留输入构成规范句型规范推导规范推导 规范句型规范句型 规

5、范归约规范归约最右推导：在推导的任何一步最右推导：在推导的任何一步，其中其中、是句型，都是对是句型，都是对中中的最右非终结符进行替换的最右非终结符进行替换最右推导被称为规范推导。最右推导被称为规范推导。由规范推导所得的句型称为规范句型由规范推导所得的句型称为规范句型GS：SE E EE+T|T T(E)|EE+T|T T(E)|intintS SE T(E)(E+T)(E+int)(T+int)(int+int)规范归约规范归约假定假定是是G G的一个句子，称序列的一个句子，称序列n n,n-1n-1 ,0 0是是 的一个的一个规范归约规范归约如果该序列满足：如果该序列满足：（1）n n=（2

6、 2）0 0为文法的开始符号为文法的开始符号（3 3）对任何）对任何j,0j=n,j,0j if E then S|if E then S else S如输入if E then if E then S else S分析某一时刻，栈的内容:if E then if E then S而 else 是下一 token 归约还是移进？特定的一种特定的一种shift-reduce实现技术分析分析L R 最右推导最右推导u分析器模型和分析算法分析器模型和分析算法u分析特征讨论分析特征讨论分析分析器模型总控程序outputInput#S1 XmS1X1S0#栈状态文法符号ACTION GOTOLR分析表产生

7、式表ACTION GOTOa c e b d#S A B0 S2 11 acc2 S4 33 S5 S64 r2 r2 r2 r2 r2 r25 S8 76 r3 r3 r3 r3 r3 r37 S98 r4 r4 r4 r4 r4 r49 r1 r1 r1 r1 r1 r1 LR分析算法u置ip指向输入串w的第一个符号令S为栈顶状态 a是ip指向的符号重复 beginif ACTIONS,a=Sj then begin PUSH j,a(进栈)ip 前进(指向下一输入符号)endelse if ACTIONS,a=rj (第j条产生式为A)分析程序分析程序then beginupop|项u令

8、当前栈顶状态为Supush GOTOS,A和A(进栈)endelse if ACTIONs,a=accuthen return(成功）uelse errorend.重复分析程序分析程序u例:GS:S a A c B e 1 A b2 A Ab3 B d4uw=abbcde#uStep states.Syms.The rest of inputaction gotou1 0#abbcde#s2u2 02#a bbcde#s4u3 024#ab bcde#r2 goto(2,A)u4 023#aA s6u5 0236#aAb cde#r3u6 023#aA s5u7 0235#aAc de#s8u

9、8 02358#aAcd e#r4 u9 02357#aAcB s9u10 023579#aAcBe#r1u11 01#S acc文法文法GS：(1)S aAcBe(2)A b(3)A Ab(4)B da b b c de步骤步骤符号栈符号栈输入符号串输入符号串动作动作 1）#abbcde#移进移进 2）#a bbcde#移进移进A 3）#ab bcde#归约归约(Ab)4）#aA bcde#移进移进A 5）#aAb cde#归约归约(AAb)6）#aA cde#移进移进 7）#aAc de#移进移进B 8）#aAcd e#归约归约(Bd)9）#aAcB e#移进移进11）#S#接受接受S10

10、）#aAcBe#归约归约符号串符号串abbcdeabbcde是否是是否是GSGS的子的子对输入串对输入串abbcde#的移进的移进-规约分析过程规约分析过程SaAcBe aAcde aAbcde abbcde步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 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 S911）#S#接受接受 01 acc对输入串对输入串abbcde#的的LR

11、分析过程分析过程 3）#ab bcde#归约归约(Ab)024 r2 3 5）#aAb cde#归约归约(AAb)0236 r3 3 8）#aAcd e#归约归约(Bd)02358 r4 710）#aAcBe#归约归约(SaAcBe)023579 r1 1ACTIONGOTOacebd#SAB0S211acc2S433S5S64r2r2r2r2r2r25S876r3r3r3r3r3r37S98r4r4r4r4r4r49r1r1r1r1r1r1状态栈状态栈ACTIONGOTO文法文法GS：(1)S aAcBe(2)A b(3)A Ab(4)B dSi:移进，将状态移进，将状态i和和输入符输入符进

12、栈进栈ri:归约，用第归约，用第i个产生式归约，同个产生式归约，同时状态栈与符号栈退出相应个符时状态栈与符号栈退出相应个符号，并把号，并把GOTO表相应状态和第表相应状态和第i个产生式的个产生式的左部非终结非终结符入栈。符入栈。分析程序分析程序u推导过程S aAcBe1 aAcd4e1 aAb3cd4e1ab2b3cd4e1u规约时在栈里的句型的前缀规约前可在栈里的规范句型(不含句柄)的前缀ab2aaAb3a,aAaAcd4a,aA,aAcaAcBe1a,aA,aAc,aAcBR分析程序分析程序uLR 文法文法u对于一个对于一个cfg 文法文法,如果能够构造一张如果能够构造一张 LR 分析表分

13、析表,使得它的每一个入口均是唯一的使得它的每一个入口均是唯一的（Sj,rj,acc,空白），则称该空白），则称该 cfg 是是LR 文文法法分析分析u特征特征:规范的规范的符号栈中的符号是规范句型的前缀，符号栈中的符号是规范句型的前缀，且不含句柄以后的任何符号且不含句柄以后的任何符号(活前缀活前缀)分析决策依据分析决策依据栈顶状态和现行栈顶状态和现行输入符号？识别活前缀的输入符号？识别活前缀的 DFA.u四种技术LR(0)SLR(1)LR(1)LALR(1)LR(0)分析分析 LR(0)文法文法 能力最弱，理论上最重要能力最弱，理论上最重要存在存在FA 识别活前缀识别活前缀识别活前缀的识别活前

14、缀的DFA如何构造如何构造（LR(0)项目集规范族的构造）项目集规范族的构造）LR(0)分析表的构造分析表的构造分析分析u活前缀G=(Vn,Vt,P,S),若有S A ,是的前缀,则称是文法G的活前缀.其中S是对原文法扩充(SS)增加的非终结符.?为使S不出现在任何产生式的右部.如G=(S,a,SSa,Sa,S)RR*识别活前缀的识别活前缀的DFAu启示:LR分析使用的信息之一是句柄左部 的内容.u定义(非终结符的左文)LC(A)=|SA,V*,Vt*,对拓广文法的开始符号S:LC(S)=若BA 则:LC(A)LC(B).R*GS:(0)SS (1)S a A c B e (2)A b (3)

15、A Ab (4)B d每个非终结符的左文方程组uLC(S)=uLC(S)=LC(S).uLC(A)=LC(S).a LC(A)uLC(B)=LC(S).aAc化简为：uS=uS=SuA=Sa+A uB=SaAc用代入法求解得：uS=uS=uA=a+A u B=aAc令=S，S，A，B，a，A,c则方程两边都是上的正规式而A=a+A 即为 A=a|A 由正规式所表示的正规集u得：A=a 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

16、(0)LC(SS)=SLR(0)(LC(SaAcBe)=aAcBeLR(0)LC(Ab)=abLR(0)LC(AAb)=aAbLR(0)LC(Bd)=aAcd (=VnVt)上的正规式R*Rx59214306710111216151718SaaaaAAAbccbdeB B DFAx235789641AbaSbcBed构造构造LR(0)项目集规范族项目集规范族uLR(0)项目集规范族项目集规范族(构成识别一个文法的活前缀的构成识别一个文法的活前缀的DFA的状态的全体的状态的全体)。uLR（0）项目或配置（项目或配置（item or configuration）.u-在右端某一位置有圆点的在右端某

17、一位置有圆点的G的产生式的产生式 A xyz A.xyz Ax.yz Axy.z Axyz.如：如：SSaAd aAd S.S.aAd aAd Sa.Ad SSa.Ad SaAaA.d S.d SaAdaAd.活前缀与句柄的关系：活前缀与句柄的关系：uGS:u若若S =A A =r是是的前缀，则的前缀，则u称称r是是G的一个活前缀的一个活前缀u1.活前缀已含有句柄的全部符号，表明产生式活前缀已含有句柄的全部符号，表明产生式A的的 右部右部已出现在栈顶已出现在栈顶u2.2.活前缀只含句柄的一部分符号表明活前缀只含句柄的一部分符号表明A1 12 2的右部的右部子串子串1 1已出现在栈顶，期待从输入

18、串中看到已出现在栈顶，期待从输入串中看到2 2推出的推出的符号符号u3.活前缀不含有句柄的任何符号，此时期望活前缀不含有句柄的任何符号，此时期望A的的右部所推出的符号串右部所推出的符号串R*R活前缀活前缀,与句柄与句柄,与与 LR(0)LR(0)项目项目u为刻划这种分析过程中的文法为刻划这种分析过程中的文法G的每一个产生式的右部符号的每一个产生式的右部符号已有多大一部分被识别（出现在栈顶）的情况，分别用标有已有多大一部分被识别（出现在栈顶）的情况，分别用标有圆点的产生式来指示位置。圆点的产生式来指示位置。A刻划产生式刻划产生式A的的 右部右部已出现在栈顶已出现在栈顶 A1 12 2 刻划刻划A

19、1 12 2的右部子串的右部子串1 1已出现在栈顶，已出现在栈顶，期待从输入串中看到期待从输入串中看到2 2推出的推出的符号符号 A 刻划没有句柄的任何符号刻划没有句柄的任何符号在栈顶在栈顶，此时期望，此时期望A的右部所推出的符号串的右部所推出的符号串u对于对于A的的LR(0)LR(0)项目只有项目只有A构造识别活前缀的DFAuLR（0）项目集的闭包项目集的闭包LOSURE,GO 函数，函数，function CLOSURE(I);/*I 是项目集是项目集*/J:=I;repeat for J 中的每个项目中的每个项目A .B 和产生式和产生式 B ，若若B.不在不在J中中 do 将将 B .

20、加到加到J中中 until 再没有项目加到再没有项目加到J中中return J;GO(I,x)=CLOSURE(J);其中，其中，I:项目集，项目集，x:文法符号，文法符号，J=任何形如任何形如A x.的项目的项目|A .x ILR（0）项目集的闭包项目集的闭包LOSUREu若当前处于A XYZ刻划的情况，期望移进 First(Y)中的某些符号，假如有产生式 Y u|w.那么Y u和Y w这两个项目便是刻划期望移进 First(Y)中的某些符号的情况.uA XYZuY uuY w 这三个项目对应移进归约分析的同一个状态,这三个项目构成一个配置集,对应每个配置集，分析表将有一个状态.LR(0)项

21、目集规范族项目集规范族u计算计算LR（0）项目集规范族项目集规范族u C=I0 ，I1 ,.In u Procedure itemsets(G);u Begin C:=CLOSURE(S.S)u Repeatu For C 中每一项目集中每一项目集I和每一文法符号和每一文法符号x u Do if GO(I,x)非空且不属于非空且不属于Cu Then 把把 GO(I,x)放入放入C中中u Until C 不再增大不再增大uEnd;u例：文法例：文法G G:u（0 0）SE (1)ESE (1)EaA aA (2)E(2)EbBbBu (3)A(3)AcA cA (4)Ad (5)B(4)Ad (

22、5)BcBcBu(7)Bd (7)Bd uLR(0)LR(0)项目集规范族（项目集规范族（识别识别G G的活前缀的的活前缀的DFA)DFA)：I I0:0:S SE IE I1 1:SE:SE I I2 2:Ea:EaA A u E EaA aA A.A.cA cA u EEbB bB A Ad d u u I I3 3:Eb:EbB IB I4 4:Ac.A Ac.A I5:B BcB cB AAcA cA BcBcB B B Bd A.d Bd A.d BcB cB BBd d I6:I7:I I8 8:EaAaA EbBbB AcAcA I9:BcBcB I I1010:Ad:Ad I

23、I1111:B:BcBcB LR(0)分析表的构造u假定假定C=I0,I1,，In，令每个项目集令每个项目集Ik的下标的下标k 为分析器的一为分析器的一个状态，因此，个状态，因此，G 的的LR(0)分析表含有状态分析表含有状态0，1，n。令令那个含有项目那个含有项目SS的的Ik的下标的下标k为初态。为初态。ACTION和和GOTO可可按如下方法构造：按如下方法构造：若项目若项目Aaa属于属于Ik且且GO(Ik,a)=Ij,a为终结符，则为终结符，则置置ACTIONk,a为为“把状态把状态j和符号和符号a移进栈移进栈”，简记为，简记为“sj”;若项目若项目A属于属于Ik,那么，对任何终结符那么，

24、对任何终结符a,置置ACTIONk,a为为“用产生式用产生式A进行规约进行规约”，简记为，简记为“rj”;其中，假定其中，假定A为文法为文法GG的第的第j j个产生式；个产生式；若项目若项目SSS属于属于Ik,则置则置ACTIONk,#为为“接受接受”，简，简记为记为“acc”;若若GO(Ik,A)=Ij,A为非终结符，则置为非终结符，则置GOTO(k,A)=j;分析表中凡不能用规则分析表中凡不能用规则1至至4填入信息的空白格均置上填入信息的空白格均置上“出出错标志错标志”。u按上述算法构造的含有按上述算法构造的含有ACTION和和GOTO两部分的分两部分的分析表，如果每个入口不含多重定义，则

25、称它为文法析表，如果每个入口不含多重定义，则称它为文法G的一张的一张LR(0)表。具有表。具有LR(0)表的文法表的文法G称为一个称为一个LR（0）文法。文法。uLR(0)文法是无二义的。文法是无二义的。ACTION GOTOa c b d#E A B0 S2 S3 11 acc2 S4 S10 63 S5 S11 74 S4 S10 85 S5 S11 9 6 r1 r1 r1 r1 r17 r2 r2 r2 r2 r28 r3 r3 r3 r3 r3 r39 r5 r5 r5 r5 r5 r510 r4 r4 r4 r4 r4 r411 r6 r6 r6 r6 r6 r6 LR(0)LR(

26、0)项目项目根据根据圆点所在的位置圆点所在的位置和和圆点后圆点后是是终结符终结符还是还是非终结符非终结符或为或为空空把项目分为以把项目分为以下几种：下几种：移进移进项目，形如项目，形如 A a a是是终结符终结符,V*以下同以下同待约待约项目，形如项目，形如 A B 归约归约项目，形如项目，形如 A 接受接受项目，形如项目，形如 S S A的的LR(0)LR(0)项目只有项目只有A 是是归约归约项目项目作用？作用？u例：（例：（0 0）SS (1)SS (1)SSrDrDu (2)DD,i (3)Di(2)DD,i (3)DiuLRLR（0 0）项目项目u1.1.SSS 2.SSS 2.SS

27、3.S 3.SrD rD u4.Sr4.SrD 5.SD 5.SrDrD 6.D 6.DD,i D,i u7.DD7.DD,i 8.DD,i 8.DD,i 9.DD,ii 9.DD,i u10.D10.Di 11.Dii 11.Di NFA13107859112 iSrrD46 D,u例：（例：（0 0）SS (1)SS (1)SSrDrDu(2)DD,i (3)Di(2)DD,i (3)DiuLRLR（0 0）项目集规范族项目集规范族uI I0 0:S:SS IS I3 3:Sr D:Sr Du S Sr D DDr D DDi iuI I1 1:SS:SS I I4 4:Di:Di uI

28、I2 2:Sr:SrD ID I5 5:DD:DDi i u D DD i ID i I6 6:D:DDiDi u D Di iu其中其中I I3 3中含有移进中含有移进/归约冲突归约冲突u 文法不是文法不是LR(0)LR(0)的，如何解决？的，如何解决？SLR(1)技术u若若 LR(0)项目集规范族中有项目集项目集规范族中有项目集IK含含 移进移进/归约归约 归约归约/归约归约u 冲突：冲突：uIK :.A.b ,.b ,P .,Q .,u若若FOLLOWQA)FOLLOW(P)=uFOLLOWP(P)b =u FOLLOW(Q)b=u则解决冲突的SLR(1)技术：u action k,b

29、=移进u对a FOLLOW(P)则 action k,a =用 P 归约归约 u对a FOLLOW(Q)则 action k,a =用 Q 归约归约u能用能用SLR(1)技术技术解决冲突的文法称为SLR(1)文法。uSLR(1)文法是无二义的。SLR表表u假定假定C=I0,I1,，In，令每个项目集令每个项目集Ik的下标的下标k 为分析器的一个状态，因此，为分析器的一个状态，因此，G 的的SLR分析表含有状态分析表含有状态0，1，n。令那个含有项目令那个含有项目SS的的Ik的下标的下标k为初态。函数为初态。函数ACTION和和GOTO可按如下方法构造：可按如下方法构造：若项目若项目Aaa属于属

30、于Ik且且GO(Ik,a)=Ij,a为终结符，则置为终结符，则置ACTIONk,a为为“把状态把状态j和符号和符号a移进栈移进栈”，简记为，简记为“sj”;若项目若项目A属于属于Ik,那么，对任何输入符号那么，对任何输入符号a,aFOLLOW(A),FOLLOW(A),置置ACTIONk,a为为“用产生式用产生式A进行规约进行规约”，简记为，简记为“rj”;其中，其中，假定假定A为文法为文法GG的第的第j j个产生式；个产生式；若项目若项目SSS属于属于Ik,则置则置ACTIONk,#为为“接受接受”，简记为，简记为“acc”;若若GO(Ik,A)=Ij,A为非终结符，则置为非终结符，则置GO

31、TO(k,A)=j;分析表中凡不能用规则分析表中凡不能用规则1至至4填入信息的空白格均置上填入信息的空白格均置上“出错标志出错标志”。u按上述算法构造的含有按上述算法构造的含有ACTION和和GOTO两部分的分析表，如果每个入两部分的分析表，如果每个入口不含多重定义，则称它为文法口不含多重定义，则称它为文法G的一张的一张SLR表。具有表。具有SLR表的文法表的文法G称为称为一个一个SLR（1）文法。数字文法。数字1的意思是，在分析过程中顶多只要向前看一个符号。的意思是，在分析过程中顶多只要向前看一个符号。u实数说明文法的实数说明文法的SLR（1）分析表分析表u 状态状态 ACTION GOTO

32、u r ,i#S Du 0 S2 1 u 1 accu 2 S4 3u 3 r1 S5 r1 r1u 4 r3 r3 r3 r3u 5 S6u 6 r2 r2 r2 r2?SLRu例：文法例：文法G G:u（0 0）SS (1)SSS (1)SaAd aAd (2)S(2)SbAcbAcu (3)S(3)Saec aec (4)Sbed (5)Ae(4)Sbed (5)AeuLR(0)LR(0)项目集规范族（项目集规范族（识别识别G G的活前缀的的活前缀的DFA)DFA)：I I0:0:S SS IS I1 1:SS:SS I I2 2:Sa:SaAd Ad u S SaAd aAd SaSa

33、ec ec u SSbAc bAc AAe e u S Saec aec u SSbedbedu?SLRu I I3 3:Sb:SbAc IAc I4 4:I5:u Sb Sbed Sed SaAaAd d Saeaec c u A Ae Ae e Ae u u I6:I7:I I8 8:u SSbAbAc c SbeSbed d SSaAdaAdu Ae Ae u uI9:Saecaec I I1010:S:SbAcbAc I I1111:Sbed:Sbed ACTION GOTOa c e b d#S A 0 S2 S3 11 acc2 S5 43 S7 64 S85 r5 r5S9 r5

34、 r5 r5 r5 6 S107 r7 r7 r7 r7 r7 S11 r78 r1 r1 r1 r1 r1 r19 r3 r3 r3 r3 r3 r310 r2 r2 r2 r2 r2 r211 r4 r4 r4 r4 r4 r4?u I I5 5:S:S aeaec c u A A ee u S=S=S=aAdaAd=aed aed u S=S=S=S=aec aec u I I7 7:S:S bebed d u A A eeu S=S=S=S=bAcbAc=becbecu S=S=bed S=S=bed u？信息？信息 哪些输入符号能跟在句柄之后哪些输入符号能跟在句柄之后RRRRRRRR

35、RRAnother exampleuGS:u(0)SS (1)SL=R (2)SRL=R (2)SRu(3)L(3)L*R (4)Li (5)RLR (4)Li (5)RLuLR(0)LR(0)项目集规范族和项目集规范族和G0G0函数函数uI I1 1 S S.I S S.I6 6 uI0 SS IS I2 2 SL SL=R S L=.R L.=R S L=.R L.*R Ru S SL=R R L.R.L L.iL=R R L.R.L L.iu S SR R u L L*R IR I3 3 u L Li SRi SRu R RL IL I4 4 u L L*R I R I7 7uI I5

36、5 R RL LL L*R R uLiLi L L*R R u L.i I L.i I8 8 RL RLu(1)(1)不是不是LR(0)LR(0)文法文法 u I I2 2 SL SL=R R L.=R R L.中存在移进中存在移进/归约冲突归约冲突u（2 2）SLR能否能否解决解决I I2 2中的冲突中的冲突u FOLLOWFOLLOW（R R）=#,=#,=与与=交不为空交不为空 不是不是SLR（1）文法文法u SL.=R RL.L.=R RL.若用若用 RL L 归约归约 则形成则形成u R=R=而而 R=R=不是活前缀不是活前缀?早知此信息早知此信息 u向前搜索符向前搜索符 LR（1）

37、方法方法u若若 A .B Iu则则 B .（B 是一产生式）是一产生式）Iu把把FIRST（B）中的符号作为用中的符号作为用B 归约的搜索符归约的搜索符uLR（1）项目项目 A .，a uLR（K）项目项目 A .，a1 a2 aK 构造构造LR(1)项目集项目集规范族和规范族和G0G0函数函数closure(I)按如下方式构造按如下方式构造u(1)I的任何项目属的任何项目属closure(I)；u(2)若若A1 1BB2 2，aaclosure(I)，B是一产生式，那么对是一产生式，那么对于于FIRST(2 2a a)中的每个终结符中的每个终结符b，如果如果B,b,b不在不在closure(

38、I)中，则把它加进去；中，则把它加进去；u(3)重复（重复（1）（）（2），直至），直至closure(I)不再增大。不再增大。GO函数：函数：u若若I是一个项目集，是一个项目集，X是一个文法符号是一个文法符号uGO(I,X)=closure(J)u其中其中 J=任何形如任何形如AXX,a,a的项目的项目A.X,aI.X,aIuLR(I)LR(I)项目规范族项目规范族C C的构造算法类同的构造算法类同LR(0)LR(0)的，只是初始时：的，只是初始时：uC=closure(SSS,#);S,#);LR(1)项目集规范族项目集规范族uI0:S SS,S,#I5:S aeaec,c,#u S aA

39、daAd,#A ee,d ,d u S S bAcbAc,#I6:S bAbAc,c,#u S aecaec,#I7:S bebed,d,#u S bed,bed,#A ee,c ,c uI I1 1:S:S SS,#I I8 8:S:S aAdaAd,#uI2:S aaAd,Ad,#I9:S aecaec,#u S aaecec,#I10:S bAcbAc,#u A e,d Ie,d I1111:S bedbed,#uI3:S bbAc,Ac,#u S bbed,ed,#u Ae,c e,c uI I4 4:S:S aAaAd,d,#LR(1)项目集规范族项目集规范族uI I1 1:SS:S

40、S,#I9:S L=R.,#,#I9:S L=R.,#u I I2:2:I I6 6:SL=:SL=R,#R,#uI I0 0:S:SS,#SLS,#SL=R,#R=R,#RL,#L,#u S SL=R,#RLL=R,#RL,#L,#L*R,#R,#u S SR,#IR,#I3 3:L:Li,#i,#u L L*R,=/#SRR,=/#SR,#,#u L Li,=/#Ii,=/#I4 4:I I1111:u R RL,#LL,#L*R,=/#LR,=/#L*R,#R,#u L L*R,=/#RR,=/#RL,#L,#uI I5 5:Li:Li,=/#L,=/#Li,=/#Li,=/#L*R,#

41、R,#u R RL,=/#LL,=/#Li,#i,#uI I7 7 LL*R R,=/#I,=/#I8 8 RL RL,#/=I,#/=I1010 I I1313uI12:Li.RLI12:Li.RL,#L,#L*R R,#,#LR(1)分析表的构造u若项目若项目AAA属于属于Ik,那么那么 置置 ACTIONk,a为为“用产生式用产生式A进行规约进行规约”，简记为，简记为“rj”;其中，假定其中，假定A为文法为文法GG的第的第j j个产生式；个产生式；uAt the heart of the table construction is the notion of an LR(0)configuration or item.A configuration is a production of the grammar with a dot at someuposition on its right side.For example,A XYZ gives four items:uA XYZuA XYZuA XYZuA XYZ