編譯原理課程設(shè)計(jì)報(bào)告 (語法分析)

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

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