編譯原理課設_王遠

1、學 號：0121210680218課 程 設 計題 目二-十進制的語法分析及語義分析程序設計學 院計算機科學與技術學院專 業(yè)軟件工程班 級軟件zy1201班姓 名王遠指導教師饒文碧2015年1月14日課程設計任務書學生姓名： 王遠 專業(yè)班級： 軟件zy1201班 指導教師： 饒文碧 工作單位： 計算機科學與技術學院題目: 二-十進制的語法分析及語義分析程序設計1目的通過設計、編制、調試語法及語義分析程序，加深對語法及語義分析原理的理解。2設計內容及要求（1）學號19-22的同學按順序分別選擇遞歸下降法、LL（1）、算符優(yōu)先分析法（或簡單優(yōu)先法）、LR法完成以上任務。（2）如1題寫出符合分析方法

2、要求的文法，給出分析方法的思想，完成分析程序設計。（3）編制好分析程序后，設計若干用例，上機測試并通過所設計的分析程序。上機時間安排：序號階段內容所需時間1消化資料、系統(tǒng)設計1天2編程、調試天3撰寫報告1天合計天指導老師簽名： 年 月 日目錄1.系統(tǒng)描述11.1目的11.2設計內容11.3文法和翻譯12.詞法分析23.語法分析23.1遞歸子程序法概述23.1.1構造遞歸子程序的方法33.1.2非終結符對應的子程序44.屬性文法74.1 文法和屬性文法的描述75.詞法、語法錯誤檢測和處理76.用例分析87.個人總結98.源代碼109. 參考文獻15武漢理工大學編譯原理課程設計二-十進制的語法分析

3、及語義分析程序設計遞歸下降法1. 系統(tǒng)描述1.1目的通過設計、編制、調試語法及語義分析程序，加深對語法及語義分析原理的理解。并實現詞法分析程序對單詞序列的詞法檢查和分析。1.2設計內容（1）選擇遞歸下降法進行語法分析和語義分析（2）寫出符合分析方法要求的文法，給出分析方法的思想，完成分析程序設計。（3）編制好分析程序后，設計若干用例，上機測試并通過所設計的分析程序。1.3文法和翻譯正整數二進制自然數的正規(guī)式為: B =0 | (0|1) *正整數十進制自然數的正規(guī)式為： D =0 | (1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*正小數二進制的正規(guī)式為：C=

4、(0 | 1) . (0 | 1)*正小數十進制的正規(guī)式為：E=(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)* .(0|1|2|3|4|5|6|7|8|9)*二十進制自然數的文法GE如下:表 1.3.1 文法表產生式語法制導翻譯方法2. 詞法分析詞法分析是計算機科學中將字符序列轉換為單詞（Token）序列的過程。進行語法分析的程序或者函數叫作詞法分析器（Lexical analyzer，簡稱Lexer），也叫掃描器（Scanner）。詞法分析器一般以函數的形式存在，供語法分析器調用。詞法分析是編譯過程中的第一個階段，在語法分析前進行 。也可以和語法分析結合在

5、一起作為一遍，由語法分析程序調用詞法分析程序來獲得當前單詞供語法分析使用。簡化設計、改進編譯效率、增加編譯系統(tǒng)的可移植性。詞法分析是編制一個讀單詞的過程，從輸入的源程序中，識別出各個具有獨立意義的單詞，即基本保留字、標識符、常數、運算符、分隔符五大類。并依次輸出各個單詞的內部編碼及單詞符號自身值。單詞的分類主要分為五類：1. 關鍵字：由程序語言定義的具有固定意義的標識符。也稱為保留字或基本字。2. 標識符：用來表示程序中各種名字的字符串。3. 常 數：常數的類型一般有整型、實型、布爾型、文字型。4. 運算符：如+、 、*、/ 等。5. 界限符：如逗號、分號、括號等。這里將詞法分析程序設計成一個

6、子程序，每當語法分析程序需要一個單詞時，則調用該子程序。詞法分析程序每調用一次，便從源程序文件中讀入一些字符，直到識別出一個單詞。因為輸入的就是以“#”結尾的二進制串，所以該程序的詞法分析很簡單，只需要一個符號數組和一個初始指向數組第一個元素地址的指針，就可以讀出每一個單詞。3.語法分析3.1遞歸子程序法概述遞歸子程序法是比較簡單直觀易于構造的一種語法分析方法。它要求滿足LL（1）文法。它的實現思想是對應文法中每個非終結符編寫一個遞歸過程，每個過程的功能是識別由該非終結符推出的串，當某個非終結符有多個候選時能夠按LL(1)形式可唯一地確定選擇某個候選進行推導。由于遞歸子程序法對每個過程可能存在

7、直接或間接遞歸調用，所以對某個過程在退出之前可能又被調用，因此有些信息需要保留，通常在入口時需保留某些信息，出口時需恢復。由于遞歸過程是遵循先進后出規(guī)律，所以通常開辟先進后出棧來處理。遞歸子程序法的缺點是：對文法要求高，必須滿足LL（1）文法，當然在某些語言中個別產生式的推導當不滿足LL（1）而滿足LL(2)時，也可以采用多向前掃描一個符號的方法；它的另一個缺點是由于遞歸調用多，所以速度慢占用空間多，盡管這樣，它還是許多高級語言，例如Pascal，C等編譯系統(tǒng)常常采用的語法分析方法。由于該文法在正整數和正小數一起考慮時的文法并不是LL(1)文法，所以將正整數和正小數分別單獨處理，最后在程序中綜

8、合起來。程序分程序語句條件二進制串單詞圖3.1 語法調用關系圖3.1.1構造遞歸子程序的方法為每個非終結符編制一個遞歸下降分析函數，每個函數名是相應的非終結符，函數體則是根據規(guī)則右部符號串的結構和順序編寫。（1）當遇到終結符a時，則編寫語句if (當前讀來的輸入符號=a) 讀下一個輸入符號（2）當遇到非終結符A時，則編寫語句調用 A( )（3）當遇到規(guī)則A 時，則編寫語句if (當前讀來的輸入符號ÏFOLLOW(A) error( )；（4）當某個非終結符的規(guī)則有多個候選式時，按LL(1)文法的條件能唯一地選擇一個候選式進行推導。當前單詞函數匹配單詞進入分支讀取下一個進入子函數計算屬

9、性翻譯模型決定順序構建字母表生成中間代碼圖3.1.1 程序的調用結構和順序圖3.1.2非終結符對應的子程序產生式對應的語義是，即是顯示S的值val是S的綜合屬性。實現程序如下：void E()cout<<"E->S-"<<endl;if(strchr(input,'.') = NULL)result=S2();elseresult=S1();cout<<endl;cout<<"*遞歸下降分析成功*"<<endl;cout<<"對應的十進制表示為：&qu

10、ot;<<"*"<<result<<"*"<<endl;inputstrchr(input,'#')-input='.'return;產生式對應的語義是，其中val和length都是綜合屬性。功能是調用正整數二進制轉換函數，實現正小數二進制轉換。實現程序如下：double S1()Attribute L1,L2,S;char *point1,*point2;point1=input;point2=strchr(input,'.')+1;inputstrchr(

11、input,'.')-input='#'cout<<"S->L1.L2-"<<endl;L1=L(point1);L2=L(point2);/語義規(guī)則s.val=L1.val+L2.val/2L2.length; S.value=L1.value+L2.value/(pow(2,(double)(L2.length);return S.value;產生式對應的語義為，val是S和L的綜合屬性。對正整數二進制進行轉換，其子程序需要調用L（），為：double S2()Attribute Ll;cout<<

12、;"S->L-"<<endl;Ll=L(input);/語義規(guī)則s.val=L.val return Ll.value;非終結符L對應的產生式有：、。需要調用函數R（），其實現為：Attribute L(char *p)Attribute Ll,Rr;point=p;/產生式L->0R/語義規(guī)則：L.val=R.val;L.length=1+R.length; if( *point ='0')cout<<"L->0R-0"<<endl;point+;Rr=R();Ll.value=Rr

13、.value;Ll.length=1+Rr.length;return Ll;/產生式L->0R/語義規(guī)則：L.val=1*2R.length+R.val;L.length=1+R.length; else if(*point = '1')cout<<"L->1R-1"<<endl;point+;Rr=R();Ll.value=1*pow(2,(double)(Rr.length)+Rr.value;Ll.length=1+Rr.length;return Ll;非終結符R對應的產生式為：，其實現為：Attribute R

14、()Attribute Rr1,Rr;/產生式R->0R/語義規(guī)則:R.val=R1.val;R.length=1+R1.length; if(*point = '0')cout<<"R->0R-0"<<endl;point+;Rr1=R();Rr.value=Rr1.value;Rr.length=1+Rr1.length;return Rr;/產生式R->1R/語義規(guī)則：R.val=1*2R1.length+R1.val;R.length=1+R1.length; else if(*point = '1&

15、#39;)cout<<"R->1R-1"<<endl;point+;Rr1=R();Rr.value=1*pow(2,(double)(Rr1.length)+Rr1.value;Rr.length=1+Rr1.length;return Rr;/產生式R->EMPTY/*point是否包含在FOLLOW(R)集中 else if(*point = '#')cout<<"R->EMPTY-"<<endl;Rr.value=0;Rr.length=0;return Rr;el

16、se cout<<"error"<<endl;exit(0);4.屬性文法對于文法的每個產生式都配備了一組屬性的計算規(guī)則，稱為語義規(guī)則。所謂語法制導的翻譯指的是在語法分析過程中，完成這些語義規(guī)則描述的動作，從而實現語義處理。 一個屬性文法包含一個上下文無關文法和一系列語義規(guī)則，這些語義規(guī)則附在文法的每個產生式上。4.1 文法和屬性文法的描述對于文法的每個產生式都配備了一組屬性的計算規(guī)則，稱為語義規(guī)則。所謂語法制導的翻譯指的是在語法分析過程中，完成這些語義規(guī)則描述的動作，從而實現語義處理。 一個屬性文法包含一個上下文無關文法和一系列語義規(guī)則，這些語義規(guī)

17、則附在文法的每個產生式上。形式上講，屬性文法是一個三元組 :A=(G，V，F)， 其中：G:是一個上下文無關文法；V:有窮的屬性集,每個屬性與文法的一個終結符或非終結符相連,這些屬性代表與文法符號相關信息；F:關于屬性的屬性斷言或一組屬性的計算規(guī)則(稱為語義規(guī)則) 。 斷言或語義規(guī)則與一個產生式相聯,只引用該產生式左端或右端的終結符或非終結符相聯的屬性。5.詞法、語法錯誤檢測和處理對于輸入的字符串需要進行檢測，看是否符合詞法、語法規(guī)則。如果符合則進行語法、語義分析；否則，報錯，重新輸入。對于錯誤的可能情況為：（1） 輸入的單詞不是1，0，.和終止符#，例如：1a2.01#；（2） 輸入的字符串

18、沒有終止符#，例如：101.101；（3） 輸入的字符串小數點的個數大于1，例如：101.101#；（4） 輸入的字符串以單詞.結尾，例如：101.；（5） 輸入有多個終止符#，將會進行警告，忽略第一個#后面的內容；（6） 輸入的字符串以小數點.開頭，將會進行警告，在小數點前面自動補0。如果出現了錯誤，則將不會進行語法、語義分析；如果出現了警告，則仍然進行語法、語義分析。6.用例分析用例一：輸入的字符串中包含除0，1，.，#之外的字符：圖6.1 用例一的運行結果圖用例二：輸入的字符串沒有以終止符#結尾：圖6.2 用例二的運行結果圖用例三：輸入的字符串的小數點的個數不止一個：圖6.3 用例三運行

19、結果圖用例四：輸入的字符串以.開頭和有多個終止符#：圖6.4 用例四運行結果圖用例五：輸入的二進制串完全按照規(guī)定格式：圖6.5 用例五運行結果圖7.個人總結經過不斷的查閱資料，終于完成本次編譯原理的課程設計。運用了遞歸下降方法對二-十進制的語法分析及語義分析程序設計，通過本次實踐我學會和領悟了許多：1. 良好的編程習慣如此重要在編寫程序之前，要先寫好自己的軟件定義，軟件流程圖。對自己要做的事要有很清晰的了解，知道其中難點之所在。在編寫程序時，要符合規(guī)范，詳盡的中英文注釋，模塊化編程，程序要簡潔，可讀性和可修改性要強。在編寫后，要進行不斷的測試，降低程序的bug，增加程序的健壯性。2.工作計劃不

20、可缺少每天早上打開工作計劃，檢查一下昨天的任務是不是已經完成，今天的工作又有哪些，搞清自己的工作方向。3學習理論知識要講方法每次接觸新課題時，就必須要學習新的知識。先要了解其框架，比較抽象，比較粗略，不需要精確，有一個思路即可，然后在做具體的設計時，遇到困難，再查查資料。具體、詳細、精確的了解。如此反復可以事半功倍，提高效率。通過這次大作業(yè)，在這整個過程中我學到了很多東西，掌握了一些常用的開發(fā)技能,也發(fā)現了大量的問題，有些在設計過程中已經解決，有些還有待今后慢慢學習。只要學習就會有更多的問題，有更多的難點，但也會有更多的收獲。8.源代碼#include "iostream"

21、#include "string.h"#include "stdlib.h"#include "math.h"using namespace std;/*用遞歸下降方法二-十進制的語法分析及語義分析程序設計 分為正整數二進制和帶小數點的二進制轉換兩部分 */char input255; /存儲輸入的二進制串 char *point; /指向當前單詞的指針 double result; /存儲二進制轉換后的結果 typedef struct shuxingdouble value;int length; Attribute;Attrib

22、ute R();Attribute L(char *p);double S1();/帶小數點的二進制轉換部分 double S2();/正整數二進制轉換部分void E();void hander_point();/處理小數點開頭的情況 int error_handle();/簡單的詞法分析和語法分析 int main()char mark='Y'int error_flag;while(mark = 'Y' | mark = 'y')system("cls");cout<<"請輸入二進制表達式，以#結束

23、"<<endl;cin>>input;point=input;error_flag=error_handle();cout<<endl<<"*"<<endl;if(error_flag = 0)E(); /開始遞歸下降分析 elsecout<<"請重新按正確格式輸入二進制串"<<endl;cout<<endl<<"*繼續(xù)輸入二進制串?*(Y/N)"<<endl;cin>>mark;return

24、0;/*遞歸下降法* /產生式E->s print(s.val) void E()cout<<"E->S-"<<endl;if(strchr(input,'.') = NULL)result=S2();elseresult=S1();cout<<endl;cout<<"*遞歸下降分析成功*"<<endl;cout<<"對應的十進制表示為："<<"*"<<result<<"

25、*"<<endl;inputstrchr(input,'#')-input='.'return;/帶小數點的二進制轉換部分 /對應文法S->L.L; double S1()Attribute L1,L2,S;char *point1,*point2;point1=input;point2=strchr(input,'.')+1;inputstrchr(input,'.')-input='#'cout<<"S->L1.L2-"<<endl;

26、L1=L(point1);L2=L(point2);/語義規(guī)則s.val=L1.val+L2.val/2L2.length; S.value=L1.value+L2.value/(pow(2,(double)(L2.length);return S.value;/正整數二進制轉換部分/對應文法S->L; double S2()Attribute Ll;cout<<"S->L-"<<endl;Ll=L(input);/語義規(guī)則s.val=L.val return Ll.value; Attribute L(char *p)Attribute

27、 Ll,Rr;point=p;/產生式L->0R/語義規(guī)則：L.val=R.val;L.length=1+R.length; if( *point ='0')cout<<"L->0R-0"<<endl;point+;Rr=R();Ll.value=Rr.value;Ll.length=1+Rr.length;return Ll;/產生式L->0R/語義規(guī)則：L.val=1*2R.length+R.val;L.length=1+R.length; else if(*point = '1')cout<

28、;<"L->1R-1"<<endl;point+;Rr=R();Ll.value=1*pow(2,(double)(Rr.length)+Rr.value;Ll.length=1+Rr.length;return Ll;Attribute R()Attribute Rr1,Rr;/產生式R->0R/語義規(guī)則:R.val=R1.val;R.length=1+R1.length; if(*point = '0')cout<<"R->0R-0"<<endl;point+;Rr1=R()

29、;Rr.value=Rr1.value;Rr.length=1+Rr1.length;return Rr;/產生式R->1R/語義規(guī)則：R.val=1*2R1.length+R1.val;R.length=1+R1.length; else if(*point = '1')cout<<"R->1R-1"<<endl;point+;Rr1=R();Rr.value=1*pow(2,(double)(Rr1.length)+Rr1.value;Rr.length=1+Rr1.length;return Rr;/產生式R->

30、;EMPTY/*point是否包含在FOLLOW(R)集中 else if(*point = '#')cout<<"R->EMPTY-"<<endl;Rr.value=0;Rr.length=0;return Rr;else cout<<"error"<<endl;exit(0);/簡單的詞法分析和語法分析 int error_handle()char *p;int point_flag,star_flag,error_flag,warn_flag;point_flag=0;star_

31、flag=0;error_flag=0;warn_flag=0;p=input;if(p0 = '.')warn_flag+;cout<<"warn "<<warn_flag<<" :二進制串以小數點.開頭"<<endl;hander_point();/處理小數點開頭的情況 while(*p != '0')if(*p != '0' && *p !='1' && *p!='.' && *p!='#')error_flag+;cout<<"error "<<error_flag<<" :輸入的單詞不是'0'或者'1'或者'.'"<<endl;if(*p