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