1、程序设计语言与编译第一节第一节 引言引言自下而上分析：从输入串出发，归约，直至开始符方法：采用栈，在移进的过程中，观察栈顶是否形成某个产生式的一个候选 程序设计语言与编译 G(S)：SSAS Sb AccA Aa看输入串bccab的归约过程一一.分析树分析树bScSccSaccSAccSASbASSASS符号栈符号栈 程序设计语言与编译SSSAbccAbaSbAcAacAaSb输入串输入串bccabbccab分析树的形成分析树的形成 程序设计语言与编译分析树的剪枝过程分析树的剪枝过程SSSAbccA baSSSAccA baSSSAccA bSSSAccAbSSSAbSSSA 程序设计语言与编
2、译 关键问题关键问题：如何判断栈顶符号串是否形 成可归约串、如何归约？当对不同的归约串进行归约，即形成了 不同不同的自下而上语法分析方法。程序设计语言与编译 设有文法G，S是开始符号，设是G的一个句型，若有 S且A 则称是句型关于A的；+在上面定义中，如果A直接推出,即A，则称是句型关于A的；一个句型的最左直接短语称为；二二.回顾几个核心概念回顾几个核心概念程序设计语言与编译E EE ET T+T TT TF FF Fi i*G(E)EE+T|T TT*F|F F(E)|i求T*F+i的短语、直接短语、句柄利用推导树判断句型的短语利用推导树判断句型的短语 程序设计语言与编译 ：文法：文法G G
3、某句型的一个短语某句型的一个短语 是是，当且仅，当且仅当它至少含有一个终结符，且除它自身之外不再含更当它至少含有一个终结符，且除它自身之外不再含更小的素短语；小的素短语；：在具有多个素短语的句型中处于最左边的：在具有多个素短语的句型中处于最左边的那个那个；E E1 1E E2 2+T T2 2T T1 1T T3 3*F F2 2F F1 1i i1 1F F3 3i i2 2程序设计语言与编译SSSAbccA baSSSAccA baSSSAccA bSSSAccAbSSSAbSSSA 程序设计语言与编译 假定是文法G的一个句子,序列n,n-1,0满足下述条件时称为规范归约。(1)n=;(2
4、)0为文法的开始符,即0=S;(3)对i,0in,i-1是从i经把句柄替换为相应产生式的左部符号而得到的。三三.规范归约（最左归约）规范归约（最左归约）程序设计语言与编译E EE ET T+F FT Ti ii i*F FT Ti iF Fi i+i+i*i iF F+i+i*i iT T+i+i*i iE+E+i i*i iE+E+F F*i iE+TE+T*i iE+E+T T*F FE+TE+TE E例:G(E)EE+TT TT*FF F(E)i i+i*i的分析过程 程序设计语言与编译例:G(S)SaAcBe AAb|b Bd abbcde的分析过程S Sa A c B ea A c
5、B e A b d A b d b ba ab bbcdebcdea aAbAbcdecdeaAcaAcd de eaAcBeaAcBeS S 程序设计语言与编译内容回顾内容回顾 语法分析语法分析自上而下自上而下自上而下自上而下1.1.规范规约规范规约程序设计语言与编译1.1.算符文法算符文法上下文无关文法G,没有形如P或P.QR.的产生式,则称G为第二节第二节 算符优先分析法算符优先分析法一一.算符优先文法算符优先文法 程序设计语言与编译对算符文法G,a,bVT 定义2.2.终结符之间的优先关系终结符之间的优先关系 (1)a=b:G(1)a=b:G中有中有P.ab.P.ab.或或 P.aQb
6、.P.aQb.+(2)ab:G(2)ab:G(3)ab:G中有中有P.Qb.P.Qb.且且 Q Q.a.a或或Q QaRaR程序设计语言与编译若算符文法G的任何终结符a,b之间的优先关系至多有=、=算符优先关系表算符优先关系表 程序设计语言与编译从上表可知从上表可知:(1)相同终结符之间的优先关系未必是=(2)有aa(3)a、b之间未必一定有优先关系故=、不同于关系运算符“等于”、“小于”、“大于”程序设计语言与编译初始化初始化:#:#栈栈读一符号读一符号b ba=b=#a=b=#ababab归约最左素短语归约最左素短语,最左素短语出栈最左素短语出栈,左部符号入栈左部符号入栈结束结束b b入栈
7、入栈出错出错Y YN NY YY YN NN N二二.算符优先分析算法算符优先分析算法a a为为栈顶终结符栈顶终结符程序设计语言与编译 这是一种结构归约结构归约,处于栈顶待归约的最左素短语与对应的产生式在结构上应一致,即长度一致,对应的终结符一致,而非终结符可以不一致。归约最左素短语的方法归约最左素短语的方法 EE+TEE+TE E+E E程序设计语言与编译 ：使用一个分析栈，当其栈顶形：使用一个分析栈，当其栈顶形成最左素短语时，就进行归约。成最左素短语时，就进行归约。分析算法分析算法k:=1;Sk=#;k:=1;Sk=#;repeatrepeat b:=b:=下一输入符号下一输入符号;if
8、Sk if Sk V VT T then j:=k else j:=k-1;then j:=k else j:=k-1;while Sjb do while Sjb do begin begin repeat repeat Q:=Sj;Q:=Sj;if Sj-1 if Sj-1 V VT T then j:=j-1 else j:=j-2;then j:=j-1 else j:=j-2;until SjQ;until SjQ;把把Sj+1SkSj+1Sk归约成某个归约成某个N;N;k:=j+1;k:=j+1;Sk:=N;Sk:=N;end of while;end of while;if Sj
9、b or Sj=b then if Sjb or Sj=b then begin k:=k+1;Sk:=b end begin k:=k+1;Sk:=b end else error else erroruntil a=#;until a=#;初始化，栈底置输初始化，栈底置输入串结束符；入串结束符；栈顶终结符，如栈顶终结符，如果栈顶是终结符果栈顶是终结符，则栈顶终结符，则栈顶终结符是该终结符；如是该终结符；如果栈顶是非终结果栈顶是非终结符，则栈顶终结符，则栈顶终结符是下一个终结符是下一个终结符；符；如果栈顶终结符如果栈顶终结符的优先级大于输的优先级大于输入字符入字符a,a,开始归开始归约；约；
10、在栈顶寻找最左素在栈顶寻找最左素短语；短语；如果栈顶终结符如果栈顶终结符的优先级小于或的优先级小于或等于输入字符，等于输入字符，把输入字符移进把输入字符移进栈；栈；栈顶终结符栈顶终结符=输入输入字符字符=#=#时，分时，分析结束析结束程序设计语言与编译例 G(E)EE+TT TT*FF F(E)i i+i*i的分析过程 程序设计语言与编译步骤步骤1 12 23 34 45 56 67 78 89 910101111下推栈下推栈输入串输入串动作动作#i+ii+i*i#i#i,#+,i+,用用F Fi i归约归约#F#F+i+i*i#i#+,#+,移进移进+#F+#F+i i*i#i#+i,+i*
11、,用用F Fi i归约归约#F+F#F+F *i#i#+*,移进移进*#F+F#F+F*i#i#*i,#,i#,用用F Fi i归约归约*#,#,用用T TT T*F F归约归约+#,+#,用用E EE+TE+T归约归约结束结束#F+F#F+F*F F#F+T#F+T#E#E 程序设计语言与编译E EE ET T+F FT Ti ii i*F FT Ti iF FE EE ET T+F FT Ti ii i*F FT TF FE EE ET T+F FT Ti i*F FT TF FE EE ET T+F FT T*F FT TF FE EE ET T+T TF F 程序设计语言与编译 FIR
12、STVT(P)=a|Pa,或PQa,aVT,Q VN +三三.优先关系表的构造优先关系表的构造(1)FIRSTVT(1)FIRSTVT集集若Pa或PQa,则aFIRSTVT(P);若PQ,则FIRSTVT(Q)FIRSTVT(P);直至FIRSTVT(P)不再增大。求法 程序设计语言与编译 LASTVT(P)=a|P.a,或PaQ,aVT,Q VN +(2)LASTVT(2)LASTVT集集若P.a或PaQ,则aLASTVT(P);若P.Q,则LASTVT(Q)LASTVT(P);直至LASTVT(P)不再增大。求法 程序设计语言与编译例例 G(E)EE+TTG(E)EE+TT TT TT*F
13、FFF F(E)i F(E)iE ET TF FFIRSTVTFIRSTVTLASTVTLASTVT(i +(i +*(i(i)i +)i +*)i )i *)i)i(i (i *程序设计语言与编译(3)(3)构造优先关系表构造优先关系表 a=b:a=b:G G中有中有P.ab.P.ab.或或 P.aQb.P.aQb.ab:ab:G G中有中有P.aQ.P.aQ.且且Q Qbb或或 Q QRb.Rb.a b a b:ab:G G中有中有P.Qb.P.Qb.且且 Q Q.a.a或或Q QaRaRa a LAST LASTVT(QVT(Q）b b程序设计语言与编译 FOR 每条产生式PX1X2Xn
14、 DO FOR i:=1 TO n-1 DO BEGIN IF Xi和Xi+1均为终结符 THEN Xi=Xi+1;IF i=n-2 且 Xi和Xi+2均为终结符 但 Xi+1VN THEN Xi=Xi+2;IF XiVT,Xi+1VN THEN aFIRSTVT(Xi+1)XiXi+1 END;构造优先关系表的算法构造优先关系表的算法 程序设计语言与编译例例 G(E)EE+TTG(E)EE+TT TT TT*FFFF F(E)i F(E)iETFFIRSTVTLASTVT(i +*(i)i +*)i *)i(i *考察考察EE+TEE+T中的中的E E和和+、+和和T T考察考察TTTT*F
15、 F中的中的T T和和*、*和和F F考察考察F(E)F(E)中的中的(和和E E 、(和和)、E E和和)程序设计语言与编译+*ii()#=算符优先关系表算符优先关系表 程序设计语言与编译内容回顾内容回顾 条件一：条件一：无无 PP算符优先分析法算符优先分析法1.1.算符文法算符文法条件二：条件二：无无 PQPPQP2.2.定义优先关系定义优先关系(1)a=b(1)a=b(2)ab(2)ab(3)ab3.3.算法优先文法算法优先文法优先关系表优先关系表程序设计语言与编译内容回顾内容回顾 5.5.分析方法分析方法初始化初始化:#:#栈栈读一符号读一符号b ba=b=#a=b=#ababab归约
16、最左素短语归约最左素短语,最左素短语出栈最左素短语出栈,左部符号入栈左部符号入栈结束结束b b入栈入栈出错出错Y YN NY YY YN NN N程序设计语言与编译内容回顾内容回顾 5.5.构造算符优先表构造算符优先表(1)FIRSTVT(1)FIRSTVT(2)LASTVT(2)LASTVT(3)(3)构造方法构造方法P.Qb.P.Qb.P.bQ.P.bQ.P.ab.P.ab.或或.aQb.aQb.程序设计语言与编译已知文法 G=(a,b,(,),S,A,B,S,P)其中 P为 SbAb A(B|a BAa)1.求出文法G的FIRSTVT和LASTVT集。2.构造文法G的优先关系表。3.文法
17、G是算符优先文法吗？为什么？课堂练习课堂练习程序设计语言与编译第二节第二节 LRLR分析法分析法一一.LR(K).LR(K)分析法分析法自底向上的LR分析法是指从左向右扫描输入串,每次分析由分析栈中符号及向前搜索K个输入符号,以确定作为产生式右部的短语(句柄)是否已在分析栈的栈顶形成,从而决定应采取的动作。这种分析方法称为LR(K)分析法。一般只考虑K1的情况。-“L”是指从左至右扫描输入符号串，-“R”是指构造一个最右推导的逆过程，-“k”是指为了作出分析决定而向前看的输入符号的个数 程序设计语言与编译其组成为其组成为:分析栈分析栈,控制程序控制程序,分析表分析表,输入串输入串输入串输入串分
18、析栈分析栈驱动程序驱动程序输出输出actionactiongotogoto分析表分析表s s0 0.s sm-1m-1s sm ma a1 1a ai i.程序设计语言与编译 1.1.分析栈分析栈存放状态;初始时,置初始状态s0;栈里的每一状态概括了从分析开始到某一时刻已进行的分析工作。程序设计语言与编译2.2.分析表分析表 由由actions,aactions,a和和gotos,xgotos,x两个子表组成。两个子表组成。(1)actions,a定义了在状态s下,当前输入符号为a时应采取的分析动作:移进,归约,接受,出错。(2)goto表是一个状态及非终结符的二维矩阵,gotos,x定义了在
19、状态s下,面对文法符号x时的状态转换。程序设计语言与编译例例 G G0 0(E)(E)(1)EE+T (1)EE+T (2)ET (2)ET (3)TT (3)TT*F F (4)TF (4)TF (5)F(E)(5)F(E)(6)Fi (6)Fi的的LRLR分析表如下：分析表如下：程序设计语言与编译LRLR分析表分析表状状态态0 01 12 23 34 45 56 67 78 89 910101111actionactiongotogotoi i+*()E ET TF Fs5s5s4s41 12 23 3s6s6accaccr2r2s7s7r2r2r2r2r4r4r4r4r4r4r4r4r4
20、r4s5s5s4s48 82 23 3r6r6r6r6r6r6r6r6s5s5s4s49 93 3s5s5s4s41010s6s6s11s11r1r1s7s7r1r1r1r1r3r3r3r3r3r3r3r3r5r5r5r5r5r5r5r5 程序设计语言与编译3.3.控制程序的工作控制程序的工作据据actions,aactions,a进行进行(1)(1)若若actions,a=actions,a=s sj j ,则将状态j推入栈顶,输入指针指向下一输入符号;(2)(2)若若actions,a=ractions,a=rj j ,则按第j个产生式A归约,设|=t,应在分析栈栈顶上托t个状态出栈,呈现
21、栈顶的状态设为s si i,则根据s si i及归约后的非终结符A,查goto表,gotos si i ,A=j,则将状态j下推入分析栈栈顶。(3)(3)若若actions,a=accactions,a=acc,则结束分析,输入串被接受。(4)(4)若若actions,aactions,a或或gotos,Agotos,A不是上述情况不是上述情况,转出错处理程序 程序设计语言与编译 序号序号状态状态符号符号输入串输入串动作动作1 10 0#i+ii+i*i#i#action0,i=s5action0,i=s52 20,50,5#+i+i*i#i#action5,+=r6,goto0,F=3act
22、ion5,+=r6,goto0,F=33 30,30,3#+i+i*i#i#action3,+=r4,goto0,T=2action3,+=r4,goto0,T=24 40,20,2#+i+i*i#i#action2,+=r2,goto0,E=1action2,+=r2,goto0,E=15 50,10,1#E#E+i+i*i#i#action1,+=s6action1,+=s66 60,1,60,1,6#E+#E+i i*i#i#action6,i=s5action6,i=s57 70,1,6,50,1,6,5#E+#E+*i#i#action5,action5,*=r6,goto6,F=3
23、=r6,goto6,F=38 80,1,6,30,1,6,3#E+#E+*i#i#action3,action3,*=r4,goto6,T=9=r4,goto6,T=99 90,1,6,90,1,6,9#E+T#E+T*i#i#action9,action9,*=s7=s710100,1,6,9,70,1,6,9,7#E+T#E+T*i#i#action7,i=s5action7,i=s511110,1,6,9,7,50,1,6,9,7,5#E+T#E+T*#action5,#=r6,goto7,F=10action5,#=r6,goto7,F=1012120,1,6,9,7,100,1,6,
24、9,7,10#E+#E+#action10,#=r3,goto6,T=9action10,#=r3,goto6,T=913130,1,6,90,1,6,9#action9,#=r1,goto0,E=1action9,#=r1,goto0,E=114140,10,1#E#E#action1,#=acc,action1,#=acc,接受接受例例:i+i:i+i*i i的分析过程的分析过程(6)Fi(6)Fi程序设计语言与编译 序号序号状态状态符号符号输入串输入串动作动作1 10 0i+ii+i*i#i#action0,i=s5action0,i=s52 20,50,5+i+i*i#i#action
25、5,+=r6,goto0,F=3action5,+=r6,goto0,F=33 30,30,3+i+i*i#i#action3,+=r4,goto0,T=2action3,+=r4,goto0,T=24 40,20,2+i+i*i#i#action2,+=r2,goto0,E=1action2,+=r2,goto0,E=15 50,10,1+i+i*i#i#action1,+=s6action1,+=s66 60,1,60,1,6i i*i#i#action6,i=s5action6,i=s57 70,1,6,50,1,6,5*i#i#action5,action5,*=r6,goto6,F=
26、3=r6,goto6,F=38 80,1,6,30,1,6,3*i#i#action3,action3,*=r4,goto6,T=9=r4,goto6,T=99 90,1,6,90,1,6,9*i#i#action9,action9,*=s7=s710100,1,6,9,70,1,6,9,7i#i#action7,i=s5action7,i=s511110,1,6,9,7,50,1,6,9,7,5#action5,#=r6,goto7,F=10action5,#=r6,goto7,F=1012120,1,6,9,7,100,1,6,9,7,10#action10,#=r3,goto6,T=9a
27、ction10,#=r3,goto6,T=913130,1,6,90,1,6,9#action9,#=r1,goto0,E=1action9,#=r1,goto0,E=114140,10,1#action1,#=acc,action1,#=acc,接受接受例例:i+i:i+i*i i的分析过程的分析过程(6)Fi(6)Fi程序设计语言与编译E EE ET T+F FT Ti ii i*F FT Ti iF Fi i+i+i*I IF F+i+i*i iT T+i+i*i iE+E+i i*i iE+E+F F*i iE+TE+T*i iE+E+T T*F FE+TE+TE E 程序设计语言与编
28、译归约符号串总是在栈顶；归约符号串总是在栈顶；句柄之后的待入栈符号串总是终结符；句柄之后的待入栈符号串总是终结符；在符号栈中的符号串是规范句型的前缀在符号栈中的符号串是规范句型的前缀.程序设计语言与编译内容回顾内容回顾 LRLR分析法分析法(4)(4)总控程序总控程序(3)LR(3)LR分析表分析表(1)(1)输入串输入串(2)(2)分析栈分析栈actions,aactions,as sj j rjrj accaccerrorerrorgotogotos si i ,A=j,A=j程序设计语言与编译例子：例子：（0 0）SESE（1 1）EaAEaA（2 2）EbBEbB（3 3）AcAAcA
29、（4 4）AdAd（5 5）BcBBcB（6 6）BdBd对输入串对输入串bccd#bccd#分析。分析。程序设计语言与编译 序号序号状态状态符号符号输入串输入串动作动作1 10 0#bccd#bccd#action0,b=s3action0,b=s32 20,30,3#ccd#ccd#action3,c=s5action3,c=s53 30,3,50,3,5#cd#cd#action5,c=s5action5,c=s54 40,3,5,50,3,5,5#d#d#action5,d=s11action5,d=s115 50,3,5,5,110,3,5,5,11#bcc#bccd d#actio
30、n11,#=r6,goto5,B=9action11,#=r6,goto5,B=96 60,3,5,5,90,3,5,5,9#bc#bccBcB#Action9,#=r5,goto5,B=9Action9,#=r5,goto5,B=97 70,3,5,90,3,5,9#b#bcBcB#Action9,#=r5,goto3,B=7Action9,#=r5,goto3,B=78 80,3,70,3,7#bBbB#action7,#=r2,goto0,E=1action7,#=r2,goto0,E=19 90,10,1#E#E#action9,action9,*=acc=accbccd#bccd#的
31、分析过程的分析过程程序设计语言与编译4.4.几种几种LRLR分析法分析法LR(0)、SLR(1)、LR(1)、LALR(1)程序设计语言与编译*R RR R二二.LR.LR（0 0）项目集规范族）项目集规范族 1.1.活前缀活前缀:规范句型的不含句柄之后任何符号的一个前缀。亦即:若A是文法的一个产生式,且有 SA 则的任何前缀都是规范句型的活前缀。程序设计语言与编译已知文法G（S），分析符号串abbcde是否是G（S）的句子 (1)S aAcBe (2)A b (3)A Ab (4)B d句子的最右推导过程为：S=aAcBe=aAcde=aAbcde=abbcde 程序设计语言与编译 由于最右
32、推导就是规范推导，因此句型 aAcBe、aAcde、aAbcde、abbcde为规范句型。S=aAcBeaAcBe的活前缀：,a,aA,aAc,aAcB,aAcBeS=aAcBe=aAcdeaAcde的活前缀：,a,aA,aAc,aAcdS=aAcBe=aAcde=aAbcdeaAbcde的活前缀：,a,aA,aAbB dA AbS=aAcBe=aAcde=aAbcde=abbcdeA babbcde的活前缀：,a,ab S=aAcBe=aAcde=aAbcde=abbcde程序设计语言与编译(1)作为规范句型的活前缀,它不含句柄后的任何符号。(2)活前缀与句柄之间的三种关系:活前缀不含句柄的
33、任何符号,此时期待从剩余输入串中识别由A的能推导出的符号串;活前缀只含句柄的真前缀,也即产生式A中已识别于分析栈栈顶之上,期待从剩余输入串中识别由所能推导出的符号串;活前缀已含句柄的全部符号,这表明产生式A的右部符号已在分析栈栈顶之上,应将归约为A。(3)句柄是一类活前缀的后缀,如果能识别一个文法的所有活前缀,自然也就能识别这个文法的所有句柄了。程序设计语言与编译:在产生式右部添加一个圆点 如A、A、A 左边：已经识别；右边：等等识别左边：已经识别；右边：等等识别 项目个数：n+1n+1归约项目归约项目:形如A移进项目移进项目:形如Aa，aVT待约项目待约项目:形如AB，BVN接受项目接受项目
34、:形如S，S为开始符2.LR2.LR（0 0）项目及分类）项目及分类 程序设计语言与编译例：产生式SaAcBe对应的6个项目是：0S.aAcBe 1Sa.AcBe 2SaA.cBe 3SaAc.Be 4SaAcB.e 5SaAcBe.程序设计语言与编译3.3.拓广文法拓广文法增加产生式SS，从而SS成为唯一的接受项目.4.4.状态转换图的构造状态转换图的构造一个项目对应一个状态,SS为唯一初态，其余均为终态(活前缀识别态)。程序设计语言与编译每个状态是一个；SS是唯一的；所有的其他项目是，是某个活前缀的识别态；若 状 态 i 为 X X1 Xi-1 Xi Xn，状 态 j 为XX1XiXi+1
35、Xn，则从状态i画一条有向边到状态j，标记为Xi；如果Xi为一非终结符，并有Xi1|2|m 则从状态i画有向边到所有状态Xii。SSE EEET T程序设计语言与编译例：SBBBaBBbSSS SSSSSSSBBBBSBSBB BSBBSBBBBaBaBBaBaB BBaBBaBBBb bBbBbSSSBBBaBBb拓广拓广这个文法的项目有这个文法的项目有:1 12 2S S 3 34 45 5B BB B 6 67 78 8B Ba a9 91010b b 程序设计语言与编译*R RR R5.5.项目的有效性项目的有效性(1)对于项目A,如果有 SA则称A对活前缀有效。意思是:到达项目A时,
36、已识别出,希望继续识别从推出的串。若AB对活前缀有效,则B 对活前缀也有效。程序设计语言与编译因为 SAB则,设,有 SAB B即 SB所以所以,B 对对也有效。也有效。*RRR R*RRRRRR*若AB对活前缀有效,则B 对活前缀也有效。程序设计语言与编译 (2)有效项目集:对活前缀有效的项目的集合称为对的有效项目集。(3)LR(0)项目集规范族:文法G的所有有效项目集组成的集合。程序设计语言与编译内容回顾内容回顾 LRLR分析法分析法输入串输入串分析栈分析栈总控程序总控程序LRLR分析表分析表活前缀活前缀规范句型规范句型+不含句柄之后任何符号不含句柄之后任何符号LRLR（0 0）项目）项目
37、归约项目归约项目:形如形如AA 移进项目移进项目:形如形如AA a a，a a VTVT待约项目待约项目:形如形如AA B B，B B VNVN接受项目接受项目:形如形如SS，S S为开始符为开始符状态转换图状态转换图SBBBaB程序设计语言与编译*R RR R(1)对于项目A,如果有 SA 则称A对活前缀有效。（2)若AB对活前缀有效,则B 对活前缀也有效。有效项目集有效项目集LR(0)LR(0)项目集规范族项目集规范族有效项目有效项目程序设计语言与编译6.6.闭包函数闭包函数closure(I)closure(I)设设I I是文法是文法G G的一个的一个LR(0)LR(0)项目集项目集 (
38、1)(1)对任何iI,都有iclosureclosure(I);(2)(2)若项目ABclosureclosure(I),且B为文法G的一个产生式,则B closureclosure(I)；(3)(3)重复(2)直至closureclosure不再增大。程序设计语言与编译例：SBBBaBBbSSS SSSSSSSBBBBSBSBB BSBBSBBBBaBaBBaBaB BBaBBaBBBb bBbBbSSSBBBaBBb拓广拓广这个文法的项目有这个文法的项目有:closure(Sclosure(S S)S)Closure(SS)Closure(SBB)=SS=SBB,BaB,Bb=SS,SBB
39、,BaB,Bb=SBB,BaB,Bb程序设计语言与编译7.7.转换函数转换函数Go(I,X)Go(I,X)设XVTVN go(I,X)=closure(J)J:任何形如AX的项目|AXIAX项目集IXAXClosure(AX)Go(I,X)程序设计语言与编译SSS SSSSSSSBBBBSBSBB BSBBSBBBBaBaBBaBaB BBaBBaBBBb bBbBb I I0 0=closure(S=closure(S S)S)=SS,SBB,BaB,BbI I1 1=Go(I I0,0,S)=Closure(SS)=SSI I2 2=Go(I I0,0,B)=Closure(SBB)=SB
40、B,BaB,BbI I3 3=Go(I I0,0,a)=Closure(SaB)=SaB,BaB,BbI I4 4=Go(I I0,0,b)=Closure(Bb)=Bb程序设计语言与编译8.LR(0)8.LR(0)项目集规范族的构造项目集规范族的构造begin C:=closure(SS);repeat for C中每一项目集I和文法符号X do if go(I,X)不空 且 go(I,X)C then 把go(I,X)加入C中 until C不再增大end;I I2 2=SBB,BaB,Bbgo(I I2 2,S)为空程序设计语言与编译 I I0 0=closure(S=closure(S
41、 S)S)I I1 1=go(I=go(I0 0,S,S)I I2 2=go(I=go(I0 0,B,B)I I3 3=go(I=go(I0 0,a,a)I I4 4=go(I=go(I0 0,b,b)I I5 5=go(I=go(I2 2,B,B)I I6 6=go(I=go(I3 3,B,B)=SS,SBB,BaB,Bb=SS=SBB,BaB,Bb=BaB,BaB,Bb=Bbgo(I2,a)=go(I2,b)=SBBgo(I3,a)=I I3 3,go(I3,b)=I I4 4=BaB,I I3 3I I4 4S SB BB Bb b1 12 23 34 45 56 60 0a ab bb
42、 ba aB BSSS SSSSSSSBBBBSBSBB BSBBSBBBBaBaBBaBaB BBaBBaBBBb bBbBb例子例子程序设计语言与编译三三.LR.LR（0 0）分析表的构造）分析表的构造(1)C=I0,I1,In,Ii对应状态i,I0=closure(SS)为唯一初态;(2)对每个Ii,若AaIi,且go(Ii,a)=Ij,则actioni,a=sj;若AIi,A为第j个产生式,则bVT#,actioni,b=rj;若SSIi,则actioni,#=acc;(3)若go(Ii,A)=Ij,则gotoi,A=j;(4)凡不能用规则(2)、(3)登记的表项均为“错误”程序设计语
43、言与编译状状态态ActionActiongotogotoa ab b#S SB B0 0s3s3S4S41 12 21 1accacc2 2s3s3s4s45 53 3s3s3s4s46 64 4r3r3r3r3r3r35 5r1r1r1r1r1r16 6r2r2r2r2r2r2I I0 0=closure(S=closure(S S)S)I I2 2=go(I=go(I0 0,B,B)I I3 3=go(I=go(I0 0,a,a)I I4 4=go(I=go(I0 0,b,b)I I5 5=go(I=go(I2 2,B,B)I I6 6=go(I=go(I3 3,B,B)=SS,SBB,B
44、aB,Bb=SS=SBB,BaB,Bb=Bbgo(I2,a)=go(I2,b)=SBBgo(I3,a)=I I3 3go(I3,b)=I I4 4=BaBI I1 1=go(I=go(I0 0,S,S)I I3 3I I4 4=BaB,BaB,Bb（0 0）SSSS（1 1）SBBSBB（2 2）BaBBaB（3 3）BbBb 程序设计语言与编译内容回顾内容回顾 LR(0)LR(0)分析表的构造分析表的构造1.1.扩广文法扩广文法2.2.确定所有项目确定所有项目3.3.构造构造LR(0)LR(0)项目规范族项目规范族闭包函数闭包函数closure(I)closure(I)转换函数转换函数Go(
45、I,X)Go(I,X)ABclosureclosure(I)且B为文法G的一个产生式 I：AXGo(I,X)=Go(I,X)=Closure(AX)则B closureclosure(I)C=IC=I0 0=Closure(SS)对C中每一个项目集I和每一个文法符合Xgo(I,X)不空 且 go(I,X)C 把go(I,X)加入C中程序设计语言与编译内容回顾内容回顾 4.4.构造构造LR(0)LR(0)分析表分析表C=I0,I1,In 若AaIi且go(Ii,a)=Ij则actioni,a=Sj若AIi A为第j个产生式则bVT#actioni,b=rj若SSIiactioni,#=acc若A
46、BIi且go(Ii,B)=IjGotoIi,B=Ij程序设计语言与编译例例 G G0 0(E)(E)(0)SE (0)SE (1)EE+T (1)EE+T (2)ET (2)ET (3)TT (3)TT*F F (4)TF (4)TF (5)F(E)(5)F(E)(6)Fi (6)Fi 程序设计语言与编译I0=closure(SS)SE EE+T ET,TT*F TF,F(E)F iI1=go(I0,E)SE EE+TI2=go(I0,T)ET TT*FI3=go(I0,F)TFSESEEE+TTEE+TTTTTT*FFFFF(E)iF(E)i I I4 4=go(=go(I I0 0,(),
47、()F F(E)E)E EE+T EE+T ET T T TT T*F TF TF F F F(E)F(E)F i iI6I6=go(I1,+)=go(I1,+)E EE+E+T T T TT T*F TF TF F F F(E)F(E)F i iI I5 5=go(=go(I I0 0,i),i)F F i i I7I7=go(I2,=go(I2,*)T TT T*F FF F(E),F(E),F i iI8I8=go(I4,E)=go(I4,E)F F(E(E)E)EE E+T+TI9I9=go(I6,T)=go(I6,T)E EE+TE+T,T,TT T*F F I10I10=go(I7
48、,F)=go(I7,F)T TT T*F F I11I11=go(I8,)=go(I8,)F F(E)(E)程序设计语言与编译I I0 0=closure(S=closure(S E E)S SE E E EE+T EE+T ET,T,T TT T*F TF TF,F,F F(E)F(E)Fi iI I1 1=go(=go(I I0 0,E),E)S SE E E EE E+T+TI I2 2=go(=go(I I0 0,T),T)E ET T T TT T*F FI I3 3=go(=go(I I0 0,F),F)T TF F I I4 4=go(=go(I I0 0,(),()F F(E)
49、E)E EE+T EE+T ET T T TT T*F TF TF F F F(E)F(E)F i i I6 I6=go(I1,+)=go(I1,+)E EE+E+T T T TT T*F TF TF F F F(E)F(E)F i iI I5 5=go(=go(I I0 0,i),i)F F i i(0)SE(0)SE(1)EE+T(1)EE+T(2)ET(2)ET(3)TT(3)TT*F F(4)TF(4)TF(5)F(E)(5)F(E)(6)Fi(6)Fi程序设计语言与编译 I7I7=go(I2,=go(I2,*)T TT T*F F F F(E),F(E),F i iI8I8=go(I
50、4,E)=go(I4,E)F F(E(E)E)EE E+T+TI9I9=go(I6,T)=go(I6,T)E EE+TE+T,T,TT T*F F I10I10=go(I7,F)=go(I7,F)T TT T*F F I11I11=go(I8,)=go(I8,)F F(E)(E)go(I4,T)=go(I4,T)=I2I2go(I4,F)=go(I4,F)=I3I3go(I4,()=go(I4,()=I4I4go(I4,i)=go(I4,i)=I5I5go(I6,F)=go(I6,F)=I3I3go(I6,()=go(I6,()=I4I4go(I6,i)=go(I6,i)=I5I5go(I7,
