《編譯原理》課程設(shè)計(jì)說明書-DO-WHILE循環(huán)語(yǔ)句的翻譯程序設(shè)計(jì)(LR方法、輸出三地址表示).doc

*理工大學(xué)編譯原理課程設(shè)計(jì)說明書第1頁(yè)共16頁(yè)DO-WHILE循環(huán)語(yǔ)句的翻譯程序設(shè)計(jì)（LR方法、輸出三地址表示）1.系統(tǒng)描述1.1設(shè)計(jì)目的通過設(shè)計(jì)、編制、調(diào)試一個(gè)DO-WHILE循環(huán)語(yǔ)句的語(yǔ)法及語(yǔ)義分析程序，加深對(duì)語(yǔ)法及語(yǔ)義分析原理的理解，并實(shí)現(xiàn)詞法分析程序?qū)卧~序列的詞法檢查和分析。1.2設(shè)計(jì)內(nèi)容及步驟對(duì)循環(huán)語(yǔ)句：DO賦值語(yǔ)句WHILE表達(dá)式按給定的題目寫出符合自身語(yǔ)法分析方法要求的文法和屬性文法描述。(1)按給定的題目給出語(yǔ)法分析方法的思想及分析表設(shè)計(jì)。(2)按給定的題目給出中間代碼序列的結(jié)構(gòu)設(shè)計(jì)。(3)完成相應(yīng)的詞法分析、語(yǔ)法分析和語(yǔ)義分析程序設(shè)計(jì)。(4)編制好分析程序后，設(shè)計(jì)若干用例，上機(jī)測(cè)試并通過所設(shè)計(jì)的分析程序。2文法的描述本程序所用的文法如下：GS:(1)S-doE；while(B)ifB.truegotoB.trueelsegotoB.false；(2)B-I1ropI2B.type=bool；B.val=I1.valropI2.val；(3)E-I1=I2opI3I1.val=I2.valopI3.val；(4)I-idI.val=id.val；注意：ropis，opis+,-,*,/,idisanynumberoridentifier由上可知，非終結(jié)符B表示布爾表達(dá)式，E表示賦值表達(dá)式3.語(yǔ)法分析方法描述及語(yǔ)法分析表設(shè)計(jì)3.1語(yǔ)法分析方法描述本實(shí)驗(yàn)采用LR分析方法對(duì)DO-WHILE語(yǔ)句進(jìn)行語(yǔ)法分析。LR分析法是一種能根據(jù)當(dāng)前分析棧中的符號(hào)串（通常以狀態(tài)表示）和向右順序查看輸入串的K個(gè)（K=0）符號(hào)就能惟一的確定分析器的動(dòng)作是移進(jìn)還是歸約和用哪個(gè)產(chǎn)生式歸約，因而也就能惟一的確定句柄。LR分析法的歸約過程是規(guī)范推導(dǎo)的逆過程，所以LR分析過程是一種規(guī)范過程。一個(gè)LR分析器由3個(gè)部分組成：總控程序，也可以稱為驅(qū)動(dòng)程序。對(duì)所有的LR分析器，總控程序是相同的。分析表或分析函數(shù)。不同的方法分析表將不同，同一個(gè)方法采用的LR分析器不同時(shí)，分析表也不同，分析表表又可以分為動(dòng)作（ACTION）表和狀態(tài)轉(zhuǎn)換（GOTO）表兩個(gè)部分，它們都可以用二維數(shù)組表示。分析棧，包括文法符號(hào)棧和相應(yīng)的狀態(tài)棧。它們均是先進(jìn)后出棧。*理工大學(xué)編譯原理課程設(shè)計(jì)說明書第2頁(yè)共16頁(yè)分析器的動(dòng)作由棧頂狀態(tài)和當(dāng)前輸入符號(hào)所決定。LR分析器工作過程示意圖如圖所示：其中SP為棧頂指針，Si為狀態(tài)棧，Xi為文法符號(hào)棧。狀態(tài)轉(zhuǎn)換表內(nèi)容按關(guān)系GOTOSi,X=Sj確定，改關(guān)系式是指當(dāng)前棧頂狀態(tài)為Si遇到當(dāng)前文法符號(hào)為X時(shí)應(yīng)轉(zhuǎn)向狀態(tài)Sj。X為終結(jié)符或非終結(jié)符。ACTIONSi,a規(guī)定了棧頂狀態(tài)為Sj時(shí)遇到輸入符號(hào)ci應(yīng)該執(zhí)行的動(dòng)作。動(dòng)作有以下四種可能：移進(jìn)：當(dāng)Sj=GOTOSi，a成立，則把Sj移入到文法符號(hào)棧。其中i，j表示狀態(tài)號(hào)。規(guī)約：當(dāng)在棧頂形成句柄為b時(shí)，則用b歸約為相應(yīng)的非終結(jié)符A，即當(dāng)文法中有A-b的產(chǎn)生式，而b的長(zhǎng)度為r，則從狀態(tài)棧和文法符號(hào)棧中自棧頂向下去掉r個(gè)符號(hào)。并把A移入文法符號(hào)棧內(nèi)，再把滿足Sj=GOTOSi，A的狀態(tài)移進(jìn)狀態(tài)棧，其中Si為修改指針后的棧頂狀態(tài)。接受acc：當(dāng)歸約到文法符號(hào)棧中只剩下文法的開始符號(hào)S時(shí)，并且輸入符號(hào)串已結(jié)束即當(dāng)前輸入符是#，則為分析成功。報(bào)錯(cuò)：當(dāng)遇到狀態(tài)棧頂為某一狀態(tài)下出現(xiàn)不該遇到的文法符號(hào)時(shí)，則報(bào)錯(cuò)，說明輸入串不是該分發(fā)能接受的句子。3.2語(yǔ)法分析表設(shè)計(jì)3.2.1構(gòu)造文法的DFAI0:S-.SS-.doE；while(B)I1:S-S.I2:S-do.E；while(B)I3:S-do.E；while(B)E-.I=IopII-.id輸入串XXX#總控程序ACTION表GOTO表Sn.S1S0Xn.X1#SP輸出*理工大學(xué)編譯原理課程設(shè)計(jì)說明書第3頁(yè)共16頁(yè)I4:S-doE.；while(B)I5:E-I.=IopII6:I-id.I7:S-doE；.while(B)I8:E-I=.IopII-.idI9:S-doE；.while(B)I10:E-I=I.opII11:S-doE；while.(B)I12:E-I=Iop.II=.idI13:S-doE；while(.B)B-.IropII-.idI14:E-I=IopI.I15:S-doE；while(B.)I16:B-I.ropII17:S-doE；while(B).I18:B-Irop.II19:B-IropI.3.2.2然后寫出LR分析表：狀態(tài)ACTIONGOTODo=；While()RopOpId#SBEI0S211acc2S3I1I0I19I4I13I9I14I15I12I6I10I8I2I7I16I11I5I3I17I18*理工大學(xué)編譯原理課程設(shè)計(jì)說明書第4頁(yè)共16頁(yè)3S6454S75S86R4R4R4R4R4R4R4R4R4R4R4R47S98S6109S1110S1211S1312S1413S6151614R3R3R3R3R3R3R3R3R3R3R3R315S1716S1817R1R1R1R1R1R1R1R1R1R1R1R118S61919R2R2R2R2R2R2R2R2R2R2R2R24.中間代碼形式的描述及中間代碼序列的結(jié)構(gòu)設(shè)計(jì)4.1中間代碼形式的描述在本程序中作用三地址碼表示中間代碼三地址碼的表達(dá)形式為：標(biāo)號(hào)結(jié)果：=操作數(shù)1操作符操作數(shù)2常見三地址表示舉例：賦值