編譯原理課程設(shè)計(jì)算術(shù)表達(dá)式的語法分析及語義分析程序設(shè)計(jì)

1、課程設(shè)計(jì)任務(wù)書學(xué)生姓名： 專業(yè)班級： 指導(dǎo)教師： 工作單位： 題 目: 算術(shù)表達(dá)式的語法分析及語義分析程序設(shè)計(jì)1目的通過設(shè)計(jì)、編制、調(diào)試一個(gè)算術(shù)表達(dá)式的語法及語義分析程序，加深對語法及語義分析原理的理解，并實(shí)現(xiàn)詞法分析程序?qū)卧~序列的詞法檢查和分析。2設(shè)計(jì)內(nèi)容及要求 算術(shù)表達(dá)式的文法：（1） 選擇算符優(yōu)先分析法完成以上任務(wù)，中間代碼選用逆波蘭式。（2） 寫出算術(shù)表達(dá)式的符合分析方法要求的文法，給出分析方法的思想，完成分析程序設(shè)計(jì)。（3） 編制好分析程序后，設(shè)計(jì)若干用例，上機(jī)測試并通過所設(shè)計(jì)的分析程序。3.課程設(shè)計(jì)報(bào)告書的內(nèi)容應(yīng)包括：（1）設(shè)計(jì)題目、班級、學(xué)號(hào)、姓名、完成日期；（2）給出算術(shù)表達(dá)

2、式的語法分析和語義分析的設(shè)計(jì)。（3）簡要的分析與概要設(shè)計(jì)；（4）詳細(xì)的算法描述；（5）源程序清單；（6）給出軟件的測試方法和測試結(jié)果；（7）設(shè)計(jì)的評價(jià)、收獲與體會(huì)。時(shí)間安排：第18周，周1-周3下午，周5全天指導(dǎo)教師簽名： 年 月 日系主任（或責(zé)任教師）簽名： 年 月 日1 課設(shè)要求設(shè)計(jì)題目 算術(shù)表達(dá)式轉(zhuǎn)換成逆波蘭式（用算符優(yōu)先分析法）1.1課程設(shè)計(jì)的目的課程設(shè)計(jì)是對學(xué)生的一種全面綜合訓(xùn)練，是與課堂聽講、自學(xué)和練習(xí)相輔相成的必不可少的一個(gè)教學(xué)環(huán)節(jié)。通常，設(shè)計(jì)題中的問題比平時(shí)的練習(xí)題要復(fù)雜，也更接近實(shí)際。編譯原理這門課程安排的課程設(shè)計(jì)的目的是旨在要求學(xué)生進(jìn)一步鞏固課堂上所學(xué)的理論知識(shí)，深化理解和

3、靈活掌握教學(xué)內(nèi)容，選擇合適的數(shù)據(jù)邏輯結(jié)構(gòu)表示問題，然后編制算法和程序完成設(shè)計(jì)要求，從而進(jìn)一步培養(yǎng)學(xué)生獨(dú)立思考問題、分析問題、解決實(shí)際問題的動(dòng)手能力。 要求學(xué)生在上機(jī)前應(yīng)認(rèn)真做好各種準(zhǔn)備工作，熟悉機(jī)器的操作系統(tǒng)和語言的集成環(huán)境，獨(dú)立完成算法編制和程序代碼的編寫。1.2 設(shè)計(jì)內(nèi)容及要求 算術(shù)表達(dá)式的文法：無符號(hào)整數(shù) 數(shù)字?jǐn)?shù)字標(biāo)志符 字母字母數(shù)字表達(dá)式 項(xiàng)加法運(yùn)算符項(xiàng)項(xiàng) 因子乘法運(yùn)算符因子因子 標(biāo)志符無符號(hào)整數(shù)（表達(dá)式）加法運(yùn)算符 乘法運(yùn)算符 1.選擇算符優(yōu)先分析法完成以上任務(wù)，中間代碼選用逆波蘭式。2.寫出算術(shù)表達(dá)式的符合分析方法要求的文法，給出分析方法的思想，3.完成分析程序設(shè)計(jì)。編制好分析程序

4、后，設(shè)計(jì)若干用例，上機(jī)測試并通過所設(shè)計(jì)的分析程序。2 摘要一個(gè)新的語言的出現(xiàn)，必然會(huì)有與之配套的編譯器的產(chǎn)生。編譯器對于一個(gè)語言的重要性不言而喻。編譯過程分為詞法分析、語法分析、語義分析、中間代碼生成、代碼優(yōu)化和目標(biāo)代碼生成這六個(gè)階段。而語法分析和語義分析是最關(guān)鍵的核心部分。要做好一個(gè)編譯器必須要懂得如何根據(jù)構(gòu)造的文法來識(shí)別出它的語法和語義。語法分析的方法很多，而比較容易懂的就有算符優(yōu)先分析法，本次課設(shè)的主題就是要弄懂算符優(yōu)先分析發(fā)。學(xué)習(xí)制作編譯器不僅會(huì)讓你弄懂這門課，還會(huì)讓你提高寫代碼的能力，特別是寫出高效，可靠性好的代碼。關(guān)鍵字：算術(shù)表達(dá)式，算符優(yōu)先文法，逆波蘭式3 引言逆波蘭式又叫做后綴

5、表達(dá)式，它的用途很多，譬如做計(jì)算器的時(shí)候可以對算術(shù)表達(dá)式采用這種形式來表示，從而可以很容易的來進(jìn)行計(jì)算。在編譯原理中，生成中間代碼的步驟里，逆波蘭式也是中間代碼的一種表示形式。算符優(yōu)先分析法是自底向上進(jìn)行語法分析的一種方式。自底向上分析的思想就是對輸入的符號(hào)串自左向右的進(jìn)行掃描，并將輸入符逐個(gè)移入一個(gè)后進(jìn)先出棧，邊移入邊分析，一旦棧頂符號(hào)串形成某個(gè)句型的句柄或可規(guī)約串時(shí)，就用該產(chǎn)生式左部的非終結(jié)符代替相應(yīng)右部的文法符號(hào)串，這一步叫做規(guī)約。重復(fù)這一過程直到規(guī)約到棧中只剩文法的開始符號(hào)時(shí)則規(guī)約成功，也就確認(rèn)了這個(gè)輸入串是文法的句子。算符優(yōu)先法規(guī)定了算符之間的優(yōu)先關(guān)系，通過先于關(guān)系識(shí)別句柄尾，通過后

6、于關(guān)系識(shí)別句柄頭，以此來進(jìn)行規(guī)約。4 正文4.1 需求分析 要通過算符優(yōu)先分析方法進(jìn)行將算術(shù)表達(dá)式轉(zhuǎn)換成為逆波蘭式，首先要經(jīng)過詞法分析，然后是語法分析，通過規(guī)約來輸出算術(shù)表達(dá)式的逆波蘭式。故先要求出每個(gè)非終結(jié)符的firstvt()集和lastvt()集，然后求出終結(jié)符的算符優(yōu)先矩陣，最后以此來規(guī)約。因此程序應(yīng)該能夠提供輸入一個(gè)任意的算符優(yōu)先文法，并可以對輸入的文法進(jìn)行判斷，還可以對文法進(jìn)行改寫，便于后面的分析。自動(dòng)求出每個(gè)非終結(jié)符的firstvt()集和lastvt()集，自動(dòng)構(gòu)造終結(jié)符的優(yōu)先矩陣，然后自動(dòng)規(guī)約，輸出逆波蘭式。4.2 理論基礎(chǔ)算符優(yōu)先分析法是自底向上分析法法的一種，它的工作原理

7、是先求出文法中每個(gè)非終結(jié)符的firstvt()集和lastvt()集，通過文法中每個(gè)產(chǎn)生式的右部非終結(jié)符所處的位置來確定每個(gè)非終結(jié)符之間的優(yōu)先關(guān)系。譬如s-aab，則a后于a的lastvt()集規(guī)約，也后于a的firstvt()集規(guī)約。然后求出非終結(jié)符的算符優(yōu)先矩陣，根據(jù)矩陣所確定的優(yōu)先關(guān)系進(jìn)行規(guī)約。為了將算符優(yōu)先分析方法與輸出逆波蘭式聯(lián)系起來，首先要明白算符優(yōu)先方法規(guī)約的每一步是如何進(jìn)行的，在確定某個(gè)終結(jié)符要規(guī)約時(shí)，應(yīng)該將它保存起來，然后在最后輸出這一串符號(hào)，即為所求的逆波蘭式。4.3 總體設(shè)計(jì)先改寫文法，在求各個(gè)非終結(jié)符的firstvt()集和lastvt()集，確定優(yōu)先關(guān)系矩陣后就進(jìn)行規(guī)

8、約。系統(tǒng)流程圖如下：開始輸入文法文法是否正確改寫文法y求每個(gè)非終結(jié)符的firstvt()集和lastvt()集求算符優(yōu)先矩陣規(guī)約成功輸出逆波蘭式結(jié)束ynn所要用到的數(shù)據(jù)結(jié)構(gòu)及自定義函數(shù)如下：char data2020; /算符優(yōu)先關(guān)系char s100; /模擬符號(hào)棧s char lable20; /文法終極符集char input100; /文法輸入符號(hào)串char string2010; /用于輸入串的分析int k; char a; int j; char q; int r; /文法規(guī)則個(gè)數(shù)int r1; int m,n,n; /轉(zhuǎn)化后文法規(guī)則個(gè)數(shù)char st1030; /用來存儲(chǔ)文法規(guī)

9、則char first1010; /文法非終結(jié)符firstvt集char last1010; /文法非終結(jié)符lastvt集int fflag10=0; /標(biāo)志第i個(gè)非終結(jié)符的firstvt集是否已求出int lflag10=0; /標(biāo)志第i個(gè)非終結(jié)符的lastvt集是否已求出int deal(); /對輸入串的分析int zhongjie(char c); /判斷字符c是否是終極符int xiabiao(char c); /求字符c在算符優(yōu)先關(guān)系表中的下標(biāo)void out(int j,int k,char *s); /打印s棧void firstvt(char c); /求非終結(jié)符c的firs

10、tvt集void lastvt(char c); /求非終結(jié)符c的lastvt集void table(); /創(chuàng)建文法優(yōu)先關(guān)系表char shuchu10;/存儲(chǔ)逆波蘭式4.4 詳細(xì)設(shè)計(jì)4.4.1 判斷文法是否正確要對輸入的文法進(jìn)行判斷是否為算符文法。首先判斷文法是否為上下文無關(guān)文法，然后判斷是否為算符文法。判斷的過程比較簡單，先看每個(gè)產(chǎn)生式的左部是否為非終結(jié)符（在這里人為規(guī)定大寫字母表示非終結(jié)符，且不用進(jìn)行判斷），然后看產(chǎn)生式的右部是否有兩個(gè)非終結(jié)符挨在一起的，若挨在一起，則不是算符文法，否則就是算符文法。4.4.2 改寫文法 若產(chǎn)生式的右部有形如s-a+b|a-b的產(chǎn)生式，則應(yīng)該改寫為兩條

11、產(chǎn)生式：(1)s-a+b；(2)s-a-b；按此方式對文法改寫后輸出到屏幕上。4.4.3求每個(gè)非終結(jié)符的firstvt()集和lastvt()集對firstvt()集的構(gòu)造可以根據(jù)以下兩條規(guī)則構(gòu)造：(1)若有產(chǎn)生式a-ba.或a-a.，則a屬于firstvt(a)；(2)若a屬于firstvt(b)且有產(chǎn)生式a-b.則有a屬于firstvt(a)部分代碼如下：if(fflagi=0)n=firsti0+1;m=0;doif(m=2|stim=|)if(zhongjie(stim+1)firstin=stim+1;n+;elseif(zhongjie(stim+2)firstin=stim+2;

12、n+;if(stim+1!=c)firstvt(stim+1);for(j=0;jr;j+)if(stj0=stim+1)break;for(k=0;kfirstj0;k+)int t;for(t=0;tn;t+)if(firstit=firstjk+1)break;if(t=n)firstin=firstjk+1;n+;m+;while(stim!=0);firstin=0;firsti0=-n;fflagi=1;同樣lastvt()集也可以按照類似的方式構(gòu)造。4.4.4 求算符優(yōu)先矩陣構(gòu)造算符優(yōu)先關(guān)系表。算符優(yōu)先矩陣在本程序中的作用是最大的，算符優(yōu)先關(guān)系表是一個(gè)二維數(shù)組，用來存放任意兩個(gè)終

13、結(jié)符之間的優(yōu)先關(guān)系。首先構(gòu)造表頭，通過掃描所有產(chǎn)生式將終結(jié)符不重復(fù)的存放在一個(gè)一維數(shù)組中并置為優(yōu)先關(guān)系表的行和列，并將優(yōu)先關(guān)系表其他內(nèi)容全部初始化為空。接著遍歷所有產(chǎn)生式，找出任意兩個(gè)終結(jié)符之間存在的關(guān)系（可以沒有關(guān)系），并判斷任意兩終結(jié)符是否至多存在一種優(yōu)先關(guān)系，如發(fā)現(xiàn)優(yōu)先關(guān)系表不為空，則證明該文法不是算符優(yōu)先文法，否則，將相應(yīng)的關(guān)系填入到相應(yīng)的行列對應(yīng)的單元中。部分代碼如下：for(i=0;ix;i+)for(j=1;textij+1!=0;j+)if(zhongjie(textij)&zhongjie(textij+1)m=xiabiao(textij);n=xiabiao(textij

14、+1);datamn=;if(textij+2!=0&zhongjie(textij)&zhongjie(textij+2)&!zhongjie(textij+1)m=xiabiao(textij);n=xiabiao(textij+2);datamn=;if(zhongjie(textij)&!zhongjie(textij+1)/終結(jié)符和非終結(jié)符相接，用后于關(guān)系填表for(k=0;kr;k+)if(stk0=textij+1)break;m=xiabiao(textij);for(t=0;tfirstk0;t+)n=xiabiao(firstkt+1);datamn=;if(!zhongj

15、ie(textij)&zhongjie(textij+1)/非終結(jié)符和終結(jié)符相接，用先于關(guān)系填表for(k=0;kr;k+)if(stk0=textij)break;n=xiabiao(textij+1);for(t=0;t;4.4.5 輸出逆波蘭式要想在規(guī)約的時(shí)候輸出算術(shù)表達(dá)式的逆波蘭式，確定規(guī)約的終結(jié)符后，用一個(gè)字符數(shù)組將這些終結(jié)符存起來，在規(guī)約成功輸出這些字符串即為所求的逆波蘭式部分代碼如下：if(dataxy=)if(lablex!=) shuchusize+=lablex;/將要規(guī)約的終結(jié)符存起來out(1,k,s);printf(%c,a);out(i+1,z,input);pri

16、ntf(規(guī)約n);5 調(diào)試及運(yùn)行結(jié)果更換文法后：6 心得體會(huì)本次課程設(shè)計(jì)相對來來說不是很容易的，它的要求比較高，要將編譯原理中所學(xué)的很多知識(shí)聯(lián)系起來，并且要有比較良好的編程能力。一開始看到題目的時(shí)候我也是沒什么頭緒，理不清思路，不明白為什么將算術(shù)表達(dá)式轉(zhuǎn)換為逆波蘭式與算符優(yōu)先分析法有何種聯(lián)系。沒辦法，我只好在書本中尋找靈感，在看到確定了算符優(yōu)先矩陣之后，每一步規(guī)約的終結(jié)符按先后順序連接起來剛好是逆波蘭式。按照這個(gè)想法，我開始有了大概的規(guī)劃，然后照著這個(gè)想法去做，終于做好了。課程設(shè)計(jì)與一般的實(shí)驗(yàn)不同，與在課堂上學(xué)習(xí)理論知識(shí)更加不同，它是考查學(xué)習(xí)成果的一種手段，更加是檢驗(yàn)?zāi)愕哪芰退降囊环N方式。

17、將理論與實(shí)踐結(jié)合起來才是王道。當(dāng)然，我的程序也存在著不足，沒有進(jìn)行詞法分析，只是簡單的默認(rèn)了所輸入的符號(hào)串都符合規(guī)定。通過本次課程設(shè)計(jì)，不僅加強(qiáng)了我對編譯原理的認(rèn)識(shí)，掌握了很多知識(shí)，更加讓我明白了動(dòng)手能力的重要性。在未來學(xué)習(xí)的道路上，應(yīng)該繼續(xù)發(fā)揚(yáng)這種精神，將實(shí)踐進(jìn)行到底！7 源代碼#include stdio.h#include stdlib.h#include iostream.hchar data2020; /算符優(yōu)先關(guān)系char s100; /模擬符號(hào)棧s char lable20; /文法終極符集char input100; /文法輸入符號(hào)串char string2010; /用于輸入

18、串的分析int k; char a; int j; char q; int r; /文法規(guī)則個(gè)數(shù)int r1; int m,n,n; /轉(zhuǎn)化后文法規(guī)則個(gè)數(shù)char st1030; /用來存儲(chǔ)文法規(guī)則char first1010; /文法非終結(jié)符firstvt集char last1010; /文法非終結(jié)符lastvt集int fflag10=0; /標(biāo)志第i個(gè)非終結(jié)符的firstvt集是否已求出int lflag10=0; /標(biāo)志第i個(gè)非終結(jié)符的lastvt集是否已求出int deal(); /對輸入串的分析int zhongjie(char c); /判斷字符c是否是終極符int xiabia

19、o(char c); /求字符c在算符優(yōu)先關(guān)系表中的下標(biāo)void out(int j,int k,char *s); /打印s棧void firstvt(char c); /求非終結(jié)符c的firstvt集void lastvt(char c); /求非終結(jié)符c的lastvt集void table(); /創(chuàng)建文法優(yōu)先關(guān)系表char shuchu10;/存儲(chǔ)逆波蘭式void main()int i,j,k=0; printf(請輸入文法規(guī)則數(shù)：);scanf(%d,&r);printf(請輸入文法規(guī)則：n);for(i=0;ir;i+)scanf(%s,sti); /存儲(chǔ)文法規(guī)則，初始化firs

20、tvt集和lastvt集*/ firsti0=0; /*firsti0和lasti0分別表示sti0非終極符的firstvt集和lastvt集中元素的個(gè)數(shù)*/lasti0=0;for(i=0;ir;i+) /判斷文法是否合法for(j=0;stij!=0;j+)if(sti0z)printf(不是算符文法!n); exit(-1);if(stij=a&stij=a&stij+1=z)printf(不是算符文法!n); exit(-1); for(i=0;ir;i+)/for(j=0;stij!=0;j+)if(stijz)&stij!=-&stij!=&stij!=|)lablek+=stij

21、;lablek=#;lablek+1=0; table();/printf(每個(gè)非終結(jié)符的firstvt集為：n); /輸出每個(gè)非終結(jié)符的firstvt集for(i=0;ir;i+)printf(%c: ,sti0);for(j=0;jfirsti0;j+)printf(%c ,firstij+1);printf(n);printf(每個(gè)非終結(jié)符的lastvt集為：n); /輸出每個(gè)非終結(jié)符的lastvt集for(i=0;ir;i+)printf(%c: ,sti0);for(j=0;jlasti0;j+)printf(%c ,lastij+1);printf(n);printf(算符優(yōu)先分析

22、表如下:n);for(i=0;lablei!=0;i+) printf(t%c,lablei);printf(n); for(i=0;ik+1;i+)printf(%ct,lablei);for(j=0;jk+1;j+)printf(%ct,dataij);printf(n);printf(請輸入文法輸入符號(hào)串以#結(jié)束:);scanf(%s,input); deal();cout逆波蘭式為：;for(i=0;lablei!=0;i+) coutshuchui0;/coutendl;void table()char text2010;/存儲(chǔ)改寫后的文法int i,j,k,t,l,x=0,y=0;

23、int m,n;x=0;for(i=0;ir;i+)firstvt(sti0);lastvt(sti0);for(i=0;i;elsetextxy=stij;y+;textxy=0;x+;y=0;r1=x;/printf(轉(zhuǎn)化后的文法為:n);for(i=0;ix;i+) /輸出轉(zhuǎn)化后的文法規(guī)則串printf(%sn,texti);for(i=0;i后的轉(zhuǎn)化文法，用于最后的規(guī)約)*/stringi0=texti0;for(j=3,l=1;textij!=0;j+,l+)stringil=textij;stringil=0;for(i=0;ix;i+)for(j=1;textij+1!=0;j+

24、)if(zhongjie(textij)&zhongjie(textij+1)m=xiabiao(textij);n=xiabiao(textij+1);datamn=;if(textij+2!=0&zhongjie(textij)&zhongjie(textij+2)&!zhongjie(textij+1)m=xiabiao(textij);n=xiabiao(textij+2);datamn=;if(zhongjie(textij)&!zhongjie(textij+1)/終結(jié)符和非終結(jié)符相接，用后于關(guān)系填表for(k=0;kr;k+)if(stk0=textij+1)break;m=xi

25、abiao(textij);for(t=0;tfirstk0;t+)n=xiabiao(firstkt+1);datamn=;if(!zhongjie(textij)&zhongjie(textij+1)/非終結(jié)符和終結(jié)符相接，用先于關(guān)系填表for(k=0;kr;k+)if(stk0=textij)break;n=xiabiao(textij+1);for(t=0;t;m=xiabiao(#);/#后于所有的終結(jié)符規(guī)約for(t=0;tfirst00;t+)n=xiabiao(first0t+1);datamn=;n=xiabiao(#);/for(t=0;t;datann=;void fir

26、stvt(char c) /求firstvt集int i,j,k,m,n;for(i=0;ir;i+)/找出是第i個(gè)非終結(jié)符if(sti0=c)break;if(fflagi=0)n=firsti0+1;m=0;doif(m=2|stim=|)if(zhongjie(stim+1)firstin=stim+1;n+;elseif(zhongjie(stim+2)firstin=stim+2;n+;if(stim+1!=c)firstvt(stim+1);for(j=0;jr;j+)if(stj0=stim+1)break;for(k=0;kfirstj0;k+)int t;for(t=0;tn

27、;t+)if(firstit=firstjk+1)break;if(t=n)firstin=firstjk+1;n+;m+;while(stim!=0);firstin=0;firsti0=-n;fflagi=1;void lastvt(char c) /求lastvt集int i,j,k,m,n;for(i=0;ir;i+)if(sti0=c)break;if(lflagi=0)n=lasti0+1;m=0;doif(stim+1=0|stim+1=|)if(zhongjie(stim)lastin=stim;n+;elseif(zhongjie(stim-1)lastin=stim-1;n+;if(stim!=c)lastvt(stim);for(j=0;jr;j+)if(stj0=stim)break;for(k=0;klastj0;k+)int t;for(t=0;t)if(lablex!=) shuchusize+=lablex;/將要規(guī)約的終結(jié)符存起來out(1,k,s);printf(%c,a);out(i+1,z,input);printf(規(guī)約n);doq=sj;if(zhongjie(sj-1)j=j-1;else j=j-2;x=xiabiao(sj);y=xiabiao(q);while