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

1、課程設(shè)計(jì)任務(wù)書 學(xué)生姓名：* *專業(yè)班級(jí)：軟sy120班 指導(dǎo)教師：碧工作單位：計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 題目:二十進(jìn)制的語(yǔ)法分析及語(yǔ)義分析程序的設(shè)計(jì) 1目 通過設(shè)計(jì)編制調(diào)試一個(gè)語(yǔ)*法及語(yǔ)義分析程序加深對(duì)語(yǔ)法及語(yǔ)義分析原理 的理解。 2.設(shè)計(jì)內(nèi)容及要求 設(shè)計(jì)一個(gè)二十進(jìn)制的語(yǔ)法分析及語(yǔ)義分析程序 ）選擇算符優(yōu)先分析法完成以上任務(wù) 寫出符合分析方法要求的文法給出分析方法的思想完成分析程序設(shè) 計(jì)。 編制好分析程序后設(shè)計(jì)若干用例上機(jī)測(cè)試并通過所設(shè)計(jì)的分析程序。 3.課程設(shè)計(jì)進(jìn)度安 序號(hào) 階段內(nèi) 所需用時(shí) 天 1 給出語(yǔ)法分析方法及中間代碼形式的描述、文法和屬性文法天 代碼的設(shè)計(jì) 的設(shè)計(jì)；或者詞法分析方法及

2、符號(hào)表代碼的設(shè)計(jì) 2 簡(jiǎn)要的分析與概要設(shè)計(jì)、算法設(shè)計(jì)與程序設(shè)計(jì) 天 3 撰寫課程設(shè)計(jì)報(bào)告書 天 合計(jì) 天 武漢理工大學(xué)編譯原理課程設(shè)計(jì) 目錄 目3 1.系統(tǒng)描述4 12設(shè)計(jì)內(nèi)容及步驟4 2翻譯方法概述4 2.1詞法分析4 2.2 語(yǔ)法分析5 2.3中間代碼生成5 2.4屬性文法5 3算符優(yōu)先分析法6 4文法7 4.1文法形式7 4.2文法分類7 4.3類型說(shuō)明7 5. 系統(tǒng)的詳細(xì)設(shè)計(jì)8 5.1 文法設(shè)計(jì)8 5.2構(gòu)造算符優(yōu)先關(guān)系矩陣9 5.3算法設(shè)計(jì)9 5.4 運(yùn)行結(jié)果14 6.總結(jié)及體會(huì)15 7. 源代碼16 武漢理工大學(xué)編譯原理課程設(shè)計(jì) 二十進(jìn)制的語(yǔ)法分析及語(yǔ)義分析程序設(shè)計(jì) 算符優(yōu)先分析

3、算符優(yōu)先分析 - 1.系統(tǒng)描述 通過設(shè)計(jì)、編制、調(diào)試一個(gè)十進(jìn)制的語(yǔ)法分析及語(yǔ)義分析程序，加深對(duì) 語(yǔ)法及語(yǔ)義分析原理的理解 1 2設(shè)計(jì)內(nèi)容及步驟 （Vn,Vt,P,S （Vn,Vt,P,S 詞法分析是計(jì)算機(jī)科學(xué)中將字符序列轉(zhuǎn)換為單詞Token （）設(shè)計(jì)算符優(yōu)先文法G= ） analyzer analyzer 簡(jiǎn)稱Lexer （）構(gòu)造算符優(yōu)先關(guān)系矩 （）設(shè)計(jì)語(yǔ)法分析程序，對(duì)輸入的數(shù)據(jù)進(jìn)行語(yǔ)法分 （）將輸入的合法二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制 2翻譯方法概述 2.1詞法分析 行語(yǔ)法分析的程序或者函數(shù)叫作詞法分析（Lexical 也叫掃描器Scanner ）。詞法分析器一般以函數(shù)的形式存在，供語(yǔ)法分析器調(diào) 用。

4、詞法分析是編譯過程中的第一個(gè)階段，在語(yǔ)法分析前進(jìn)。也可以和語(yǔ)法 分析結(jié)合在一起作為一遍由語(yǔ)法分析程序調(diào)用詞法分析程序來(lái)獲得當(dāng)前單詞供 析 也叫掃描器Scanner 的 ： 。 。 。 武漢理工大學(xué)編譯原理課程設(shè)計(jì) 運(yùn)算符：如、運(yùn)算符：如、/等。 5. 語(yǔ)法分析（Parser 界限符：如逗號(hào)、分號(hào)、括號(hào)等。 由于該程序不需進(jìn)行詞法分析，故在設(shè)計(jì)程序時(shí)省去了詞法分析這一步驟 2.2 語(yǔ)法分析 語(yǔ)法分析是編譯過程的一個(gè)邏輯階段語(yǔ)法分析的任務(wù)是在詞法分析的基礎(chǔ) 上將單詞序列組合成各類語(yǔ)法短語(yǔ)，如“程序”，“語(yǔ)句”，“表達(dá)式”等等。 語(yǔ)法分析程序判斷源程序在結(jié)構(gòu)上是否正源程序的結(jié)構(gòu)由上下文無(wú)關(guān)文法描 述

5、。 通常是作為編譯器或解釋器的組件出現(xiàn)的它的作用 是進(jìn)行語(yǔ)法檢查并構(gòu)建由輸入的單詞組成的數(shù)據(jù)結(jié)（一般是語(yǔ)法分析樹抽 象語(yǔ)法樹等層次化的數(shù)據(jù)結(jié)構(gòu)語(yǔ)法分析器通常使用一個(gè)獨(dú)立的詞法分析器從 輸入字符流中分離出一個(gè)個(gè)的“單詞”，并將單詞流作為其輸入。實(shí)際開發(fā)中 務(wù) （輸入文本 2.3中間代碼生成 中間代碼也稱中間語(yǔ)言是復(fù)雜性介于源程序語(yǔ)言和機(jī)器語(yǔ)言的一種表示 形式為了使編譯程序有較高的目標(biāo)程序質(zhì)量或要求從編譯程序邏輯結(jié)構(gòu)上把 與機(jī)器無(wú)關(guān)和與機(jī)器有關(guān)的工作明顯的分開來(lái)時(shí)許多編譯程序都采用了某種復(fù) 雜性介于源程序語(yǔ)言和機(jī)器語(yǔ)言之間的中間語(yǔ)言中間代（語(yǔ)言是一種特殊 結(jié)構(gòu)的語(yǔ)言編譯程序所使用的中間代碼有多種形

6、式按其結(jié)構(gòu)分常見的有逆波 蘭式（后綴式）、三地址代碼（三元式、四元式）和樹形表示 表示。 DAG 表示。 2.4屬性文法 對(duì)于文法的每個(gè)產(chǎn)生式都配備了一組屬性的計(jì)算規(guī)則稱為語(yǔ)義規(guī)則 語(yǔ)法制導(dǎo)的翻譯指的是在語(yǔ)法分析過程中完成這些語(yǔ)義規(guī)則描述的動(dòng)作 武漢理工大學(xué)編譯原理課程設(shè)計(jì) 實(shí)現(xiàn)語(yǔ)義處理。 些語(yǔ)義規(guī)則附在文法的每個(gè)產(chǎn)生式上。 3算符優(yōu)先分析法 算符文法即它的任一產(chǎn)生式的右部都不含兩個(gè)相繼的非終結(jié)符的文法 果是一個(gè)不含空字符的算法文法，那么只要它的任一對(duì)終結(jié)符都之多只 p=Qa 、，、或P-Qa 、， 而屬于非終結(jié)字符集 （）=a|P-.a 或P-.aQ 集： (1) 、或P-Qa （）=a|P

7、-.a 或P-.aQ 集： (1) 、或P-Qa （）； (2) 若有屬于FirstVT 集的規(guī)則： (1) 或P- aQ 集。 (2) 若屬于LastVT （），且有產(chǎn)生式P- ，則屬于LastVT LastVT ，屬于終結(jié)字符集，而 當(dāng)且僅當(dāng)中含有形如當(dāng)且僅當(dāng)中含有形如ab 或aQb 的產(chǎn)生式； 結(jié)字符集 由以下兩條規(guī)則來(lái)構(gòu)造FirstVT (2)ab, 的產(chǎn)生式(2)aQb 若有產(chǎn)生式P- ，則屬于FirstVT 當(dāng)且僅當(dāng)中含有形如當(dāng)且僅當(dāng)中含有形如Rb （且有產(chǎn)生式P則屬于FirstVT(P); 類似的有構(gòu)造LastVT aQ aQ 和LastVT 若有產(chǎn)生式P- ，則屬于LastVT

8、 集。 假定是一個(gè)不含空字符產(chǎn)生式的算符文法。對(duì)于任何一對(duì)終結(jié)符, (1)a=b, 當(dāng)且僅當(dāng)中含有形如aR ； - (3)ab, ； 這樣再結(jié)合上次的FirststVT 的產(chǎn)生式而或 集的概念便可以由文法自動(dòng) 算符優(yōu)先表。 武漢理工大學(xué)編譯原理課程設(shè)計(jì) 4文法 4.1文法形式 巴克斯范式)，而另一個(gè)重要的概念巴克斯范式)，而另一個(gè)重要的概念 年建立形式語(yǔ)言的描述以來(lái) 論發(fā)展很快這種理論對(duì)計(jì)算機(jī)科學(xué)有著深刻的影響 設(shè)計(jì)、編譯方法和計(jì)算復(fù)雜性等方面更有重大的作用 喬姆斯基把文法分成四種類型，即型、和 差別在于對(duì)產(chǎn)生式施加不同的限制。 多數(shù)程序設(shè)計(jì)語(yǔ)言的單詞的語(yǔ)法都能用正規(guī)文法或型文法來(lái)描述。 型文

9、法G=(VN 自從喬姆斯(Chomsky) 在計(jì)算機(jī)科學(xué)中文法是編譯原理的基礎(chǔ) 其編譯器的方法。文法的描述多用 BNF( 則表達(dá)式，也是文法的另一種形式 4.2文法分類 于1956 VTS的中的規(guī)則有兩種形式：一種是前面定義的形 式即AaB或Aa其中ABVN aVT*另一種形式是ABa或 前者稱為右線性文法，后者稱為左線性文法。正規(guī)文法所描述的是VT*上的正規(guī) 集。 四個(gè)文法類的定義是逐漸增加限制的因此每一種正規(guī)文法都是上下文無(wú)關(guān) 的，每一種上下文無(wú)關(guān)文法都是上下文有關(guān)的，而每一種上下文有關(guān)文法都是0 型文法稱型文法產(chǎn)生的語(yǔ)言為型語(yǔ)言上下文有關(guān)文法上下文無(wú)關(guān)文法 和正規(guī)文法產(chǎn)生的語(yǔ)言分別稱為上

10、下文有關(guān)語(yǔ)言、上下文無(wú)關(guān)語(yǔ)言和正規(guī)語(yǔ)言 4.3類型說(shuō)明 設(shè) G=(VN ，VT，S，如果它的每個(gè)產(chǎn)生式 是這樣一種結(jié)構(gòu)： 而 則個(gè)設(shè) G=(VN 。 武漢理工大學(xué)編譯原理課程設(shè)計(jì) 型文法也稱短語(yǔ)文法。一個(gè)非常重要的理論結(jié)果是， 于圖靈機(jī)(Turing) 何型文法也稱短語(yǔ)文法。一個(gè)非常重要的理論結(jié)果是， 于圖靈機(jī)(Turing) 對(duì)，和。 設(shè) ，T，S)為一文法，若 P中的每一個(gè)產(chǎn)生式 | | |，僅僅S除外，則文法是型或上下文有關(guān)的 設(shè)G=(VS若式 ：結(jié) ， 為型的或上下文無(wú)關(guān)的。有時(shí)將 產(chǎn)生式表示為形如：A其中AVN，也就是說(shuō)用取代非終結(jié)符A與 。 設(shè)，T，)若是 或 中A和B，a是。 法

11、組N，T，)中 號(hào)(量)； ； ； N，T和是 。 ，為 。 N和T 5. 系統(tǒng)的詳細(xì)設(shè)計(jì) 5.1 文法設(shè)計(jì) （Vn,Vt,P,S（Vn,Vt,P,S 設(shè)計(jì)算符優(yōu)先文法G= 產(chǎn)生式組成 （）S-A.A|A （）A-0A|1A （）A-0|1 其中Vn=S,A,V下 武漢理工大學(xué)編譯原理課程設(shè)計(jì) 5.2構(gòu)造算符優(yōu)先關(guān)系矩陣 . 0 1 # . 0 1 # = 5.3算法設(shè)計(jì) （）設(shè)計(jì)語(yǔ)法分析程序 定義兩個(gè)向量myvector 中棧頂元素即當(dāng)前符號(hào)存 符號(hào)棧最外面一個(gè)非終結(jié)符與當(dāng)前符號(hào)的優(yōu)先級(jí)中棧頂元素即當(dāng)前符號(hào)存 符號(hào)棧最外面一個(gè)非終結(jié)符與當(dāng)前符號(hào)的優(yōu)先級(jí) 價(jià)于當(dāng)前符號(hào)則移進(jìn)當(dāng)前符號(hào)至wuhui

12、vector wuhuivector 棧頂元素存于中，當(dāng)動(dòng)作為移進(jìn)時(shí)，彈出棧頂元素 if(s1= 將myvector 和wuhuivector ，myvector和wuhuivector ，myvector 中若該非終結(jié)符優(yōu)先級(jí)先于當(dāng) 否則分析失敗。分析至符號(hào)棧中最外面的非終結(jié)符與當(dāng)前符號(hào)均為時(shí)，分 析成功。 a. 移進(jìn)) c=myvectormyvector.size()-1; myvector.pop_back(); b比較符號(hào)棧最外面一個(gè)非終結(jié)符與當(dāng)前符號(hào)的優(yōu)先級(jí)，優(yōu)先關(guān)系事先用 ta存儲(chǔ)了 while(j4結(jié) if(wuhuivectork=Vtj) 武漢理工大學(xué)編譯原理課程設(shè)計(jì) l=

13、1 else j+; for(j=0;j4;j+) if(wuhuivectork=Vtj) m=j; if(c=Vtj) n=j; tablemn 即為兩者的優(yōu)先級(jí) 即為兩者的優(yōu)先級(jí) table44=-999,-1,-1,1,1,-1,-1,1,1,-1,-1,1,-1,-1,-1,0; /-999 表示無(wú)關(guān)系，表示先于關(guān)系，表示等價(jià)關(guān)系，-表示后于關(guān)系 因無(wú)優(yōu)先關(guān)系分析失敗函數(shù)： if(tablemn=-999)/因無(wú)優(yōu)先關(guān)系分析失敗函數(shù)： if(tablemn=-999)/ 失敗 cout cout warn=0; break; 分析成功或移進(jìn)函數(shù)： d.分析成功或移進(jìn)函數(shù)： else

14、if(tablemn=0) if(wuhuivectork=#) warn=0; 分析成功！; s1= 分析成功！; 武漢理工大學(xué)編譯原理課程設(shè)計(jì) else wuhuivector.push_back(c); 移進(jìn); s1= 移進(jìn); 移進(jìn) else if(tablemn=-1)/ 移進(jìn) wuhuivector.push_back(c); 移進(jìn); s1= 移進(jìn); e規(guī)約及因無(wú)匹配產(chǎn)生式分析失敗函數(shù)： 規(guī)約 else if(tablemn=1)/ 規(guī)約 q=k 找符號(hào)棧第二個(gè)終結(jié)符，尋找最左素短語(yǔ) 找符號(hào)棧第二個(gè)終結(jié)符，尋找最左素短語(yǔ) l=0; do p=0; q- while(p4)&(l=0)

15、 if(wuhuivectorq=Vtp) l=1; else p+; while(l!=1) 武漢理工大學(xué)編譯原理課程設(shè)計(jì) for(j=0;j4;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(x6)&(l!=1) if(s2=chanshengsh

16、ix) l=1; x+; if(l=0) 分析失??！endl; warn=0; 分析失??！2)&(x7) wuhuivector.push_back(Vn1); 規(guī)約; s1= 規(guī)約; （）設(shè)計(jì)二進(jìn)制轉(zhuǎn)十進(jìn)制函數(shù)： a. 判斷輸入的二進(jìn)制數(shù)是否有小數(shù)點(diǎn)時(shí)的函數(shù)：判斷輸入的二進(jìn)制數(shù)是否有小數(shù)點(diǎn)時(shí)的函數(shù)： while(ji-1)&(k=0) if(aj=.) k=1; j+; b. 無(wú)小數(shù)點(diǎn)時(shí)的轉(zhuǎn)換函數(shù)： if(k=0) for(l=0;li-1;l+) ans=ans+(al-48)*pow(2,(i-2-l c. 有小數(shù)點(diǎn)時(shí)的轉(zhuǎn)換函數(shù)： 有小數(shù)點(diǎn)時(shí)的轉(zhuǎn)換函數(shù)： if(k=1) for(l=0;

17、lj-1;l+) 武漢理工大學(xué)編譯原理課程設(shè)計(jì) ans=ans+(al-48)*pow(2,(j-2-l for(l=j;li-1;l+) ans=ans+(al-48)*pow(2,(j-1-l 5.4 運(yùn)行結(jié)果 （）輸入一個(gè)正確的二進(jìn)制數(shù)時(shí)的運(yùn)行結(jié)果 （）輸入一個(gè)帶不屬于該文法中非終結(jié)符的字符串時(shí)的運(yùn)行結(jié)果 武漢理工大學(xué)編譯原理課程設(shè)計(jì) （3輸入一個(gè)無(wú)法規(guī)約的字符串時(shí)的運(yùn)行結(jié)果： 6.總結(jié)及體會(huì) 在編寫這次課程設(shè)計(jì)的過程中真的是受益良多編譯原理雖然平時(shí)都一直 在看也自認(rèn)為看得挺懂的但是當(dāng)真正要親手寫個(gè)編譯器的時(shí)候確實(shí)真沒想 卻 是 的 實(shí) ， 武漢理工大學(xué)編譯原理課程設(shè)計(jì) 7.源代碼 #i

18、nclude #include #include #include using namespace std; vector myvector; char Vn2=S,A; char Vt4=.,0,1,#; string chanshengshi6=A.A,A,0A,1A int table44=-999,-1,-1,1,1,-1,-1,1,1 9示無(wú)關(guān)系表示先于關(guān)系表示等價(jià)關(guān)系-表示后于關(guān) int Analyze(); void change(char *a,int i); int main() int i=0,j; char a50; coutai; i+; while(ai-1!=#);

19、 for(j=i-1;j=0;j-) myvector.push_back(aj); if(Analyze()=1) change(a,i); return 0; int Analyze()/ 語(yǔ)法分析 int ret=1,v=0,warn=1; char c=myvectormyvector.size()-1; string s1= 移進(jìn); vector wuhuivector; wuhuivector.push_back(#); do if(c=0)&(c=0) 是符號(hào)串的輸出內(nèi)容 s4=wuhuivectorp+s4; /s4 是符號(hào)串的輸出內(nèi)容 p-; l=0; k=wuhuivect

20、or.size(); do 是符號(hào)棧的第一個(gè)終結(jié)符的下標(biāo) k-; /k 是符號(hào)棧的第一個(gè)終結(jié)符的下標(biāo) j=0; 找符號(hào)棧的最外面一個(gè)終結(jié)符 while(j4)&(l=0)/ 找符號(hào)棧的最外面一個(gè)終結(jié)符 if(wuhuivectork=Vtj) l=1 else j+ while(l!=1) for(j=0;j4;j+) if(wuhuivectork=Vtj) m=j; if(c=Vtj) n=j; 失敗 失敗 cout 分析失?。ndl; ret=0; warn=0; break; else if(tablemn=0) if(wuhuivectork=#) warn=0; 武漢理工大學(xué)編譯

21、原理課程設(shè)計(jì) 分析成功！; s1= 分析成功！; else wuhuivector.push_back(c); 移進(jìn); s1= 移進(jìn); 移進(jìn) else if(tablemn=-1)/ 移進(jìn) wuhuivector.push_back(c); 移進(jìn); 移進(jìn); else if(tablemn=1)/ 規(guī)約 q=k 找符號(hào)棧第二個(gè)終結(jié)符，尋找最左素短語(yǔ) do / 找符號(hào)棧第二個(gè)終結(jié)符，尋找最左素短語(yǔ) l=0; do p=0; q- while(p4)&(l=0) if(wuhuivectorq=Vtp) l=1; else p+; while(l!=1) for(j=0;j4;j+) if(wuhuivectorq=Vtj) m=j; if(wuhuivectork=