二---十進(jìn)制的語法分析及語義分析程序設(shè)計(算符優(yōu)先分析法)

1、武漢理工大學(xué)編譯原理課程設(shè)計Ni 學(xué) 號： 0121210680*課 程 設(shè) 計題 目二-十進(jìn)制的語法分析及語義分析程序設(shè)計（算符優(yōu)先分析法）學(xué) 院計算機科學(xué)與技術(shù)學(xué)院專 業(yè)軟件工程班 級軟件sy1201班姓 名*指導(dǎo)教師饒文碧2015年1月14日 課程設(shè)計任務(wù)書學(xué)生姓名： * * 專業(yè)班級： 軟件sy1201班 指導(dǎo)教師： 饒文碧 工作單位： 計算機科學(xué)與技術(shù)學(xué)院 題目: 二-十進(jìn)制的語法分析及語義分析程序的設(shè)計1目的通過設(shè)計、編制、調(diào)試一個語*法及語義分析程序，加深對語法及語義分析原理的理解。2. 設(shè)計內(nèi)容及要求設(shè)計一個二-十進(jìn)制的語法分析及語義分析程序。 （1）選擇算符優(yōu)先分析法完成以上

2、任務(wù)。 （2）寫出符合分析方法要求的文法，給出分析方法的思想，完成分析程序設(shè)計。 （3）編制好分析程序后，設(shè)計若干用例，上機測試并通過所設(shè)計的分析程序。3.課程設(shè)計進(jìn)度安排序號階段內(nèi)容所需用時間1給出語法分析方法及中間代碼形式的描述、文法和屬性文法的設(shè)計；或者詞法分析方法及符號表和TOKEN代碼的設(shè)計。1天2簡要的分析與概要設(shè)計、算法設(shè)計與程序設(shè)計3天3撰寫課程設(shè)計報告書1天合計5天 目錄目錄21.系統(tǒng)描述312設(shè)計內(nèi)容及步驟42翻譯方法概述42.1詞法分析42.2 語法分析52.3中間代碼生成52.4屬性文法53算符優(yōu)先分析法64文法74.1文法形式74.2文法分類74.3類型說明75. 系

3、統(tǒng)的詳細(xì)設(shè)計85.1 文法設(shè)計85.2構(gòu)造算符優(yōu)先關(guān)系矩陣95.3算法設(shè)計95.4 運行結(jié)果146.總結(jié)及體會157. 源代碼16 二-十進(jìn)制的語法分析及語義分析程序設(shè)計 -算符優(yōu)先分析法1.系統(tǒng)描述通過設(shè)計、編制、調(diào)試一個二-十進(jìn)制的語法分析及語義分析程序，加深對語法及語義分析原理的理解。12設(shè)計內(nèi)容及步驟（1） 設(shè)計算符優(yōu)先文法：G=（Vn,Vt,P,S）（2） 構(gòu)造算符優(yōu)先關(guān)系矩陣（3） 設(shè)計語法分析程序，對輸入的數(shù)據(jù)進(jìn)行語法分析（4） 將輸入的合法二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)2翻譯方法概述2.1詞法分析詞法分析是計算機科學(xué)中將字符序列轉(zhuǎn)換為單詞（Token）序列的過程。進(jìn)行語法分析的程序或者

4、函數(shù)叫作詞法分析器（Lexical analyzer，簡稱Lexer），也叫掃描器（Scanner）。詞法分析器一般以函數(shù)的形式存在，供語法分析器調(diào)用。詞法分析是編譯過程中的第一個階段，在語法分析前進(jìn)行 。也可以和語法分析結(jié)合在一起作為一遍，由語法分析程序調(diào)用詞法分析程序來獲得當(dāng)前單詞供語法分析使用。簡化設(shè)計、改進(jìn)編譯效率、增加編譯系統(tǒng)的可移植性。詞法分析是編制一個讀單詞的過程，從輸入的源程序中，識別出各個具有獨立意義的單詞，即基本保留字、標(biāo)識符、常數(shù)、運算符、分隔符五大類。并依次輸出各個單詞的內(nèi)部編碼及單詞符號自身值。單詞的分類主要分為五類：1. 關(guān)鍵字：由程序語言定義的具有固定意義的標(biāo)識符

5、。也稱為保留字或基本字。2. 標(biāo)識符：用來表示程序中各種名字的字符串。3. 常 數(shù)：常數(shù)的類型一般有整型、實型、布爾型、文字型。4. 運算符：如+、 、*、/ 等。5. 界限符：如逗號、分號、括號等。由于該程序不需進(jìn)行詞法分析，故在設(shè)計程序時省去了詞法分析這一步驟。2.2 語法分析 語法分析是編譯過程的一個邏輯階段。語法分析的任務(wù)是在詞法分析的基礎(chǔ)上將單詞序列組合成各類語法短語，如“程序”，“語句”，“表達(dá)式”等等。語法分析程序判斷源程序在結(jié)構(gòu)上是否正確.源程序的結(jié)構(gòu)由上下文無關(guān)文法描述。 語法分析器（Parser）通常是作為編譯器或解釋器的組件出現(xiàn)的，它的作用是進(jìn)行語法檢查、并構(gòu)建由輸入的單

6、詞組成的數(shù)據(jù)結(jié)構(gòu)（一般是語法分析樹、抽象語法樹等層次化的數(shù)據(jù)結(jié)構(gòu)）。語法分析器通常使用一個獨立的詞法分析器從輸入字符流中分離出一個個的“單詞”，并將單詞流作為其輸入。實際開發(fā)中，語法分析器可以手工編寫，也可以使用工具（半）自動生成。語法分析器的任務(wù)主要是確定是否可以以及如何從語法的起始符號推導(dǎo)出輸入符號串（輸入文本）。 2.3中間代碼生成中間代碼，也稱中間語言，是復(fù)雜性介于源程序語言和機器語言的一種表示形式。為了使編譯程序有較高的目標(biāo)程序質(zhì)量，或要求從編譯程序邏輯結(jié)構(gòu)上把與機器無關(guān)和與機器有關(guān)的工作明顯的分開來時，許多編譯程序都采用了某種復(fù)雜性介于源程序語言和機器語言之間的中間語言。中間代碼（

7、語言）是一種特殊結(jié)構(gòu)的語言，編譯程序所使用的中間代碼有多種形式。按其結(jié)構(gòu)分常見的有逆波蘭式（后綴式）、三地址代碼（三元式、四元式）和樹形表示（抽象語法樹）、DAG表示。2.4屬性文法對于文法的每個產(chǎn)生式都配備了一組屬性的計算規(guī)則，稱為語義規(guī)則。所謂語法制導(dǎo)的翻譯指的是在語法分析過程中，完成這些語義規(guī)則描述的動作，從而實現(xiàn)語義處理。 一個屬性文法包含一個上下文無關(guān)文法和一系列語義規(guī)則，這些語義規(guī)則附在文法的每個產(chǎn)生式上。3算符優(yōu)先分析法算符文法：即它的任一產(chǎn)生式的右部都不含兩個相繼的非終結(jié)符的文法。如果G是一個不含空字符的算法文法，那么只要它的任一對終結(jié)符都之多只滿 足>，=，<的關(guān)

8、系的其中一種，則稱G是一個算符優(yōu)先文法。< p=""><!-的關(guān)系的一種，則稱G是一個算符優(yōu)先文法。對于一個算符優(yōu)先文法，只要能夠造出它的算符優(yōu)先表，就可以利用算符優(yōu)先分析方法，分析一個句子是否符合這個文法的定義。那么定義FirstVT(P)=a|P->a、或P->Qa、，a屬于終結(jié)字符集，而Q屬于非終結(jié)字符集LastVT（P）=a|P->.a或P->.aQ，a屬于終結(jié)字符集，而Q屬于非終結(jié)字符集由以下兩條規(guī)則來構(gòu)造FirstVT集：(1)若有產(chǎn)生式P-a、或P->Qa，則a屬于FirstVT（P）；(2)若有a屬于First

9、VT（Q），且有產(chǎn)生式P-Q，則a屬于FirstVT(P);類似的有構(gòu)造LastVT集的規(guī)則：(1)若有產(chǎn)生式P->a或P->aQ，則a屬于LastVT集。(2)若a屬于LastVT（Q），且有產(chǎn)生式P-Q，則a屬于LastVT集。假定是一個不含空字符產(chǎn)生式的算符文法。對于任何一對終結(jié)符,(1)a=b,當(dāng)且僅當(dāng)中含有形如>ab或>aQb的產(chǎn)生式；(2)a<b, 當(dāng)且僅當(dāng)中含有形如>aR的產(chǎn)生式,而或->Qb；(3)a>b, 當(dāng)且僅當(dāng)中含有形如>Rb的產(chǎn)生式,而>a或->aQ；這樣再結(jié)合上次的FirststVT和LastVT集的概

10、念便可以由文法自動構(gòu)造出算符優(yōu)先表。4文法4.1文法形式在計算機科學(xué)中，文法是編譯原理的基礎(chǔ)，是描述一門程序設(shè)計語言和實現(xiàn)其編譯器的方法。文法的描述多用BNF(巴克斯范式)，而另一個重要的概念:正則表達(dá)式，也是文法的另一種形式。4.2文法分類自從喬姆斯基(Chomsky)于1956年建立形式語言的描述以來，形式語言的理論發(fā)展很快。這種理論對計算機科學(xué)有著深刻的影響，特別是對程序設(shè)計語言的設(shè)計、編譯方法和計算復(fù)雜性等方面更有重大的作用。喬姆斯基把文法分成四種類型，即0型、1型、2型和3型。這幾類文法的差別在于對產(chǎn)生式施加不同的限制。多數(shù)程序設(shè)計語言的單詞的語法都能用正規(guī)文法或3型文法來描述。3型

11、文法G=(VN，VT，P，S)的P中的規(guī)則有兩種形式：一種是前面定義的形式，即：AaB或Aa其中A，BVN ，aVT*，另一種形式是：ABa或Aa，前者稱為右線性文法，后者稱為左線性文法。正規(guī)文法所描述的是VT*上的正規(guī)集。四個文法類的定義是逐漸增加限制的，因此每一種正規(guī)文法都是上下文無關(guān)的，每一種上下文無關(guān)文法都是上下文有關(guān)的，而每一種上下文有關(guān)文法都是0型文法。稱0型文法產(chǎn)生的語言為0型語言。上下文有關(guān)文法、上下文無關(guān)文法和正規(guī)文法產(chǎn)生的語言分別稱為上下文有關(guān)語言、上下文無關(guān)語言和正規(guī)語言。4.3類型說明設(shè)G=(VN，VT，P，S)，如果它的每個產(chǎn)生式是這樣一種結(jié)構(gòu)：( VNVT )*且至

12、少含有一個非終結(jié)符，而( VNVT )*，則G是一個0型文法。0型文法也稱短語文法。一個非常重要的理論結(jié)果是，0型文法的能力相當(dāng)于圖靈機(Turing)?；蛘哒f，任何0型語言都是遞歸可枚舉的；反之，遞歸可枚舉集必定是一個0型語言。對0型文法產(chǎn)生式的形式作某些限制，以給出1，2和3型文法的定義。設(shè)G=(VN，VT，P，S)為一文法，若P中的每一個產(chǎn)生式均滿足| ，僅僅S除外，則文法G是1型或上下文有關(guān)的。設(shè)G=(VN，VT，P，S)，若P中的每一個產(chǎn)生式滿足：是一非終結(jié)符，( VNVT )*則此文法稱為2型的或上下文無關(guān)的。有時將2型文法的產(chǎn)生式表示為形如：A其中AVN，也就是說用取代非終結(jié)符A

13、時，與A所在的上下文無關(guān)，因此取名為上下文無關(guān)文法。設(shè)G=(VN，VT，P，S)，若P中的每一個產(chǎn)生式的形式都是AaB或Aa，其中A和B都是非終結(jié)符，a是終結(jié)符，則G是3型文法或正規(guī)文法。文法G定義為四元組(VN，VT，P，S )其中VN:非終結(jié)符號(或語法實體，或變量)集；VT:終結(jié)符號集；P: 規(guī)則的集合；VN，VT和P是 非空有窮集。S:稱作識別符號或開始符號的一個非終結(jié)符，它至少要在一條產(chǎn)生式中作為左部出現(xiàn)。VN和VT不含公共的元素，即VN VT = 5. 系統(tǒng)的詳細(xì)設(shè)計5.1 文法設(shè)計 設(shè)計算符優(yōu)先文法：G=（Vn,Vt,P,S）,其中Vn=S,A,Vt=.,0，1,P由下列產(chǎn)生式組

14、成：（1）S->A.A|A （2）A->0A|1A（3）A->0|15.2構(gòu)造算符優(yōu)先關(guān)系矩陣 . 0 1 #. < < >0 > < < >1 > < < ># < < < =5.3算法設(shè)計（1） 設(shè)計語法分析程序：定義兩個向量myvector和wuhuivector，myvector用來存儲剩余輸入串，wuhuivector作為符號棧。將myvector中棧頂元素即當(dāng)前符號存于c中，比較符號棧最外面一個非終結(jié)符與當(dāng)前符號的優(yōu)先級，若該非終結(jié)符優(yōu)先級后于或等價于當(dāng)前符號，則移進(jìn)當(dāng)前符號至wu

15、huivector中，若該非終結(jié)符優(yōu)先級先于當(dāng)前符號，則找到符號棧中的最左素短語，并規(guī)約它，若規(guī)約成功，則繼續(xù)分析，否則分析失敗。分析至符號棧中最外面的非終結(jié)符與當(dāng)前符號均為#時，分析成功。a.將myvector棧頂元素存于c中，當(dāng)動作為移進(jìn)時，彈出棧頂元素：if(s1="移進(jìn)") c=myvectormyvector.size()-1;myvector.pop_back();b.比較符號棧最外面一個非終結(jié)符與當(dāng)前符號的優(yōu)先級，優(yōu)先關(guān)系事先用table數(shù)組存儲了：while(j<4)&&(l=0)/找符號棧的最外面一個終結(jié)符 if(wuhuivecto

16、rk=Vtj)l=1; elsej+;for(j=0;j<4;j+) if(wuhuivectork=Vtj)m=j;if(c=Vtj)n=j;tablemn即為兩者的優(yōu)先級 table44=-999,-1,-1,1,1,-1,-1,1,1,-1,-1,1,-1,-1,-1,0;/-999表示無關(guān)系，1表示先于關(guān)系，0表示等價關(guān)系，-1表示后于關(guān)系c.因無優(yōu)先關(guān)系分析失敗函數(shù)：if(tablemn=-999)/失敗cout<<"分析失?。?quot;<<endl;ret=0;warn=0;break; d.分析成功或移進(jìn)函數(shù)： else if(table

17、mn=0)if(wuhuivectork='#')warn=0;s1="分析成功！"elsewuhuivector.push_back(c);s1="移進(jìn)" else if(tablemn=-1)/移進(jìn)wuhuivector.push_back(c);s1="移進(jìn)"e.規(guī)約及因無匹配產(chǎn)生式分析失敗函數(shù)： else if(tablemn=1)/規(guī)約 q=k;do /找符號棧第二個終結(jié)符，尋找最左素短語l=0;dop=0;q-;while(p<4)&&(l=0)if(wuhuivectorq=Vtp)

18、l=1;elsep+;while(l!=1);for(j=0;j<4;j+)if(wuhuivectorq=Vtj)m=j;if(wuhuivectork=Vtj)n=j;q=q-1;while(tablemn!=-1);q+;t=wuhuivector.size()-1;/s2是剩余輸入串while(t!=q)s2=wuhuivectort+s2;wuhuivector.pop_back();t-;l=0;while(x<6)&&(l!=1)if(s2=chanshengshix)l=1;x+;if(l=0)cout<<"分析失?。?quot

19、;<<endl;warn=0;ret=0;break;else if(l=1)if(x=1)|(x=2)wuhuivector.push_back(Vn0);else if(x>2)&&(x<7)wuhuivector.push_back(Vn1);s1="規(guī)約"（2） 設(shè)計二進(jìn)制轉(zhuǎn)十進(jìn)制函數(shù)： a.判斷輸入的二進(jìn)制數(shù)是否有小數(shù)點時的函數(shù)： while(j<i-1)&&(k=0) if(aj='.') k=1; j+;b.無小數(shù)點時的轉(zhuǎn)換函數(shù)： if(k=0) for(l=0;l<i-1;l

20、+) ans=ans+(al-48)*pow(2,(i-2-l);c.有小數(shù)點時的轉(zhuǎn)換函數(shù)： if(k=1) for(l=0;l<j-1;l+) ans=ans+(al-48)*pow(2,(j-2-l); for(l=j;l<i-1;l+) ans=ans+(al-48)*pow(2,(j-1-l); 5.4 運行結(jié)果（1） 輸入一個正確的二進(jìn)制數(shù)時的運行結(jié)果：（2） 輸入一個帶不屬于該文法中非終結(jié)符的字符串時的運行結(jié)果：（3） 輸入一個無法規(guī)約的字符串時的運行結(jié)果：6.總結(jié)及體會 在編寫這次課程設(shè)計的過程中，真的是受益良多。編譯原理雖然平時都一直在看，也自認(rèn)為看得挺懂的，但是當(dāng)

21、真正要親手寫個編譯器的時候，確實真沒想象中那么容易。雖然在編寫之前，已經(jīng)先構(gòu)造好了思路，但是在寫的過程中，卻遇到了一個又一個瓶頸，但好歹還算順利，都一一解決了。真正令我頭疼的，是編寫完開始運行的時候，一個一個的問題就都顯現(xiàn)出來了。由于事先沒考慮周全，發(fā)現(xiàn)運行結(jié)果老是出問題，在一次又一次的排查之后，成功運行出了正確的結(jié)果，本以為已經(jīng)做好了，但在給學(xué)長檢查的時候才發(fā)現(xiàn)之前都沒考慮到輸入不合法的字符串時的解決方法，在改正這些問題后，才算真正完成了這個編譯器。通過該課程設(shè)計，全面系統(tǒng)的理解了編譯原理程序構(gòu)造的一般原理和基本實現(xiàn)方法。能夠把學(xué)過的計算機編譯原理的知識強化，并通過自己設(shè)計的程序表現(xiàn)出來，加

22、深了對理論知識的理解，同時也激發(fā)了學(xué)習(xí)的積極性。7. 源代碼#include <iostream>#include<string>#include<vector>#include<math.h>using namespace std;vector<char> myvector;char Vn2='S','A'char Vt4='.','0','1','#'string chanshengshi6="A.A","

23、A","0A","1A","0","1"int table44=-999,-1,-1,1,1,-1,-1,1,1,-1,-1,1,-1,-1,-1,0;/-999表示無關(guān)系，1表示先于關(guān)系，0表示等價關(guān)系，-1表示后于關(guān)系int Analyze();void change(char *a,int i);int main() int i=0,j; char a50; cout<<"請輸入一個無符號二進(jìn)制數(shù)，并以#結(jié)束：" do cin>>ai; i+; while

24、(ai-1!='#'); for(j=i-1;j>=0;j-) myvector.push_back(aj); if(Analyze()=1) change(a,i); return 0;int Analyze()/語法分析 int ret=1,v=0,warn=1;char c=myvectormyvector.size()-1;string s1="移進(jìn)" vector<char> wuhuivector; wuhuivector.push_back('#'); doif(c>='0')&&

25、amp;(c<='9')|(c='.')|(c='#')int j,k,l,m,n,p,q,t,x=0;string s2="",s3,s4="",s5=""if(s1="移進(jìn)")c=myvectormyvector.size()-1;myvector.pop_back();p=wuhuivector.size()-1;while(p>=0)s4=wuhuivectorp+s4; /s4是符號串的輸出內(nèi)容p-;l=0;k=wuhuivector.size(

26、);dok-; /k是符號棧的第一個終結(jié)符的下標(biāo)j=0;while(j<4)&&(l=0)/找符號棧的最外面一個終結(jié)符if(wuhuivectork=Vtj)l=1;elsej+;while(l!=1); for(j=0;j<4;j+)if(wuhuivectork=Vtj)m=j;if(c=Vtj)n=j;if(tablemn=-999)/失敗cout<<"分析失敗！"<<endl;ret=0;warn=0;break;else if(tablemn=0)if(wuhuivectork='#')warn=

27、0;s1="分析成功！"elsewuhuivector.push_back(c);s1="移進(jìn)"else if(tablemn=-1)/移進(jìn)wuhuivector.push_back(c);s1="移進(jìn)"else if(tablemn=1)/規(guī)約q=k;do /找符號棧第二個終結(jié)符，尋找最左素短語l=0;dop=0;q-;while(p<4)&&(l=0)if(wuhuivectorq=Vtp)l=1;elsep+;while(l!=1);for(j=0;j<4;j+)if(wuhuivectorq=Vtj)m=j;if(wuhuivectork=Vtj)n=j;q=q-1;while(tablemn!=-1);q+;t=wuhuivector.size()-1;/s2是剩余輸入串while(t!=q)s2=wuhuivectort+s2;wuhuivector.pop_back();t-;l=0;while(x<6)&&(l!=1)if(s2=chanshen