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