編譯原理課設(shè)_王遠

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

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

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

4、(0 | 1) . (0 | 1)*正小數(shù)十進制的正規(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)*二十進制自然數(shù)的文法GE如下:表 1.3.1 文法表產(chǎn)生式語法制導(dǎo)翻譯方法2. 詞法分析詞法分析是計算機科學(xué)中將字符序列轉(zhuǎn)換為單詞（Token）序列的過程。進行語法分析的程序或者函數(shù)叫作詞法分析器（Lexical analyzer，簡稱Lexer），也叫掃描器（Scanner）。詞法分析器一般以函數(shù)的形式存在，供語法分析器調(diào)用。詞法分析是編譯過程中的第一個階段，在語法分析前進行 。也可以和語法分析結(jié)合在

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

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

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

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

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

10、ot;<<"*"<<result<<"*"<<endl;inputstrchr(input,'#')-input='.'return;產(chǎn)生式對應(yīng)的語義是，其中val和length都是綜合屬性。功能是調(diào)用正整數(shù)二進制轉(zhuǎn)換函數(shù)，實現(xiàn)正小數(shù)二進制轉(zhuǎn)換。實現(xiàn)程序如下：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;產(chǎn)生式對應(yīng)的語義為，val是S和L的綜合屬性。對正整數(shù)二進制進行轉(zhuǎn)換，其子程序需要調(diào)用L（），為：double S2()Attribute Ll;cout<<

12、;"S->L-"<<endl;Ll=L(input);/語義規(guī)則s.val=L.val return Ll.value;非終結(jié)符L對應(yīng)的產(chǎn)生式有：、。需要調(diào)用函數(shù)R（），其實現(xiàn)為：Attribute L(char *p)Attribute Ll,Rr;point=p;/產(chǎn)生式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;/產(chǎn)生式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;非終結(jié)符R對應(yīng)的產(chǎn)生式為：，其實現(xiàn)為：Attribute R

14、()Attribute Rr1,Rr;/產(chǎn)生式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;/產(chǎn)生式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;/產(chǎn)生式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.屬性文法對于文法的每個產(chǎn)生式都配備了一組屬性的計算規(guī)則，稱為語義規(guī)則。所謂語法制導(dǎo)的翻譯指的是在語法分析過程中，完成這些語義規(guī)則描述的動作，從而實現(xiàn)語義處理。 一個屬性文法包含一個上下文無關(guān)文法和一系列語義規(guī)則，這些語義規(guī)則附在文法的每個產(chǎn)生式上。4.1 文法和屬性文法的描述對于文法的每個產(chǎn)生式都配備了一組屬性的計算規(guī)則，稱為語義規(guī)則。所謂語法制導(dǎo)的翻譯指的是在語法分析過程中，完成這些語義規(guī)則描述的動作，從而實現(xiàn)語義處理。 一個屬性文法包含一個上下文無關(guān)文法和一系列語義規(guī)則，這些語義規(guī)

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

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

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

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

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

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

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;/*遞歸下降法* /產(chǎn)生式E->s print(s.val) void E()cout<<"E->S-"<<endl;if(strchr(input,'.') = NULL)result=S2();elseresult=S1();cout<<endl;cout<<"*遞歸下降分析成功*"<<endl;cout<<"對應(yīng)的十進制表示為："<<"*"<<result<<"

25、*"<<endl;inputstrchr(input,'#')-input='.'return;/帶小數(shù)點的二進制轉(zhuǎn)換部分 /對應(yīng)文法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;/正整數(shù)二進制轉(zhuǎn)換部分/對應(yīng)文法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;/產(chǎn)生式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;/產(chǎn)生式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;/產(chǎn)生式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;/產(chǎn)生式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;/產(chǎn)生式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<<" :二進制串以小數(shù)點.開頭"<<endl;hander_point();/處理小數(shù)點開頭的情況 while(*p != '0')if(*p != '0' && *p !='1' && *p!='.' && *p!='#')error_flag+;cout<<"error "<<error_flag<<" :輸入的單詞不是'0'或者'1'或者'.'"<<endl;if(*p