編譯原理課程設(shè)計將FOR語句轉(zhuǎn)換成四元式的程序?qū)崿F(xiàn)

PAGE3編譯原理實驗報告設(shè)計題目設(shè)計題目將FOR語句轉(zhuǎn)換成四元式的程序?qū)崿F(xiàn)學(xué)號學(xué)號學(xué)生姓名專業(yè)班級專業(yè)班級指導(dǎo)教師指導(dǎo)教師羅珣目錄引言2第一章概述31.1設(shè)計內(nèi)容31.2設(shè)計要求3第二章設(shè)計的基本原理32.1詞法分析32.2語法分析32.3語義分析32.4文法描述32.5屬性文法描述42.6語法分析方法描述52.7操作符優(yōu)先級62.8中間代碼形式描述62.9中間代碼序列的結(jié)構(gòu)設(shè)計7第三章程序設(shè)計73.1總體方案設(shè)計73.2各模塊設(shè)計8程序測試94.1測試方法94.2測試結(jié)果9第五章結(jié)論16參考文獻17附錄程序清單17合肥工業(yè)大學(xué)課程設(shè)計任務(wù)書設(shè)計題目將FOR語句轉(zhuǎn)換成四元式的程序?qū)崿F(xiàn)成績主要內(nèi)容設(shè)計內(nèi)容及要求：設(shè)計一個語法制導(dǎo)翻譯器，將FOR語句翻譯成四元式。要求：先確定一個定義FOR語句的文法，為其設(shè)計一個語法分析程序，為每條產(chǎn)生式配備一個語義子程序，按照一遍掃描的語法制導(dǎo)翻譯方法，實現(xiàn)翻譯程序。對用戶輸入的任意一個正確的FOR語句，程序?qū)⑵滢D(zhuǎn)換成四元式輸出(可按一定格式輸出到指定文件中)。指導(dǎo)教師意見該生能按時完成課程設(shè)計任務(wù)書所規(guī)定的程序設(shè)計，綜合運用所學(xué)知識獨立分析和解決問題的能力。程序設(shè)計方案。論文論述，文理，格式。程序運行結(jié)果。程序驗收時回答問題。簽名：第一章概述1.1設(shè)計內(nèi)容設(shè)計一個語法制導(dǎo)翻譯器，將FOR語句翻譯成四元式。1.2設(shè)計要求先確定一個定義FOR語句的文法，為其設(shè)計一個語法分析程序，為每條產(chǎn)生式配備一個語義子程序，按照一遍掃描的語法制導(dǎo)翻譯方法，實現(xiàn)翻譯程序。對用戶輸入的任意一個正確的FOR語句，程序?qū)⑵滢D(zhuǎn)換成四元式輸出(可按一定格式輸出到指定文件中)。第二章設(shè)計的基本原理2．1詞法分析設(shè)計詞法分析算法，每當語法分析程序需要一個單詞時，則調(diào)用該算法函數(shù)。詞法分析程序每調(diào)用一次，便從源程序文件中讀入一些字符，直到識別出一個單詞，送給語法分析器2．2語法分析采用遞歸下降方法，為對應(yīng)文法中的每個非終結(jié)符編寫一個遞歸過程，每個過程的功能是識別由該非終結(jié)符推出的串。若輸入串是給定文法的句子，則從文法的開始符號出發(fā)一定能推導(dǎo)出與輸入的單詞串完全相同的句子。2．3語義分析在語法分析的同時可由語法分析程序調(diào)用相應(yīng)的語義子程序進行語義處理，完成附加在所使用的產(chǎn)生式上的語義規(guī)則描述，并生成四元式的中間代碼形式。2．4文法描述遞歸下降法要求文法滿足LL(1)文法，則消除左遞歸后的文法如下：start→spsceofspsc→for[parse;parse;parse]{spsclist}|e list→parse;list |e parse→cdexprmorecdexprsmorecdexprs→=cdexprmorecdexprs|ecdexpr→cdsexprmorecdsexprsmorecdsexprs→||cdsexprmorecdsexprs |ecdsexpr→cdtermmorecdtermsmorecdterms→&&cdtermmorecdterms|ecdterm→cdstermmorecdstermsmorecdsterms→==cdstermmorecdsterms|!=cdstermmorecdsterms |ecdsterm→exprmoreexprsmoreexprs→<exprmoreexprs |<=exprmoreexprs |>exprmoreexprs |>=exprmoreexprs |eexpr→termmoretermsmoreterms→+termmoreterms |-termmoreterms |eterm→factormorefactorsmorefactors→*factormorefactors|/factormorefactors |efactor→!factor|(cdexpr)|id|num圖1FOR循環(huán)語句文法描述2．5屬性文法描述將語義規(guī)則附加在文法產(chǎn)生式的合適位置上，構(gòu)成屬性文法如下：start→spsceofspsc→for[parse;parse;parse]{spsclist}|e list→parse;list |e parse→cdexprmorecdexprsmorecdexprs→=cdexpr{print(“=”)}morecdexprs|ecdexpr→cdsexprmorecdsexprsmorecdsexprs→||cdsexpr{print(“||”)}morecdsexprs |ecdsexpr→cdtermmorecdtermsmorecdterms→&&cdterm{print(“&&”)}morecdterms|ecdterm→cdstermmorecdstermsmorecdsterms→==cdsterm{print(“==”)}morecdsterms|!=cdsterm{print(“!=”)}morecdsterms |ecdsterm→exprmoreexprsmoreexprs→<expr{print(“<”)}moreexprs |<=expr{print(“<=”)}moreexprs |>expr{print(“>”)}moreexprs |>=expr{print(“>=”)}moreexprs |eexpr→termmoretermsmoreterms→+term{print(“+”)}moreterms |-term{print(“-”)}moreterms |eterm→factormorefactorsmorefactors→*factor{print(“*”)}morefactors|/factor{print(“/”)}morefactors |efactor→!factor{print(“!”)}|(cdexpr)|id{print(id.lexeme)}|num{print(num.value)}圖2FOR循環(huán)語句屬性文法描述2.6語法分析方法描述遞歸下降分析方法是一種自頂向下語法分析方法，其目的是從文法的開始符號開始，根據(jù)輸入字符串進行最左推導(dǎo)，試圖推導(dǎo)出給定的字符串?；蛘哒f，從根節(jié)點（文法開始符號）開始，自上而下，從左到右地為輸入字符串建立一棵語法樹，并以預(yù)先確定的順序創(chuàng)建語法樹的節(jié)點。遞歸下降分析法可能需要回溯，即需要重復(fù)地掃描輸入。遞歸子程序法的實現(xiàn)思想是對應(yīng)每個非終結(jié)符編寫一個遞歸過程，每個過程的功能是識別由該非終結(jié)符推出的串，當某非終結(jié)符的產(chǎn)生式有多個候選式時，能夠按照LL（1）形式唯一地確定選擇某個候選式進行推導(dǎo)，因此首先要消除左遞歸。其文法及屬性文法如圖1和圖2所示。由于遞歸下降法對每個過程可能存在直接或間接的遞歸調(diào)用，所以對某個過程在退出之前可能又要被調(diào)用，因此有些信息需要保留，通常在入口時需保留某些信息，出口時需恢復(fù)。由于遞歸過程是遵循先進后出規(guī)律，通常開辟棧來處理。2.7操作符優(yōu)先級在對for循環(huán)語句進行翻譯時，涉及到對賦值表達式和布爾表達式語句的翻譯。在文法的描述中給出了算術(shù)運算符、關(guān)系運算符和邏輯運算符之間的優(yōu)先級關(guān)系，其結(jié)合性由下表所示：優(yōu)先級操作符類型操作對象的個數(shù)結(jié)合性1（）邏輯運算符——左—>右2!邏輯非運算符單目運算符右—>左3*,/算術(shù)運算符雙目運算符左—>右4+，-算術(shù)運算符雙目運算符左—>右5<,<=,>,>=關(guān)系運算符雙目運算符左—>右6==,!=關(guān)系運算符雙目運算符左—>右7&&邏輯與運算符雙目運算符左—>右8||邏輯或運算符雙目運算符左—>右9=賦值運算符雙目運算符右—>左2.8中間代碼形式的描述常見的中間代碼形式有逆波蘭記號，三元式，四元式和樹形表示。本課題設(shè)計輸出的中間代碼的表示方法是四元式。它是帶有四個域的記錄結(jié)構(gòu)，這四個域分別稱為算符op，第一運算對象arg1，第二運算對象arg2及結(jié)果result。域op包含一個代表運算符的內(nèi)部碼。例如x=yopz的四元式表示為（op,y,z,x）,即將y置于arg1域，z置于arg2域，x置于result域，=置于算符域op，如果op是單目運算符，例如非‘！’(x=!y)的四元式表示形式中不用填arg2。通常，四元式中的arg1，arg2和result的內(nèi)容都是一個指針，此指針指向有關(guān)名字的符號表入口。這樣，臨時變量名也要填入符號表中。2.9中間代碼序列的結(jié)構(gòu)設(shè)計型如for[parse1;parse2;parse3]{list}的中間代碼序列的結(jié)構(gòu)設(shè)計如下：parse1parse1parse2parse3listTRUEENDFALSE圖3中間代碼序列結(jié)構(gòu)設(shè)計第三章程序設(shè)計3．1總體方案設(shè)計本程序采用遞歸下降的方法實現(xiàn)FOR循環(huán)語句的翻譯，并以四元式的中間代碼形式輸出。經(jīng)過詞法分析，語法分析，同時執(zhí)行語法制導(dǎo)翻譯將中間結(jié)果表達出來，然后通過一個函數(shù)轉(zhuǎn)化成要求的四元式結(jié)構(gòu)的中間代碼。上述的這個過程在一遍掃描過程中完成：在語法分析的過程中調(diào)用詞法分析來不斷的分解出下一個句柄；在用遞歸下降方法進行語法分析的同時進行中間形式數(shù)據(jù)的保存，在分析出操作符號的同時結(jié)合當前棧中的數(shù)據(jù)輸出四元式。源文件源文件詞法分析語法分析語義分析中間代碼出錯處理3.2各模塊方案設(shè)計程序中各階段的功能如下：詞法分析階段對源程序流進行掃描，每識別出一個單詞，若是標識符，則到符號表中查找，如果符號表中沒有此標識符的記錄，那么將此標識符插入符號表。最后按照單詞其所屬的類別，把類標識返回，作為語法分析階段的輸入。詞法分析算法在symr.h頭文件中：voidsymbolnum()；voidsymbolchar()；voidsymbolothers()；intSymbolanalysis()；語法及語義分析階段由文法開始符號對應(yīng)的子程序控制for循環(huán)語句各個模塊的執(zhí)行順序，并由文法開始符號對應(yīng)的子程序遞歸調(diào)用其他的子程序，對各個模塊采用自頂向下，自左至右的推導(dǎo)方法完成對輸入字符進行匹配的工作，試圖推導(dǎo)出與輸入符號串一致的文法的句子。voidFor_s1(int*k,int*j)；//初值賦值語句voidFor_s2(int*k,int*j)；//條件判斷語句voidFor_s3(int*k,int*j)；//變量更新語句voidTrans_for();//for語句入口voidphrasinganalyse()；//語法語義分析中間代碼生成階段控制代碼的輸出形式，以四元式形式輸出中間代碼。中間代碼最終以cout語句和outfile、outfile2、oufile3文件輸出結(jié)果。程序測試4.1測試方法由于本程序在設(shè)計上考慮到for循環(huán)語句的多種表現(xiàn)形式，如for嵌套的方式，條件語句的表述等，所以在理論上能完成的功能很全，因此為了測試程序在實際應(yīng)用中能否完成這些功能，我設(shè)計了三種測試途徑：輸入最簡單的for循環(huán)語句（無嵌套）增加條件語句的復(fù)雜度實現(xiàn)簡單for嵌套，可包括多個賦值語句4.2測試結(jié)果（1）簡單的for循環(huán)語句（無嵌套）圖5簡單FOR循環(huán)輸入文件圖6詞法分析二元式結(jié)果圖7四元式輸出（2）增加條件語句的復(fù)雜度圖8FOR循環(huán)輸入圖9詞法分析結(jié)果圖10四元式輸出（3）簡單for循環(huán)嵌套圖11內(nèi)嵌FOR循環(huán)輸入圖12詞法分析結(jié)果圖13四元式輸出結(jié)論本程序?qū)崿F(xiàn)的功能有：簡單for循環(huán)，for循環(huán)嵌套，賦值語句，能完成的計算功能有布爾表達式，基本的四則運算，能將各個功能結(jié)合起來形成for循環(huán)，賦值語句，布爾表達式，空語句的復(fù)合出現(xiàn)。for語句的實現(xiàn)上，通過將之分解成三個表達式來分別調(diào)用，初值賦值語句、條件控制語句和變量更新語句。在詞法分析階段，區(qū)分一元和二元操作符的方法是：當取得的第一個字符為一元操作符時，繼續(xù)取下一個字符，若仍為操作符，則返回宏定義的標號，若不是操作符則將其放回，返回一元操作符的標號。在詞法分析階段在每一個類型判斷中都需要進行放回操作。對語法分析，詞法分析，四元式輸出分離設(shè)計，同步控制，使得代碼更靈活，結(jié)構(gòu)更緊湊，不必要對中間結(jié)果進行大量重復(fù)的存儲后，然后逐一檢索后使用。此次課程設(shè)計讓我想了老師說過的一句話：“編譯原理這門課很難”。經(jīng)過這次課程設(shè)計，我更體會到了這句話的含義。編譯原理這門課，不僅難理解而且很抽象。很多知識需要仔細琢磨才能理解，很多概念都很抽象，不找到例子很難搞明白。由于我本人C++編程并不好，很多的東西都不懂。所以，這次課程設(shè)計，我參考和查找了很多資料，也找同學(xué)詢問不懂的地方，請他們幫忙講解。經(jīng)過幾天的努力，按照以上所述的研制過程，終于做完了這次課程設(shè)計。將一個抽象的過程轉(zhuǎn)變?yōu)樵敿毜慕Y(jié)果，顯示出來。實現(xiàn)這個過程，是很有難度的。在設(shè)計時，通過仔細分析各功能程序段之間的聯(lián)系、函數(shù)的調(diào)用實現(xiàn)和程序代碼的運行效率，最終制定出了完整的程序?qū)崿F(xiàn)方案。本程序采用C++語言編寫，在編碼的過程中使我熟悉了C++語言的語法和庫函數(shù)的使用，以及數(shù)據(jù)結(jié)構(gòu)的應(yīng)用?，F(xiàn)在我能熟練的運用他們了，而且通過查看源代碼，對大部分庫函數(shù)的內(nèi)部實現(xiàn)有了一個很好的把握。通過此次課程設(shè)計，讓我看到了自己的很多不足之處。很多知識點知識淺嘗輒止，只看到了皮毛，沒有深入理解。人都是有惰性的，我也不例外。很多問題，都不愿意仔細思考。做事沒耐心，不能堅持到最后，輕易放棄也是我的重大缺點。這些問題，以后我必須盡量改正。只有這樣，才能有利于自己的發(fā)展，自己才能成為一個合格的大學(xué)生。參考文獻[1]陳火旺、劉春林、譚慶平、趙克佳、劉越．程序設(shè)計語言編譯原理（第3版）．國防工業(yè)出版社．2007年8月第46次印刷[2]李師賢、李文軍等.面向?qū)ο蟪绦蛟O(shè)計.高等教育出版社.2008年4月第6次印刷附錄程序清單#include"symr.h"http://S-->forS1S2S3Incycle//S1-->(E1；//S2-->E2;//S3-->E1)//Incycle-->E1;//(E1為賦值語句）//(E2為布爾表達式）voidphrasinganalyse();voideval(int*,int*);charjudge(string,string);voidTrans_for();strings[10]={"T1","T2","T3","T4","T5","T6","T7","T8","T9","T10"};stringad[5]={"Begin","Adress2","Again","Adress4","Exit"};stringad_e[20]={"(0)","(1)","(2)","(3)","(4)","(5)","(6)","(7)","(8)","(9)","(10)","(11)","(12)","(13)","(14)","(15)","(16)","(17)","(18)","(19)"};structgoto_adress{stringname;intvalue;}adress[5];//跳轉(zhuǎn)地址structexpression_adress{stringname;intvalue;}e_adress[20];//四元式地址stack<string>sqstacks;stack<string>sqstackr;fstreamoutfile2("outfile2.txt",ios::out);fstreamoutfile3("outfile3.txt",ios::out);stringbuffer[50];externintn;externSymbolattributesymattri[100];inti;intmain(){i=Symbolanalysis();phrasinganalyse();cin>>i;outfile2.close();return0;}//語法語義分析voidphrasinganalyse(){for(intm=0;m<5;m++)adress[m].name=ad[m];for(m=0;m<20;m++)e_adress[m].name=ad_e[m]; stringtype; stringch; do{ type=symattri[i].stype; if(type=="4"){ ch=symattri[i].svalue; if(ch=="for")Trans_for(); } i++; }while(i<n); return;}//跳轉(zhuǎn)地址回填voidbackpath(intl,int*j){adress[l].value=(*j);}/*循環(huán)語句*/voidIncircle(int*k,int*j){ into=i; cout<<adress[2].name<<":"<<endl; outfile2<<ad[2]<<":"<<"\n"; backpath(2,j); while(symattri[i].svalue!=")")i++; while(symattri[i].svalue=="{"||symattri[i].svalue==""||symattri[i].svalue==")"||symattri[i].svalue=="\n")i++; eval(k,j); i=o;}/*初值賦值語句*/voidFor_s1(int*k,int*j){ cout<<adress[0].name<<":"<<endl; outfile2<<adress[0].name<<":"<<"\n"; backpath(0,j); eval(k,j);}/*條件判斷語句*/voidFor_s2(int*k,int*j){ cout<<adress[1].name<<":"<<endl; outfile2<<adress[1].name<<":"<<"\n";backpath(1,j); eval(k,j); Incircle(k,j);}/*變量更新語句*/voidFor_s3(int*k,int*j){ cout<<adress[3].name<<":"<<endl; outfile2<<adress[3].name<<":"<<"\n"; backpath(3,j); eval(k,j); cout<<e_adress[*j].name<<"(jump"+adress[1].name+")"<<endl; outfile2<<e_adress[*j].name<<"(jump"+adress[1].name+")"<<"\n"; (*j)++; e_adress[*j].value=(*j); cout<<adress[4].name<<":"<<endl;backpath(4,j); outfile2<<adress[4].name<<":"<<"\n"; cout<<"analysishasfinished"<<endl;}/*for語句入口*/voidTrans_for(){ i++; if(symattri[i].svalue!="(")return;//actually,hereshouldgotoerror(); i++; intk=0; intj=0; For_s1(&k,&j);//S=>S1S2S3 For_s2(&k,&j); For_s3(&k,&j);for(intm=0;m<5;m++){cout<<adress[m].name<<"="<<adress[m].value<<endl;outfile3<<adress[m].name<<"="<<adress[m].value<<"\n";} return;}/*賦值語句分析函數(shù)*/voideval(int*k,int*j){ intm=i; stringch; stringsh; string*p; string*q; sqstacks.push("#"); sqstackr.push("#"); while(!(symattri[i].svalue==";")&&!(symattri[i].svalue==")")){ if(symattri[i].stype=="1"||symattri[i].stype=="2"||symattri[i].stype=="3") { ch=symattri[i].svalue; sqstacks.push(ch); i++;} if(!(symattri[i].svalue==";")&&!(symattri[i].svalue==")")) if(symattri[i].stype=="6"){ ch=symattri[i].svalue; p=&sqstackr.top(); switch(judge(ch,*p)){ case'=':; case'>':; sqstackr.push(ch); i++; break; case'<': sqstacks.push(symattri[i+1].svalue); buffer[2]=sqstacks.top();sqstacks.pop(); buffer[1]=sqstackr.top();sqstackr.pop(); buffer[0]=sqstacks.top();sqstacks.pop(); buffer[0]=e_adress[*j].name+"("+buffer[1]+""+buffer[0]+""+buffer[2]+""+s[*k]+")"+"\n"; sqstacks.push(s[*k]); sqstackr.push(ch); (*k)++; (*j)++; e_adress[*j].value=(*j); cout<<*buffer; outfile2<<*buffer; i++; break;} if(!(symattri[i].stype=="1"||symattri[i].stype=="2"||symattri[i].stype=="3"||symattri[i].svalue==";")){ cout<<"cancel"<<endl; } } else{cout<<"wrongsentence"<<endl;i++;} else{while(sqstackr.top()!="#"&&sqstackr.top()!="="&&sqstackr.top()!="<"&&sqstackr.top()!=">"){ buffer[2]=sqstacks.top();sqstacks.pop(); buffer[1]=sqstackr.top();sqstackr.pop(); buffer[0]=sqstacks.top();sqstacks.pop(); buffer[0]=e_adress[*j].name+"("+buffer[1]+""+buffer[0]+""+buffer[2]+""+s[*k]+")"+"\n"; sqstacks.push(s[*k]); //sqstackr.push(ch); cout<<*buffer; outfile2<<*buffer; (*k)++;(*j)++;e_adress[*j].value=(*j);} if(sqstackr.top()=="="){ buffer[2]=sqs