編譯原理課程設計將FOR語句轉換成四元式的程序實現(xiàn)

PAGE3編譯原理實驗報告設計題目設計題目將FOR語句轉換成四元式的程序實現(xiàn)學號學號學生姓名專業(yè)班級專業(yè)班級指導教師指導教師羅珣目錄引言2第一章概述31.1設計內容31.2設計要求3第二章設計的基本原理32.1詞法分析32.2語法分析32.3語義分析32.4文法描述32.5屬性文法描述42.6語法分析方法描述52.7操作符優(yōu)先級62.8中間代碼形式描述62.9中間代碼序列的結構設計7第三章程序設計73.1總體方案設計73.2各模塊設計8程序測試94.1測試方法94.2測試結果9第五章結論16參考文獻17附錄程序清單17合肥工業(yè)大學課程設計任務書設計題目將FOR語句轉換成四元式的程序實現(xiàn)成績主要內容設計內容及要求：設計一個語法制導翻譯器，將FOR語句翻譯成四元式。要求：先確定一個定義FOR語句的文法，為其設計一個語法分析程序，為每條產生式配備一個語義子程序，按照一遍掃描的語法制導翻譯方法，實現(xiàn)翻譯程序。對用戶輸入的任意一個正確的FOR語句，程序將其轉換成四元式輸出(可按一定格式輸出到指定文件中)。指導教師意見該生能按時完成課程設計任務書所規(guī)定的程序設計，綜合運用所學知識獨立分析和解決問題的能力。程序設計方案。論文論述，文理，格式。程序運行結果。程序驗收時回答問題。簽名：第一章概述1.1設計內容設計一個語法制導翻譯器，將FOR語句翻譯成四元式。1.2設計要求先確定一個定義FOR語句的文法，為其設計一個語法分析程序，為每條產生式配備一個語義子程序，按照一遍掃描的語法制導翻譯方法，實現(xiàn)翻譯程序。對用戶輸入的任意一個正確的FOR語句，程序將其轉換成四元式輸出(可按一定格式輸出到指定文件中)。第二章設計的基本原理2．1詞法分析設計詞法分析算法，每當語法分析程序需要一個單詞時，則調用該算法函數(shù)。詞法分析程序每調用一次，便從源程序文件中讀入一些字符，直到識別出一個單詞，送給語法分析器2．2語法分析采用遞歸下降方法，為對應文法中的每個非終結符編寫一個遞歸過程，每個過程的功能是識別由該非終結符推出的串。若輸入串是給定文法的句子，則從文法的開始符號出發(fā)一定能推導出與輸入的單詞串完全相同的句子。2．3語義分析在語法分析的同時可由語法分析程序調用相應的語義子程序進行語義處理，完成附加在所使用的產生式上的語義規(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ī)則附加在文法產生式的合適位置上，構成屬性文法如下：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ù)輸入字符串進行最左推導，試圖推導出給定的字符串。或者說，從根節(jié)點（文法開始符號）開始，自上而下，從左到右地為輸入字符串建立一棵語法樹，并以預先確定的順序創(chuàng)建語法樹的節(jié)點。遞歸下降分析法可能需要回溯，即需要重復地掃描輸入。遞歸子程序法的實現(xiàn)思想是對應每個非終結符編寫一個遞歸過程，每個過程的功能是識別由該非終結符推出的串，當某非終結符的產生式有多個候選式時，能夠按照LL（1）形式唯一地確定選擇某個候選式進行推導，因此首先要消除左遞歸。其文法及屬性文法如圖1和圖2所示。由于遞歸下降法對每個過程可能存在直接或間接的遞歸調用，所以對某個過程在退出之前可能又要被調用，因此有些信息需要保留，通常在入口時需保留某些信息，出口時需恢復。由于遞歸過程是遵循先進后出規(guī)律，通常開辟棧來處理。2.7操作符優(yōu)先級在對for循環(huán)語句進行翻譯時，涉及到對賦值表達式和布爾表達式語句的翻譯。在文法的描述中給出了算術運算符、關系運算符和邏輯運算符之間的優(yōu)先級關系，其結合性由下表所示：優(yōu)先級操作符類型操作對象的個數(shù)結合性1（）邏輯運算符——左—>右2!邏輯非運算符單目運算符右—>左3*,/算術運算符雙目運算符左—>右4+，-算術運算符雙目運算符左—>右5<,<=,>,>=關系運算符雙目運算符左—>右6==,!=關系運算符雙目運算符左—>右7&&邏輯與運算符雙目運算符左—>右8||邏輯或運算符雙目運算符左—>右9=賦值運算符雙目運算符右—>左2.8中間代碼形式的描述常見的中間代碼形式有逆波蘭記號，三元式，四元式和樹形表示。本課題設計輸出的中間代碼的表示方法是四元式。它是帶有四個域的記錄結構，這四個域分別稱為算符op，第一運算對象arg1，第二運算對象arg2及結果result。域op包含一個代表運算符的內部碼。例如x=yopz的四元式表示為（op,y,z,x）,即將y置于arg1域，z置于arg2域，x置于result域，=置于算符域op，如果op是單目運算符，例如非‘！’(x=!y)的四元式表示形式中不用填arg2。通常，四元式中的arg1，arg2和result的內容都是一個指針，此指針指向有關名字的符號表入口。這樣，臨時變量名也要填入符號表中。2.9中間代碼序列的結構設計型如for[parse1;parse2;parse3]{list}的中間代碼序列的結構設計如下：parse1parse1parse2parse3listTRUEENDFALSE圖3中間代碼序列結構設計第三章程序設計3．1總體方案設計本程序采用遞歸下降的方法實現(xiàn)FOR循環(huán)語句的翻譯，并以四元式的中間代碼形式輸出。經過詞法分析，語法分析，同時執(zhí)行語法制導翻譯將中間結果表達出來，然后通過一個函數(shù)轉化成要求的四元式結構的中間代碼。上述的這個過程在一遍掃描過程中完成：在語法分析的過程中調用詞法分析來不斷的分解出下一個句柄；在用遞歸下降方法進行語法分析的同時進行中間形式數(shù)據(jù)的保存，在分析出操作符號的同時結合當前棧中的數(shù)據(jù)輸出四元式。源文件源文件詞法分析語法分析語義分析中間代碼出錯處理3.2各模塊方案設計程序中各階段的功能如下：詞法分析階段對源程序流進行掃描，每識別出一個單詞，若是標識符，則到符號表中查找，如果符號表中沒有此標識符的記錄，那么將此標識符插入符號表。最后按照單詞其所屬的類別，把類標識返回，作為語法分析階段的輸入。詞法分析算法在symr.h頭文件中：voidsymbolnum()；voidsymbolchar()；voidsymbolothers()；intSymbolanalysis()；語法及語義分析階段由文法開始符號對應的子程序控制for循環(huán)語句各個模塊的執(zhí)行順序，并由文法開始符號對應的子程序遞歸調用其他的子程序，對各個模塊采用自頂向下，自左至右的推導方法完成對輸入字符進行匹配的工作，試圖推導出與輸入符號串一致的文法的句子。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文件輸出結果。程序測試4.1測試方法由于本程序在設計上考慮到for循環(huán)語句的多種表現(xiàn)形式，如for嵌套的方式，條件語句的表述等，所以在理論上能完成的功能很全，因此為了測試程序在實際應用中能否完成這些功能，我設計了三種測試途徑：輸入最簡單的for循環(huán)語句（無嵌套）增加條件語句的復雜度實現(xiàn)簡單for嵌套，可包括多個賦值語句4.2測試結果（1）簡單的for循環(huán)語句（無嵌套）圖5簡單FOR循環(huán)輸入文件圖6詞法分析二元式結果圖7四元式輸出（2）增加條件語句的復雜度圖8FOR循環(huán)輸入圖9詞法分析結果圖10四元式輸出（3）簡單for循環(huán)嵌套圖11內嵌FOR循環(huán)輸入圖12詞法分析結果圖13四元式輸出結論本程序實現(xiàn)的功能有：簡單for循環(huán)，for循環(huán)嵌套，賦值語句，能完成的計算功能有布爾表達式，基本的四則運算，能將各個功能結合起來形成for循環(huán)，賦值語句，布爾表達式，空語句的復合出現(xiàn)。for語句的實現(xiàn)上，通過將之分解成三個表達式來分別調用，初值賦值語句、條件控制語句和變量更新語句。在詞法分析階段，區(qū)分一元和二元操作符的方法是：當取得的第一個字符為一元操作符時，繼續(xù)取下一個字符，若仍為操作符，則返回宏定義的標號，若不是操作符則將其放回，返回一元操作符的標號。在詞法分析階段在每一個類型判斷中都需要進行放回操作。對語法分析，詞法分析，四元式輸出分離設計，同步控制，使得代碼更靈活，結構更緊湊，不必要對中間結果進行大量重復的存儲后，然后逐一檢索后使用。此次課程設計讓我想了老師說過的一句話：“編譯原理這門課很難”。經過這次課程設計，我更體會到了這句話的含義。編譯原理這門課，不僅難理解而且很抽象。很多知識需要仔細琢磨才能理解，很多概念都很抽象，不找到例子很難搞明白。由于我本人C++編程并不好，很多的東西都不懂。所以，這次課程設計，我參考和查找了很多資料，也找同學詢問不懂的地方，請他們幫忙講解。經過幾天的努力，按照以上所述的研制過程，終于做完了這次課程設計。將一個抽象的過程轉變?yōu)樵敿毜慕Y果，顯示出來。實現(xiàn)這個過程，是很有難度的。在設計時，通過仔細分析各功能程序段之間的聯(lián)系、函數(shù)的調用實現(xiàn)和程序代碼的運行效率，最終制定出了完整的程序實現(xiàn)方案。本程序采用C++語言編寫，在編碼的過程中使我熟悉了C++語言的語法和庫函數(shù)的使用，以及數(shù)據(jù)結構的應用。現(xiàn)在我能熟練的運用他們了，而且通過查看源代碼，對大部分庫函數(shù)的內部實現(xiàn)有了一個很好的把握。通過此次課程設計，讓我看到了自己的很多不足之處。很多知識點知識淺嘗輒止，只看到了皮毛，沒有深入理解。人都是有惰性的，我也不例外。很多問題，都不愿意仔細思考。做事沒耐心，不能堅持到最后，輕易放棄也是我的重大缺點。這些問題，以后我必須盡量改正。只有這樣，才能有利于自己的發(fā)展，自己才能成為一個合格的大學生。參考文獻[1]陳火旺、劉春林、譚慶平、趙克佳、劉越．程序設計語言編譯原理（第3版）．國防工業(yè)出版社．2007年8月第46次印刷[2]李師賢、李文軍等.面向對象程序設計.高等教育出版社.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];//跳轉地址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;}//跳轉地址回填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