編譯原理課程設(shè)計(jì)(c++)-語(yǔ)法分析器

上傳人：奔*** IP屬地：河北更新時(shí)間：2024-03-01 格式：doc 頁(yè)數(shù)：16 大小：201.00KB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

編譯原理課程設(shè)計(jì)(c++)-語(yǔ)法分析器_第1頁(yè)

已閱讀1頁(yè)，還剩15頁(yè)未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說(shuō)明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、　　課程設(shè)計(jì)報(bào)告　　2010~2011學(xué)年第一學(xué)期　課程名稱：編譯原理　課程設(shè)計(jì)題目：語(yǔ)法分析器　姓名：　系：計(jì)算機(jī)　專

2、業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)　年級(jí)：　學(xué) 號(hào)：　指導(dǎo)教師：　職稱：　　目錄　　1 正則表達(dá)式1　　1.1

3、正則表達(dá)式1　　1.2 確定化(化簡(jiǎn))后的狀態(tài)轉(zhuǎn)換圖1　　1.3 分析程序代碼1　　1.4 程序運(yùn)行截圖4　　1.5 小結(jié)4　　2 LL(1)分析5

4、　　2.1 LL(1)文法5　　2.2 LL(1)預(yù)測(cè)分析表5　　2.3 分析程序代碼5　　2.4 程序運(yùn)行截圖7　　2.5 小結(jié)7　　3 算符優(yōu)先分析

5、8　　3.1 算符優(yōu)先文法8　　3.2 算符優(yōu)先關(guān)系表8　　3.3 分析程序代碼8　　3.4 程序運(yùn)行截圖10　　3.5 小結(jié)11　　4 LR分析12</p

6、>　　4.1 LR文法12　　4.2 LR分析表12　　4.3 分析程序代碼12　　4.4 程序運(yùn)行截圖14　　4.5 小結(jié)14　　參考文獻(xiàn)：14</b&g

7、t;　　1 正則表達(dá)式　　1.1 正則表達(dá)式　　(a|b)*(aa|bb)(a|b)* (注：該正規(guī)式為示例，可更改）　　1.2 確定化(化簡(jiǎn))后的狀態(tài)轉(zhuǎn)換圖　　1.3 分析程序代碼

8、　　#include <iostream> 　　#include <string> 　　using namespace std; 　　cons

9、t int Max=20; 　　typedef struct ArcNode{ 　　int&

10、#160;adjvex;//該弧所指向的頂點(diǎn)的位置 　　char info; //權(quán) 　　struct ArcNode *nextarc;//指向下一條弧的指針 　　}ArcNode;

11、 　　typedef struct VNode{ 　　char data; //

12、頂點(diǎn)信息 　　ArcNode *firstarc; //指向第一條依附該頂點(diǎn)的弧的指針 　　}VNode; </p&g

13、t;　　class Nfa 　　{ 　　public: 　　Nfa();

14、0;//構(gòu)造函數(shù),初始化nfa 　　int FindAdj(char c); //返回c狀態(tài)的在鄰接表中的序號(hào) 　　void AlpAdd(char c);

15、; //向字母表集合中添加表中沒(méi)有的新元素c 　　void InitVisit(); //初始化Visited集合 　　voi

16、d e_closure(int index); //求單一狀態(tài)c的e-閉包 　　void e_closure(int a[]); //重載的狀態(tài)集合的e-閉包 　　void move(int&#

17、160;I,char a); //單一狀態(tài)I的a弧轉(zhuǎn)換 　　void move(int I[],char a); //重載的狀態(tài)集合的a弧轉(zhuǎn)換 　　void Nfa::Visit_I(int&#

18、160;*Temp); //Visited轉(zhuǎn)換為集合 　　void Insert(int I[],int a); //向狀態(tài)集合中添加新元素 　　int TAdd(int I[]);

19、 //狀態(tài)矩陣T中加入新?tīng)顟B(tài)集合 　　void Resault(int i); 　　void Nfa_Dfa(); 　　private:

20、　　int K; //狀態(tài)數(shù) 　　int T[Max][Max];

21、; //狀態(tài)子集矩陣 　　VNode AdjList[Max]; //nfa,鄰接表的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ) 　　VNode Dfa[Max];

22、60; //dfa 　　bool Visited[Max]; //存e-閉包結(jié)果 　　char Alp[Max];&

23、#160; //字母表,0號(hào)單元用于存放個(gè)數(shù) 　　}; 　　Nfa::Nfa() 　　{ &

24、lt;/p>　　K=Alp[0]=0; 　　char c; 　　string line; 　　ArcNode *p; </p

25、>　　while(cin>>c&&c!='#') 　　{ 　　AdjList[K].data=c; 　　AdjList[K].firsta

26、rc=new ArcNode; 　　AdjList[K].firstarc->nextarc=NULL; 　　K++; 　　} <

27、;/p>　　getline(cin,line); 　　while(getline(cin,line)&&line!="#") 　　{ &

28、lt;/b>　　int index=FindAdj(line[0]); 　　if(index!=-1) 　　{ 　　p=AdjList[index].f

29、irstarc; 　　while(p->nextarc) 　　p=p->nextarc; 　　p->nextarc=new ArcNode; 　　p->

30、;nextarc->nextarc=NULL; 　　p->nextarc->adjvex=FindAdj(line[4]); 　　p->nextarc->info=line[2]; 　　AlpAdd(p->nex

31、tarc->info); 　　} 　　} 　　cout<<"------------------------------"<&l

32、t;endl; 　　cout<<"Initialization completely."<<endl; 　　cout<<"K={"; 　　for(int

33、;i=0;i<K-1;i++) 　　cout<<AdjList[i].data<<","; 　　cout<<AdjList[K-1].data<<"}."<<endl; </p&

34、gt;　　cout<<"∑={"; 　　for(int i=1;i<(int)Alp[0];i++) 　　cout<<Alp[i]<<","; <

35、p>　　cout<<Alp[Alp[0]]<<"}."<<endl; 　　for(int i=0;i<K;i++) 　　{ 　　p=

36、AdjList[i].firstarc; 　　p=p->nextarc; 　　while(p) 　　{ 　　cout<<&quo

37、t;f("<<AdjList[i].data<<","<<p->info<<")="<<p->adjvex<<" "; 　　p=p->nextarc;

38、　　} 　　if(i<K&&AdjList[i].firstarc->nextarc) 　　#include<stdio.h>　　int exch[4][2]={1,2,

39、3,2,1,3,3,3};　　void judge(char *s) 　　{　　int cur = 0, i = 0;　　while(s[i])　　{&l

40、t;/p>　　if(s[i]-'a' > 1 || s[i] < 'a')　　break;　　cur=exch[cur][ s[i++] - 'a'];　　}</b

41、>　　if(s[i] == 0 && cur == 3)　　printf ("%s √ Right！\n\n",s);　　else printf ("%s × Wrong！\n\n",s);<

42、b>　　}　　int main()　　{　　char str[100];　　while(1)　　{</

43、b>　　printf("有限自動(dòng)機(jī)，判斷是否符合 (a|b)*(aa|bb)(a|b)*\n");　　printf("請(qǐng)輸入字符串： ");　　gets(str);　　judge(str);<

44、p>　　}　　}　　1.4 程序運(yùn)行截圖　　1.5 小結(jié)　　平時(shí)的學(xué)習(xí)需要通過(guò)實(shí)踐來(lái)檢驗(yàn)，通過(guò)這次實(shí)驗(yàn)我能發(fā)現(xiàn)自身存在的一些問(wèn)題，并且加以改正，同時(shí)通

45、過(guò)實(shí)驗(yàn)加強(qiáng)了自己的動(dòng)手能力，并且增強(qiáng)了對(duì)于正則表達(dá)式的理解，并不只在于應(yīng)試方面。　　2 LL(1)分析　　2.1 LL(1)文法　　E→TE' (注：該文法為示例，可更改）　　E'→+TE'|ε&l

46、t;/p>　　T→FT'　　T'→*FT'|ε　　F→(E)|i　　2.2 LL(1)預(yù)測(cè)分析表　　2.

47、3 分析程序代碼　　輸入文法：E→TE' (注：該文法為示例，可更改）　　E'→+TE'|ε　　T→FT'　　T'→*FT

48、9;|ε　　F→(E)|i　　代碼：　　#include<stdio.h>　　#include<string.h> <

49、p>　　char data[5][6][10]={ "12","","","12","","",　　"","12+","","","-","-",

50、　　"34","","","34","","",　　"","-","34*","","-","-",</p&g

51、t;　　"i","","",")0(","","",　　};// 第一維0-4分別代表 EE'TT'F ，第二維0-5代表i+*()# -代表ε　　int exch(char ch)</p&g

52、t;　　{　　switch(ch)　　{　　case 'i': return 0;　　case '+': return 1;

53、;　　case '*': return 2;　　case '(': return 3;　　case ')': return 4;　　case 0 : return 5; //字符串結(jié)束標(biāo)志代表'#'.&

54、lt;p>　　default: return -1;　　}　　}　　void judge(char *s)　　{

55、;　　int tot=0,i=0,cur,k=exch(s[0]);　　char sta[100];;　　sta[++tot]='0';　　while(tot>0)　　{

56、　　cur = sta[tot] - '0';　　if(s[i] == ' ') // 去空格　　++tot,k=exch(s[++i]);　　else if(cur+'0' == s[i]) // 推導(dǎo)出相同字符，出棧

57、　　k=exch(s[++i]);　　else if(k < 0 || data[cur][k][0] == 0) // 踩空，或者出現(xiàn)非法字符　　break;　　else if(data[cur][k][0] != '-') //不是ε，進(jìn)棧繼續(xù)推導(dǎo)

58、　　{　　strcpy(sta+tot,data[cur][k]);　　tot+=strlen(data[cur][k]);　　}　　-

59、-tot;　　}　　if(tot==0)　　printf(" %s √ Right！\n\n",s);　　else printf(" %

60、s × Wrong！\n\n",s);　　}　　int main()　　{　　char str[100];　　printf(&quo

61、t;判斷符號(hào)串是否符合文法：\n\n\tE→TE'\n\t");　　printf("E'→+TE'|ε\n\tT→FT'\n\tT'→*FT'|ε\n\tF→(E)|i\n\n");　　while(printf("輸入符號(hào)串: ")&&get

62、s(str)&&str[0])　　judge(str);　　return 0;　　}　　2.4 程序運(yùn)行截圖　　2.5

63、小結(jié)　　實(shí)踐實(shí)踐驗(yàn)證里的唯一標(biāo)準(zhǔn)，這次課程設(shè)計(jì)主要鞏固了我對(duì)LL(1)文法的深刻認(rèn)識(shí)，掌握程序?qū)崿F(xiàn)文法判斷、鏈表的使用等多種問(wèn)題的基本方法，進(jìn)一步提高了綜合運(yùn)用所學(xué)知識(shí)的能力。　　3 算符優(yōu)先分析　　3.1 算符優(yōu)先文法&l

65、　#include<stdio.h>　　#include<string.h>　　char com[8][8]={ '>', '>', '<', '<', '<', '>', '<

66、;', '>',　　'>', '>', '<', '<', '<', '>', '<', '>',　　'>', '>

67、;', '>', '>', '<', '>', '<', '>',　　'>', '>', '>', '>', '<', '>'

68、, '<', '>',　　'<', '<', '<', '<', '<', '=', '<', ' ',　　'>', '

69、;>', '>', '>', '-', '>', '-', '>', 　　'>', '>', '>', '>', '-', '>'

70、, '-', '>',　　'<', '<', '<', '<', '<', '-', '<', '=',　　}; // 0-7 分別代表　+ - * /

71、( ) i #　　int exch(char ch)　　{　　switch(ch)　　{　　case '+': return 0;<

72、/p>　　case '-': return 1;　　case '*': return 2;　　case '/': return 3;　　case '(': return 4;　　c

73、ase ')': return 5;　　case 'i': return 6;　　case 0 : return 7; //字符串結(jié)束標(biāo)志代表‘#’　　default: return -1;　　}<

74、;/p>　　}　　char expre[6][5]={"N+N","N-N","N*N","N/N","(=N)","i"}; //為了挽回因忽略語(yǔ)法變量而產(chǎn)生的錯(cuò)誤，在規(guī)約時(shí)檢驗(yàn)終結(jié)符是否帶了應(yīng)有的操作對(duì)象。

75、　　int confirm(char *sta,int t) //檢驗(yàn)終結(jié)符是否帶了應(yīng)有的變量。　　{　　int i,n=t;　　while( n>0&&sta[n]!='<')</p

76、>　　n--;　　if(n>0)　　for(i=0;i<6;i++)　　if(memcmp(expre[i],sta+n+1,sizeof(char)*(t-n))==0)&

77、lt;p>　　{　　sta[n] = 'N'; // 說(shuō)明是有應(yīng)有的操作對(duì)象，所以進(jìn)行規(guī)約。　　return n;　　}<b&g

78、t;　　return 0;　　}　　void judge(char *s)　　{　　char sta[100];　　int tot=0

79、,cur,m,k,i=0;　　sta[++tot]=0;　　while(tot>0)　　{　　m=tot;　　do {</b

80、>　　cur=exch(sta[m--]);　　}while(cur<0); // 要忽略變量，直接對(duì)終結(jié)符進(jìn)行比較優(yōu)先級(jí)。　　while(s[i] == ' ') // 跳過(guò)空格　　i++;<

81、/p>　　k = exch(s[i]);　　if( cur==k&&cur==7)　　tot = 0; // 規(guī)約成功，結(jié)束標(biāo)記。　　else if( k<0 || com[cur][k] == '-' ) // 踩空或者輸入非法符</p&

82、gt;　　tot = -1;　　else if( com[cur][k] != '>' ) // 遇到‘>'，準(zhǔn)備規(guī)約　　{　　if(sta[tot] == 'N

83、9;) // 這里一個(gè)小問(wèn)題就是變量N是要在'<'左邊還是右邊呢，這要取決于終結(jié)符是什么，左右兩邊有幾個(gè)變量，不過(guò)針對(duì)本程序方法，只需全部放在右邊。　　{　　sta[tot] = com[cur][k];　　sta[++tot] = 'N&#

84、39;;　　}　　else 　　sta[++tot] = com[cur][k];　　sta[++tot] =s[i++];　　}<

85、;/b>　　else if( (tot = confirm( sta,tot ))==0 ) //檢驗(yàn)終結(jié)符是否帶了應(yīng)有的變量。沒(méi)有，就規(guī)約失敗　　tot = -1;　　}　　if(tot=

86、=0)　　printf(" %s √ Right！\n\n",s);　　else printf(" %s × Wrong！\n\n",s);　　}<

87、p>　　int main()　　{　　char str[100];　　printf("判斷符號(hào)串是否符合文法：\n\n\tE→T | E+T | E-T\n\tT→F | T*F | T/F\n\tF→(E) | i\n\n");

88、　　while(printf("輸入符號(hào)串: ")&&gets(str)&&str[0])　　judge(str);　　return 0;　　}

89、　　3.4 程序運(yùn)行截圖　　3.5 小結(jié)　　通過(guò)這次課程設(shè)計(jì)，我發(fā)現(xiàn)之前沒(méi)發(fā)現(xiàn)的問(wèn)題。算符優(yōu)先分析方法有一定的局限性由于算符優(yōu)先分析法去掉了單非終結(jié)符之間的歸約，盡管在分析過(guò)程中，當(dāng)決定是否為句柄時(shí)采取一些檢查措施，但仍難完全避免把錯(cuò)誤的句子得到正確的歸約。<p

90、>　　4 LR分析　　4.1 LR文法　　(0) S'→S (注：該文法為示例，可更改）　　(1) S→BB 　　(2) B→aB <p

91、>　　(3) B→b　　4.2 LR分析表　　4.3 分析程序代碼　　#include<stdio.h>　　#include<string.h> 　　in

92、t action[7][5]= {　　3, 4, 0, 1, 2,　　0, 0,-4, 0, 0,　　3, 4, 0, 0, 5,　　3, 4, 0, 0, 6,　　-3,-3,-3, 0, 0,<

93、;p>　　-1,-1,-1, 0, 0,　　-2,-2,-2, 0, 0　　};// 負(fù)數(shù)代表此時(shí)可規(guī)約，即r，第二維0-5分別代表a b # S B,-4表示acc　　int cnt[]={0,'S'*10+2,'B'*10+2,'B'*10+1};// 表

94、示ri的產(chǎn)生式的左邊變量和右邊長(zhǎng)度　　int exch(char ch)　　{　　switch(ch)　　{　　case 'a': ret

95、urn 0;　　case 'b': return 1;　　case '#':　　case'\0': return 2; //字符串結(jié)束標(biāo)志代表‘#'.　　case 'S&

96、#39;: return 3;　　case 'B': return 4;　　default: return -1;　　}　　}　　void

97、 judge(char *s)　　{　　int int_stack[100],ti=0,tc=0,i=1,cur,k=exch(s[0]);　　char char_stack[100];　　int_stack[++ti]=0;<

98、/p>　　while(ti>0)　　{　　cur = int_stack[ti];　　if(k<0||action[cur][k]==0) // 踩空，或者出現(xiàn)非法字符　　ti

99、 = -1;　　else if(action[cur][k]>0) //入棧，等待規(guī)約　　{　　int_stack[++ti] = action[cur][k]; //數(shù)字棧　　char_stack[++t

100、c] = s[i]; //字符棧　　k = exch(s[i++]);　　}　　else if(action[cur][k] == -4) //規(guī)約完成，說(shuō)明是符合要求　　ti = 0;</

101、p>　　else // 可以規(guī)約　　{　　--i; //說(shuō)明輸入的字符s[i-1]還沒(méi)有用，此時(shí)它不進(jìn)棧，故i--，以便下次取到的是要s[i-1];　　ti -= cnt[ -action[cur][k] ]%10; // 取ri的長(zhǎng)度，出棧這么

102、多個(gè)的字符　　tc -= cnt[ -action[cur][k] ]%10;　　char_stack[++tc] = cnt[ -action[cur][k] ]/10; // 取產(chǎn)生式的左邊變量，進(jìn)行規(guī)約。　　k = exch( char_stack[tc] );

103、　　}　　}　　if(ti == 0)　　printf(" %s √ Right！\n\n",s);　　else printf("

104、 %s × Wrong！\n\n",s);　　}　　int main()　　{　　char str[100];　　prin

105、tf("判斷符號(hào)串是否符合如下文法：\n\n\tS→BB\n\tB→aB\n\tB→b\n\n");　　while(printf("輸入符號(hào)串: ")&&gets(str)&&str[0])　　judge(str);　　re

106、turn 0;　　}　　4.4 程序運(yùn)行截圖　　4.5 小結(jié)　　LR(0)分析器規(guī)約沒(méi)有平時(shí)學(xué)的那么輕松，在實(shí)驗(yàn)的過(guò)程中我還是借助了老師、同學(xué)以及參考書(shū)的力量來(lái)完成改課程設(shè)

眾賞文庫(kù)> 全部分類> 畢業(yè)設(shè)計(jì)

溫馨提示

1. 本站所有資源如無(wú)特殊說(shuō)明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間，僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

編譯原理課程設(shè)計(jì)(c++)-語(yǔ)法分析器

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

編譯原理課程設(shè)計(jì)(c++)-語(yǔ)法分析器

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載