專業(yè)課課件編譯原理匯編語言3note

2014/LR(1)分LR(1)項(xiàng)LR(1)項(xiàng)目集規(guī)范LR(1)LALR(1)分二義文1 2014/LR（1）項(xiàng)A.,ALR（0）a為向前搜索符 2014/LR（1）項(xiàng)目解A.,LR（1）LR（0）的歸約項(xiàng)目，但只有當(dāng)下一個(gè)輸入符是a時(shí)才能進(jìn)行歸約對(duì)于其它形式的LR（1）a只起到信息 2014/記A.,a1A.,…A.,A.,a1/a2/…/

2014/類似于LR(0)A，可以在LR（1）項(xiàng)目的基礎(chǔ)上為上下文無關(guān)文法G構(gòu)造一個(gè)類似的有限狀態(tài)機(jī)，稱為L(zhǎng)R(1)自動(dòng)機(jī)（LR(1)A） 2014/LR（1）A的構(gòu)計(jì)算LR（1）ICLOSURE(I)function J:=repeatforJ中的每個(gè)項(xiàng)[AB，a和產(chǎn)生Bdo將所有形如[B.b]的項(xiàng)目加到J中這b return 2014/LR（1）A的構(gòu)設(shè)文法G[S] 文法為G’[S’],則G’的的初 I0=CLOSURE({[S’.S，#]}設(shè)右邊文法G[S]的文法為G[S，LR（1）A的初態(tài)I0:S.E，#E.(L,E)E.FF.(F)F.d

E(L,EELL,LF(FF 2014/LR（1）A的構(gòu)GO(I,X)=其中，I為自動(dòng)機(jī)的狀態(tài)（閉包的項(xiàng)目集），X為文法符號(hào)，J={[AXa][AXa]I}數(shù)，可逐步構(gòu)造出完整的LR（1）A對(duì)于文法GLR（1）A 2014/LR（1）A的構(gòu)設(shè)文法G[S]的 文法為G’[S’],則G’的LR（1）項(xiàng)目集規(guī)范族C可由如下算法計(jì)算：C:={CLOSURE({[S’.S,#]})ForCI和每一文法符號(hào)Do GO(I,X) GO(I,XCUntilC LR（1）A的構(gòu)造舉構(gòu) 文法G’[S]的

2014/文法G’SE(L,EEI0:S.E,E.(L,E),E.F,

I3:E(.L,E),F(.F), L.L,E,

I5:LE.,

LL,LF(FF.(F),

L.E,

I:Fd.,,

FI4:Fd.,I4:Fd., II2:EF.,

F.(F),, F.d,, E.(L,E),I7:F(F.),I7:F(F.),#EF.,,I6:E(L.,E)LL.,E,I1:SE.,I16I16:F(F).,

E(.L,E),F(.F),,)L.L,E,,L.E,F.(F),,F.d,,)E.(L,E),,E.F,, LR（1）A的構(gòu)造舉構(gòu) 文法G’[S]的

2014/I6:E(L.,E),#LL.,E,,I25:I6:E(L.,E),#LL.,E,,I25:E(L,E).,,I)I24:E(L,E.),,I)I24:E(L,E.),,)LL,E.,, L.L,E, :E(L,.E),

L.E, F.(F),, ((LL,.E,E.(L,E),,E.F,,F.(F),,F.d,, I12:EF.,,

F.d,,)E.(L,E),,E.F,,LI14:E(L.,E),,LL.,E,

I18:E(L,.E),,)LL,.E,,E.(L,E),, E.F,,F.(F),,F.d,,

I(I FI20:E(L,E)., I11:EI20:E(L,E)., LR（1）A的構(gòu)造舉I19:E(L,.E),,LL,.E,I19:E(L,.E),,LL,.E,,E.(L,E),,E.F,,F.(F),,F.d,,I8:EI8:E(.L,E),F(.F),,)L.L,E,,L.E,F.(F),,F.d,,)E.(L,E),,E.F,,

2014/I(II I I9,I17,I17:E(L.,E),,LL.,E,,I22:I22:E(L,E.),,LL,E.,,(FI15:FI15:F(F.),,)EF.,,I23:E(L,E).,I21:F(F).,, 解決前例SLR（1）分析中當(dāng)?shù)竭_(dá)狀態(tài)I7（棧上的活前綴為(F）時(shí)，F(xiàn)所期望的下一個(gè)輸入符號(hào)只有,，沒有)，因而該狀態(tài)下不存在移進(jìn)歸約可以驗(yàn)證，對(duì)本例中G[SLR（1）A，

2014/文文法G’SE(L,EELL,LF(FFI3:I3:E(.L,E),#F(.F),#L.L,E,L.E,F.(F),,F.d,,)E.(L,E),,E.F,,I0:S.E,E.(L,E),E.F,F.(F),F.d,I7I7:F(F.),#EF.,, 2014/假定C={I0,I1,…，In}，令狀態(tài)Ik對(duì)應(yīng)的LR（1）分析表的棧頂狀態(tài)為k；令含有項(xiàng)目[S’.S，]的狀態(tài)為I0因此0為初態(tài)。ACTION表項(xiàng)和GOTO表項(xiàng)可按如下方若項(xiàng)目[Aα.aβb]IkGOIka)Ija為終結(jié)符，則ACTION[k,a]為“把狀態(tài)j移進(jìn)?！?，簡(jiǎn)記為若項(xiàng)目[Aα.b屬于Ik那么置ACTION[k,b]為“用產(chǎn)生式Aα進(jìn)行歸約”，簡(jiǎn)記為“rj”;這里，假定Aα為文法G’的第j個(gè)產(chǎn)生若項(xiàng)目[S’S屬于Ik則置ACTION[k,為“接受”，記為分析表中凡不能用上述規(guī)則填入信息的空 置上“出錯(cuò)標(biāo)志 2014/ 文法： （2）G’

（3）LL,E（4）LE（5）F(F)狀d #ELF04567891565 2014/ 文法： （2）G’

（3）LL,E（4）LE（5）F(F) 狀

2014/LR（1）文GLR（1）表，并稱G為一個(gè)LR（1）文法[Au.avb，a是終結(jié)符那么就不會(huì)有項(xiàng)目[Bw.a]能同時(shí)含有項(xiàng)目[Au.,a]和[Bv.,a] 2014/可推廣到更強(qiáng)大的LR（k）分A,a1a2…ak],其中移進(jìn)項(xiàng)目形如：A.a，a1a2ak]待約項(xiàng)目形如：A.Ba1a2ak]歸約項(xiàng)目形如：A.，a1a2…ak] 2014/LR（1）和SLR（1）SLR（1）LR（0）A狀態(tài)數(shù)目要比它的LR（1）A狀態(tài)數(shù)目少得多 狀態(tài)合并，得到與LR（0）A相同數(shù)目的狀態(tài)，但 2014/LR（1）A ”LR（1）[A,a中的A LR（1）A同芯狀態(tài)舉文法G’[SLR（1）AI9:Fd.I9:Fd.,,I4:Fd.,I2I2:EF.,I12:EF.,,

2014/文法G’SE(L,EELL,LF(FFI3:EI3:E(.L,E),#F(.F),#L.L,E,L.E,F.(F),,F.d,,)E.(L,E),,E.F,,I8:E(.L,E),F(.F),,)L.L,E,,L.E,F.(F),,F.d,,)E.(L,E),,E.F,,I13:E(.L,E),,F(.F),,)L.L,E,,L.E,F.(F),,F.d,,)E.(L,E),,E.F,, 2014/LR（1）A同芯狀態(tài)舉文法G[SLR（1）A中的同芯狀態(tài)（9組I17:I17:E(L.,E),,LL.,E,,I14:E(L.,E),,)LL.,E,,I6:E(L.,E),#LL.,E,,I15:F(F.),,EF.,I7:F(F.),#EF.,,I19:E(L,.E),,LL,.E,,E.(L,E),,E.F,,F.(F),,F.d,,I18:E(L,.E),,)LL,.E,,E.(L,E),,E.F,,F.(F),,F.d,,I10:E(L,.E),#LL,.E,,E.(L,E),,E.F,,F.(F),,F.d,, 2014/LR（1）A同芯狀態(tài)舉文法G[SLR（1）A中的同芯狀態(tài)（9組II24:E(L,E.),,)LL,E.,,I22:E(L,E.),,LL,E.,,I11:E(L,E.),#LL,E.,,II21:F(F).,,I16:F(F).,II25:E(L,E).,,I23:E(L,E).,I20:E(L,E)., 2014/LR（1）A9組同芯狀態(tài)合并為9E(L,.E),,)E(L,.E),,)#LL,.E,,E.(L,E),,E.F,,F.(F),,F.d,,Fd.,,)EF.,,)E(L.,E),E(L.,E),,)LL.,E,FF(F.),,)#EF.,,EE(L,E.),,)#LL,E.,,

I16-F(F).F(F).,,)E(.L,E),,)F(.F),,)#L.L,E,,L.E,F.(F),,F.d,,)E.(L,E),,E.F,,EE(L,E).,,) 2014/LALR（1）文由于是LR（1）文法，所以未合并的狀態(tài)合并同芯狀態(tài)后，不會(huì)產(chǎn)生新的移進(jìn)歸（分析一下為什么合并同芯狀態(tài)后，可能產(chǎn)生新的歸約歸 2014/LALR（1）A的構(gòu) 文法的LR（1）A狀得到LALR(1)A的狀態(tài)LALR(1)AGO函數(shù)得到的后繼狀態(tài)是所若兩個(gè)狀態(tài)“同芯”，那么其原來的后繼狀 LALR（1）A的構(gòu)

2014/I0:S.E,E.(L,E),

I3-8-E(.L,E),,) F(.F),,)

I6-14-

E(L.,E),,)#LL.,E,,E.F,

L.L,E,

I:LE., F.(F),F.d,EdI1:SE.,

L.E,F.(F),,F.d,,)E.(L,E),,E.F,,

IdI4-

I10-18- E(L,.E),,)#LL,.E,, E.(L,E),,E.F,,I2-

EEF.,,)FF(F.),,)#EF.,,

EE(L,E).,,)

I2- )

F.(F),,F.d,,EFF(F).,,)E(L,E.),,)#LL,E.,,Fd.Fd.,,)

I16- 2014/LALR（1）A的構(gòu)（step-by-step ”的方法更有LALR（1）AGO 2014/LALR（1）分析 2014/ 文法： （2）G’

（3）LL,E（4）LE（5）F(F)狀狀01 s4- s3-8- 2-2-3-8-s4-s3-8-56-14-177-4-56-14-s10-18-7-s16-10-18-s4-s3-8-11-22- 2-11-22-s20-23-16-20-23- 2014/與SLR（1）分析相LR（0）A（左）LALR（1）A（右）I7:FI7:F(F.)EF.(E(.L,E),,)F(.F),,)#L.L,E,,L.E,F.(F),,F.d,,)E.(L,E),,E.F,,I0:S.E,E.(L,E),E.F,F.(F),F.d,FF(F.),,)#EF.,,I0:SEEFF(I3:E(.L,E)F(.F)L.L,EL.EFFE.(L,E)E.FF二義文法在LR 2014/某些二義文法可以構(gòu)造出高效的LR分析法，人為地給出合理的限定規(guī)則，可能構(gòu)造出文法G’文法G’SEE+EEE(EEE二義文法在LR

2014/ v

I3:EI3:EI1:SEEE.I0:SEE.EEE.(E)E.vE I4:Ed(I7:E