編譯原理-逆波蘭式的產(chǎn)生及計算

1、學(xué)號1406410107成績編譯原理上機(jī)報告名學(xué)專班姓稱：逆波蘭式的產(chǎn)生及計算院：信息與控制工程學(xué)院業(yè)：計算機(jī)科學(xué)與技術(shù)級：計算機(jī)1401班名：葉達(dá)成2016年11月4日一、上機(jī)目的通過設(shè)計、編制、調(diào)試一個典型的語法分析程序，實現(xiàn)對詞法分析程序所提供的單詞序列進(jìn)行語法檢查和結(jié)構(gòu)分析，進(jìn)一步掌握常用的語法分析方法。1、選擇最有代表性的語法分析方法，如ll(1)語法分析程序、算符優(yōu)先分析程序和lr分析分析程序，并至少完成兩個題目。2、選擇對各種常見程序語言都用的語法結(jié)構(gòu)，如賦值語句（尤指表達(dá)式）作為分析對象，并且與所選語法分析方法要比較貼切。實驗前的準(zhǔn)備按實驗的目的和要求，編寫語法分析程序，同時考

2、慮相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。調(diào)試調(diào)試?yán)討?yīng)包括符合語法規(guī)則的算術(shù)表達(dá)式，以及分析程序能夠判別的若干錯例。輸出對于所輸入的算術(shù)表達(dá)式，不論對錯，都應(yīng)有明確的信息告訴外界。擴(kuò)充有余力的同學(xué)，可適當(dāng)擴(kuò)大分析對象。譬如：算術(shù)表達(dá)式中變量名可以是一般標(biāo)識符，還可含一般常數(shù)、數(shù)組元素、函數(shù)調(diào)用等等。除算術(shù)表達(dá)式外，還可擴(kuò)充分析布爾、字符、位等不同類型的各種表達(dá)式。加強(qiáng)語法檢查，盡量多和確切地指出各種錯誤。二、基本原理和上機(jī)步驟基本原理：將運算對象寫在前面，而把運算符號寫在后面。用這種表示法表示的表達(dá)式也稱做后綴式。逆波蘭式的特點在于運算對象順序不變，運算符號位置反映運算順序。采用逆波蘭式可以很好的表示簡單算術(shù)表達(dá)式

3、，其優(yōu)點在于易于計算機(jī)處理表達(dá)式。上機(jī)步驟：(1)構(gòu)造一個棧，存放運算對象。(2)讀入一個用逆波蘭式表示的簡單算術(shù)表達(dá)式。(3)自左至右掃描該簡單算術(shù)表達(dá)式并判斷該字符，如果該字符是運算對象，則將該字符入棧。若是運算符，如果此運算符是二目運算符，則將對棧頂部的兩個運算對象進(jìn)行該運算，將運算結(jié)果入棧，并且將執(zhí)行該運算的兩個運算對象從棧頂彈出。如果該字符是一目運算符，則對棧頂部的元素實施該運算，將該棧頂部的元素彈出，將運算結(jié)果入棧。(4)重復(fù)上述操作直至掃描完整個簡單算術(shù)表達(dá)式的逆波蘭式，確定所有字符都得到正確處理，我們便可以求出該簡單算術(shù)表達(dá)式的值。三、上機(jī)結(jié)果程序清單：#include#inc

4、lude#include#include#include#includeusingnamespacestd;charstr50;inttop;charstack50;charex50;double_stack50;intflag50;/用于存放原來的表達(dá)式/棧頂指針/定義棧，用于計算逆波蘭式/存放后綴表達(dá)式/定義棧，用于計算逆波蘭式子/用于區(qū)分+、-號的含義，0表示運算符，1表示正負(fù)號/生成逆波蘭式voidnibolan()memset(flag,0,sizeof(flag);/flag初始值設(shè)為0charch=str0;inti=1,t=0;top=0;while(ch!=#)switch(

5、ch)case(:top+;stacktop=ch;break;case):while(stacktop!=()ext=stacktop;top-;t+;top-;break;case:while(stacktop=)/設(shè)置運算符優(yōu)先級為最高ext=stacktop;top-;t+;top+;stacktop=ch;break;case+:case-:/當(dāng)ch為+、-號是，若前面相鄰字符不是)或數(shù)字且后面相鄰字符是數(shù)字時表示正負(fù)號if(isdigit(stri)&!isdigit(stri-2)&stri-2!=)flagt=1;/標(biāo)記符號為正負(fù)號ext+=ch;ch=stri+;while(

6、ch=0&ch=a&ch=0&ch=a&ch=0&ch=0&ch=0&ch=0&ch=0&ch=0&ch=9)d=d+double(ch-0)/(10.0*k);k=k+1.0;ch=ex+t;top+;_stacktop=d;ch=ext;cout計算結(jié)果：_stacktopendl;intmain()printf(請輸入中綴表達(dá)式：);/printf(計算結(jié)果：%lfn,_stacktop);scanf(%s,&str);/輸入原表達(dá)式printf(原表達(dá)式為：%sn,str);nibolan();calculate();return0;/生成逆波蘭式/計算逆波蘭式屏幕截圖：四、討論與分析通過這次的實驗，知道了算符優(yōu)先文法的概念以及這個文法的簡單應(yīng)用。通過對中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式的實驗，我對算符優(yōu)先級有了更深的理解。并解決了如何構(gòu)造這些優(yōu)先級以及如何運用他們來計算后綴表達(dá)式，同時計