LR(0)分析器的設計分析

現代商貿工業(yè)No.3,2010Modern Business Trade Industry2010年第3期LR(0)分析器的設計分析褚亞飛陳德城宋一波(浙江海洋學(xué)院蕭山科技學(xué)院,浙江杭州311258)摘要:闡述了 編譯原理課程中的LR(0)分析器的設計原理和算法。對給定的文法設計一個(gè)LR(0)分析器，給出LR .(0)分析表,并對給定的文法進(jìn)行分析。關(guān)鍵詞:LR(0);原理;文法;算法;設計中圖分類(lèi)號:TP文獻標識碼:A文章編號:1672-3198(2010)03-0280-031 LR(0)分析表的構造F→. (E)LR(0)分析表包括兩個(gè)部分,一是“動(dòng)作" (ACTION)F→.i表,另一是“狀態(tài)轉換"(GOTO)表，它們都是二維數組。1.2 構造狀態(tài)轉換函數 GO(I,X)ACTION[S,a]規定了當狀態(tài)s面臨輸人符號a時(shí)應采取什構造狀態(tài)轉換函數是構造DFA的前提條件,這個(gè)函數么動(dòng)作。GOTO[S,X]規定了狀態(tài)s面對文法符號X(終結的意義是:當項目集1面臨文法符號X的時(shí)候所轉向的另符或非終結符)時(shí)下-狀態(tài)是什么。下面就具體說(shuō)明在構一個(gè)項目集。 它的定義為造LR(0)分析表過(guò)程中要涉及到的具體內容。GO(I,X) =CLOSURE()1.1構造文 法的項目集規范族如下列文法:J= {任何形如[A→aX. p,a]的項目I [A→a Xp,a]∈(1)E-E+TI} ,那么,在設計中采用的文法的GO函數構造如下:GO(I0,E)=l1G0(I6,i)=15(2)E-TG0(10,)=I5GO(I6,F)=I3(3)T→T#FGO(IO,F)=I3GO(I6,()=I4(4)T→FGO(I0,()=I4GO(17,i)=I5 .(5)F→+(E)GO(IO,T)=I2GO(17,()=14(6)F→i .G0(l1,+)=16GO(I7,F)=I10LR(0)項目集規范族的構造的基本思想是根據雙標記GO(I2,*)=17G0(I8,+)=I6法,定義兩個(gè)標志位ltag.rtag. Ltag 表示項目集是否增加.GO(I4,F)=13GO(I8,))=111完。在構造項目集時(shí),若該項目集不再增大,則將ltag置為GO(I4,()=I4 .G0(I9,*)=17true,否則false. rtag 表示該項目集是否傳播完。在已經(jīng)構GO(I4,i)=I5造的項目集中,若已經(jīng)求出所有的該項目集的狀態(tài)轉移后GO(I4,E)= I8的新的項目集,那么將rtag置為true,并 以分析表表示邊的.3 構造識別活前緩的DFA關(guān)系。這個(gè)文法的項目集規范族為:把這些項目集規范族和轉換函數GO表示成有限自動(dòng)S'+.E5;機便成為一個(gè)能識別活前綴的DFA,如下圖1所示。E→. E+T6:E→+E+.T這樣,我們就可以利用這個(gè)有限自動(dòng)機來(lái)構造LR分析E→.TT→.T*F表的ACTION和GOTO子表。接著(zhù),我們的任務(wù)就是要利T+.F用它來(lái)構造LR(0)分析表。T→.FF→.(F)1.4構造LR(0)分析表.4.1 類(lèi)的定義.7:T→T#.F①集合類(lèi)Set和產(chǎn)生式類(lèi)Precept的定義和LL(1)預測1:S'→E. F→. (E)分析器中的定義一樣;E→E. +T②其他類(lèi)的定義2:E- +T. .I8;F→(E.)class Pair //定義項目類(lèi)T→T. *F3:T→F.public :I4;F→(. E)9:E→E+T.Pair( );E+. E+TT→T. *PPair(inti, int j);E+. TIl0:T→T*F.11:F-(E).中國煤化工T-.FYHCN M H Gair) const;作者簡(jiǎn)介:宋一波(1981-)男,于2006 年開(kāi)始在浙江海洋學(xué)院蕭山科技學(xué)院工作至今,主要從事網(wǎng)絡(luò )管理及計算機類(lèi)相關(guān)學(xué)科教學(xué)工作。一咒數據現代商貿工業(yè)No. 3,2010Modern Business Trade Industry2010年第3期，Precept GetPrecept(int n);Grammar( void) ;~Grammar( void);Grammar(const Grammar & g);const Grammar operator = (const Grammar & g);'void SetVt(string vt);void SetVn(string vn) ;void SetStart(char start);void AddPrecept(string p) ;bool IsGrammarLegal( );bool IsInVn(char cChar);bool IsInVt(char cChar);char GetStart( );void GenerateLR0Table( ); .string OutputHTML( );void Output(char # pFilename);囝1識別活前緩的DFAbool IsLegalLROGrammar( );};private:class GoData //對項目進(jìn)行傳播的類(lèi)定義Set VtSet Vn;public:char cStart;GoData( );vector P;~GoData( );vector C;int iFrom;Pair * pTable;char eChar;vector GoSet;int iTo;int nVt;);int nVn; :class ProijectSet//定義項目集族類(lèi)int nP; .{int nC;void EnlargeGrammar( );ProjetSet(void);void MakeProjects( );~ ProjectSet( void);void GenerateTable( ); .ProjectSet( const ProjectSet & set);Precept GetProject( const Pair & pair1);ProjectSet(Pair pair) ;ProjectSet GetClosure( const Pair & pair1);bool Insert(Pair insert);ProjectSet MakeGoSet(int iI, char cChar);bool Delete(Pair del);int GetGoSet(int il, char eChar) ;bool Find(const Pair & find) const;bool AddProject( const ProjectSet & ps);int FindPos(const Pair & find) const;bool FllTable(int nLine, char eChar, Pair p);int Add(const ProjectSet & set);int ilegal;int Sub( const ProjectSet & set);void CopyGrammar(const Granmar & g);int Size( ) const;protected;PrijetSet operator + (const ProjectSet & set);int GetProjectNum(const Pair & p);PrietSet operator - (const ProjectSet & set);const ProjectSet operator =(const ProjectSet & set);1.4.2構造算法bool operator = = (const ProjectSet & set);構造LR(0)分析表的關(guān)鍵就是要它的ACTION和GO-Pair GetAt(int iPos);TO子表,上面已經(jīng)構造好了這個(gè)文法的GO函數,我們將bool IsEmpty( );利用這個(gè)GO函數來(lái)構造出這兩個(gè)子表。算法如下:①若項目A→a.a屬于Ik且GO(Ik,a)=lj,a為終結vector SetContent;符,則置ACTION[k,a]為“把(j,a)移進(jìn)?！?簡(jiǎn)記為“s”;中國煤化工何終結符a(或終結.class Grammar //定義LR(0)文法類(lèi)符#)，MHCNMHG→a進(jìn)行歸約”，簡(jiǎn).記為“;個(gè)產(chǎn)生式):③若項目S'→S.屬于k,則置ACTION[k, #]為“接.int GetGoTo(int iStatus, char eChar);受”,簡(jiǎn)記為“ace" ;Pair GetAction(int iStatus, char cNext);④若GO(Ilk,A) =Ij,A為非終結符,則置GOTO[k,A]一281一現代商貿工業(yè)No.3,2010Modern Business Trade Industry2010年第3期=j;.0..... sm - rs, # x2.....m- rA,aiai+ ....n#).⑤分析表中凡不能用規則1至4填入信息的空白格均此處,s= GOTO[sm-r,A],r為β的長(cháng)度,β= Xm- -τ置上“報錯標志”.+.....Xmn.根據這個(gè)算法構造出文法的LR(0)分析表如下:③若ACTION sm,ai]為“接受”,則三元式不再變化，表1 LR(0)分析表變化過(guò)程終止,宣布分析成功.ACTION(動(dòng)作) COTO(轉 換)④若ACTION[ sm,ai]為“報錯”,則三元式的變化過(guò)程狀態(tài)終止,報告錯誤。0523一個(gè)LR分析器的工作過(guò)程就是一步一步地變換三元s6acc式,直至執行“接受”或“報錯”為止。r2 s7r2r22.2 LR(0)分 析程序總控程序的流程4I4r4r4LR分析器實(shí)際上就是一個(gè)有限自動(dòng)機,分析棧的棧頂4s5Is482 3的狀態(tài)概括了整個(gè)棧的內容，因此,無(wú)需掃描整個(gè)棧。我們r(jià)6Tr6r6 r66| s9T 3只要根據棧頂的內容和現行輸人符號就可以識別一個(gè)句s5s40柄。只是LR分析表的設計較LL(1)分析表的設計要麻煩，8 s6s11但是LR(0)分析法比LL(1)分析法的功能要強,并且一般9r1Ts71r能用LL(1)分析的文法用LR(0)也一定可以分析。具體的r3r3r3 r3流程圖分析如下:C開(kāi)舶D說(shuō)明:記號的意義是:Stane 0 FLAG TRUE(1)sj:把下一-狀態(tài)j和現行輸人符號a移進(jìn)棧;(2)r;:按第j個(gè)產(chǎn)生式進(jìn)行歸約;把狀態(tài)0利行號分壓入狀態(tài)控利符號園(3)acc:接受;厄第一個(gè)許號請(4)空白格:出錯標志,報錯.2 LR(0)分 析器的設計< FLAG-TRUEDY2.1設計原理LR(0)分析器的核心就是一張分析表.這張分析表現為移進(jìn)少在也已經(jīng)構成,下面我們要做的工作就是構造LR(0)分析移進(jìn)接受報銷(xiāo)器了。每一項ACTION[s,a]所規定的動(dòng)作不外是下述四State -GOTO狀態(tài)找和符號校分析成功] 出鎖處理]種可能之一:Isuaie.l分別進(jìn)行歡出校(1)移進(jìn)。把(s,a)的下一狀態(tài)s' = GOTO[s,a]和輸入[ Sase進(jìn)狀泰線(xiàn)] 5 =狀棧L 棧麗狀態(tài)CASE ASE符號a推進(jìn)棧，下一輸人符號變成現行輸人符號.C進(jìn)符號棧]Erisre -OOTO1(2)歸約。用某一個(gè)產(chǎn)生式A→β進(jìn)行歸約。假若β的長(cháng)度是r,歸約的動(dòng)作是A,去除棧頂的r個(gè)項,使狀態(tài)sm-r變成棧頂狀態(tài),然后把(sm- -r,A)的下一狀態(tài)s'= GOTO[隨符號技J[sm- r,A]和文法符號A推進(jìn)棧。歸約動(dòng)作不改變現行輸下一輸入粉號讀遇]人符號.執行歸約動(dòng)作意味著(zhù)(= Xm-r+1-Xm)巳墾現于棧頂而且是一個(gè)相對于A(yíng)的句柄。C紡乘)(3)接受。宣布分析成功,停止分析器的工作。圉2.(4)報錯。發(fā)現源程序含有錯誤,調用出錯處理程序。一個(gè)LR分析器的工作過(guò)程可看成是棧里的狀態(tài)序列、3結束語(yǔ)已歸約串和輸人串所構成的三元式的變化過(guò)程。分析開(kāi)始該分析器不同于傳統的多媒體教學(xué)軟件限制教學(xué)案例:用時(shí)的初始三元式為戶(hù)只要按規定的格式輸入問(wèn)題，系統能自動(dòng)地給出該問(wèn)題的答(s0，#，a2....n#)案和解答過(guò)程。該系統能作為學(xué)生學(xué)習的輔助工具,同時(shí)也可其中s0為分析器的初態(tài), #為句子的左括號a2......以作 為教師的教學(xué)工具,輔助教學(xué),這也是適應新世紀教學(xué)改an為輸入串,其后的#為結束符(句子右括號).分析過(guò)程革的需要。 本分析器專(zhuān)門(mén)是針對編譯原理這門(mén)課程而設計的，每步的結果可表示為因此,它的運用就僅局限于對編詳原理的解答。<....sm,.. # X2..... Xm, a+....an#)分析器的下一步動(dòng)作是由棧頂狀態(tài)sm和現行輸人符參考文獻號ai所唯一決定的，即執行ACTION[sm,ai]所規定的動(dòng)[1] 呂映芝,張素琴,編譯原理[M].北京:清華大學(xué)出版社,1998.作,經(jīng)執行每種可能的動(dòng)作之后,三元式的變化情形是:[2]K“中國煤化工峰原理反實(shí)成[M]北①若ACTION[Ssm,a門(mén)]為移進(jìn)，且s= GOTO[sm,ai],則[3]陳|YHCN M H G(第3版)[MJ.北京，三元式的變成:.0..... sms, # X2..... Xmai, a+..... an# )國防工業(yè)出殿社,Z0U1.②若ACTION[sm,ai]={A→β) ,則按產(chǎn)生式A→β進(jìn)[4]盧偉,李堂秋.嵌入語(yǔ)義動(dòng)作的LR分析器構造方法[J].計算機工程與應用,1998,37(6) ;41-47.行歸約。此時(shí)三元式變?yōu)榉綌祿?/p>