編譯原理課設(shè)_王遠(yuǎn)(共19頁(yè))

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

2、LR法完成以上任務(wù)。（2）如1題寫出符合分析方法要求的文法，給出分析方法的思想，完成分析程序設(shè)計(jì)。（3）編制好分析程序后，設(shè)計(jì)若干用例，上機(jī)測(cè)試并通過(guò)所設(shè)計(jì)的分析程序。上機(jī)時(shí)間安排：序號(hào)階段內(nèi)容所需時(shí)間1消化資料、系統(tǒng)設(shè)計(jì)1天2編程、調(diào)試天3撰寫報(bào)告1天合計(jì)天指導(dǎo)老師簽名(qin mng)： 年 月 日目錄 TOC o 1-3 h z u HYPERLINK l _Toc408938283 1.系統(tǒng)描述 PAGEREF _Toc408938283 h 1 HYPERLINK l _Toc408938284 1.1目的 PAGEREF _Toc408938284 h 1 HYPERLINK l

3、_Toc408938285 1.2設(shè)計(jì)內(nèi)容 PAGEREF _Toc408938285 h 1 HYPERLINK l _Toc408938286 1.3文法和翻譯 PAGEREF _Toc408938286 h 1 HYPERLINK l _Toc408938287 2.詞法分析 PAGEREF _Toc408938287 h 2 HYPERLINK l _Toc408938288 3.語(yǔ)法分析 PAGEREF _Toc408938288 h 2 HYPERLINK l _Toc408938289 3.1遞歸子程序法概述 PAGEREF _Toc408938289 h 2 HYPERLINK

4、 l _Toc408938290 3.1.1構(gòu)造遞歸子程序的方法 PAGEREF _Toc408938290 h 3 HYPERLINK l _Toc408938291 3.1.2非終結(jié)符對(duì)應(yīng)的子程序 PAGEREF _Toc408938291 h 4 HYPERLINK l _Toc408938292 4.屬性文法 PAGEREF _Toc408938292 h 7 HYPERLINK l _Toc408938293 4.1 文法和屬性文法的描述 PAGEREF _Toc408938293 h 7 HYPERLINK l _Toc408938294 5.詞法、語(yǔ)法錯(cuò)誤檢測(cè)和處理 PAGERE

5、F _Toc408938294 h 7 HYPERLINK l _Toc408938295 6.用例分析 PAGEREF _Toc408938295 h 8 HYPERLINK l _Toc408938296 7.個(gè)人總結(jié) PAGEREF _Toc408938296 h 9 HYPERLINK l _Toc408938297 8.源代碼 PAGEREF _Toc408938297 h 10 HYPERLINK l _Toc408938298 9. 參考文獻(xiàn) PAGEREF _Toc408938298 h 15武漢理工大學(xué)編譯原理課程設(shè)計(jì)二十進(jìn)制的語(yǔ)法分析(fnx)及語(yǔ)義分析程序設(shè)計(jì)遞歸下降(x

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

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

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

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

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

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

12、單詞進(jìn)入分支讀取下一個(gè)進(jìn)入子函數(shù)計(jì)算屬性翻譯模型決定順序構(gòu)建字母表生成中間代碼圖3.1.1 程序的調(diào)用(dioyng)結(jié)構(gòu)和順序圖3.1.2非終結(jié)符對(duì)應(yīng)(duyng)的子程序產(chǎn)生(chnshng)式對(duì)應(yīng)的語(yǔ)義是，即是顯示S的值val是S的綜合屬性。實(shí)現(xiàn)程序如下：void E()coutSendl;if(strchr(input,.) = NULL)result=S2();elseresult=S1();coutendl;cout*遞歸下降分析成功*endl;cout對(duì)應(yīng)的十進(jìn)制表示為：*result*endl;inputstrchr(input,#)-input=.;return;產(chǎn)生(chn

13、shng)式對(duì)應(yīng)(duyng)的語(yǔ)義是，其中(qzhng)val和length都是綜合屬性。功能是調(diào)用正整數(shù)二進(jìn)制轉(zhuǎn)換函數(shù)，實(shí)現(xiàn)正小數(shù)二進(jìn)制轉(zhuǎn)換。實(shí)現(xiàn)程序如下：double S1()Attribute L1,L2,S;char *point1,*point2;point1=input;point2=strchr(input,.)+1;inputstrchr(input,.)-input=#;coutL1.L2endl;L1=L(point1);L2=L(point2);/語(yǔ)義規(guī)則s.val=L1.val+L2.val/2L2.length; S.value=L1.value+L2.value/

14、(pow(2,(double)(L2.length);return S.value;產(chǎn)生式對(duì)應(yīng)的語(yǔ)義為，val是S和L的綜合屬性。對(duì)正整數(shù)二進(jìn)制進(jìn)行轉(zhuǎn)換，其子程序需要調(diào)用L（），為：double S2()Attribute Ll;coutL0R/語(yǔ)義規(guī)則：L.val=R.val;L.length=1+R.length; if( *point =0)cout0R00R/語(yǔ)義規(guī)則(guz)：L.val=1*2R.length+R.val;L.length=1+R.length; else if(*point = 1)cout1R10R/語(yǔ)義規(guī)則:R.val=R1.val;R.length=1+R1

15、.length; if(*point = 0)cout0R01R/語(yǔ)義規(guī)則：R.val=1*2R1.length+R1.val;R.length=1+R1.length; else if(*point = 1)cout1R1EMPTY/*point是否(sh fu)包含在FOLLOW(R)集中(jzhng) else if(*point = #)coutEMPTYendl;Rr.value=0;Rr.length=0;return Rr;else couterrorendl;exit(0);4.屬性文法對(duì)于文法的每個(gè)產(chǎn)生式都配備了一組屬性的計(jì)算規(guī)則，稱為語(yǔ)義規(guī)則。所謂語(yǔ)法制導(dǎo)的翻譯指的是在語(yǔ)法

16、分析過(guò)程中，完成這些語(yǔ)義規(guī)則描述的動(dòng)作，從而實(shí)現(xiàn)語(yǔ)義處理。 一個(gè)屬性文法包含一個(gè)上下文無(wú)關(guān)文法和一系列語(yǔ)義規(guī)則，這些語(yǔ)義規(guī)則附在文法的每個(gè)產(chǎn)生式上。4.1 文法和屬性文法的描述對(duì)于文法的每個(gè)產(chǎn)生式都配備了一組屬性的計(jì)算規(guī)則，稱為語(yǔ)義規(guī)則。所謂語(yǔ)法制導(dǎo)的翻譯指的是在語(yǔ)法分析過(guò)程中，完成這些語(yǔ)義規(guī)則描述的動(dòng)作，從而實(shí)現(xiàn)語(yǔ)義處理。 一個(gè)屬性文法包含一個(gè)上下文無(wú)關(guān)文法和一系列語(yǔ)義規(guī)則，這些語(yǔ)義規(guī)則附在文法的每個(gè)產(chǎn)生式上。形式上講，屬性文法是一個(gè)三元組 :A=(G，V，F(xiàn))， 其中：G:是一個(gè)上下文無(wú)關(guān)文法；V:有窮的屬性集,每個(gè)屬性與文法的一個(gè)終結(jié)符或非終結(jié)符相連,這些屬性代表與文法符號(hào)相關(guān)信息；F:

17、關(guān)于屬性的屬性斷言或一組屬性的計(jì)算規(guī)則(稱為語(yǔ)義規(guī)則) 。 斷言或語(yǔ)義規(guī)則與一個(gè)產(chǎn)生式相聯(lián),只引用該產(chǎn)生式左端或右端的終結(jié)符或非終結(jié)符相聯(lián)的屬性。5.詞法、語(yǔ)法錯(cuò)誤檢測(cè)和處理對(duì)于輸入的字符串需要進(jìn)行檢測(cè)，看是否符合詞法、語(yǔ)法規(guī)則。如果符合則進(jìn)行語(yǔ)法、語(yǔ)義分析；否則，報(bào)錯(cuò)，重新輸入。對(duì)于錯(cuò)誤的可能情況為：輸入的單詞不是1，0，.和終止符#，例如：1a2.01#；輸入(shr)的字符串沒(méi)有終止符#，例如(lr)：101.101；輸入(shr)的字符串小數(shù)點(diǎn)的個(gè)數(shù)大于1，例如：101.101#；輸入的字符串以單詞.結(jié)尾，例如：101.；輸入有多個(gè)終止符#，將會(huì)進(jìn)行警告，忽略第一個(gè)#后面的內(nèi)容；輸入的

18、字符串以小數(shù)點(diǎn).開(kāi)頭，將會(huì)進(jìn)行警告，在小數(shù)點(diǎn)前面自動(dòng)補(bǔ)0。如果出現(xiàn)了錯(cuò)誤，則將不會(huì)進(jìn)行語(yǔ)法、語(yǔ)義分析；如果出現(xiàn)了警告，則仍然進(jìn)行語(yǔ)法、語(yǔ)義分析。6.用例分析用例一：輸入的字符串中包含除0，1，.，#之外的字符：圖6.1 用例一的運(yùn)行結(jié)果圖用例二：輸入的字符串沒(méi)有以終止符#結(jié)尾：圖6.2 用例二的運(yùn)行結(jié)果圖用例三：輸入的字符串的小數(shù)點(diǎn)的個(gè)數(shù)不止一個(gè)：圖6.3 用例三運(yùn)行結(jié)果圖用例四：輸入(shr)的字符串以.開(kāi)頭(ki tu)和有多個(gè)終止符#：圖6.4 用例四運(yùn)行(ynxng)結(jié)果圖用例五：輸入的二進(jìn)制串完全按照規(guī)定格式：圖6.5 用例五運(yùn)行結(jié)果圖7.個(gè)人總結(jié)經(jīng)過(guò)不斷的查閱資料，終于完成本次編譯

19、原理的課程設(shè)計(jì)。運(yùn)用了遞歸下降方法對(duì)二十進(jìn)制的語(yǔ)法分析及語(yǔ)義分析程序設(shè)計(jì)，通過(guò)本次實(shí)踐我學(xué)會(huì)和領(lǐng)悟了許多：1. 良好的編程習(xí)慣如此重要在編寫程序之前，要先寫好自己的軟件定義，軟件流程圖。對(duì)自己要做的事要有很清晰的了解，知道其中難點(diǎn)之所在。在編寫程序時(shí)，要符合規(guī)范，詳盡的中英文注釋，模塊化編程，程序要簡(jiǎn)潔，可讀性和可修改性要強(qiáng)。在編寫后，要進(jìn)行不斷的測(cè)試，降低程序的bug，增加程序的健壯性。2.工作計(jì)劃不可(bk)缺少每天早上打開(kāi)工作計(jì)劃，檢查一下昨天的任務(wù)(rn wu)是不是已經(jīng)完成，今天的工作又有哪些，搞清自己的工作方向。3學(xué)習(xí)(xux)理論知識(shí)要講方法每次接觸新課題時(shí)，就必須要學(xué)習(xí)新的知識(shí)

20、。先要了解其框架，比較抽象，比較粗略，不需要精確，有一個(gè)思路即可，然后在做具體的設(shè)計(jì)時(shí)，遇到困難，再查查資料。具體、詳細(xì)、精確的了解。如此反復(fù)可以事半功倍，提高效率。通過(guò)這次大作業(yè)，在這整個(gè)過(guò)程中我學(xué)到了很多東西，掌握了一些常用的開(kāi)發(fā)技能,也發(fā)現(xiàn)了大量的問(wèn)題，有些在設(shè)計(jì)過(guò)程中已經(jīng)解決，有些還有待今后慢慢學(xué)習(xí)。只要學(xué)習(xí)就會(huì)有更多的問(wèn)題，有更多的難點(diǎn)，但也會(huì)有更多的收獲。8.源代碼#include iostream#include string.h#include stdlib.h#include math.husing namespace std;/*用遞歸下降方法二十進(jìn)制的語(yǔ)法分析及語(yǔ)義分析程

21、序設(shè)計(jì) 分為正整數(shù)二進(jìn)制和帶小數(shù)點(diǎn)的二進(jìn)制轉(zhuǎn)換兩部分 */char input255; /存儲(chǔ)輸入的二進(jìn)制串 char *point; /指向當(dāng)前單詞的指針 double result; /存儲(chǔ)二進(jìn)制轉(zhuǎn)換后的結(jié)果 typedef struct shuxingdouble value;int length; Attribute;Attribute R();Attribute L(char *p);double S1();/帶小數(shù)點(diǎn)的二進(jìn)制轉(zhuǎn)換部分 double S2();/正整數(shù)二進(jìn)制轉(zhuǎn)換部分void E();void hander_point();/處理小數(shù)點(diǎn)開(kāi)頭的情況 int error_h

22、andle();/簡(jiǎn)單的詞法分析和語(yǔ)法分析 int main()char mark=Y;int error_flag;while(mark = Y | mark = y)system(cls);cout請(qǐng)輸入(shr)二進(jìn)制表達(dá)式，以#結(jié)束(jish)input;point=input;error_flag=error_handle();coutendl*endl;if(error_flag = 0)E(); /開(kāi)始遞歸下降(xijing)分析 elsecout請(qǐng)重新按正確格式輸入二進(jìn)制串endl;coutendl*繼續(xù)輸入二進(jìn)制串?*(Y/N)mark;return 0;/*遞歸下降法* /

23、產(chǎn)生式E-s print(s.val) void E()coutSendl;if(strchr(input,.) = NULL)result=S2();elseresult=S1();coutendl;cout*遞歸下降分析成功*endl;cout對(duì)應(yīng)的十進(jìn)制表示為：*result*L.L; double S1()Attribute L1,L2,S;char *point1,*point2;point1=input;point2=strchr(input,.)+1;inputstrchr(input,.)-input=#;coutL1.L2L; double S2()Attribute Ll;

24、coutL0R/語(yǔ)義規(guī)則：L.val=R.val;L.length=1+R.length; if( *point =0)cout0R00R/語(yǔ)義規(guī)則(guz)：L.val=1*2R.length+R.val;L.length=1+R.length; else if(*point = 1)cout1R10R/語(yǔ)義規(guī)則(guz):R.val=R1.val;R.length=1+R1.length; if(*point = 0)cout0R01R/語(yǔ)義規(guī)則：R.val=1*2R1.length+R1.val;R.length=1+R1.length; else if(*point = 1)cout1

25、R1EMPTY/*point是否包含在FOLLOW(R)集中 else if(*point = #)coutEMPTYendl;Rr.value=0;Rr.length=0;return Rr;else couterrorendl;exit(0);/簡(jiǎn)單(jindn)的詞法分析和語(yǔ)法分析 int error_handle()char *p;int point_flag,star_flag,error_flag,warn_flag;point_flag=0;star_flag=0;error_flag=0;warn_flag=0;p=input;if(p0 = .)warn_flag+;coutwarn warn_flag :二進(jìn)制串以小數(shù)點(diǎn).開(kāi)頭(ki tu)endl;hander_point();/處理小數(shù)點(diǎn)開(kāi)頭(ki tu)的情況 while(*p != 0)if(*p != 0 & *p !=1 & *p!=. & *p!=#)error_flag+;couterror error