編譯原理實(shí)驗(yàn)報(bào)告-語(yǔ)法分析

1、v1.0可編輯可修改編譯原理課程實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)2:語(yǔ)法分析姓名院系軟件學(xué)院學(xué)號(hào)任課教師指導(dǎo)教師實(shí)驗(yàn)地點(diǎn)軟件學(xué)院三樓機(jī)房實(shí)驗(yàn)時(shí)間2016/10/30/星期日實(shí)驗(yàn)課表現(xiàn)出勤、表現(xiàn)得分實(shí)驗(yàn)報(bào)告得分實(shí)驗(yàn)總分操作結(jié)果得分一、需求分析得分要求：采用至少一種句法分析技術(shù)(LL(1)、SLR(1)、LR(1)或LALR(1)對(duì)類高級(jí)語(yǔ)言中的基本語(yǔ)句進(jìn)行句法分析。闡述句法分析系統(tǒng)所要完成的功能。本語(yǔ)法分析器是在詞法分析器的基礎(chǔ)上實(shí)現(xiàn)對(duì)類高級(jí)語(yǔ)言中的基本語(yǔ)句進(jìn)行句法分析，基本功能如下：(1)能識(shí)別以下幾類語(yǔ)句：聲明語(yǔ)句(包括變量聲明、數(shù)組聲明、記錄聲明和過(guò)程聲明)表達(dá)式及賦值語(yǔ)句(包括數(shù)組元素的引用和賦值)分支語(yǔ)句

2、：if_then_else循環(huán)語(yǔ)句：do_while過(guò)程調(diào)用語(yǔ)句(2)本語(yǔ)法分析器采用自頂向下的分析技術(shù)，能根據(jù)導(dǎo)入的文法，自動(dòng)計(jì)算first集和follow集，能夠生成每個(gè)產(chǎn)生式的select集，并自動(dòng)生成預(yù)測(cè)分析表。(3)本語(yǔ)法分析器具備語(yǔ)法錯(cuò)誤處理能力，可以進(jìn)行錯(cuò)誤檢測(cè)，如果檢測(cè)到在出錯(cuò)時(shí)，采用恐慌模式，能夠給出錯(cuò)誤提示信息，格式：錯(cuò)誤項(xiàng)錯(cuò)誤原因行號(hào)a)忽略輸入中的一些符號(hào)，直到輸入中出現(xiàn)選定的同步詞法單元集合中的某個(gè)詞法單元，同步集合的選取是非終結(jié)符的follow集；b)如果終結(jié)符在棧頂而不能匹配，彈出此終結(jié)符。c)輸入棧中缺少某些應(yīng)有的符號(hào)，比如只有右括號(hào)沒(méi)有左括號(hào)等，會(huì)給出相應(yīng)的提

3、示。(4)系統(tǒng)的輸入形式多樣：可以通過(guò)文件導(dǎo)入文法和測(cè)試用例，可以通過(guò)用戶界面顯示并編輯測(cè)試用例。測(cè)試用例涵蓋了第(1)條中列出的各種類型的語(yǔ)句，并設(shè)置了一些語(yǔ)法錯(cuò)誤。(5)系統(tǒng)的輸出分為兩部分：一部分是打印輸出語(yǔ)法分析器的FIRST集、FOLLOW集、select集和LL(1)分析表。另一部分是打印輸出語(yǔ)法分析結(jié)果。(6)本系統(tǒng)還實(shí)現(xiàn)了輸出語(yǔ)法分析樹(shù)的功能，讓語(yǔ)法分析的過(guò)程更清晰。二、文法設(shè)計(jì)得分要求：給出如下語(yǔ)言成分的文法描述。聲明語(yǔ)句(包括變量聲明、數(shù)組聲明、記錄聲明和過(guò)程聲明)表達(dá)式及賦值語(yǔ)句(包括數(shù)組元素的引用和賦值)分支語(yǔ)句：if_then_else循環(huán)語(yǔ)句：do_while過(guò)程調(diào)

4、用語(yǔ)句本語(yǔ)法分析器主要針對(duì)C語(yǔ)言進(jìn)行文法設(shè)計(jì)，下面給出各語(yǔ)言成分的文法描述。程序入口：Program->PP->DP/支持連續(xù)聲明P->SPP->£1)聲明語(yǔ)句：Dprocid;DS|Tid;/支持過(guò)程聲明和變量聲明T一XC|recordD/支持結(jié)構(gòu)體聲明X一short|int|long|float|double|char|string/支持多種基本類型的聲明C一numC|£/支持?jǐn)?shù)組的聲明2)表達(dá)式及賦值語(yǔ)句：Sid=E;|L=E;EE+E|E*E|E|(E)|id|digit|LLidE|LE/支持?jǐn)?shù)組元素的引用和賦值3)控制流語(yǔ)句：SifBth

5、enS1elseS2|whileBdoS1B一B|B/或語(yǔ)句|B&&B/且語(yǔ)句|!B/非語(yǔ)句|(B)/使用括號(hào)|ErelopE/關(guān)系語(yǔ)句|true/bool型|false/bool型relop一<|<=|=|!=|>|>=/關(guān)系符號(hào)4)過(guò)程調(diào)用語(yǔ)句Scallid(Elist)ElistElist,EElistE卜面給出整個(gè)程序的無(wú)二義性，無(wú)左遞歸的LL(1)文法:Program->PP->DP|SP|emptyD->procTid(M)P|TidA;|recordidPM->XidM'M'->,XidM

6、9;|emptyA->=F|empty|,idAF->digit|id|char|G|stringG->HG'G'->,HG'|emptyH->digit|charT->XCX->short|int|long|float|double|char|void|string|booleanC->digitC|emptyS->L=E;|ifBthenSelseS|whileBdoS|callid(Elist);|returnE;E->-EE'|(E)E'|digitE'|LE'|stri

7、ngE'E'->+EE'|*EE'|emptyL->idL'L'->digitL'|emptyB->!BB'|(B)B'|ErelopEB'|trueB'|falseB'B'->orBB'|andBB'|emptyrelop-><|<=|=|!=|>|>=日ist->EElist'Elist'->,E曰ist'|empty注：此處用empty代表空三、系統(tǒng)設(shè)計(jì)得分要求：分為系統(tǒng)概要

8、設(shè)計(jì)和系統(tǒng)詳細(xì)設(shè)計(jì)。(1)系統(tǒng)概要設(shè)計(jì)：給出必要的系統(tǒng)宏觀層面設(shè)計(jì)圖，如系統(tǒng)框架圖、數(shù)據(jù)流圖、功能模塊結(jié)構(gòu)圖等以及相應(yīng)的文字說(shuō)明。1)系統(tǒng)的數(shù)據(jù)流圖：說(shuō)明說(shuō)明：本語(yǔ)法分析器是基于上一個(gè)實(shí)驗(yàn)詞法分析器的基礎(chǔ)上，通過(guò)在界面寫(xiě)或者是導(dǎo)入源程序，詞法分析器將源程序識(shí)別的詞法單元傳遞給語(yǔ)法分析器，語(yǔ)法分析器驗(yàn)證這個(gè)詞法單元組成的串是否可以由源語(yǔ)言的文法生成，能夠輸出語(yǔ)法分析的結(jié)果，文法的first集、follow集和預(yù)測(cè)分析表，當(dāng)然也可以以易于理解的方式報(bào)告語(yǔ)法錯(cuò)誤。2)系統(tǒng)框架圖皇頂利辦所用用資產(chǎn)笠或酸?一1幅到產(chǎn)場(chǎng)式里建費(fèi)國(guó)或單X有±E本系統(tǒng)框架主要是三部分，一部分是詞法分析，負(fù)責(zé)識(shí)別源程

9、序的詞法單元識(shí)別，并將其存儲(chǔ)，以供語(yǔ)法分析時(shí)讀??；第二部分是文法分析部分，負(fù)責(zé)將導(dǎo)入的文法進(jìn)行分析，得出文法的first集和follow集，以及自動(dòng)構(gòu)造出預(yù)測(cè)分析表，在語(yǔ)法分析時(shí)進(jìn)行查詢；第三部分是用戶界面，提供源程序輸入功能，以及語(yǔ)法分析結(jié)果的顯示，顯示語(yǔ)法分析樹(shù)，還有first集、follow集和預(yù)測(cè)分析表的展示。(2)系統(tǒng)詳細(xì)設(shè)計(jì)：對(duì)如下工作進(jìn)行展開(kāi)描述核心數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)核心數(shù)據(jù)結(jié)構(gòu)主要有兩種：1) Tuple三元組為了存儲(chǔ)預(yù)測(cè)分析表，我使用Tuple<string,string,string>三元組的數(shù)據(jù)結(jié)構(gòu)，分別存儲(chǔ)產(chǎn)生式的頭部，產(chǎn)生式體，輸入符號(hào)。2) Stack棧為了

10、能夠在語(yǔ)法分析時(shí)根據(jù)預(yù)測(cè)分析表來(lái)進(jìn)行分析，我寫(xiě)了一個(gè)CStack的類用來(lái)實(shí)現(xiàn)棧的數(shù)據(jù)結(jié)構(gòu)，在進(jìn)行語(yǔ)法分析時(shí)，一個(gè)棧用來(lái)存儲(chǔ)文法符號(hào)，一個(gè)棧用來(lái)存儲(chǔ)輸入符號(hào)，然后根據(jù)預(yù)測(cè)分析表進(jìn)行語(yǔ)法分析。主要功能函數(shù)說(shuō)明主要功能函數(shù)：1) IDContent類：功能：充當(dāng)符號(hào)表的角色，主要是用來(lái)保存關(guān)鍵字，運(yùn)算符，界符，轉(zhuǎn)義字符等各類單詞。主要函數(shù)：boolisConstCh(stringstr)/判斷是否轉(zhuǎn)義字符boolisLetter_(charc)/判斷是否字母或下劃線boolisDigit(charc)/判斷是否數(shù)字boolisBlank(charc)/判斷是否是空格、制表符、換行、回車boolisK

11、eyWord(stringstr)/判斷是否關(guān)鍵字boolisBoundary(charc)/判斷是否是邊界符號(hào)boolisOperator(stringch)/判斷是否運(yùn)算符2) Identifier類功能：識(shí)別單詞的核心類主要函數(shù)：stringisID(stringstr,refinti)/是否是標(biāo)識(shí)符stringisSixteen(stringstr,refinti,outboolright)/是否16進(jìn)制數(shù)stringisEight(stringstr,refinti,outboolright)/是否8進(jìn)制數(shù)stringisNumber(stringstr,refinti,outboo

12、lright)/是否是常數(shù)string isOperator( string str, refstring isNote( string str, ref intstring isBoundary( string str, refstring isChar( string str, ref int3) FirstAndFollow 類int i, out bool right)/是否是運(yùn)算符i,out bool right)/是否注釋int i, out bool right)/是否界符i,out bool right)/是否字符常數(shù)功能：得到first集、follow集、select集、預(yù)測(cè)

13、分析表publicvoidgetFirstCollection()/得到first集合publicvoidgetFollowCollection()/得到follow集合publicvoidgetSelectCollection()/得到預(yù)測(cè)分析表publicvoidgetAnalysisTable(stringstr1,stringstr2,stringstr3)/得到預(yù)測(cè)分析表publicvoiderrorHandle()/加入同步詞法單元324)CStack類功能：棧結(jié)構(gòu)publicboolisEmpty()/判斷棧是否為空publicvoidpush(objectitem)/往棧中加入

14、一個(gè)元素publicobjectpop()/從棧中彈出一個(gè)元素publicobjectpeek()/返回棧頂對(duì)象5)Form類publicvoidanalysis(stringstr)/詞法單元識(shí)別publicvoidparse()/語(yǔ)法單元識(shí)別privatevoid導(dǎo)入文法ToolStripMenuItem_Click(objectsender,EventArgse)/導(dǎo)入文法privatevoid顯示語(yǔ)法分析樹(shù)ToolStripMenuItem_Click(objectsender,EventArgse)/輸出語(yǔ)法分析樹(shù)privatevoidaddListview1Item()/輸出fir

15、st集和follow集privatevoidaddListview3Item()/輸出預(yù)測(cè)分析表程序核心部分的程序流程圖語(yǔ)法分析核心部分流程圖:開(kāi)始將文法開(kāi)始符號(hào)壓入文法棧中輸出語(yǔ)法分析樹(shù)法棧是是否為$從文法棧中取出頂?shù)姆?hào)從輸入棧中讀取詞法單元I*是否是產(chǎn)生結(jié)束將產(chǎn)生式的右部替換文法棧中產(chǎn)生式的左部報(bào)錯(cuò)掃描預(yù)測(cè)分析表彈出文法棧棧頂對(duì)棧頂是否為彈出文法棧棧頂對(duì)象和輸入棧棧頂對(duì)象和輸入棧型否入字符是否匹否配是“詞是:彈出文法棧頂對(duì)象彈出輸入棧棧頂象四、系統(tǒng)實(shí)現(xiàn)及結(jié)果分析得分要求：對(duì)如下內(nèi)容展開(kāi)描述。(1)系統(tǒng)實(shí)現(xiàn)過(guò)程中遇到的問(wèn)題；實(shí)現(xiàn)過(guò)程中主要遇到的問(wèn)題有：1)如何修改文法使其時(shí)LL(1)文法通

16、過(guò)對(duì)文法的修改，主要是對(duì)文法消除左遞歸，消除二義性，以及提取公因式等，最終對(duì)于相同左部的產(chǎn)生式他們的select集不相交，得到了LL(1)文法。2 )如何得到文法符號(hào)的first集對(duì)于終結(jié)符，其first集就是本身，但是對(duì)非終結(jié)符，在遍歷的時(shí)候依賴于其他的非終結(jié)符，于是我采用循環(huán)遍歷的方法，如果當(dāng)前某個(gè)非終結(jié)符的first集依賴于其他非終結(jié)符，且其他非終結(jié)符的first集還沒(méi)有求出來(lái)，則跳過(guò)當(dāng)前的非終結(jié)符求下一個(gè)非終結(jié)符的first集，直到其依賴的非終結(jié)符的first集求出來(lái)后再求解。直到所有的非終結(jié)符的first集求出來(lái)后，循環(huán)結(jié)束，就得到了所有文法符號(hào)的first集合。3 )如何得到非終結(jié)

17、符的follow集為了使思路清晰，我采用兩遍遍歷的方式來(lái)求非終結(jié)符的follow集。第一遍之后，所有非終結(jié)符都將得到一個(gè)暫時(shí)的follow集(不是最終的follow集)，第二遍的目標(biāo)就是發(fā)現(xiàn)其中是否有非終結(jié)符的follow集發(fā)生了改變，如果改變，則繼續(xù)遍歷整個(gè)文法，直到?jīng)]有新的符號(hào)加入follow集中。求follow集的具體思想就是：不斷應(yīng)用下列規(guī)則，直到?jīng)]有新的終結(jié)符可以被加入到任何FOLLO慷合中為止將$放入FOLLOWS)中，其中S是開(kāi)始符號(hào)，$是輸入右端的結(jié)束標(biāo)記如果存在一個(gè)產(chǎn)生式-“Bp,那么FIRST(§)中除£之外的所有符號(hào)都在FOLLOWB)中如果存在一個(gè)產(chǎn)

18、生式AaB,或存在產(chǎn)生式aBp且FIRST(§)包含e,那么FOLLOWA)中的所有符號(hào)都在FOLLOWB)中）如何根據(jù)預(yù)測(cè)分析表進(jìn)行語(yǔ)法分析這里主要依賴于棧的結(jié)構(gòu)，將經(jīng)過(guò)詞法分析得到的詞法單元壓入輸入棧，將文法起始符號(hào)壓入文法棧，然后根據(jù)預(yù)測(cè)分析表得到各個(gè)產(chǎn)生式進(jìn)行語(yǔ)法分析。(2)輸出該句法分析器的分析表;文法符號(hào)Frogram$Fr&grim->rprocFrcsgrsWtintFroprm->Flong:FrfloatFrogrwn->FdoubleFregrFP->e*ptyF->D?P->DPF->DFP->DFF-&

19、gt;DFp->drD3yHyhD->TlaA.D->TliA.E->7idA.I->TUAD->Tk.MM->IidMM->KidMM->Xi&TK->XidMM-aidK岷AFCG，HTXC5synchsync!T->XCI->shflrtsynT->ICX->int15yli型hT->XC工->1OI樣synchT->XCsynchT->XCsynchE£LLBb1relopElistElist"&9rPr<r4m->PvoidPrf

20、isrsm->?stringPirogrih-？FrecordFregrwn->PidProgrsi>->PifProgram->PwhileFrogrwn-FUrProgr»=>FP->B?p->rfP->DPP->DPP->SFF->SPF->SPF->SFD-)TidA；U->TiiA:D-?TitA；D.比電csynchsynclisynchLsynchM->XidftM->XilM歸雙ilM1B->ch.arHWf->Etrin.gF-Jidcharr->

21、xrKcha-T->XCI->¥oidT->XCX*>strin.,.synchsynchC">enptysynchipxohsynchlynchS->L=E;S-)iEE,.S->cal.E->L£JL->idL1L'emptyErd.U->Krel.synchEliEt_JEB.ssynchJTEturnProgram->PT-5S?1r>«iptysyncJi幅一*里.k->ridkVTemE站片F(xiàn)A->eiiipLydi£Jt!(syiichr-

22、.'diLCr->(l).對(duì)"G"G'：力p，y&f：4CHiyAcliCTdi哥5->retiir.qynchsynch50dEyvchB->digtMsynchE-)QB-ptyF一乳可勺E-)imptyE-gyujcK邙E1sn？ZLsyLcK510111L*-ieiipt/1/->Biiity17-XnptyLT*EmptyI?->E.SGHldl斤?Er*l.穹均syrteliIlist-?1.Ilist'_j.KT-EtE->fEiE"3"hEirk中mh,synrhcyn溫

23、Ft*ekF-xEfFX力ptyF->eiriptyEX*ptyIT->an.ytya-ynli耳皿;k工yn>?hsyn?k>yn?Lsyn?kl'->enptyL-fty1Z一注nptyLfenptyV-?in|ptyB->IreL.,B-?iB1VsynckcynckL由p-乂Tfllop-i<!=ral勺p-3=tJopT!=Elt'Et>1.sPElist->1,nyncsrw-FT餐liptyL"Jeiiptyswobz-*電nftye./elqIjJL-Z-1->4liiptTSi卯工jhLTe

24、nEySyiWFanriptyDsii54追s'T呻"EMch.E74巾ly工>«rptyx.jnciiL7g均cynth蘭加注synthBr>1JtBrETtrt*1B->fJsaS'->«rEV日TajsdH.f.才y因?yàn)轭A(yù)測(cè)分析表實(shí)在是過(guò)于龐大，因此本處分段截取預(yù)測(cè)分析表，下面的表是接在上面表的右側(cè)。(3)針對(duì)一測(cè)試程序輸出其句法分析結(jié)果；測(cè)試程序：假人區(qū)012345678901231234567 8 QJ11111111112222int a J*變里廣明*/cliar c - ? as =或：/*字符串聲明注

25、71;值 int 3 c = 黑2, %，哪組聲日再口賦惜磔的/甫*/a0 = 1：# (aM)支J3dtken a 三 aelsewhile (水1) /*嵌套的循環(huán)語(yǔ)句*/ do a=a+2;call addSuuk /*過(guò)程聲明， pioc int addSu>(int a, iat b) int c, d:c = %/*變量之間的寓值的口的函數(shù)”lettirn c+td ；,高支持返回值以表達(dá)式的形式瓶/*記錄聲明*/ record 皿int 1：char c;語(yǔ)法分析結(jié)果:語(yǔ)法分折結(jié)果Frograjnfl)FD(1)TX加上(1)id:a;PBTXcharid:uA=Fchar

26、：'M；PD(3)TXstzingid：s(3)A二(3)F(3)fixing；"aaa"DT(4)Kint(4)CC4)digit:3(4)C4)id:c(4)A(4)=F(4)GH(4)diit：1(4)G'，Hdigit:2(4)G'nH(4)dieit：3(4)G);(4)PSLid:a(5)LtilVI-WJ55il5(d/)H.rLE11-nJff&xx55K-5drl6SJ/l的)(B6fLRFio!T-LuJ(d)76(E(XJJ7rlk.7IQ77)(ir7)(Lth.s*E(7)digit：3(7);5ijrhileBB)

27、C(9)BE(9)Larelopdigii；1(9)do(IQ)S(10)L(10)id：a(10)=(10)E(10)L(10)id：:a(IC1)E!(10)+(10)E(10)digit:2(10):(10)P<1L)S(IDcall(11)id.:丑dd3刖(11)C(11)Elist(11)E(11>digit:1(11)Eli"'Cll),(11)E(11)digit:2(11)(11)：Hl)P(13)D(13)piQC(13)T(13>X(13)inf(13)id:addSujfc(13)(13)I(13)X(13)£nt(13)i

28、d：a(13)M(B).(13)XC13)int(13)id:b(13)-Ir-41(4L4t(1n1i-1A4I-15-1/Lx-Is)Id344(T-1-BT-I(CCDIQ1CJ-1-1-i(5/VL_(s)1pa51XIQXI/0(i71±-HJfx-s(17)letumC17jE(17)L(17)id:(17)E(17)十UT)EC17)LC17)id:d(17):(17)1(ie)P(20)D(20)record(20)id：m(20)()F(21)D(21)TC21)K(21)int(21)id:a(21):C21)F(22)D(22)T(22)義(22)char(.2

29、2)id;c(22);(22)(22)語(yǔ)法分析樹(shù):語(yǔ)法分析樹(shù)Tregran匚FIE)D=T!占工int白-id：IXTjjid-:.日-J_D.白AQie三-x±=-Txi=l-=HlB=TI=B3x-=-壬-=I-T工T3£：-intlzI-CklF品L3I-idiIH*C臼“G-Hj-iipt-1：由EHdi或tL.2占GFl-X目?jī)?cè)七p-else自5while白，Ei-(1=1Bi!iE:占L=II目斗iel-"relopI-I".ISE自digit1日了!：-產(chǎn)00i白*int百M(fèi)d:!<日M白.X!-intwidIiI:一a日就tI日p!

30、日L&-id"yL=is-eg&LHiiIa!.占F-)-5:白ig.LALdL.=;a.E!BLEj-iJLj-1-1PH,§rttwn.-E:白工I日idL-#i各V.)白-LE-ia白"pS"SJreturzi白E白L4dBlIQI百”工L_.4!5E日.L,"i_dherd亡id(4)f0目工iQ"Xchar1B輸出針對(duì)此測(cè)試程序?qū)?yīng)的語(yǔ)法錯(cuò)誤報(bào)告；帶錯(cuò)誤的測(cè)試程序:中國(guó)萬(wàn)歲產(chǎn)，字符未封閉可if (a>l誘風(fēng)門進(jìn)制格式，缺少分號(hào)*/Wmi)do a=a +工.0左-；/*錯(cuò)誤 call addSin Cl, 2): /*E zee ord stack &qu