華北電力大學(xué)編譯實驗報告.doc

課程設(shè)計報告( 2012 - 2013年度第 1 學(xué)期) 名 稱：編譯技術(shù)課程設(shè)計B 題 目：詞法分析器設(shè)計 算符優(yōu)先分析程序設(shè)計 基于算符優(yōu)先分析方法的語法制導(dǎo)翻譯程序設(shè)計 院 系： 計算機(jī)系 班 級： 學(xué) 號： 學(xué)生姓名： 指導(dǎo)教師： 閻蕾, 岳燕 設(shè)計周數(shù)： 1周 成 績： 日期：年月日23編譯技術(shù)課程設(shè)計B任 務(wù) 書一、 目的與要求1詞法分析器設(shè)計的目的與要求1.1 詞法分析器設(shè)計的實驗?zāi)康谋緦嶒炇菫橛嬎銠C(jī)科學(xué)與技術(shù)專業(yè)、網(wǎng)絡(luò)工程專業(yè)、信息安全專業(yè)的學(xué)生在學(xué)習(xí)編譯技術(shù)課程后，為加深對課堂教學(xué)內(nèi)容的理解，培養(yǎng)解決實際問題能力而設(shè)置的實踐環(huán)節(jié)。通過這個實驗，使學(xué)生應(yīng)用編譯程序設(shè)計的原理和技術(shù)設(shè)計出詞法分析器，了解掃描器的組成結(jié)構(gòu)，不同種類單詞的識別方法。能使得學(xué)生在設(shè)計和調(diào)試編譯程序的能力方面有所提高。為將來設(shè)計、分析編譯程序打下良好的基礎(chǔ)。1.2 詞法分析器設(shè)計的實驗要求設(shè)計一個掃描器，該掃描器是一個子程序，其輸入是源程序字符串，每調(diào)用一次識別并輸出一個單詞符號。為了避免超前搜索，提高運(yùn)行效率，簡化掃描器的設(shè)計，假設(shè)該程序設(shè)計語言中，基本字（也稱關(guān)鍵詞）不能做一般標(biāo)識符用，如果基本字、標(biāo)識符和常數(shù)之間沒有確定的運(yùn)算符或界符作間隔，則用空白作間隔。單詞符號及其內(nèi)部表示如表1-1所示，單詞符號中標(biāo)識符由一個字母后跟多個字母、數(shù)字組成，常數(shù)由多個十進(jìn)制數(shù)字組成。單詞符號的內(nèi)部表示，即單詞的輸出形式為二元式：（種別編碼,單詞的屬性值）。表1-1單詞符號及其內(nèi)部表示單詞符號種別編碼單詞的屬性值BEGINIFTHENELSEEND標(biāo)識符整型常數(shù)+*（）123456789101112在名字表中的地址十進(jìn)制整數(shù)2算符優(yōu)先分析程序設(shè)計的目的和要求2.1 算符優(yōu)先分析程序設(shè)計的實驗?zāi)康谋緦嶒炇菫橛嬎銠C(jī)科學(xué)與技術(shù)專業(yè)的學(xué)生在學(xué)習(xí)編譯技術(shù)課程后，為加深對課堂教學(xué)內(nèi)容的理解，培養(yǎng)解決實際問題能力而設(shè)置的實踐環(huán)節(jié)。通過這個實驗，使學(xué)生應(yīng)用編譯程序設(shè)計的原理和技術(shù), 設(shè)計、編寫和調(diào)試算符優(yōu)先分析程序，了解算符優(yōu)先分析程序的組成結(jié)構(gòu)，掌握實現(xiàn)通用算符優(yōu)先分析算法的方法。能使得學(xué)生在設(shè)計和調(diào)試編譯程序的能力方面有所提高。為將來設(shè)計、分析編譯程序打下良好的基礎(chǔ)。2.2 算符優(yōu)先分析程序設(shè)計的實驗要求算符優(yōu)先分析屬于自下而上的分析方法，該語法分析程序的輸入是終結(jié)符號串（即單詞符號串，以一個“”結(jié)尾），如果輸入串是句子則輸出“YES”，否則輸出“NO”和錯誤信息。算符優(yōu)先分析過程與非終結(jié)符號無關(guān)，當(dāng)由文法產(chǎn)生了優(yōu)先關(guān)系之后文法也就失去了作用,本題目給出文法的目的是為了便于對語法分析結(jié)果進(jìn)行驗證。(1)文法設(shè)算符優(yōu)先文法為： 說明：i為整型常數(shù)或者為標(biāo)識符表示整型變量；使用中用*表示。(2)優(yōu)先關(guān)系表設(shè)優(yōu)先關(guān)系表如表1-2所示。表1-2優(yōu)先關(guān)系表+ * i ( ) # + * i ( ) # 3基于算符優(yōu)先分析方法的語法制導(dǎo)翻譯程序設(shè)計的目的和要求3.1 基于算符優(yōu)先分析方法的語法制導(dǎo)翻譯程序設(shè)計的實驗?zāi)康谋緦嶒炇菫橛嬎銠C(jī)科學(xué)與技術(shù)專業(yè)的學(xué)生在學(xué)習(xí)編譯技術(shù)課程后，為加深對課堂教學(xué)內(nèi)容的理解，培養(yǎng)解決實際問題能力而設(shè)置的實踐環(huán)節(jié)。通過這個實驗，使學(xué)生應(yīng)用編譯程序設(shè)計的原理和技術(shù), 通過設(shè)計、編寫和調(diào)試語法制導(dǎo)翻譯程序，掌握從一種語句的語法和語義出發(fā)，構(gòu)造相應(yīng)的語義子程序，實現(xiàn)基于算符優(yōu)先分析方法的語法制導(dǎo)翻譯的方法。能使得學(xué)生在設(shè)計和調(diào)試編譯程序的能力方面有所提高。為將來設(shè)計、分析編譯程序打下良好的基礎(chǔ)。3.2 基于算符優(yōu)先分析方法的語法制導(dǎo)翻譯程序設(shè)計的實驗要求算符優(yōu)先分析方法是通過反復(fù)把輸入符號移進(jìn)分析棧，使用優(yōu)先關(guān)系表在分析棧頂尋找最左素短語，將其歸約為一個非終結(jié)符號而實現(xiàn)的。這個分析過程與非終結(jié)符號無關(guān)，當(dāng)由文法產(chǎn)生了優(yōu)先關(guān)系之后文法也就失去了作用（所以本題目無需給出文法）?；谒惴麅?yōu)先分析方法的語法制導(dǎo)翻譯是在算符優(yōu)先語法分析的基礎(chǔ)上進(jìn)行翻譯工作（即語義分析），每當(dāng)將一個最左素短語歸約為一個非終結(jié)符號時，就調(diào)用對應(yīng)產(chǎn)生式的語義子程序，去完成相應(yīng)的語義翻譯工作，這步歸約使用的產(chǎn)生式對非終結(jié)符號不加區(qū)分（即將所有的非終結(jié)符號用一個通用的非終結(jié)符號表示）。語法制導(dǎo)翻譯程序的輸入是終結(jié)符號串（即單詞符號串，以一個“”結(jié)尾），如果輸入符號串是句子,則按照其語義進(jìn)行翻譯,輸出等價的四元式序列（作為練習(xí)應(yīng)顯示輸出）。4上機(jī)前的準(zhǔn)備為了充分利用上機(jī)時間，在進(jìn)行編譯技術(shù)上機(jī)實驗前應(yīng)做好各種準(zhǔn)備工作，具體應(yīng)包括：(1)復(fù)習(xí)與上機(jī)題目有關(guān)的知識，熟悉有關(guān)定義、概念和實現(xiàn)算法。(2)設(shè)計出程序流程框圖和數(shù)據(jù)結(jié)構(gòu)，編寫出完整的源程序，進(jìn)行靜態(tài)檢查。(3)為所編寫的程序構(gòu)思一個運(yùn)行、調(diào)試環(huán)境，例如，以什么方式提供輸入數(shù)據(jù)、顯示輸出數(shù)據(jù)，如何調(diào)用（或啟動）編寫的程序。制定出程序調(diào)試計劃和典型輸入代碼數(shù)據(jù)。5課程設(shè)計報告課程設(shè)計完成后，按學(xué)校給定的格式和要求寫出課程設(shè)計報告。二、 主要內(nèi)容完成以下課程設(shè)計內(nèi)容：1完成詞法分析器設(shè)計，實現(xiàn)輸入源程序字符串，每調(diào)用一次掃描器，就輸出一個以內(nèi)部形式表示的單詞符號，輸出形式為二元式：（種別編碼，單詞屬性）2完成算符優(yōu)先分析程序設(shè)計，掌握實現(xiàn)通用算符優(yōu)先分析算法的方法，實現(xiàn)輸入終結(jié)符號串（即單詞符號串，以一個“”結(jié)尾），如果輸入串是句子則輸出“YES”，否則輸出“NO”和錯誤信息。3完成基于算符優(yōu)先分析方法的語法制導(dǎo)翻譯程序設(shè)計，實現(xiàn)輸入是終結(jié)符號串（即單詞符號串，以一個“”結(jié)尾），如果輸入符號串是句子,則按照其語義進(jìn)行翻譯,輸出等價的四元式序列。三、 進(jìn)度計劃序號設(shè)計內(nèi)容完成時間備注1查閱資料，編譯器各部分概要設(shè)計一天2詞法分析器設(shè)計一天3算符優(yōu)先分析程序設(shè)計一天4基于算符優(yōu)先分析方法的語法制導(dǎo)翻譯程序設(shè)計一天半5驗收交實驗報告半天已完成的學(xué)生驗收交實驗報告四、設(shè)計成果要求1按進(jìn)度計劃和自己的能力完成課程設(shè)計內(nèi)容要求，包括程序框圖、源程序、調(diào)試步驟、調(diào)試方法、對運(yùn)行結(jié)果的分析等。 2總結(jié)整個課程設(shè)計，撰寫出課程設(shè)計報告。五、 考核方式1程序調(diào)試完成后，由指導(dǎo)教師在計算機(jī)上檢查，驗收課程設(shè)計成果，并現(xiàn)場答辯。2評閱課程設(shè)計報告。 學(xué)生姓名： （簽字） 指導(dǎo)教師： 年 月 日 實驗一詞法分析器的設(shè)計與實現(xiàn)一、課程設(shè)計(綜合實驗)的目的與要求1.1 詞法分析器設(shè)計的實驗?zāi)康谋緦嶒炇菫橛嬎銠C(jī)科學(xué)與技術(shù)專業(yè)的學(xué)生在學(xué)習(xí)編譯技術(shù)課程后，為加深對課堂教學(xué)內(nèi)容的理解，培養(yǎng)解決實際問題能力而設(shè)置的實踐環(huán)節(jié)。通過這個實驗，使學(xué)生應(yīng)用編譯程序設(shè)計的原理和技術(shù)設(shè)計出詞法分析器，了解掃描器的組成結(jié)構(gòu)，不同種類單詞的識別方法。能使得學(xué)生在設(shè)計和調(diào)試編譯程序的能力方面有所提高。為將來設(shè)計、分析編譯程序打下良好的基礎(chǔ)。1.2 詞法分析器設(shè)計的實驗要求設(shè)計一個掃描器，該掃描器是一個子程序，其輸入是源程序字符串，每調(diào)用一次識別并輸出一個單詞符號。為了避免超前搜索，提高運(yùn)行效率，簡化掃描器的設(shè)計，假設(shè)該程序設(shè)計語言中，基本字（也稱關(guān)鍵詞）不能做一般標(biāo)識符用，如果基本字、標(biāo)識符和常數(shù)之間沒有確定的運(yùn)算符或界符作間隔，則用空白作間隔。單詞符號及其內(nèi)部表示如表1-1所示，單詞符號中標(biāo)識符由一個字母后跟多個字母、數(shù)字組成，常數(shù)由多個十進(jìn)制數(shù)字組成。單詞符號的內(nèi)部表示，即單詞的輸出形式為二元式：（種別編碼,單詞的屬性值）。表1-1單詞符號及其內(nèi)部表示單詞符號種別編碼單詞的屬性值BEGINIFTHENELSEEND標(biāo)識符整型常數(shù)+*（）123456789101112在名字表中的地址十進(jìn)制整數(shù)二、設(shè)計（實驗）正文1.詞法分析器流程圖2.詞法分析器設(shè)計開始結(jié)束初始化讀入需要分析的句子還有單詞未分析？否是是字母？是否其他單詞分析程序是數(shù)字？否輸出單詞二元式關(guān)鍵字或標(biāo)識符分析程序讀一個字符是常數(shù)分析程序程序代碼/ first.cpp : 定義控制臺應(yīng)用程序的入口點(diǎn)。/#include stdafx.h#include #include using namespace std; int what(char a)if(int(a)=48)&(int(a)=97)&(int(a)=122)return 1;/a-z的字母elsereturn 2;/其他的標(biāo)點(diǎn)符號void scan(char a,int &m,char zc100100,int &n)char zh100;int b=0,weizhi,r=0;int zbbm;/-檢測整形常數(shù)while(am= )cout遇到空格endl;m+;if(what(am)=0)while(what(am)=0)b=b*10+int(am)-48;m+;zbbm=7;cout(zbbm,b)endl;else/-檢測字符型if(what(am)=1)if(am=b)&(am+1=e)&(am+2=g)&(am+3=i)&(am+4=n)&(what(am+5)=2)m=m+5;zbbm=1;cout(zbbm,-)endl;/=檢測beginelseif(am=i)&(am+1=f)&(what(am+2)=2)m=m+2;zbbm=2;cout(zbbm,-)endl;/檢測ifelseif(am=t)&(am+1=h)&(am+2=e)&(am+3=n)&(what(am+4)=2)m=m+4;zbbm=3;cout(zbbm,-)endl;/檢測thenelseif(am=e)&(am+1=l)&(am+2=s)&(am+3=e)&(what(am+4)=2)m=m+4;zbbm=4;cout(zbbm,-)endl;/檢測elseelseif(am=e)&(am+1=n)&(am+2=d)&(what(am+3)=2)m=m+3;zbbm=5;cout(zbbm,-)0)int k=0,y=1;while(kn)&(y=1)r=0;while(zckr!=#)r+;if(r!=j)k+;y=1;elseif(r=j)r=0;while(int(zckr)=int(zhr)&(rj)r+; if(r=j)weizhi=k+1;y=0;elsek+;y=1;if(y=1)j=0;while(zhj!=#)zcnj=zhj;j+;zcnj=#;n=n+1;weizhi=n;zbbm=6;/怎么輸出地址cout(zbbm,weizhi)endl; elseif(what(am)=2)if(am=+)zbbm=8;m+;cout(zbbm,-)endl;/檢測+elseif(am=()zbbm=11;m+;cout(zbbm,-)endl;/檢測（elseif(am=)zbbm=12;m+;cout(zbbm,-)endl;/檢測）elseif(am=*)if(am+1=*)zbbm=10;m+=2;elsezbbm=9;m+;cout(zbbm,-)endl;int main()char zc100100;int n=0;coutbegin-1endl;coutif -2endl;coutthen -3endl;coutelse -4endl;coutend -5endl;cout標(biāo)志符-6endl;cout整型常數(shù)-7endl;cout+-8endl;cout*-9endl;cout*-10endl;cout（-11endl;cout）-12endl;cout=endl;coutendl;int m=0;char a100; cout請輸入測試語句:; cin.getline(a,100,n); cout輸出格式為： (種別編碼，單詞的屬性值)endl;while(am!=#)scan(a,m,zc,n);return 0;3.詞法分析器運(yùn)行結(jié)果實驗二. 算符優(yōu)先分析的設(shè)計與實現(xiàn)一、課程設(shè)計(綜合實驗)的目的與要求2.1 算符優(yōu)先分析程序設(shè)計的實驗?zāi)康谋緦嶒炇菫橛嬎銠C(jī)科學(xué)與技術(shù)專業(yè)的學(xué)生在學(xué)習(xí)編譯技術(shù)課程后，為加深對課堂教學(xué)內(nèi)容的理解，培養(yǎng)解決實際問題能力而設(shè)置的實踐環(huán)節(jié)。通過這個實驗，使學(xué)生應(yīng)用編譯程序設(shè)計的原理和技術(shù), 設(shè)計、編寫和調(diào)試算符優(yōu)先分析程序，了解算符優(yōu)先分析程序的組成結(jié)構(gòu)，掌握實現(xiàn)通用算符優(yōu)先分析算法的方法。能使得學(xué)生在設(shè)計和調(diào)試編譯程序的能力方面有所提高。為將來設(shè)計、分析編譯程序打下良好的基礎(chǔ)。2.2 算符優(yōu)先分析程序設(shè)計的實驗要求算符優(yōu)先分析屬于自下而上的分析方法，該語法分析程序的輸入是終結(jié)符號串（即單詞符號串，以一個“”結(jié)尾），如果輸入串是句子則輸出“YES”，否則輸出“NO”和錯誤信息。算符優(yōu)先分析過程與非終結(jié)符號無關(guān)，當(dāng)由文法產(chǎn)生了優(yōu)先關(guān)系之后文法也就失去了作用,本題目給出文法的目的是為了便于對語法分析結(jié)果進(jìn)行驗證。(1)文法設(shè)算符優(yōu)先文法為： 說明：i為整型常數(shù)或者為標(biāo)識符表示整型變量；使用中用*表示。(2)優(yōu)先關(guān)系表設(shè)優(yōu)先關(guān)系表如表1-2所示。表1-2優(yōu)先關(guān)系表+ * i ( ) # + * i ( ) # 二、設(shè)計（實驗）正文1算符優(yōu)先分析流程圖開始結(jié)束初始化，顯示算符優(yōu)先矩陣打開需要讀入的文檔a的優(yōu)先關(guān)系大于arry中最后一個終結(jié)符？是是Array為空？否是將array中優(yōu)先關(guān)系一樣的字符規(guī)約為N構(gòu)造字符串s ，存儲需要分析的句子從s 中讀取一個字符a將a壓入數(shù)組array2.程序代碼/ third.cpp : 定義控制臺應(yīng)用程序的入口點(diǎn)。/#include stdafx.h#include #include malloc.h using namespace std;struct Lchar char char_ch; struct Lchar *next;LLchar,*p,*h,*temp,*top,*base;int table77=1,-1,-1,-1,-1,1,1, 1,1,-1,-1,-1,1,1, 1,1,-1,-1,-1,1,1, 1,1,1,0,0,1,1, -1,-1,-1,-1,-1,-1,0, 1,1,1,0,0,1,1, -1,-1,-1,-1,-1,0,-1; /存儲算符優(yōu)先關(guān)系表，大于為，小于或等于為-1，其它為表示出char curchar; char curcmp; int i,j; int k; int push(char pchar) /*入棧函數(shù)*/ temp=(Lchar*)malloc(sizeof(LLchar); /*分配動態(tài)內(nèi)存，返回一個指向內(nèi)存首地址的指針temp-char_ch=pchar; temp-next=top; top=temp; return 0; int pop() /*出棧函數(shù)*/ if(top-char_ch!=#) top=top-next; return 0; int change(char ch) /*將字符轉(zhuǎn)為數(shù)字，以得到算符優(yōu)先值*/ int t; switch(ch) case +:t=0;break; case *:t=1;break; case |:t=2;break; case i:t=3;break; case (:t=4;break; case ):t=5;break; case #:t=6; return t; int fenxi() int right=0;k=1; for(;) /*無條件的循環(huán) curchar=h-char_ch; temp=top; for(;) if(temp-char_ch=N) temp=temp-next; k+; else curcmp=temp-char_ch; break; coutendltableij ;temp=top; for(;) /*打印棧*/ coutchar_ch;if(temp-char_ch=#) break; else temp=temp-next; cout ; temp=h; for(;) /*打印待比較的字符*/ coutchar_ch; if(temp-char_ch=#) break; else temp=temp-next; i=change(curcmp); j=change(curchar); if(tableij=0) /*算符優(yōu)先值為空*/ coutendl錯誤 tableij curcmp curchar;right=0; break; else /*算符優(yōu)先值不為空*/ if(tableij0) /*算符優(yōu)先值為-1，移進(jìn)*/ if(curchar=#) /*待比較字符為空*/ if(k=2) /*當(dāng)前比較字符在棧的位置為兩個元素*/ break; else coutendl錯誤 tableij curcmp next; else /*算符優(yōu)先值為，歸約*/ if(curcmp=i) /*當(dāng)前比較為i,出棧一次*/ pop(); else /*當(dāng)前比較不為i,出棧三次*/ pop(); pop(); pop(); push(N); /*歸約到N*/ k=1; return 0; int main(void) char ch; int right=1; base=(Lchar*)malloc(sizeof(LLchar); base-next=NULL; base-char_ch=#; top=base; h=(Lchar*)malloc(sizeof(LLchar); h-next=NULL; p=h; cout輸入待比較字符串，以#結(jié)束ch;if(ch=i|ch=+|ch=*|ch=|ch=(|ch=)|ch=#) /*用temp保存運(yùn)算符，并使h指向temp，即保存運(yùn)算符的位置 temp=(Lchar*)malloc(sizeof(LLchar); temp-next=NULL; temp-char_ch=ch; h-next=temp; h=h-next; else cout輸入錯誤，請重新輸入，以#結(jié)束next; /*P指向待比較的字符串h=p; fenxi(); /*開始識別*/ if(right) coutendlYESendl;else coutendlNOendl;return 0; 3.實驗運(yùn)行結(jié)果如下：實驗三. 基于算符優(yōu)先分析方法的語法制導(dǎo)翻譯的設(shè)計與實現(xiàn)一、課程設(shè)計(綜