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

1、<p><b>　　課程設(shè)計(jì)任務(wù)書</b></p><p>　　學(xué)生姓名： 專業(yè)班級(jí)： </p><p>　　指導(dǎo)教師： 工作單位： </p><p>　　題 目: 算術(shù)表達(dá)式的語法分析及語義分析程序設(shè)計(jì)</p>

2、;<p><b>　　1．目的</b></p><p>　　通過設(shè)計(jì)、編制、調(diào)試一個(gè)算術(shù)表達(dá)式的語法及語義分析程序，加深對(duì)語法及語義分析原理的理解，并實(shí)現(xiàn)詞法分析程序?qū)卧~序列的詞法檢查和分析。</p><p><b>　　2．設(shè)計(jì)內(nèi)容及要求</b></p><p><b>　　算術(shù)表達(dá)式的文法：&

3、lt;/b></p><p>　　選擇算符優(yōu)先分析法完成以上任務(wù)，中間代碼選用逆波蘭式。</p><p>　　寫出算術(shù)表達(dá)式的符合分析方法要求的文法，給出分析方法的思想，完成分析程序設(shè)計(jì)。</p><p>　　編制好分析程序后，設(shè)計(jì)若干用例，上機(jī)測(cè)試并通過所設(shè)計(jì)的分析程序。</p><p>　　3.課程設(shè)計(jì)報(bào)告書的內(nèi)容應(yīng)包括：</

4、p><p>　　（1）設(shè)計(jì)題目、班級(jí)、學(xué)號(hào)、姓名、完成日期；</p><p>　?。?）給出算術(shù)表達(dá)式的語法分析和語義分析的設(shè)計(jì)。</p><p>　?。?）簡(jiǎn)要的分析與概要設(shè)計(jì)；</p><p>　?。?）詳細(xì)的算法描述；</p><p><b>　?。?）源程序清單；</b></p>

5、<p>　?。?）給出軟件的測(cè)試方法和測(cè)試結(jié)果；</p><p>　?。?）設(shè)計(jì)的評(píng)價(jià)、收獲與體會(huì)。</p><p><b>　　時(shí)間安排：</b></p><p>　　第18周，周1-周3下午，周5全天</p><p>　　指導(dǎo)教師簽名： 年 月 日&

6、lt;/p><p>　　系主任（或責(zé)任教師）簽名： 年 月 日</p><p><b>　　1 課設(shè)要求</b></p><p>　　設(shè)計(jì)題目 算術(shù)表達(dá)式轉(zhuǎn)換成逆波蘭式（用算符優(yōu)先分析法）</p><p>　　1.1課程設(shè)計(jì)的目的</p><p>　　課程設(shè)計(jì)是對(duì)學(xué)生的

7、一種全面綜合訓(xùn)練，是與課堂聽講、自學(xué)和練習(xí)相輔相成的必不可少的一個(gè)教學(xué)環(huán)節(jié)。通常，設(shè)計(jì)題中的問題比平時(shí)的練習(xí)題要復(fù)雜，也更接近實(shí)際。編譯原理這門課程安排的課程設(shè)計(jì)的目的是旨在要求學(xué)生進(jìn)一步鞏固課堂上所學(xué)的理論知識(shí)，深化理解和靈活掌握教學(xué)內(nèi)容，選擇合適的數(shù)據(jù)邏輯結(jié)構(gòu)表示問題，然后編制算法和程序完成設(shè)計(jì)要求，從而進(jìn)一步培養(yǎng)學(xué)生獨(dú)立思考問題、分析問題、解決實(shí)際問題的動(dòng)手能力。 </p><p>　　要求學(xué)生在上機(jī)

8、前應(yīng)認(rèn)真做好各種準(zhǔn)備工作，熟悉機(jī)器的操作系統(tǒng)和語言的集成環(huán)境，獨(dú)立完成算法編制和程序代碼的編寫。</p><p>　　1.2 設(shè)計(jì)內(nèi)容及要求</p><p><b>　　算術(shù)表達(dá)式的文法：</b></p><p>　　〈無符號(hào)整數(shù)〉∷＝ 〈數(shù)字〉{〈數(shù)字〉}</p><p>　　〈標(biāo)志符〉∷＝ 〈字母〉{〈字母〉｜〈數(shù)字

9、〉}</p><p>　　〈表達(dá)式〉∷＝ [＋｜－]〈項(xiàng)〉{〈加法運(yùn)算符〉〈項(xiàng)〉}</p><p>　　〈項(xiàng)〉∷＝ 〈因子〉{〈乘法運(yùn)算符〉〈因子〉}</p><p>　　〈因子〉∷＝ 〈標(biāo)志符〉｜〈無符號(hào)整數(shù)〉｜‘（’〈表達(dá)式〉‘）’</p><p>　　〈加法運(yùn)算符〉∷＝ ＋｜－</p><p>　　〈乘法運(yùn)算符〉

10、∷＝ ＊｜／</p><p>　　1.選擇算符優(yōu)先分析法完成以上任務(wù)，中間代碼選用逆波蘭式。</p><p>　　2.寫出算術(shù)表達(dá)式的符合分析方法要求的文法，給出分析方法的思想，3.完成分析程序設(shè)計(jì)。</p><p>　　編制好分析程序后，設(shè)計(jì)若干用例，上機(jī)測(cè)試并通過所設(shè)計(jì)的分析程序。</p><p><b>　　2 摘要</

11、b></p><p>　　一個(gè)新的語言的出現(xiàn)，必然會(huì)有與之配套的編譯器的產(chǎn)生。編譯器對(duì)于一個(gè)語言的重要性不言而喻。編譯過程分為詞法分析、語法分析、語義分析、中間代碼生成、代碼優(yōu)化和目標(biāo)代碼生成這六個(gè)階段。而語法分析和語義分析是最關(guān)鍵的核心部分。要做好一個(gè)編譯器必須要懂得如何根據(jù)構(gòu)造的文法來識(shí)別出它的語法和語義。語法分析的方法很多，而比較容易懂的就有算符優(yōu)先分析法，本次課設(shè)的主題就是要弄懂算符優(yōu)先分析發(fā)。&l

12、t;/p><p>　　學(xué)習(xí)制作編譯器不僅會(huì)讓你弄懂這門課，還會(huì)讓你提高寫代碼的能力，特別是寫出高效，可靠性好的代碼。</p><p>　　關(guān)鍵字：算術(shù)表達(dá)式，算符優(yōu)先文法，逆波蘭式</p><p><b>　　3 引言</b></p><p>　　逆波蘭式又叫做后綴表達(dá)式，它的用途很多，譬如做計(jì)算器的時(shí)候可以對(duì)算術(shù)表達(dá)式采用

13、這種形式來表示，從而可以很容易的來進(jìn)行計(jì)算。在編譯原理中，生成中間代碼的步驟里，逆波蘭式也是中間代碼的一種表示形式。</p><p>　　算符優(yōu)先分析法是自底向上進(jìn)行語法分析的一種方式。自底向上分析的思想就是對(duì)輸入的符號(hào)串自左向右的進(jìn)行掃描，并將輸入符逐個(gè)移入一個(gè)后進(jìn)先出棧，邊移入邊分析，一旦棧頂符號(hào)串形成某個(gè)句型的句柄或可規(guī)約串時(shí)，就用該產(chǎn)生式左部的非終結(jié)符代替相應(yīng)右部的文法符號(hào)串，這一步叫做規(guī)約。重復(fù)這一過程

14、直到規(guī)約到棧中只剩文法的開始符號(hào)時(shí)則規(guī)約成功，也就確認(rèn)了這個(gè)輸入串是文法的句子。算符優(yōu)先法規(guī)定了算符之間的優(yōu)先關(guān)系，通過先于關(guān)系識(shí)別句柄尾，通過后于關(guān)系識(shí)別句柄頭，以此來進(jìn)行規(guī)約。</p><p><b>　　4 正文</b></p><p><b>　　4.1 需求分析</b></p><p>　　要通過算符優(yōu)先分析方法

15、進(jìn)行將算術(shù)表達(dá)式轉(zhuǎn)換成為逆波蘭式，首先要經(jīng)過詞法分析，然后是語法分析，通過規(guī)約來輸出算術(shù)表達(dá)式的逆波蘭式。故先要求出每個(gè)非終結(jié)符的FIRSTVT()集和LASTVT()集，然后求出終結(jié)符的算符優(yōu)先矩陣，最后以此來規(guī)約。因此程序應(yīng)該能夠提供輸入一個(gè)任意的算符優(yōu)先文法，并可以對(duì)輸入的文法進(jìn)行判斷，還可以對(duì)文法進(jìn)行改寫，便于后面的分析。自動(dòng)求出每個(gè)非終結(jié)符的FIRSTVT()集和LASTVT()集，自動(dòng)構(gòu)造終結(jié)符的優(yōu)先矩陣，然后自動(dòng)規(guī)約，輸出

16、逆波蘭式。</p><p><b>　　4.2 理論基礎(chǔ)</b></p><p>　　算符優(yōu)先分析法是自底向上分析法法的一種，它的工作原理是先求出文法中每個(gè)非終結(jié)符的FIRSTVT()集和LASTVT()集，通過文法中每個(gè)產(chǎn)生式的右部非終結(jié)符所處的位置來確定每個(gè)非終結(jié)符之間的優(yōu)先關(guān)系。譬如S->AaB，則a后于A的LASTVT()集規(guī)約，也后于A的FIRSTVT

17、()集規(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)，即為所求的逆波蘭式。</p><p><b>　　4.3 總體設(shè)計(jì)</b></p><p>　　先改寫文法，在求各個(gè)非終結(jié)符的F

18、IRSTVT()集和LASTVT()集，確定優(yōu)先關(guān)系矩陣后就進(jìn)行規(guī)約。</p><p><b>　　系統(tǒng)流程圖如下：</b></p><p>　　所要用到的數(shù)據(jù)結(jié)構(gòu)及自定義函數(shù)如下：</p><p>　　char data[20][20]; //算符優(yōu)先關(guān)系</p><p>　　ch

19、ar s[100]; //模擬符號(hào)棧s </p><p>　　char lable[20]; //文法終極符集</p><p>　　char input[100]; //文法輸入符號(hào)串</p><p>　　char string[2

20、0][10]; //用于輸入串的分析</p><p>　　int k; </p><p><b>　　char a; </b></p><p>　　int j;

21、 </p><p>　　char q; </p><p>　　int r; //文法規(guī)則個(gè)數(shù)</p><p><b>　　int r1; </b></p>

22、<p>　　int m,n,N; //轉(zhuǎn)化后文法規(guī)則個(gè)數(shù)</p><p>　　char st[10][30]; //用來存儲(chǔ)文法規(guī)則</p><p>　　char first[10][10]; //文法非終結(jié)符FIRSTVT集</p>

23、<p>　　char last[10][10]; //文法非終結(jié)符LASTVT集</p><p>　　int fflag[10]={0}; //標(biāo)志第i個(gè)非終結(jié)符的FIRSTVT集是否已求出</p><p>　　int lflag[10]={0}; //標(biāo)志第i個(gè)非

24、終結(jié)符的LASTVT集是否已求出</p><p>　　int deal(); //對(duì)輸入串的分析</p><p>　　int zhongjie(char c); //判斷字符c是否是終極符</p><p>　　int xiabiao(char c); //

25、求字符c在算符優(yōu)先關(guān)系表中的下標(biāo)</p><p>　　void out(int j,int k,char *s); //打印s棧</p><p>　　void firstvt(char c); //求非終結(jié)符c的FIRSTVT集</p><p>　　void lastvt(char c); /

26、/求非終結(jié)符c的LASTVT集</p><p>　　void table(); //創(chuàng)建文法優(yōu)先關(guān)系表</p><p>　　char shuchu[10];//存儲(chǔ)逆波蘭式</p><p><b>　　4.4 詳細(xì)設(shè)計(jì)</b></p><p>　　4.4.1 判斷文法是否正確

27、</p><p>　　要對(duì)輸入的文法進(jìn)行判斷是否為算符文法。首先判斷文法是否為上下文無關(guān)文法，然后判斷是否為算符文法。判斷的過程比較簡(jiǎn)單，先看每個(gè)產(chǎn)生式的左部是否為非終結(jié)符（在這里人為規(guī)定大寫字母表示非終結(jié)符，且不用進(jìn)行判斷），然后看產(chǎn)生式的右部是否有兩個(gè)非終結(jié)符挨在一起的，若挨在一起，則不是算符文法，否則就是算符文法。</p><p>　　4.4.2 改寫文法</p>&l

28、t;p>　　若產(chǎn)生式的右部有形如S->A+B|A-B的產(chǎn)生式，則應(yīng)該改寫為兩條產(chǎn)生式：(1)S->A+B；(2)S->A-B；按此方式對(duì)文法改寫后輸出到屏幕上。</p><p>　　4.4.3求每個(gè)非終結(jié)符的FIRSTVT()集和LASTVT()集</p><p>　　對(duì)FIRSTVT()集的構(gòu)造可以根據(jù)以下兩條規(guī)則構(gòu)造：</p><p>　

29、　(1)若有產(chǎn)生式A->Ba...或A->a...，則a屬于FIRSTVT(A)；</p><p>　　(2)若a屬于FIRSTVT(B)且有產(chǎn)生式A->B...則有a屬于FIRSTVT(A)</p><p><b>　　部分代碼如下：</b></p><p>　　if(fflag[i]==0)</p><

30、p><b>　　{</b></p><p>　　n=first[i][0]+1;</p><p><b>　　m=0;</b></p><p><b>　　do</b></p><p><b>　　{</b></p><p>

31、　　if(m==2||st[i][m]=='|')</p><p><b>　　{</b></p><p>　　if(zhongjie(st[i][m+1]))</p><p><b>　　{</b></p><p>　　first[i][n]=st[i][m+1];</p&g

32、t;<p><b>　　n++;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　if(zhongjie(st[i][m+2]))<

33、;/p><p><b>　　{</b></p><p>　　first[i][n]=st[i][m+2];</p><p><b>　　n++;</b></p><p><b>　　}</b></p><p>　　if(st[i][m+1]!=c)</

34、p><p><b>　　{</b></p><p>　　firstvt(st[i][m+1]);</p><p>　　for(j=0;j<r;j++)</p><p><b>　　{</b></p><p>　　if(st[j][0]==st[i][m+1])</p&

35、gt;<p><b>　　break;</b></p><p><b>　　}</b></p><p>　　for(k=0;k<first[j][0];k++)</p><p><b>　　{</b></p><p><b>　　int t;<

36、;/b></p><p>　　for(t=0;t<n;t++)</p><p><b>　　{</b></p><p>　　if(first[i][t]==first[j][k+1])</p><p><b>　　break;</b></p><p><b&

37、gt;　　}</b></p><p><b>　　if(t==n)</b></p><p><b>　　{</b></p><p>　　first[i][n]=first[j][k+1];</p><p><b>　　n++;</b></p><

38、p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>

39、<b>　　m++;</b></p><p>　　}while(st[i][m]!='\0');</p><p>　　first[i][n]='\0';</p><p>　　first[i][0]=--n;</p><p>　　fflag[i]=1;</p><p>

40、;　　同樣LASTVT()集也可以按照類似的方式構(gòu)造。</p><p>　　4.4.4 求算符優(yōu)先矩陣</p><p>　　構(gòu)造算符優(yōu)先關(guān)系表。算符優(yōu)先矩陣在本程序中的作用是最大的，算符優(yōu)先關(guān)系表是一個(gè)二維數(shù)組，用來存放任意兩個(gè)終結(jié)符之間的優(yōu)先關(guān)系。首先構(gòu)造表頭，通過掃描所有產(chǎn)生式將終結(jié)符不重復(fù)的存放在一個(gè)一維數(shù)組中并置為優(yōu)先關(guān)系表的行和列，并將優(yōu)先關(guān)系表其他內(nèi)容全部初始化為空。接著遍歷所

41、有產(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)的行列對(duì)應(yīng)的單元中。</p><p><b>　　部分代碼如下：</b></p><p>　　for(i=0;i<x;i++)</p><p><b

42、>　　{</b></p><p>　　for(j=1;text[i][j+1]!='\0';j++)</p><p><b>　　{</b></p><p>　　if(zhongjie(text[i][j])&&zhongjie(text[i][j+1]))</p><p&g

43、t;<b>　　{</b></p><p>　　m=xiabiao(text[i][j]);</p><p>　　n=xiabiao(text[i][j+1]);</p><p>　　data[m][n]='=';</p><p><b>　　}</b></p><

44、;p>　　if(text[i][j+2]!='\0'&&zhongjie(text[i][j])&&zhongjie(text[i][j+2])&&!zhongjie(text[i][j+1]))</p><p><b>　　{</b></p><p>　　m=xiabiao(text[i][j])

45、;</p><p>　　n=xiabiao(text[i][j+2]);</p><p>　　data[m][n]='=';</p><p><b>　　}</b></p><p>　　if(zhongjie(text[i][j])&&!zhongjie(text[i][j+1]))//終

46、結(jié)符和非終結(jié)符相接，用后于關(guān)系填表</p><p><b>　　{</b></p><p>　　for(k=0;k<r;k++)</p><p><b>　　{</b></p><p>　　if(st[k][0]==text[i][j+1])</p><p><b

47、>　　break;</b></p><p><b>　　}</b></p><p>　　m=xiabiao(text[i][j]);</p><p>　　for(t=0;t<first[k][0];t++)</p><p><b>　　{</b></p><

48、;p>　　n=xiabiao(first[k][t+1]);</p><p>　　data[m][n]='<';</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　if(!zhongjie(text[i][j])&

49、&zhongjie(text[i][j+1]))//非終結(jié)符和終結(jié)符相接，用先于關(guān)系填表</p><p><b>　　{</b></p><p>　　for(k=0;k<r;k++)</p><p><b>　　{</b></p><p>　　if(st[k][0]==text[i][

50、j])</p><p><b>　　break;</b></p><p><b>　　}</b></p><p>　　n=xiabiao(text[i][j+1]);</p><p>　　for(t=0;t<last[k][0];t++)</p><p><b&g

51、t;　　{</b></p><p>　　m=xiabiao(last[k][t+1]);</p><p>　　data[m][n]='>';</p><p><b>　　}</b></p><p><b>　　}</b></p><p>&l

52、t;b>　　}</b></p><p>　　4.4.5 輸出逆波蘭式</p><p>　　要想在規(guī)約的時(shí)候輸出算術(shù)表達(dá)式的逆波蘭式，確定規(guī)約的終結(jié)符后，用一個(gè)字符數(shù)組將這些終結(jié)符存起來，在規(guī)約成功輸出這些字符串即為所求的逆波蘭式</p><p><b>　　部分代碼如下：</b></p><p>　　i

53、f(data[x][y]=='>')</p><p><b>　　{</b></p><p>　　if(lable[x]!=')')</p><p>　　shuchu[size++]=lable[x];//將要規(guī)約的終結(jié)符存起來</p><p>　　out(1,k,s);</

54、p><p>　　printf("%c",a);</p><p>　　out(i+1,z,input);</p><p>　　printf("規(guī)約\n");</p><p><b>　　5 調(diào)試及運(yùn)行結(jié)果</b></p><p><b>　　更換文法后：

55、</b></p><p><b>　　6 心得體會(huì)</b></p><p>　　本次課程設(shè)計(jì)相對(duì)來來說不是很容易的，它的要求比較高，要將編譯原理中所學(xué)的很多知識(shí)聯(lián)系起來，并且要有比較良好的編程能力。</p><p>　　一開始看到題目的時(shí)候我也是沒什么頭緒，理不清思路，不明白為什么將算術(shù)表達(dá)式轉(zhuǎn)換為逆波蘭式與算符優(yōu)先分析法有何種聯(lián)系

56、。沒辦法，我只好在書本中尋找靈感，在看到確定了算符優(yōu)先矩陣之后，每一步規(guī)約的終結(jié)符按先后順序連接起來剛好是逆波蘭式。按照這個(gè)想法，我開始有了大概的規(guī)劃，然后照著這個(gè)想法去做，終于做好了。</p><p>　　課程設(shè)計(jì)與一般的實(shí)驗(yàn)不同，與在課堂上學(xué)習(xí)理論知識(shí)更加不同，它是考查學(xué)習(xí)成果的一種手段，更加是檢驗(yàn)?zāi)愕哪芰退降囊环N方式。將理論與實(shí)踐結(jié)合起來才是王道。</p><p>　　當(dāng)然，我的

57、程序也存在著不足，沒有進(jìn)行詞法分析，只是簡(jiǎn)單的默認(rèn)了所輸入的符號(hào)串都符合規(guī)定。</p><p>　　通過本次課程設(shè)計(jì)，不僅加強(qiáng)了我對(duì)編譯原理的認(rèn)識(shí)，掌握了很多知識(shí)，更加讓我明白了動(dòng)手能力的重要性。在未來學(xué)習(xí)的道路上，應(yīng)該繼續(xù)發(fā)揚(yáng)這種精神，將實(shí)踐進(jìn)行到底！</p><p><b>　　7 源代碼</b></p><p>　　#include &q

58、uot;stdio.h"</p><p>　　#include "stdlib.h"</p><p>　　#include "iostream.h"</p><p>　　char data[20][20]; //算符優(yōu)先關(guān)系</p><p>　　char

59、s[100]; //模擬符號(hào)棧s </p><p>　　char lable[20]; //文法終極符集</p><p>　　char input[100]; //文法輸入符號(hào)串</p><p>　　char string[20][

60、10]; //用于輸入串的分析</p><p>　　int k; </p><p><b>　　char a; </b></p><p>　　int j;

61、 </p><p>　　char q; </p><p>　　int r; //文法規(guī)則個(gè)數(shù)</p><p><b>　　int r1; </b></p><

62、;p>　　int m,n,N; //轉(zhuǎn)化后文法規(guī)則個(gè)數(shù)</p><p>　　char st[10][30]; //用來存儲(chǔ)文法規(guī)則</p><p>　　char first[10][10]; //文法非終結(jié)符FIRSTVT集</p>&

63、lt;p>　　char last[10][10]; //文法非終結(jié)符LASTVT集</p><p>　　int fflag[10]={0}; //標(biāo)志第i個(gè)非終結(jié)符的FIRSTVT集是否已求出</p><p>　　int lflag[10]={0}; //標(biāo)志第i個(gè)非終結(jié)符

64、的LASTVT集是否已求出</p><p>　　int deal(); //對(duì)輸入串的分析</p><p>　　int zhongjie(char c); //判斷字符c是否是終極符</p><p>　　int xiabiao(char c); //求字符

65、c在算符優(yōu)先關(guān)系表中的下標(biāo)</p><p>　　void out(int j,int k,char *s); //打印s棧</p><p>　　void firstvt(char c); //求非終結(jié)符c的FIRSTVT集</p><p>　　void lastvt(char c); //求非

66、終結(jié)符c的LASTVT集</p><p>　　void table(); //創(chuàng)建文法優(yōu)先關(guān)系表</p><p>　　char shuchu[10];//存儲(chǔ)逆波蘭式</p><p>　　void main()</p><p><b>　　{</b></p>&

67、lt;p>　　int i,j,k=0;</p><p>　　printf("請(qǐng)輸入文法規(guī)則數(shù)：");</p><p>　　scanf("%d",&r);</p><p>　　printf("請(qǐng)輸入文法規(guī)則：\n");</p><p>　　for(i=0;i<r;i

68、++)</p><p><b>　　{</b></p><p>　　scanf("%s",st[i]); //存儲(chǔ)文法規(guī)則，初始化FIRSTVT集和LASTVT集*/ </p><p>　　first[i][0]=0; /*first[i][0]和last[i][0]分別表示st[i

69、][0]非終極符的FIRSTVT集和LASTVT集中元素的個(gè)數(shù)*/</p><p>　　last[i][0]=0;</p><p><b>　　}</b></p><p>　　for(i=0;i<r;i++) //判斷文法是否合法</p><p><b>

70、;　　{</b></p><p>　　for(j=0;st[i][j]!='\0';j++)</p><p><b>　　{</b></p><p>　　if(st[i][0]<'A'||st[i][0]>'Z')</p><p><b>

71、　　{</b></p><p>　　printf("不是算符文法!\n");</p><p><b>　　exit(-1);</b></p><p><b>　　}</b></p><p>　　if(st[i][j]>='A'&&

72、st[i][j]<='Z')</p><p><b>　　{</b></p><p>　　if(st[i][j+1]>='A'&&st[i][j+1]<='Z')</p><p><b>　　{</b></p><p>

73、;　　printf("不是算符文法!\n");</p><p><b>　　exit(-1);</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p&

74、gt;<p><b>　　}</b></p><p>　　for(i=0;i<r;i++)//</p><p><b>　　{</b></p><p>　　for(j=0;st[i][j]!='\0';j++)</p><p><b>　　{</b

75、></p><p>　　if((st[i][j]<'A'||st[i][j]>'Z')&&st[i][j]!='-'&&st[i][j]!='>'&&st[i][j]!='|')</p><p>　　lable[k++]=st[i][j];

76、</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　lable[k]='#';</p><p>　　lable[k+1]='\0'; </p><p>　　table();//</p&g

77、t;<p>　　printf("每個(gè)非終結(jié)符的FIRSTVT集為：\n"); //輸出每個(gè)非終結(jié)符的FIRSTVT集</p><p>　　for(i=0;i<r;i++)</p><p><b>　　{</b></p><p>　　printf("%c: ",st[i][0]);

78、</p><p>　　for(j=0;j<first[i][0];j++)</p><p><b>　　{</b></p><p>　　printf("%c ",first[i][j+1]);</p><p><b>　　}</b></p><p>

79、　　printf("\n");</p><p><b>　　}</b></p><p>　　printf("每個(gè)非終結(jié)符的LASTVT集為：\n"); //輸出每個(gè)非終結(jié)符的LASTVT集</p><p>　　for(i=0;i<r;i++)</p><p><b

80、>　　{</b></p><p>　　printf("%c: ",st[i][0]);</p><p>　　for(j=0;j<last[i][0];j++)</p><p><b>　　{</b></p><p>　　printf("%c ",last[i

81、][j+1]);</p><p><b>　　}</b></p><p>　　printf("\n");</p><p><b>　　}</b></p><p>　　printf("算符優(yōu)先分析表如下:\n");</p><p>　　f

82、or(i=0;lable[i]!='\0';i++) </p><p>　　printf("\t%c",lable[i]);</p><p>　　printf("\n"); </p><p>　　for(

83、i=0;i<k+1;i++)</p><p><b>　　{</b></p><p>　　printf("%c\t",lable[i]);</p><p>　　for(j=0;j<k+1;j++)</p><p><b>　　{</b></p><

84、p>　　printf("%c\t",data[i][j]);</p><p><b>　　}</b></p><p>　　printf("\n");</p><p><b>　　}</b></p><p>　　printf("請(qǐng)輸入文法輸入符號(hào)

85、串以#結(jié)束:");</p><p>　　scanf("%s",input); </p><p><b>　　deal();</b></p><p>　　cout<<"逆波蘭式為：";</p>

86、<p>　　for(i=0;lable[i]!='\0';i++) </p><p>　　cout<<shuchu[i]<<'\0';//</p><p>　　cout<<endl;</p><p><b>　　}</b></p><p>

87、　　void table()</p><p><b>　　{</b></p><p>　　char text[20][10];//存儲(chǔ)改寫后的文法</p><p>　　int i,j,k,t,l,x=0,y=0;</p><p><b>　　int m,n;</b></p><p

88、><b>　　x=0;</b></p><p>　　for(i=0;i<r;i++)</p><p><b>　　{</b></p><p>　　firstvt(st[i][0]);</p><p>　　lastvt(st[i][0]);</p><p><

89、b>　　}</b></p><p>　　for(i=0;i<r;i++)//改寫文法</p><p><b>　　{</b></p><p>　　text[x][y]=st[i][0];</p><p><b>　　y++;</b></p><p>　

90、　for(j=1;st[i][j]!='\0';j++)</p><p><b>　　{</b></p><p>　　if(st[i][j]=='|')//</p><p><b>　　{</b></p><p>　　text[x][y]='\0';&

91、lt;/p><p><b>　　x++;</b></p><p><b>　　y=0;</b></p><p>　　text[x][y]=st[i][0];</p><p><b>　　y++;</b></p><p>　　text[x][y++]='

92、;-';</p><p>　　text[x][y++]='>';</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　text[x

93、][y]=st[i][j];</p><p><b>　　y++;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　text[x][y]='\0';</p><p><b&

94、gt;　　x++;</b></p><p><b>　　y=0;</b></p><p><b>　　}</b></p><p><b>　　r1=x;//</b></p><p>　　printf("轉(zhuǎn)化后的文法為:\n");</p>

95、;<p>　　for(i=0;i<x;i++) //輸出轉(zhuǎn)化后的文法規(guī)則串</p><p><b>　　{</b></p><p>　　printf("%s\n",text[i]);</p><p><b>　　}</b&g

96、t;</p><p>　　for(i=0;i<x;i++) /*求每個(gè)終結(jié)符的推導(dǎo)結(jié)果(去掉"->"后的轉(zhuǎn)化文法，用于最后的規(guī)約)*/</p><p><b>　　{</b></p><p>　　string[i][0]=text[i][0];</p>

97、<p>　　for(j=3,l=1;text[i][j]!='\0';j++,l++)</p><p>　　string[i][l]=text[i][j];</p><p>　　string[i][l]='\0';</p><p><b>　　}</b></p><p>　　f

98、or(i=0;i<x;i++)</p><p><b>　　{</b></p><p>　　for(j=1;text[i][j+1]!='\0';j++)</p><p><b>　　{</b></p><p>　　if(zhongjie(text[i][j])&&am

99、p;zhongjie(text[i][j+1]))</p><p><b>　　{</b></p><p>　　m=xiabiao(text[i][j]);</p><p>　　n=xiabiao(text[i][j+1]);</p><p>　　data[m][n]='=';</p>&l

100、t;p><b>　　}</b></p><p>　　if(text[i][j+2]!='\0'&&zhongjie(text[i][j])&&zhongjie(text[i][j+2])&&!zhongjie(text[i][j+1]))</p><p><b>　　{</b>

101、</p><p>　　m=xiabiao(text[i][j]);</p><p>　　n=xiabiao(text[i][j+2]);</p><p>　　data[m][n]='=';</p><p><b>　　}</b></p><p>　　if(zhongjie(text

102、[i][j])&&!zhongjie(text[i][j+1]))//終結(jié)符和非終結(jié)符相接，用后于關(guān)系填表</p><p><b>　　{</b></p><p>　　for(k=0;k<r;k++)</p><p><b>　　{</b></p><p>　　if(st[k]

103、[0]==text[i][j+1])</p><p><b>　　break;</b></p><p><b>　　}</b></p><p>　　m=xiabiao(text[i][j]);</p><p>　　for(t=0;t<first[k][0];t++)</p>&l

104、t;p><b>　　{</b></p><p>　　n=xiabiao(first[k][t+1]);</p><p>　　data[m][n]='<';</p><p><b>　　}</b></p><p><b>　　}</b></p&g

105、t;<p>　　if(!zhongjie(text[i][j])&&zhongjie(text[i][j+1]))//非終結(jié)符和終結(jié)符相接，用先于關(guān)系填表</p><p><b>　　{</b></p><p>　　for(k=0;k<r;k++)</p><p><b>　　{</b>

106、</p><p>　　if(st[k][0]==text[i][j])</p><p><b>　　break;</b></p><p><b>　　}</b></p><p>　　n=xiabiao(text[i][j+1]);</p><p>　　for(t=0;t<

107、;last[k][0];t++)</p><p><b>　　{</b></p><p>　　m=xiabiao(last[k][t+1]);</p><p>　　data[m][n]='>';</p><p><b>　　}</b></p><p>&

108、lt;b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　m=xiabiao('#');//#后于所有的終結(jié)符規(guī)約</p><p>　　for(t=0;t<first[0][0];t++)&l

109、t;/p><p><b>　　{</b></p><p>　　n=xiabiao(first[0][t+1]);</p><p>　　data[m][n]='<';</p><p><b>　　}</b></p><p>　　n=xiabiao('#

110、');//</p><p>　　for(t=0;t<last[0][0];t++)</p><p><b>　　{</b></p><p>　　m=xiabiao(last[0][t+1]);</p><p>　　data[m][n]='>';</p><p>

111、<b>　　}</b></p><p>　　data[n][n]='=';</p><p><b>　　}</b></p><p>　　void firstvt(char c) //求FIRSTVT集</p><

112、p><b>　　{</b></p><p>　　int i,j,k,m,n;</p><p>　　for(i=0;i<r;i++)//找出是第i個(gè)非終結(jié)符</p><p><b>　　{</b></p><p>　　if(st[i][0]==c)</p><p>

113、<b>　　break;</b></p><p><b>　　}</b></p><p>　　if(fflag[i]==0)</p><p><b>　　{</b></p><p>　　n=first[i][0]+1;</p><p><b>

114、　　m=0;</b></p><p><b>　　do</b></p><p><b>　　{</b></p><p>　　if(m==2||st[i][m]=='|')</p><p><b>　　{</b></p><p>

115、;　　if(zhongjie(st[i][m+1]))</p><p><b>　　{</b></p><p>　　first[i][n]=st[i][m+1];</p><p><b>　　n++;</b></p><p><b>　　}</b></p><

116、;p><b>　　else</b></p><p><b>　　{</b></p><p>　　if(zhongjie(st[i][m+2]))</p><p><b>　　{</b></p><p>　　first[i][n]=st[i][m+2];</p>

117、<p><b>　　n++;</b></p><p><b>　　}</b></p><p>　　if(st[i][m+1]!=c)</p><p><b>　　{</b></p><p>　　firstvt(st[i][m+1]);</p><

118、;p>　　for(j=0;j<r;j++)</p><p><b>　　{</b></p><p>　　if(st[j][0]==st[i][m+1])</p><p><b>　　break;</b></p><p><b>　　}</b></p>

119、<p>　　for(k=0;k<first[j][0];k++)</p><p><b>　　{</b></p><p><b>　　int t;</b></p><p>　　for(t=0;t<n;t++)</p><p><b>　　{</b><

120、/p><p>　　if(first[i][t]==first[j][k+1])</p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　if(t==n)</b></p><p><b>

121、　　{</b></p><p>　　first[i][n]=first[j][k+1];</p><p><b>　　n++;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b

122、>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　m++;</b></p><p>　　}while(st[i][m]!='\0');</p><p

123、>　　first[i][n]='\0';</p><p>　　first[i][0]=--n;</p><p>　　fflag[i]=1;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void la

124、stvt(char c) //求LASTVT集</p><p><b>　　{</b></p><p>　　int i,j,k,m,n;</p><p>　　for(i=0;i<r;i++)</p><p><b>　　{<

125、;/b></p><p>　　if(st[i][0]==c)</p><p><b>　　break;</b></p><p><b>　　}</b></p><p>　　if(lflag[i]==0)</p><p><b>　　{</b><

126、;/p><p>　　n=last[i][0]+1;</p><p><b>　　m=0;</b></p><p><b>　　do</b></p><p><b>　　{</b></p><p>　　if(st[i][m+1]=='\0'||

127、st[i][m+1]=='|')</p><p><b>　　{</b></p><p>　　if(zhongjie(st[i][m]))</p><p><b>　　{</b></p><p>　　last[i][n]=st[i][m];</p><p>&

128、lt;b>　　n++;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　if(zhongjie(st[i][m-1]))</p><p

129、><b>　　{</b></p><p>　　last[i][n]=st[i][m-1];</p><p><b>　　n++;</b></p><p><b>　　}</b></p><p>　　if(st[i][m]!=c)</p><p>&

130、lt;b>　　{</b></p><p>　　lastvt(st[i][m]);</p><p>　　for(j=0;j<r;j++)</p><p><b>　　{</b></p><p>　　if(st[j][0]==st[i][m])</p><p><b>

131、;　　break;</b></p><p><b>　　}</b></p><p>　　for(k=0;k<last[j][0];k++)</p><p><b>　　{</b></p><p><b>　　int t;</b></p><

132、p>　　for(t=0;t<n;t++)</p><p><b>　　{</b></p><p>　　if(last[i][t]==last[j][k+1])</p><p><b>　　break;</b></p><p><b>　　}</b></p>

133、;<p><b>　　if(t==n)</b></p><p><b>　　{</b></p><p>　　last[i][n]=last[j][k+1];</p><p><b>　　n++;</b></p><p><b>　　}</b>

134、</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　m++;</b>&l

135、t;/p><p>　　}while(st[i][m]!='\0');</p><p>　　last[i][n]='\0';</p><p>　　last[i][0]=--n;</p><p>　　lflag[i]=1;</p><p><b>　　}</b></p

136、><p><b>　　}</b></p><p>　　int deal()</p><p><b>　　{</b></p><p><b>　　int i,j;</b></p><p>　　int size=0;//</p><p>

137、<b>　　int x,y;</b></p><p>　　int z; //輸入串的長(zhǎng)度</p><p><b>　　k=1;</b></p><p>　　s[k]='#';

138、 //棧置初值</p><p>　　for(i=0;input[i]!='\0';i++); //計(jì)算輸入串的長(zhǎng)度</p><p><b>　　z=i--;//</b></p><p><b>　　i=0;</b></p>

139、<p>　　while((a=input[i])!='\0')//a表示要輸入的字符</p><p><b>　　{</b></p><p>　　if(zhongjie(s[k]))</p><p><b>　　j=k;</b></p><p><b>　　e

140、lse</b></p><p><b>　　j=k-1;</b></p><p>　　x=xiabiao(s[j]);</p><p>　　y=xiabiao(a);</p><p>　　if(data[x][y]=='>')</p><p><b>　

141、　{</b></p><p>　　if(lable[x]!=')')</p><p>　　shuchu[size++]=lable[x];//將要規(guī)約的終結(jié)符存起來</p><p>　　out(1,k,s);</p><p>　　printf("%c",a);</p><p

142、>　　out(i+1,z,input);</p><p>　　printf("規(guī)約\n");</p><p><b>　　do</b></p><p><b>　　{</b></p><p><b>　　q=s[j];</b></p>&

143、lt;p>　　if(zhongjie(s[j-1]))</p><p><b>　　j=j-1;</b></p><p>　　else j=j-2;</p><p>　　x=xiabiao(s[j]);</p><p>　　y=xiabiao(q);</p><p>　　}while(dat

144、a[x][y]!='<');</p><p>　　int m,n,N;</p><p>　　for(m=j+1;m<=k;m++)</p><p><b>　　{</b></p><p>　　for(N=0;N<r1;N++)</p><p>　　for(n=1;

145、string[N][n]!='\0';n++)</p><p><b>　　{</b></p><p>　　if(!zhongjie(s[m])&&!zhongjie(string[N][n]))</p><p><b>　　{</b></p><p>　　if(zh