編譯原理課程設(shè)計報告 (語法分析)

河海大學(xué)物聯(lián)網(wǎng)工程學(xué)院（常州）課程設(shè)計報告題目編譯原理課程設(shè)計題目編譯原理課程設(shè)計TOC\o"1-5"\h\z\o"CurrentDocument"一、 課程設(shè)計概要 1\o"CurrentDocument"二、 語法分析設(shè)計思想 1\o"CurrentDocument"地位及作用 1\o"CurrentDocument"設(shè)計思路 1分析方法 1使用文法 1First集合和Follow集合 1\o"CurrentDocument"構(gòu)造LR(O)項集規(guī)范簇 2\o"CurrentDocument"構(gòu)造SLR(l)分析表 2構(gòu)造字符串的分析過程 2\o"CurrentDocument"三、 語法分析器設(shè)計算法 2\o"CurrentDocument"First集合生成算法 2\o"CurrentDocument"Follow集合生成算法 2\o"CurrentDocument"計算項集I的閉包 2\o"CurrentDocument"狀態(tài)之間的轉(zhuǎn)換 3構(gòu)造LR(O)項集規(guī)范簇 3構(gòu)造SLR(l)分析表 3\o"CurrentDocument"句子識別 3\o"CurrentDocument"四、 項目整合 4\o"CurrentDocument"五、 流程圖 5構(gòu)造Follow集合的流程圖 5語法分析流程圖 6\o"CurrentDocument"六、 主要函數(shù)描述 7Follow函數(shù)描述 7\o"CurrentDocument"項集I的閉包函數(shù)描述 7\o"CurrentDocument"項集生成函數(shù)描述 7ActionGoto表生成函數(shù) 8\o"CurrentDocument"句子識別函數(shù) 8\o"CurrentDocument"七、 運(yùn)行結(jié)果截圖 9\o"CurrentDocument"主界面 9Action矩陣和Goto矩陣 9\o"CurrentDocument"語法分析結(jié)果 10\o"CurrentDocument"八、 課程設(shè)計小結(jié) 10一、 課程設(shè)計概要課程設(shè)計由詞法分析、語法分析及語義分析構(gòu)成。詞法分析主要是屬性表的生成與展示；語法分析主要是ActionGoto表的生成、驅(qū)動程序的編寫和ActionGoto表的展示；語義分析組要是四元式的生成與展示。每個部分由一位小組成員單獨(dú)完成，小組成員經(jīng)過討論和協(xié)商完成整個課程設(shè)計的要求，構(gòu)成一個完整的系統(tǒng)。作為本次課程設(shè)計的組長，我主要負(fù)責(zé)的是語法分析部分以及如何將以上三部分整合，故在此報告中將著重對語法分析部分和整合部分進(jìn)行闡述，其他部分將在詞法分析、語義分析的報告中得到相應(yīng)得闡述。二、 語法分析設(shè)計思想地位及作用語法分析是根據(jù)某種給定的形式文法對由單詞序列(如英語單詞序列)構(gòu)成的輸入文本進(jìn)行分析并確定其語法結(jié)構(gòu)的一種過程。它通常用詞法分析所產(chǎn)生的屬性表序列作為輸入，來識其輸入的序列是否滿足文法的要求。設(shè)計思路分析方法語法分析器的任務(wù)主要是確定是否可以以及如何從語法的起始符號推導(dǎo)出輸入符號串，主要可以通過兩種方式完成：自頂向卞分析：根據(jù)形式語法規(guī)則，在語法分析樹的自頂向下展開中搜索輸入符號串可能的最左推導(dǎo)。單詞按從左到右的順序依次使用。自底向上分析：語法分析器從現(xiàn)有的輸入符號串開始，嘗試將其根據(jù)給定的形式語法規(guī)則進(jìn)行改寫，最終改寫為語法的起始符號。我采用的是自底向上的分析技術(shù)，主要使用的是SLR(l)分析方法。使用文法SLR(l)分析法的輸入是拓廣文法G[Z],如下所示：Z::=SS::=i=EE::=E+TE::=TT::=T*FT::=FF::=PP::=(E)P::=iP::=n文法存儲stmctRulef1chai左部符號；chai右部符號[MaxRightLenth]:mt右部長度；};〃聲明結(jié)構(gòu)體類型文法采用上述的結(jié)構(gòu)體數(shù)組進(jìn)行存儲。First集合和Follow集合因為在SLR(l)中我們要用到非終結(jié)符的Follow集合，而求Follow集合的我們又需要非終結(jié)符的First集合，所以，我們要先求他的First集合。在實(shí)現(xiàn)的過程中，我將求First集合和Follow集合都封裝在了Experement07這個類中了。在使用的過程中，只要給出非終結(jié)符、終結(jié)符和所有的文法，就能求出其文法對的First集合和Follow集合了！詳細(xì)實(shí)現(xiàn)見工程中的Expeiement07.cs文件中的源碼。構(gòu)造LR(O)項集規(guī)范簇LR(O)項集規(guī)范簇和規(guī)約式的左側(cè)非終極符的foUow集合可以用來構(gòu)造SLR(l)分析表。LR(0)項集規(guī)范簇的求解包含三部分：項集閉包的求解：由于項集中包含的項是動態(tài)增加的，因此，項集采用動態(tài)的數(shù)組List來存儲。轉(zhuǎn)換狀態(tài)的求解：確定狀態(tài)之間的轉(zhuǎn)換狀態(tài)I遇到符號X(XW(VtUVii))轉(zhuǎn)換到的狀態(tài)定義為：GO(LX)=CLOSURE({AfaX?B|A-a?XBWI},其中A-aX?B稱另A-ci.XB的后繼項。項集規(guī)范簇的構(gòu)造：從10的項集閉包開始，根據(jù)狀態(tài)的轉(zhuǎn)換，不斷增加項集規(guī)范簇中的項集個數(shù)，直至項集不再增加為止。構(gòu)造SLR(l)分析表ActionGoto表的構(gòu)造主要是通過項集之間的跳轉(zhuǎn)關(guān)系和文法產(chǎn)生式的規(guī)約關(guān)系來產(chǎn)生。當(dāng)一個產(chǎn)生式的識別位置到達(dá)最后的時候，那么就根據(jù)這個產(chǎn)生式前面的非終結(jié)符的Follow集合來規(guī)約到到達(dá)狀態(tài)，填入Actum表中。每一個項集狀態(tài)如果通過其他的非終結(jié)符跳轉(zhuǎn)到自己活著別的項集狀態(tài)，那么我們就對其規(guī)約到跳轉(zhuǎn)狀態(tài)，填入Action表中。如果是通過非終結(jié)符，那么我們就將跳轉(zhuǎn)的最終的狀態(tài)填入Goto表中。構(gòu)造字符串的分析過程在正確的程序編譯過程中，編譯時需要根據(jù)詞法分析器中的SLR(l)分析表來判斷所要編譯的句子是不是該文法的句子。字符串的分析過程中要求給出字符串的每一步的分析過程，輸出每一步所用的文法推導(dǎo)式。測試字符串的輸入也是采用外部文件輸入方式。三、語法分析器設(shè)計算法First集合生成算法掃描所有左部為A的產(chǎn)生式，、若A->￡,則將￡并入First(A)o、若A->a,則將a并入Fiist(A)。、若A4B.?…,則將Fust(B)Jt入First(A)。、若A->XB.…-或A->Xa?.…，且X->￡,則類似于(2)、(3)處理。Follow集合生成算法掃描所有右部包含A的產(chǎn)生式，(1)、若B->xAy,則將Fust(v)中的非￡終極符并入Follow(A)。⑵、若B->xA,或者B->xAy且y->E則將Follow(B)并入Follow(A)o(3)、若A是開始符，貝IJ將#弄入Follow(A)。構(gòu)造SLR(l)分析表計算項集I的閉包CLOSURE(I)=IU{E~?丫|A~a.EBWI,Y^P}。將起始文法并入Io對于I中，若A->a.BP且有產(chǎn)生式B->n,那么將B->.n并入I。對于A->Aa的產(chǎn)生式，判斷I中是否已經(jīng)存在該產(chǎn)生式，如果存在，繼續(xù)掃描I中的下一條文法。循壞(1)、(2)、(3),直到I不再增大。狀態(tài)之間的轉(zhuǎn)換GO(LX)=CLOSURE({A—aX?B|AfQ?XBWI},其中A-QX.B稱為A-a.XB的后繼項。J為GO到的項集。將J置空。對I中每一個形如A->Q?XB的項，將A?>aX?B并入J：調(diào)用CLOSURE(J),生成J的閉包。構(gòu)造LR(O)項集規(guī)范簇根據(jù)起始符號，構(gòu)造初始項集10,將10并入項集規(guī)范簇C對C中的每個項集I,若GO(I,X)非空且不在C中，那么將GO(I,X)并入C。循壞(2)、⑶直到C不再增大。構(gòu)造SLR(l)分析表對C中的項集IK如呆滿足GO(Ik,A)==Ij且A為非終極符，那么置矩陣GOTO[k][A]=j;對IK中的每項，若A->a.a3且GO(Ik?a)=Ij,那么置ACTION[k][a]=j+1000,襄示移進(jìn)操作;若A>a?，那么對Follow(A)中的每個終結(jié)符a,置ACTION[k][a]=1100+j,表示規(guī)約操作：若拓廣文法的第一項S->E.,那么置ACTION[k][#]=1200,表示接受句子。循壞IK中的每一項；循壞C中的每一項。句子識別FLAG：=TRUE；WHILEFLAGDOf把狀態(tài)棧頂元素上托出去并放在s中；IFACTION[S][a]==SjTHEN{把符號a推入符號棧；把狀態(tài)J推入狀態(tài)棧；把下一個輸入符號讀進(jìn)a：}ELSEIFACTION[S][a]==RjTHEN{從符號棧頂退出構(gòu)成句柄的相應(yīng)符號串:從狀態(tài)棧頂退出與句柄長度相等的若干狀態(tài)；把規(guī)則J的左部非終極符A推入符號棧；把GOTO[top（狀態(tài)棧）][A]推入狀態(tài)棧；輸出規(guī)則式J:}ELSEIFACTION[S][a]=accTHENFLAG:=FALSE；ELSEERROR：}END語法分析總控程序主要利用兩個棧作為語法分析的載體，其中一個棧為狀態(tài)棧，另一個棧為符號棧。算法通過狀態(tài)棧中棧頂?shù)慕K結(jié)符號與輸入符號中當(dāng)前輸入符號來查找ActionGoto表來進(jìn)行移進(jìn)和規(guī)約，進(jìn)行一系列的操作。通過ActionGoto表的驅(qū)動來使字符串來進(jìn)行規(guī)約到可接受狀態(tài)，否則出錯。四、項目整合Q館塊方龕CP，（2個項目），叵CP>AProperties>??■引用EGV>GlobalVar.es>GV.csGLA5AttributeWordTabie.esAttributeWordTableItem.es>c?ClassTable.es>c?ClassTableItem.es>c?lDTable.esc*LA.CSSA>c?Classl.es>c?Experement01.es>c?Experement07.esExperementl4.esExpcrcmcntl5.cst>c?GotoArtionTable_Key.esl>c?ltemSet.esl>c?Rule.est>c?Ruleltem.esc*Vialtem.es0App.configl>Proqram.es/回MyCompilerAAPropertiest>引角0App.configD圉Main.csl>Program.es工程CP：為實(shí)現(xiàn)項目業(yè)務(wù)邏輯類文件工程工程MyCompiler：為可視化界面工程五、流程圖構(gòu)造Follow集合的流程圖語法分析流程圖六、主要函數(shù)描述Follow函數(shù)描述變量名說明函數(shù)名generateFollow()該函數(shù)在類Experient07中實(shí)現(xiàn)，用來求一個文法的所有非終結(jié)符的Follow集合的傳入?yún)?shù)void由于是類內(nèi)的函數(shù)，在對象構(gòu)造的時候，所需參數(shù)己經(jīng)通過構(gòu)造函數(shù)傳入，所以此函數(shù)用到的參數(shù)有，文法，終結(jié)符，非終結(jié)符返回值void項集I的閉包函數(shù)描述變量名說明數(shù)函名TragerAddltemSet0該函數(shù)在類Experient14中實(shí)現(xiàn)，用于生成某一個項集中的一個產(chǎn)生式所觸發(fā)的所有后繼項傳入?yún)?shù)RuleltemRI項中加入的規(guī)則ruleintPosition_ISList這個項的在ISList中的位置返回值void項集生成函數(shù)描述變量名說明函數(shù)名GetStateTransitionDiagramO該函數(shù)在類experientl4中實(shí)現(xiàn)，用于生成所有的項集傳入?yún)?shù)void由于是類內(nèi)的函數(shù)，在對象構(gòu)造的時候，所需參數(shù)己經(jīng)通過構(gòu)造函數(shù)傳入，所以此函數(shù)用到的參數(shù)有，文法，終結(jié)符，非終結(jié)符返回值void返回值己經(jīng)封裝在類的內(nèi)部，所以此處實(shí)際的返回值是ISList（項集的列表）

ActionGoto表生成函數(shù)變量名說明函數(shù)名GetGotoActionTable()該函數(shù)在類Experientl4中實(shí)現(xiàn)，用來通過生成的項集來構(gòu)造ActionGoto表傳入?yún)?shù)void由于是類內(nèi)的函數(shù)，在對象構(gòu)造的時候，所需參數(shù)已經(jīng)通過構(gòu)造函數(shù)傳入，所以此函數(shù)用到的參數(shù)有，文法，終結(jié)符，非終結(jié)符返回值void返回值己經(jīng)封裝在類的內(nèi)部，所以此處實(shí)際的返回值是GotoActionTable（數(shù)據(jù)結(jié)構(gòu)是hash表）句子識別函數(shù)變量名說明數(shù)函名AnalysisSentence()該函數(shù)在類Experientl5中實(shí)現(xiàn)，用來通過GotoAction表的驅(qū)動來識別句子傳入?yún)?shù)intStartPlace要分析的句子在屬性表的起始位置返回值bool分析成功返回true否則返回false七、運(yùn)行結(jié)果截圖主界面菜單“生成”中有：詞法分析、ActionGoto表、語法分析、語義分析等菜單項。叫MyCompiler輸出文本13progrcm0c;tp輸出文本13progrcm0c;tpini0a12.0bL2,0c;L4bagin0a8=0:<20:0b8=naprcgr^n?xpixti夠b,c;bog；壯4=0x20：b=at2O：c二(a+b)心5：endAction矩陣和Goto矩陣說明：由于設(shè)計的時候釆用鍵值對的方式存儲，此處給出真正的表結(jié)構(gòu)不是很方便。所以采用了列表的方式展示。意思是：項X經(jīng)過A或者a（A為非終結(jié)符，a未終結(jié)符）結(jié)果是SX或RX或X（SX為移進(jìn)X壓入棧中，RX為用第X個產(chǎn)生式歸約，X為到第X項）。輜入姑progr^e：<pintdbc;輜入姑progr^e：<pintdbc;beg：iaa=Ox20;b=H2D;c二(a+b)*0x5;end輸出文本生質(zhì)ActionGoto羌項1經(jīng)眇結(jié)杲；xcc頂0經(jīng)過￡結(jié)1項U經(jīng)過】結(jié)果：SZ項2經(jīng)過二結(jié)果：S3項3經(jīng)過E結(jié)果：Q項3經(jīng)過T結(jié)杲：5頂3經(jīng)過F結(jié)里：6項3經(jīng)過F結(jié)杲：7頂3經(jīng)過（結(jié)舉：S8項3經(jīng)過】結(jié)果：59項3經(jīng)過"結(jié)果：S10頃4經(jīng)詞#結(jié)果：R1項4經(jīng)過十結(jié)杲；S11頂5經(jīng)過#結(jié)里：R3項5經(jīng)過+結(jié)杲：R3頂5經(jīng)過）結(jié)果^R3IffiS込河*結(jié)黑：￡1少語法分析結(jié)果對于語義分析，我們