華北電力大學編譯實驗報告.doc

課程設計報告( 2012 - 2013年度第 1 學期) 名 稱：編譯技術(shù)課程設計B 題 目：詞法分析器設計 算符優(yōu)先分析程序設計 基于算符優(yōu)先分析方法的語法制導翻譯程序設計 院 系： 計算機系 班 級： 學 號： 學生姓名： 指導教師： 閻蕾, 岳燕 設計周數(shù)： 1周 成 績： 日期：年月日23編譯技術(shù)課程設計B任 務 書一、 目的與要求1詞法分析器設計的目的與要求1.1 詞法分析器設計的實驗目的本實驗是為計算機科學與技術(shù)專業(yè)、網(wǎng)絡工程專業(yè)、信息安全專業(yè)的學生在學習編譯技術(shù)課程后，為加深對課堂教學內(nèi)容的理解，培養(yǎng)解決實際問題能力而設置的實踐環(huán)節(jié)。通過這個實驗，使學生應用編譯程序設計的原理和技術(shù)設計出詞法分析器，了解掃描器的組成結(jié)構(gòu)，不同種類單詞的識別方法。能使得學生在設計和調(diào)試編譯程序的能力方面有所提高。為將來設計、分析編譯程序打下良好的基礎(chǔ)。1.2 詞法分析器設計的實驗要求設計一個掃描器，該掃描器是一個子程序，其輸入是源程序字符串，每調(diào)用一次識別并輸出一個單詞符號。為了避免超前搜索，提高運行效率，簡化掃描器的設計，假設該程序設計語言中，基本字（也稱關(guān)鍵詞）不能做一般標識符用，如果基本字、標識符和常數(shù)之間沒有確定的運算符或界符作間隔，則用空白作間隔。單詞符號及其內(nèi)部表示如表1-1所示，單詞符號中標識符由一個字母后跟多個字母、數(shù)字組成，常數(shù)由多個十進制數(shù)字組成。單詞符號的內(nèi)部表示，即單詞的輸出形式為二元式：（種別編碼,單詞的屬性值）。表1-1單詞符號及其內(nèi)部表示單詞符號種別編碼單詞的屬性值BEGINIFTHENELSEEND標識符整型常數(shù)+*（）123456789101112在名字表中的地址十進制整數(shù)2算符優(yōu)先分析程序設計的目的和要求2.1 算符優(yōu)先分析程序設計的實驗目的本實驗是為計算機科學與技術(shù)專業(yè)的學生在學習編譯技術(shù)課程后，為加深對課堂教學內(nèi)容的理解，培養(yǎng)解決實際問題能力而設置的實踐環(huán)節(jié)。通過這個實驗，使學生應用編譯程序設計的原理和技術(shù), 設計、編寫和調(diào)試算符優(yōu)先分析程序，了解算符優(yōu)先分析程序的組成結(jié)構(gòu)，掌握實現(xiàn)通用算符優(yōu)先分析算法的方法。能使得學生在設計和調(diào)試編譯程序的能力方面有所提高。為將來設計、分析編譯程序打下良好的基礎(chǔ)。2.2 算符優(yōu)先分析程序設計的實驗要求算符優(yōu)先分析屬于自下而上的分析方法，該語法分析程序的輸入是終結(jié)符號串（即單詞符號串，以一個“”結(jié)尾），如果輸入串是句子則輸出“YES”，否則輸出“NO”和錯誤信息。算符優(yōu)先分析過程與非終結(jié)符號無關(guān)，當由文法產(chǎn)生了優(yōu)先關(guān)系之后文法也就失去了作用,本題目給出文法的目的是為了便于對語法分析結(jié)果進行驗證。(1)文法設算符優(yōu)先文法為： 說明：i為整型常數(shù)或者為標識符表示整型變量；使用中用*表示。(2)優(yōu)先關(guān)系表設優(yōu)先關(guān)系表如表1-2所示。表1-2優(yōu)先關(guān)系表+ * i ( ) # + * i ( ) # 3基于算符優(yōu)先分析方法的語法制導翻譯程序設計的目的和要求3.1 基于算符優(yōu)先分析方法的語法制導翻譯程序設計的實驗目的本實驗是為計算機科學與技術(shù)專業(yè)的學生在學習編譯技術(shù)課程后，為加深對課堂教學內(nèi)容的理解，培養(yǎng)解決實際問題能力而設置的實踐環(huán)節(jié)。通過這個實驗，使學生應用編譯程序設計的原理和技術(shù), 通過設計、編寫和調(diào)試語法制導翻譯程序，掌握從一種語句的語法和語義出發(fā)，構(gòu)造相應的語義子程序，實現(xiàn)基于算符優(yōu)先分析方法的語法制導翻譯的方法。能使得學生在設計和調(diào)試編譯程序的能力方面有所提高。為將來設計、分析編譯程序打下良好的基礎(chǔ)。3.2 基于算符優(yōu)先分析方法的語法制導翻譯程序設計的實驗要求算符優(yōu)先分析方法是通過反復把輸入符號移進分析棧，使用優(yōu)先關(guān)系表在分析棧頂尋找最左素短語，將其歸約為一個非終結(jié)符號而實現(xiàn)的。這個分析過程與非終結(jié)符號無關(guān)，當由文法產(chǎn)生了優(yōu)先關(guān)系之后文法也就失去了作用（所以本題目無需給出文法）?；谒惴麅?yōu)先分析方法的語法制導翻譯是在算符優(yōu)先語法分析的基礎(chǔ)上進行翻譯工作（即語義分析），每當將一個最左素短語歸約為一個非終結(jié)符號時，就調(diào)用對應產(chǎn)生式的語義子程序，去完成相應的語義翻譯工作，這步歸約使用的產(chǎn)生式對非終結(jié)符號不加區(qū)分（即將所有的非終結(jié)符號用一個通用的非終結(jié)符號表示）。語法制導翻譯程序的輸入是終結(jié)符號串（即單詞符號串，以一個“”結(jié)尾），如果輸入符號串是句子,則按照其語義進行翻譯,輸出等價的四元式序列（作為練習應顯示輸出）。4上機前的準備為了充分利用上機時間，在進行編譯技術(shù)上機實驗前應做好各種準備工作，具體應包括：(1)復習與上機題目有關(guān)的知識，熟悉有關(guān)定義、概念和實現(xiàn)算法。(2)設計出程序流程框圖和數(shù)據(jù)結(jié)構(gòu)，編寫出完整的源程序，進行靜態(tài)檢查。(3)為所編寫的程序構(gòu)思一個運行、調(diào)試環(huán)境，例如，以什么方式提供輸入數(shù)據(jù)、顯示輸出數(shù)據(jù)，如何調(diào)用（或啟動）編寫的程序。制定出程序調(diào)試計劃和典型輸入代碼數(shù)據(jù)。5課程設計報告課程設計完成后，按學校給定的格式和要求寫出課程設計報告。二、 主要內(nèi)容完成以下課程設計內(nèi)容：1完成詞法分析器設計，實現(xiàn)輸入源程序字符串，每調(diào)用一次掃描器，就輸出一個以內(nèi)部形式表示的單詞符號，輸出形式為二元式：（種別編碼，單詞屬性）2完成算符優(yōu)先分析程序設計，掌握實現(xiàn)通用算符優(yōu)先分析算法的方法，實現(xiàn)輸入終結(jié)符號串（即單詞符號串，以一個“”結(jié)尾），如果輸入串是句子則輸出“YES”，否則輸出“NO”和錯誤信息。3完成基于算符優(yōu)先分析方法的語法制導翻譯程序設計，實現(xiàn)輸入是終結(jié)符號串（即單詞符號串，以一個“”結(jié)尾），如果輸入符號串是句子,則按照其語義進行翻譯,輸出等價的四元式序列。三、 進度計劃序號設計內(nèi)容完成時間備注1查閱資料，編譯器各部分概要設計一天2詞法分析器設計一天3算符優(yōu)先分析程序設計一天4基于算符優(yōu)先分析方法的語法制導翻譯程序設計一天半5驗收交實驗報告半天已完成的學生驗收交實驗報告四、設計成果要求1按進度計劃和自己的能力完成課程設計內(nèi)容要求，包括程序框圖、源程序、調(diào)試步驟、調(diào)試方法、對運行結(jié)果的分析等。 2總結(jié)整個課程設計，撰寫出課程設計報告。五、 考核方式1程序調(diào)試完成后，由指導教師在計算機上檢查，驗收課程設計成果，并現(xiàn)場答辯。2評閱課程設計報告。 學生姓名： （簽字） 指導教師： 年 月 日 實驗一詞法分析器的設計與實現(xiàn)一、課程設計(綜合實驗)的目的與要求1.1 詞法分析器設計的實驗目的本實驗是為計算機科學與技術(shù)專業(yè)的學生在學習編譯技術(shù)課程后，為加深對課堂教學內(nèi)容的理解，培養(yǎng)解決實際問題能力而設置的實踐環(huán)節(jié)。通過這個實驗，使學生應用編譯程序設計的原理和技術(shù)設計出詞法分析器，了解掃描器的組成結(jié)構(gòu)，不同種類單詞的識別方法。能使得學生在設計和調(diào)試編譯程序的能力方面有所提高。為將來設計、分析編譯程序打下良好的基礎(chǔ)。1.2 詞法分析器設計的實驗要求設計一個掃描器，該掃描器是一個子程序，其輸入是源程序字符串，每調(diào)用一次識別并輸出一個單詞符號。為了避免超前搜索，提高運行效率，簡化掃描器的設計，假設該程序設計語言中，基本字（也稱關(guān)鍵詞）不能做一般標識符用，如果基本字、標識符和常數(shù)之間沒有確定的運算符或界符作間隔，則用空白作間隔。單詞符號及其內(nèi)部表示如表1-1所示，單詞符號中標識符由一個字母后跟多個字母、數(shù)字組成，常數(shù)由多個十進制數(shù)字組成。單詞符號的內(nèi)部表示，即單詞的輸出形式為二元式：（種別編碼,單詞的屬性值）。表1-1單詞符號及其內(nèi)部表示單詞符號種別編碼單詞的屬性值BEGINIFTHENELSEEND標識符整型常數(shù)+*（）123456789101112在名字表中的地址十進制整數(shù)二、設計（實驗）正文1.詞法分析器流程圖2.詞法分析器設計開始結(jié)束初始化讀入需要分析的句子還有單詞未分析？否是是字母？是否其他單詞分析程序是數(shù)字？否輸出單詞二元式關(guān)鍵字或標識符分析程序讀一個字符是常數(shù)分析程序程序代碼/ first.cpp : 定義控制臺應用程序的入口點。/#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;/其他的標點符號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標志符-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.詞法分析器運行結(jié)果實驗二. 算符優(yōu)先分析的設計與實現(xiàn)一、課程設計(綜合實驗)的目的與要求2.1 算符優(yōu)先分析程序設計的實驗目的本實驗是為計算機科學與技術(shù)專業(yè)的學生在學習編譯技術(shù)課程后，為加深對課堂教學內(nèi)容的理解，培養(yǎng)解決實際問題能力而設置的實踐環(huán)節(jié)。通過這個實驗，使學生應用編譯程序設計的原理和技術(shù), 設計、編寫和調(diào)試算符優(yōu)先分析程序，了解算符優(yōu)先分析程序的組成結(jié)構(gòu)，掌握實現(xiàn)通用算符優(yōu)先分析算法的方法。能使得學生在設計和調(diào)試編譯程序的能力方面有所提高。為將來設計、分析編譯程序打下良好的基礎(chǔ)。2.2 算符優(yōu)先分析程序設計的實驗要求算符優(yōu)先分析屬于自下而上的分析方法，該語法分析程序的輸入是終結(jié)符號串（即單詞符號串，以一個“”結(jié)尾），如果輸入串是句子則輸出“YES”，否則輸出“NO”和錯誤信息。算符優(yōu)先分析過程與非終結(jié)符號無關(guān)，當由文法產(chǎn)生了優(yōu)先關(guān)系之后文法也就失去了作用,本題目給出文法的目的是為了便于對語法分析結(jié)果進行驗證。(1)文法設算符優(yōu)先文法為： 說明：i為整型常數(shù)或者為標識符表示整型變量；使用中用*表示。(2)優(yōu)先關(guān)系表設優(yōu)先關(guān)系表如表1-2所示。表1-2優(yōu)先關(guān)系表+ * i ( ) # + * i ( ) # 二、設計（實驗）正文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 : 定義控制臺應用程序的入口點。/#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，移進*/ if(curchar=#) /*待比較字符為空*/ if(k=2) /*當前比較字符在棧的位置為兩個元素*/ break; else coutendl錯誤 tableij curcmp next; else /*算符優(yōu)先值為，歸約*/ if(curcmp=i) /*當前比較為i,出棧一次*/ pop(); else /*當前比較不為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保存運算符，并使h指向temp，即保存運算符的位置 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.實驗運行結(jié)果如下：實驗三. 基于算符優(yōu)先分析方法的語法制導翻譯的設計與實現(xiàn)一、課程設計(綜