詞法分析和算符優(yōu)先分析課程設(shè)計(jì)

1、<p>　　計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院</p><p><b>　　課程設(shè)計(jì)</b></p><p><b>　　課程名稱：編譯原理</b></p><p>　　題 目：詞法分析和算符優(yōu)先分析</p><p><b>　　班 級(jí)： </b></p>

2、<p><b>　　學(xué) 號(hào)： </b></p><p><b>　　姓 名： </b></p><p>　　2012年5月24日</p><p><b>　　設(shè)計(jì)一：詞法分析器</b></p><p>　　1. 課程設(shè)計(jì)目的和要求1</p>

3、<p><b>　　1.1實(shí)驗(yàn)?zāi)康?</b></p><p><b>　　1.2實(shí)驗(yàn)要求1</b></p><p><b>　　2.設(shè)計(jì)描述2</b></p><p><b>　　3.函數(shù)模塊3</b></p><p>　　5.測(cè)試樣

4、例與測(cè)試結(jié)果6</p><p><b>　　6. 結(jié)論7</b></p><p>　　設(shè)計(jì)二： 算符優(yōu)先語(yǔ)法分析</p><p>　　1.課程設(shè)計(jì)的目的和要求8</p><p>　　1.1 課程設(shè)計(jì)的目的8</p><p>　　1.2 課程設(shè)計(jì)的要求8</p><p&

5、gt;<b>　　2.設(shè)計(jì)描述8</b></p><p>　　2.1 自底向上分析方法的描述：8</p><p>　　2.2算符優(yōu)先文法的描述：9</p><p>　　3. 概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)10</p><p>　　4.1功能結(jié)構(gòu)10</p><p>　　4.2模塊的劃分10<

6、/p><p><b>　　5.源代碼11</b></p><p>　　5.測(cè)試樣例與測(cè)試結(jié)果21</p><p><b>　　6. 結(jié)論22</b></p><p><b>　　設(shè)計(jì)一：詞法分析器</b></p><p><b>　　課程設(shè)計(jì)

7、目的和要求</b></p><p><b>　　1.1實(shí)驗(yàn)?zāi)康?lt;/b></p><p>　　通過(guò)完成詞法分析程序，了解詞法分析的過(guò)程。編制一個(gè)讀單詞過(guò)程，從輸入的源程序中，識(shí)別出各個(gè)具有獨(dú)立意義的單詞，即基本保留字、標(biāo)識(shí)符、常數(shù)、運(yùn)算符、分隔符五大類。并依次輸出各個(gè)單詞的內(nèi)部編碼及單詞符號(hào)自身值。</p><p><b>

8、　　1.2實(shí)驗(yàn)要求</b></p><p>　　通過(guò)詞法分析器能夠?qū)崿F(xiàn)以下五種類型如單詞等的識(shí)別。</p><p>　　(1)關(guān)鍵字"begin","end","if","then","else","while","write","

9、;read"等,</p><p>　　"do", "call","const","char","until","procedure","repeat"等</p><p>　　(2)運(yùn)算符："+","-"

10、,"*","/","="等</p><p>　　(3)界符："{","}","[","]",";",",",".","(",")",":"等</p&g

11、t;<p>　　(4)標(biāo)識(shí)符 (5)常量</p><p><b>　　2.設(shè)計(jì)描述</b></p><p>　　詞法分析：逐個(gè)讀入源程序字符并按照構(gòu)詞規(guī)則切分成一系列單詞。單詞是語(yǔ)言中具有獨(dú)立意義的最小單位，包括保留字、標(biāo)識(shí)符、運(yùn)算符、標(biāo)點(diǎn)符號(hào)和常量等。詞法分析是編譯過(guò)程中的一個(gè)階段，在語(yǔ)法分析前進(jìn)行 。也可以和語(yǔ)法分析結(jié)合在一起作為一遍，由語(yǔ)法分析程

12、序調(diào)用詞法分析程序來(lái)獲得當(dāng)前單詞供語(yǔ)法分析使用。</p><p>　　表1 各種單詞符號(hào)對(duì)應(yīng)類型表</p><p><b>　　3.函數(shù)模塊</b></p><p>　　LexAnalyz()函數(shù)</p><p><b>　　實(shí)現(xiàn)整個(gè)分析的過(guò)程</b></p><p>　　2

13、.main主函數(shù)：</p><p>　　主要實(shí)驗(yàn)將輸入的字符串存進(jìn)token中，和組織其他函數(shù)已完成功能。</p><p><b>　　print()函數(shù)</b></p><p>　　將識(shí)別的結(jié)果打印出來(lái)。</p><p><b>　　4.設(shè)計(jì)源碼</b></p><p>　

14、　#include<stdio.h></p><p>　　#include<string.h></p><p>　　#include<ctype.h></p><p>　　#include<cstdlib></p><p>　　using namespace std;</p>&l

15、t;p>　　const char*reserchar[7]={"int", "if", "else", "while", "for", "read", "write" }; //關(guān)鍵字 </p><p>　　const char*rememchar[25]={"

16、;","$SYMBOL", "$CNSTANT", "$INT", "$IF", "$ELSE", "$WHILE", "$FOR", "$READ", "$WRITE", "$ADD", "$SUB&q

17、uot;, "$MUL", "$DIV", "$L", "$LE", "$G", "$GE", "$NE", "$E", "$ASSIGN", "$LPAR", "$RPAR", "$

18、COM", "$SEM" }; //助記符 </p><p>　　void LexAnalyz();</p><p>　　void Print();</p><p>　　char prog[100];</p><p>　　char token[10];</p><p>　　int syn,

19、p;</p><p><b>　　char ch;</b></p><p>　　int main()</p><p><b>　　{</b></p><p><b>　　char sym;</b></p><p><b>　　Print();&

20、lt;/b></p><p><b>　　p=0;</b></p><p><b>　　do {</b></p><p>　　ch=getchar();</p><p>　　prog[p++]=ch;</p><p>　　}while( ch!='#'

21、);</p><p><b>　　p=0; </b></p><p><b>　　do{ </b></p><p>　　LexAnalyz(); </p><p>　　if( syn==-1 )</p><p>　　printf("error\n");

22、 </p><p>　　else if( syn!=0 ){ </p><p>　　printf("%s %d %s\n", token, syn, rememchar[syn]); </p><p><b>　　}</b></p><p>　　// system("pause

23、") ; </p><p>　　}while( syn!=0 );</p><p>　　system("pause");</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p&g

24、t;　　void LexAnalyz()</p><p><b>　　{</b></p><p>　　int j=0,i=0;</p><p><b>　　syn=0;</b></p><p>　　for( i=0; i<10; i++)</p><p>　　token

25、[i]='\0';</p><p>　　ch=prog[p++];</p><p>　　while( ch ==' ' )</p><p>　　ch= prog[p++];</p><p>　　if(isalpha( ch )){</p><p>　　while(isalpha( ch

26、) || isdigit( ch )){</p><p>　　token[j++] = ch;</p><p>　　ch= prog[p++] ; </p><p><b>　　}</b></p><p>　　ch=prog[p--];</p><p>　　syn=1; </p>

27、<p>　　for( i=0; i<7; i++ )</p><p>　　if( strcmp( token, reserchar[i])==0 ){</p><p><b>　　syn=i+3;</b></p><p><b>　　break;</b></p><p><

28、b>　　}</b></p><p><b>　　}</b></p><p>　　else if( isdigit( ch ) ){</p><p>　　while( isdigit( ch ) ){</p><p>　　token[j++] = ch;</p><p>　　ch

29、= prog[p++]; </p><p><b>　　}</b></p><p>　　ch= prog[p--];</p><p><b>　　syn=2;</b></p><p><b>　　}</b></p><p><b>　　else

30、{</b></p><p>　　switch( ch ){</p><p>　　case '<': token[j++] = ch; ch = prog[p++]; </p><p>　　if( ch == '=' ){</p><p>　　token[j++] = ch;</p>

31、;<p>　　syn=15; } </p><p><b>　　else{</b></p><p><b>　　syn=14; </b></p><p>　　ch= prog[p--];</p><p><b>　　} </b></p>&

32、lt;p><b>　　break;</b></p><p>　　case '>': token[j++] = ch; ch = prog[p++]; </p><p>　　if( ch == '=' ){</p><p>　　token[j++] = ch;</p><p>　

33、　syn=17; } </p><p><b>　　else{</b></p><p><b>　　syn=16; </b></p><p>　　ch= prog[p--];}</p><p><b>　　break;</b></p><p>　　ca

34、se '!': token[j++] = ch; ch = prog[p++];</p><p>　　if(ch == '='){</p><p>　　token[j++] = ch;</p><p>　　syn=18; }</p><p><b>　　else</b></p>

35、;<p>　　ch= prog[p--];</p><p><b>　　break;</b></p><p>　　case '=': token[j++] = ch; ch = prog[p++]; </p><p>　　if( ch == '=' ){</p><p>　　

36、token[j++] = ch;</p><p>　　syn=19; } </p><p><b>　　else{</b></p><p>　　ch= prog[p--];</p><p><b>　　syn=20; </b></p><p><b>　　}<

37、;/b></p><p><b>　　break; </b></p><p>　　case '+': token[j++]=ch; syn=10; break;</p><p>　　case '-': token[j++]=ch; syn=11; break; &

38、lt;/p><p>　　case '*': token[j++]=ch; syn=12; break;</p><p>　　case '/': token[j++]=ch; syn=13; break;</p><p>　　case '(': token[j++]=ch; syn=21; break;</p>

39、<p>　　case ')': token[j++]=ch; syn=22; break;</p><p>　　case ',': token[j++]=ch; syn=23; break;</p><p>　　case ';': token[j++]=ch; syn=24; break;</p><p>

40、　　case '#': syn=0; break;</p><p>　　default: syn=-1;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p&g

41、t;　　void Print()</p><p><b>　　{</b></p><p>　　for(int i=0; i<=25; i++ )</p><p>　　printf("*");</p><p>　　printf("\n");</p><p&g

42、t;　　for(int i=0; i<=8; i++ )</p><p>　　printf(" ");</p><p>　　printf("詞法分析器\n");</p><p>　　for(int i=0; i<=25; i++ )</p><p>　　printf("*"

43、;);</p><p>　　printf("\n");</p><p>　　printf("輸入一串句子以#+enter鍵結(jié)束：\n");</p><p><b>　　}</b></p><p>　　5.測(cè)試樣例與測(cè)試結(jié)果</p><p>　　輸入的是字符串

44、；識(shí)別出的是單詞，且輸出單詞的類別編碼和助記符。</p><p><b>　　結(jié)論</b></p><p>　　通過(guò)本次課程設(shè)計(jì)的練習(xí)，熟悉了用C++語(yǔ)言編寫(xiě)詞法分析器的過(guò)程，掌握了詞法分析器的原理以及功能。詞法分析是編譯過(guò)程中的一個(gè)階段，在語(yǔ)法分析前進(jìn)行。也可以和語(yǔ)法分析結(jié)合在一起作為一遍，由語(yǔ)法分析程序調(diào)用詞法分析程序來(lái)獲得當(dāng)前單詞供語(yǔ)法分析使用。詞法分析程序的主

45、要任務(wù)：讀源程序，產(chǎn)生單詞符號(hào)。</p><p>　　詞法分析程序的其他任務(wù)：濾掉空格，跳過(guò)注釋、換行符追蹤換行標(biāo)志，復(fù)制出錯(cuò)源程序，宏展開(kāi)，等等等等。</p><p>　　詞法分析工作從語(yǔ)法分析工作獨(dú)立出來(lái)的原因：簡(jiǎn)化設(shè)計(jì)，改進(jìn)編譯效率，增加編譯系統(tǒng)的可移植性 。</p><p>　　而且從劃分關(guān)鍵字，運(yùn)算符，界符，標(biāo)識(shí)符和常量，才發(fā)現(xiàn)數(shù)字，字母及符號(hào)組合有很多很

46、多，無(wú)法全部枚舉，所以在新建的文本文檔中只象征性的列出幾種符號(hào)，但這并不影響此法分析結(jié)果的完成。</p><p>　　總之，通過(guò)本次實(shí)驗(yàn)，一點(diǎn)點(diǎn)分析詞法分析器的功能，并努力實(shí)現(xiàn)它，掌握了課程設(shè)計(jì)內(nèi)容的同時(shí)也鍛煉了自己分析解決問(wèn)題的能力以及編程能力，收獲頗豐！</p><p>　　設(shè)計(jì)二： 算符優(yōu)先語(yǔ)法分析</p><p>　　1.課程設(shè)計(jì)的目的和要求</p&g

47、t;<p>　　1.1 課程設(shè)計(jì)的目的</p><p>　　本次設(shè)計(jì)的時(shí)間為一個(gè)月，目的是件通過(guò)使用高級(jí)語(yǔ)言實(shí)現(xiàn)部分加強(qiáng)對(duì)編譯技術(shù)和理論的理解。設(shè)計(jì)的題目要求具有一定的規(guī)模，應(yīng)蘊(yùn)含本課程內(nèi)容和世紀(jì)應(yīng)用相關(guān)的主要技術(shù)。</p><p>　　1.2 課程設(shè)計(jì)的要求</p><p>　　文法使用產(chǎn)生式來(lái)定義；</p><p>　　用大

48、寫(xiě)字母和小寫(xiě)字母分別表示非終結(jié)符和終結(jié)符；產(chǎn)生式使用->；</p><p>　　文法中的空字符串統(tǒng)一使用@表示；</p><p>　　分別給出每一個(gè)終結(jié)符的FIRSTVT 集和LASTVT集；</p><p>　　版定給定的文法是否是算符優(yōu)先文法；</p><p>　　畫(huà)出算符優(yōu)先關(guān)系表；、</p><p>　　

49、給定富豪穿是否是文法中的句子，分析過(guò)程用分析表格的方式打印出來(lái)。</p><p><b>　　2.設(shè)計(jì)描述</b></p><p>　　本次實(shí)驗(yàn)使用windows vista操作系統(tǒng)下visiual c++6.0平臺(tái)，使用c語(yǔ)言，利用讀文件方式將待分析的文法讀入到程序中，通過(guò)定義數(shù)組和結(jié)構(gòu)體作為具有一定意義或關(guān)系的表或棧，存放FIRSTVT 、LASTVT、算符有限關(guān)

50、系表的元素。</p><p>　　系統(tǒng)能夠?qū)τ晌募x入的文法進(jìn)行分析，構(gòu)造出FIRSTVT LASTVT表以及算符優(yōu)先關(guān)系表?？梢愿鶕?jù)構(gòu)造的有限關(guān)系表對(duì)輸入的任意字符串進(jìn)行分析，判斷是否為本文法的句子，若是則打印歸約過(guò)程。結(jié)果顯示到DOS界面上。</p><p>　　2.1 自底向上分析方法的描述：</p><p>　　對(duì)輸入的字符串自左向右進(jìn)行掃描，并將輸入字符逐

51、個(gè)移入棧中，邊移入邊分析，一旦棧頂富豪穿形成摸個(gè)矩形的句柄時(shí)（該句柄對(duì)應(yīng)某個(gè)產(chǎn)生式的右部），就用該產(chǎn)生式的非終結(jié)符代替郵編的文法字符串，這一過(guò)程成為歸約。重復(fù)這一過(guò)程，知道棧中只剩下文法的開(kāi)始負(fù)責(zé)分析成功。</p><p>　　2.2算符優(yōu)先文法的描述：</p><p>　　之規(guī)定酸腐之間的優(yōu)先關(guān)系，也就是說(shuō)只考慮終結(jié)符之間的有限關(guān)系。由于算符優(yōu)先分析不考慮終結(jié)符之間的優(yōu)先關(guān)系，在歸約過(guò)程

52、中只要找到最左素短語(yǔ)就可以規(guī)約了。</p><p>　　如給定一個(gè)文法G[S]：</p><p><b>　　S->#E#</b></p><p><b>　　E->E+T</b></p><p><b>　　E->T</b></p><p

53、><b>　　T->T*F</b></p><p><b>　　T->F</b></p><p><b>　　F->(E)</b></p><p><b>　　F->i</b></p><p>　　利用算符優(yōu)先文法分析過(guò)程處理

54、如下：</p><p>　　計(jì)算給定文法中任意兩個(gè)終結(jié)符對(duì)（a,b）之間的優(yōu)先關(guān)系，首先計(jì)算兩個(gè)幾何</p><p>　　FIRSTVT(B)={b|B->b.......或B->Cb.......}</p><p>　　LASTVT(B)={a|B->....a或B->.......aC}</p><p>　　2.構(gòu)

55、造firstvt和lastvt集</p><p>　　下表是FIRSTVT集和LASTVT集</p><p>　　根據(jù)firstvt 和lastvt集構(gòu)造算符優(yōu)先關(guān)系表</p><p>　　下表是算符優(yōu)先關(guān)系表</p><p><b>　　3.進(jìn)行移進(jìn)和歸約</b></p><p><b&g

56、t;　　概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)</b></p><p><b>　　4.1功能結(jié)構(gòu)</b></p><p><b>　　4.2模塊的劃分</b></p><p><b>　　文件的導(dǎo)入：</b></p><p>　　int ReadFile(char exp[][col

57、]); </p><p>　　文法以文件的形式輸入而且保存在二維數(shù)組中。</p><p>　　Firstvt和Lastvt集的構(gòu)造：</p><p>　　void FirstVT(char exp[][col],char firstvt[][col],const int&exp_len,const int&first_len); </

58、p><p>　　//構(gòu)造firstvt集</p><p>　　void LastVT(char exp[][col],char lastvt[][col],const int&exp_len,const int&first_len); </p><p>　　//構(gòu)造lastvt集</p><p>　　算符優(yōu)先關(guān)系表的構(gòu)

59、造：</p><p>　　bool OperPriTable(char exp[][col],char opertable[][col],char firstvt[][col],char lastvt[][col],int exp_len,int first_len,int&oper_len);</p><p>　　//構(gòu)造算符優(yōu)先表如果不是算符優(yōu)先文法則返回false。</

60、p><p><b>　　歸約的過(guò)程：</b></p><p>　　bool GuiYue(char input[],char opertable[][col],char exp[][col],int oper_len,int exp_len); </p><p>　　//在其他的小函數(shù)的幫助下歸約 </p><p><

61、;b>　　主函數(shù)</b></p><p>　　Main函數(shù),將模塊組合，完成整個(gè)設(shè)計(jì)的功能。</p><p><b>　　5.源代碼</b></p><p>　　#include<iostream></p><p>　　#include<fstream></p>&

62、lt;p>　　#include<stack></p><p>　　#define col 50</p><p>　　#define row 50 </p><p>　　using namespace std; </p><p>　　struct Element</p><p><b>　　

63、{</b></p><p>　　char nont; //非終結(jié)符 </p><p>　　char ternal; //終結(jié)符 </p><p><b>　　};</b></p><p>　　void Init(char exp[][col],char firstvt[][col],char last

64、vt[][col],int&exp_len,int&first_len);</p><p>　　//first和lastvt的非終結(jié)符</p><p>　　bool FindRecord(Element record[],Element &a, int &r); </p><p>　　//在構(gòu)造first集時(shí)，判斷是否已經(jīng)添加了A

65、->a </p><p>　　bool TerminalJug(char ch); //判斷是否是終結(jié)符 </p><p>　　void FirstVT(char exp[][col],char firstvt[][col],const int&exp_len,const int&first_len); //構(gòu)造firstvt集&l

66、t;/p><p>　　void LastVT(char exp[][col],char lastvt[][col],const int&exp_len,const int&first_len); //構(gòu)造lastvt集</p><p>　　int ReadFile(char exp[][col]); //文法以文件的形式輸入</p><p&g

67、t;　　bool InsertTable(char opertable[][col],int&i,int&j,char oper); </p><p>　　int FindItem( char firstvt[][col],int first_len,char ch); </p><p>　　//判斷此終結(jié)符是否在firsrvt集 0列中</p>&l

68、t;p>　　int FindPosition(char term[],const char&c1,const int&term_len) ;</p><p>　　bool OperPriTable(char exp[][col],char opertable[][col],char firstvt[][col],char lastvt[][col],int exp_len,int first

69、_len,int&oper_len); //構(gòu)造算符優(yōu)先表</p><p>　　void Print(char array[][col],int r); //輸出查看 </p><p>　　bool GuiYue(char input[],char opertable[][col],char exp[][col],int oper_len,int exp_len);

70、 //歸約函數(shù) </p><p>　　char Match(char sk[],int s,int e,char exp[][col],int&exp_len); </p><p>　　//在產(chǎn)生式中查找匹配式子并返回規(guī)約后的非終結(jié)符 </p><p>　　int main()</p><p><b>　　{</b&

71、gt;</p><p>　　char firstvt[row][col]={'\0'},lastvt[row][col]={'\0'};</p><p>　　char exp[row][col]={'\0'},opertable[row][col]={'\0'};</p><p>　　int first

72、_len,exp_len,oper_len; </p><p>　　exp_len=ReadFile(exp);</p><p>　　Init(exp,firstvt,lastvt,exp_len,first_len);</p><p>　　FirstVT(exp,firstvt,exp_len,first_len);</p><p>　　c

73、out<<"\n\t文法中非終結(jié)符的firstvt集： "<<endl;</p><p>　　cout<<"**************************************"<<endl; </p><p>　　Print(firstvt,first_len);</p>

74、<p>　　LastVT(exp,lastvt,exp_len,first_len);</p><p>　　cout<<"\n\t文法中非終結(jié)符的lastvt集： "<<endl;</p><p>　　cout<<"**************************************"&

75、lt;<endl;</p><p>　　Print(lastvt,first_len);</p><p>　　if( OperPriTable(exp,opertable,firstvt,lastvt,exp_len,first_len,oper_len) ){</p><p>　　cout<<"\n\t算符優(yōu)先分析表：

76、"<<endl;</p><p>　　cout<<"**************************************"<<endl;</p><p>　　Print(opertable,oper_len);</p><p>　　cout<<endl;</p>&l

77、t;p>　　char input[col]={'\0'};</p><p>　　cout<<"輸入要分析的串 （以#+enter鍵結(jié)束）："<<endl;</p><p>　　cin>>input;</p><p>　　cout<<"\t\t分析過(guò)程描述

78、 "<<endl;</p><p>　　if( GuiYue(input,opertable,exp,oper_len,exp_len) ){</p><p>　　cout<<"該句型符合算符優(yōu)先文法"<<endl;</p><p><b>　　}</b></p>

79、;<p><b>　　else</b></p><p>　　cout<<"該句型不符合算符優(yōu)先文法,是個(gè)錯(cuò)誤的句子"<<endl;</p><p><b>　　}</b></p><p>　　//C:\\Users\\peanut\\Desktop\\編譯原理\\文

80、法.txt </p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　void FirstVT(char exp[][col],char firstvt[][col],const int&exp_len,const int&first_len)

81、 //構(gòu)造firstvt集 </p><p><b>　　{</b></p><p>　　int i,recor_len;</p><p>　　stack<Element> expstack; </p><p>　　Element temp;</p><p>　　Element r

82、ecord[col];</p><p>　　recor_len=0;</p><p>　　for( i=0; i<exp_len; i++){ //第一次掃描得出的A->a入棧 </p><p>　　for( int j=3; exp[i][j]!='\0'; j++){</p><p&g

83、t;　　if( TerminalJug( exp[i][j] ) ){ //判斷是否是終結(jié)符 </p><p>　　temp.nont=exp[i][0];</p><p>　　temp.ternal=exp[i][j];</p><p>　　if( recor_len==0 || !FindRecord(record,temp, rec

84、or_len) ){ //沒(méi)記錄就添加到記錄 </p><p>　　expstack.push(temp);</p><p>　　record[recor_len].nont=temp.nont;</p><p>　　record[recor_len].ternal=temp.ternal;</p><p>　　recor_len++;<

85、;/p><p><b>　　}</b></p><p><b>　　break; </b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b>

86、</p><p>　　Element DL,DE; </p><p>　　int location[col]; //用來(lái)記錄firstvt集中每行的長(zhǎng)度 </p><p>　　for( i=0; i<first_len; i++)</p><p>　　location[i]=1;</

87、p><p>　　while( !expstack.empty() ){</p><p>　　DE=expstack.top();</p><p>　　// cout<<DE.nont<<"->"<<DE.ternal<<endl; </p><p>　　expstack.p

88、op();</p><p>　　for( i=0; i<first_len; i++){ //將終結(jié)符加到相應(yīng)firstvt集中 </p><p>　　if( firstvt[i][0] == DE.nont ){</p><p>　　int len=location

89、[i]; </p><p>　　firstvt[i][len]=DE.ternal;</p><p>　　location[i]++;</p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</

90、b></p><p>　　for( i=0; i<exp_len; i++){ //找出能推出相應(yīng)非終結(jié)符的產(chǎn)生式 規(guī)律二: A->B </p><p>　　if( exp[i][3]==DE.nont ){</p><p>　　DL.nont=exp[i][0];</p>

91、;<p>　　DL.ternal=DE.ternal;</p><p>　　if( !FindRecord(record, DL, recor_len) ){//沒(méi)記錄就添加到記錄 </p><p>　　expstack.push(DL);</p><p>　　record[recor_len].nont=DL.nont;</p><

92、;p>　　record[recor_len].ternal=DL.ternal;</p><p>　　recor_len++;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p>&

93、lt;p><b>　　}</b></p><p><b>　　}</b></p><p>　　void LastVT(char exp[][col],char lastvt[][col],const int&exp_len,const int&first_len) //構(gòu)造lastvt集 </p>&l

94、t;p><b>　　{</b></p><p>　　int i,j,k;</p><p><b>　　char ch;</b></p><p>　　char temp[row][col]={'\0'};</p><p>　　for( i=0; i<exp_len; i++

95、){</p><p>　　for( j=0; exp[i][j]!='\0'; j++)</p><p>　　temp[i][j]=exp[i][j]; </p><p><b>　　j--;</b></p><p>　　for( k=3; k<j; k++,j--){</p><

96、;p>　　ch=temp[i][k];</p><p>　　temp[i][k]=temp[i][j];</p><p>　　temp[i][j]=ch;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　FirstVT

97、(temp,lastvt,exp_len,first_len); </p><p><b>　　}</b></p><p>　　void Init(char exp[][col],char firstvt[][col],char lastvt[][col],int&exp_len,int&first_len)</p><p>

98、　　//first和lastvt的非終結(jié)符</p><p><b>　　{</b></p><p>　　first_len=0;</p><p>　　for( int i=0; i<exp_len; i++){</p><p>　　if( TerminalJug(exp[i][0]) == false &&

99、amp; FindItem(firstvt,first_len,exp[i][0]) == -1 ){ </p><p>　　firstvt[first_len][0]=exp[i][0];</p><p>　　lastvt[first_len][0]=exp[i][0];</p><p>　　first_len++;</p><p&g

100、t;<b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　int ReadFile(char exp[][col]) //文法以文件的形式輸入 </p><p><b>　　{</b>

101、;</p><p>　　ifstream fin;</p><p><b>　　int i;</b></p><p>　　char address[30];</p><p>　　cout<<"輸入文件的路徑："<<endl; </p><p>　　cin

102、>>address;</p><p>　　cout<<endl;</p><p>　　fin.open(address,ios::in);</p><p><b>　　if(!fin)</b></p><p>　　cout<<"file can not be opened!&

103、quot;<<endl;</p><p><b>　　else{</b></p><p>　　cout<<"\t文法的中表達(dá)式:"<<endl;</p><p>　　cout<<"*****************************"<<e

104、ndl; </p><p>　　for( i=0; !fin.eof(); i++){ //表達(dá)式的輸入 </p><p>　　fin>>exp[i];</p><p>　　cout<<exp[i]<<endl;</p><p><b>　　}</b>&l

105、t;/p><p>　　fin.close();</p><p><b>　　}</b></p><p>　　return i; //返回表達(dá)式的行數(shù) </p><p><b>　　}</b></p><p>　　int FindItem(char first

106、vt[][col],int first_len,char ch) //判斷此終結(jié)符是否在firsrvt集 0列中 </p><p><b>　　{</b></p><p>　　for(int i=0; i<first_len; i++)</p><p>　　if( firstvt[i][0]==ch )</p><p&

107、gt;<b>　　return i;</b></p><p>　　return -1; </p><p><b>　　}</b></p><p>　　bool FindRecord(Element record[],Element &a, int &recor_len) //判斷是否有記錄

108、 </p><p><b>　　{</b></p><p>　　for( int k=0; k<recor_len; k++)</p><p>　　if( record[k].nont==a.nont && record[k].ternal==a.ternal ) </p><p>　　retur

109、n true;</p><p>　　return false; </p><p><b>　　}</b></p><p>　　bool TerminalJug(char ch)</p><p><b>　　{</b></p><p>　　if( ch>='A&#

110、39; && ch<='Z') </p><p>　　return false;</p><p>　　return true;</p><p><b>　　}</b></p><p>　　bool OperPriTable(char exp[][col],char opertable

111、[][col],char firstvt[][col],char lastvt[][col],int exp_len,int first_len,int&oper_len) </p><p>　　//構(gòu)造算符優(yōu)先表 </p><p><b>　　{</b></p><p>　　char term[col]={'\0'}

112、;</p><p>　　int term_len=0,i,j,k;</p><p>　　int r,c,p;</p><p>　　for( i=0; i<exp_len; i++) //得到所有終結(jié)符 </p><p>　　for( j=3; exp[i][j]!='\0'; j++)</p><

113、;p>　　if( TerminalJug(exp[i][j]) && !FindPosition(term,exp[i][j],term_len) )</p><p>　　term[term_len++]=exp[i][j];</p><p>　　oper_len=term_len+1; </p><p>　　f

114、or( i=0; i<term_len+1; i++)</p><p>　　for( j=0; j<term_len+1; j++)</p><p>　　opertable[i][j]=' ';</p><p>　　for( i=1; i<term_len+1; i++){ //初始化表頭 </p><p>

115、　　opertable[i][0]=term[i-1]; </p><p>　　opertable[0][i]=term[i-1];</p><p><b>　　} </b></p><p>　　for( i=0; i<exp_len; i++){ </p><p>　　for( j=5; exp[i][

116、j]!='\0'; j++){</p><p><b>　　// 等于關(guān)系</b></p><p>　　if(TerminalJug(exp[i][j-2])&&!TerminalJug(exp[i][j-1])&& TerminalJug(exp[i][j]) ){</p><p>　　//

117、cout<<exp[i][j-2]<<' '<<exp[i][j-1]<<' '<<exp[i][j]<<endl; </p><p>　　r=FindPosition(term,exp[i][j-2],term_len); </p><p>　　c=FindPosition(term,

118、exp[i][j],term_len);</p><p>　　if( !InsertTable(opertable, r, c, '=') ){</p><p>　　cout<<"不是算符優(yōu)先文法！"<<endl;</p><p>　　return false;</p><p>&l

119、t;b>　　} </b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　for( i=0; i<exp_len; i++){ </p><

120、p>　　for( j=4; exp[i][j]!='\0'; j++){</p><p>　　if( TerminalJug(exp[i][j-1]) && TerminalJug(exp[i][j]) ){ //相鄰兩個(gè)終結(jié)符的等于關(guān)系</p><p>　　r=FindPosition(term,exp[i][j-1],term_len); &l

121、t;/p><p>　　c=FindPosition(term,exp[i][j],term_len);</p><p>　　if( !InsertTable(opertable, r, c, '=') ){</p><p>　　cout<<"不是算符優(yōu)先文法！"<<endl;</p><p&

122、gt;　　return false;</p><p><b>　　} </b></p><p><b>　　}</b></p><p>　　// Print(opertable,term_len+1);</p><p>　　if( TerminalJug(exp[i][j-1]) &&

123、amp; !TerminalJug(exp[i][j]) ){ //小于關(guān)系</p><p>　　// cout<<exp[i][j-1]<<' '<<exp[i][j]<<endl;</p><p>　　p=FindItem( firstvt,first_len,exp[i][j] ); //在firstvt集中

124、的行標(biāo)。 </p><p>　　r=FindPosition(term,exp[i][j-1],term_len);</p><p>　　for( k=1; firstvt[p][k]!='\0'; k++ ){</p><p>　　// cout<<firstvt[p][k]<<' ';</p>

125、<p>　　c=FindPosition(term,firstvt[p][k],term_len);</p><p>　　//cout<<r<<' '<<c<<endl; </p><p>　　if( !InsertTable(opertable, r, c, '<') ){ &

126、lt;/p><p>　　cout<<"不是算符優(yōu)先文法！"<<endl;</p><p>　　return false;</p><p><b>　　} </b></p><p><b>　　} </b></p><p>

127、<b>　　} </b></p><p>　　// Print(opertable,term_len+1);</p><p>　　if( !TerminalJug(exp[i][j-1]) && TerminalJug(exp[i][j]) ){ //大于關(guān)系</p><p>　　p=FindItem( lastvt,firs

128、t_len,exp[i][j-1] ); </p><p>　　//在lastvt集中的行標(biāo)。</p><p>　　c=FindPosition(term,exp[i][j],term_len);</p><p>　　for( k=1; lastvt[p][k]!='\0'; k++ ){</p><p>

129、　　r=FindPosition(term,lastvt[p][k],term_len);</p><p>　　if( !InsertTable(opertable, r, c , '>') ){ </p><p>　　cout<<"不是算符優(yōu)先文法！"<<endl;</p><p>　　

130、return false;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　// Print(opertable,term_len+1);</p><p><

131、;b>　　}</b></p><p><b>　　} </b></p><p>　　return true; </p><p><b>　　}</b></p><p>　　int FindPosition(char term[],const char&am

132、p;c1,const int&term_len) </p><p>　　//查找字符在算符優(yōu)先表中的下標(biāo) </p><p><b>　　{</b></p><p><b>　　int i;</b></p><p>　　for( i=0; i<term_len; i++ )<

133、/p><p>　　if( term[i]==c1 )</p><p>　　return i+1;</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　bool InsertTable(char opertable[]

134、[col],int&i,int&j,char oper)</p><p><b>　　{</b></p><p>　　if( opertable[i][j]!=' ' )</p><p>　　return false; </p><p>　　opertable[i][j]=oper;&

135、lt;/p><p>　　return true;</p><p><b>　　}</b></p><p>　　void Print(char array[][col],int r)</p><p><b>　　{</b></p><p><b>　　int i,j;&l

136、t;/b></p><p>　　for( i=0; i<r; i++){</p><p>　　cout<<array[i][0]<<' ';</p><p>　　for( j=1; array[i][j]!='\0'; j++)</p><p>　　cout<<a

137、rray[i][j]<<' '; </p><p>　　cout<<endl;</p><p><b>　　} </b></p><p><b>　　}</b></p><p>　　bool GuiYue(char input[],char opertable

138、[][col],char exp[][col],int oper_len,int exp_len)</p><p><b>　　{</b></p><p>　　char sk[col]={'\0'};</p><p>　　char*str=input;</p><p>　　int k,j,pa,pb,i,

139、p;</p><p>　　char a,b,op;</p><p>　　cout.setf(ios::left);</p><p>　　cout.width(15);</p><p>　　cout<<"下推棧";</p><p>　　cout.unsetf(ios::left);<

140、/p><p>　　cout.width(15);</p><p>　　cout<<"輸入串";</p><p>　　cout.width(10);</p><p>　　cout<<"動(dòng)作"<<endl; </p><p>　　sk[0]='

141、;#'; </p><p><b>　　k=0; </b></p><p>　　for( i=0; input[i]!='\0'; ){ </p><p>　　b=input[i];</p><p>　　if( TerminalJug(sk[k]) )</p><p>&