實(shí)驗一詞法分析

1、編譯原理實(shí)驗一詞法分析1. 實(shí)驗?zāi)康耐ㄟ^實(shí)驗掌握詞法分析的理論、原理和方法，為語法分析做準(zhǔn)備。2. 實(shí)驗內(nèi)容：a) 十六進(jìn)制數(shù)識別器：規(guī)定是：必須以十六進(jìn)制數(shù)字打頭，以H結(jié)尾，十六進(jìn)制數(shù)中允許使用的數(shù)字為0-9,字母為A，B，C，D, E, F(分別表示015)。試設(shè)計一個DFA，使它能識別無符號的十六進(jìn)制整數(shù)，并編制相應(yīng)的識別程序。輸入：學(xué)生自行確定符號串的輸入形式，如鍵盤輸入、文本文件、字符數(shù)組等。輸出：標(biāo)識出規(guī)范的符號串與不合規(guī)范的符號串。b) 詞法分析：設(shè)計、編制、調(diào)試一個識別一個 Little語言單詞的詞法分析程序(見附錄1)。輸入：學(xué)生自行確定符號串的輸入形式，如鍵盤輸入、文本文件

2、、字符數(shù)組等。輸出：二元組。3. 實(shí)驗要求：(1) 上機(jī)前編寫完整的實(shí)驗報告，報告中要體現(xiàn)分析設(shè)計 實(shí)現(xiàn)等幾個過程；如無實(shí)驗報告，則取消本次上機(jī)資格，實(shí)驗成績以0分記。(2) 嚴(yán)禁相互抄襲，否則實(shí)驗成績以0分記；(3) 有完整的源代碼，源碼有規(guī)范的注釋，無明顯的語法錯誤；4. 實(shí)驗步驟(1) 分析與設(shè)計a、文法：該語言的十六進(jìn)制，如：0aH，77H，7BH等由以數(shù)字打頭及以 H結(jié)尾；該語言的標(biāo)識符，如：Num， a3，go等由A到Z(or a到z)和0至9所組成；該語言的無符號 的十進(jìn)制，如：8，90，123等由0到9之間的任意數(shù)字組成。由以上可得出該語言的 文法可表示如下：G(S) = (V

3、N，VT，P，S)其中 VN = S，X' Y' Z'，M' W' a，3，Y，卩，u，coVT = 0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f,g,h,i,j,k,l,m, n,o,p,q,r,s,t,u,v,w,x,y,z,A,B,C,D,E,F,G,H,I,G ,K,L,M,N,O,P,Q,R,S,T,U,V ,W,X,Y ,Za = 0|1| 2|3|4|5|6|7|8|93= a|b|c|d|e|f|A|B|C|D|E|FY =g| h|i|j|k|l|m| n|o|p|q|r|s|t|u|v|w|x|y|z|G|H|l|G

4、|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|ZS T X' |Y' |Z'X ' t u |u M 'M ' To |o M 'u T 3 | Yo t a | 3 | YY' T a |a Y'Z ' t a H| a W' HW'1 la W'i fa | 3可見，上式方法中，X '表示出了語言的標(biāo)識符，而Y '表示出了語言的無符號的十進(jìn)制，Z '表示出了語言中的十六進(jìn)制。-上式G(S)文法中，各式右邊只有單個的終結(jié)符號顯然，以上文法 G(S)已

5、是正規(guī)文法。(2) 正規(guī)文法轉(zhuǎn)成正規(guī)式：具體步驟如下：T M ' f 3 | w M '可表示為 M ' f w * 3W' f i 11 W' 可表示為 W' f i * iZ' f a | a Z'可表示為 Z' f a * a 轉(zhuǎn)換成正規(guī)表達(dá)式為： S= u | u w * w | a H | a i * i H | a * a代入可得：S= ( 3 Iy ) | ( 3 |Y ) ( a |3 | Y )*( a | 3 Y ) | a H | a ( a |3 )* ( a |3 )H | a * a(3) 正規(guī)

6、式轉(zhuǎn)成NFA (分裂法)初始的NFA圖下所示：(3|V)|(3|¥)(o|p|vf(a|P|Y)| aH | a (a | p)* (a |0 >H | a經(jīng)過替換規(guī)則替換后得到的最終圖1初始NFA圖NFA圖如下所示:圖2最終的NFA圖(4)NFA轉(zhuǎn)成DFA及 DFA最小化(造表法)對應(yīng)以上的NFA圖，我們可用造表法來表示如下:I1InSA54"衛(wèi)&訓(xùn)©KL23 © FJf23J ©04.E 6,7.8.5.9 Q4.F.340J.9) Q(8.10.9) (71 0F©F.U32網(wǎng)02網(wǎng)卩邛©04;E840d

7、5d9071麗疋;0色剛8.10.9 Q 0F©審0IF.3021,3© 2J3b 1顯然，由圖可看出，狀態(tài) 2與狀態(tài)5等價，而狀態(tài)1與狀態(tài)3等價，這里省去狀態(tài)3和狀態(tài)5，并將所以指向狀態(tài) 3的狀態(tài)都指向狀態(tài)1，指向狀態(tài)5的都指向狀態(tài)2。由 此可畫出最小化的 DFA圖如下：c屮可見，終結(jié)狀態(tài)1表示出了無符號的十進(jìn)制，終結(jié)狀態(tài)2表示出了標(biāo)識符， 狀態(tài)6表示出了十六進(jìn)制的整數(shù)。b、單詞的BNF表示<標(biāo)識符 >-> < 字母 ><字母數(shù)字串><字母數(shù)字串 >->< 字母 ><字母數(shù)字串>|<

8、數(shù)字 ><字母數(shù)字串>|<下劃線 ><字母數(shù)字串>| £<無符號整數(shù) >-> < 數(shù)字 >< 數(shù)字串><數(shù)字串 >-> < 數(shù)字 ><數(shù)字串> | £<加法運(yùn)算符>-> +<減法運(yùn)算符>-> -<大于關(guān)系運(yùn)算符>-> ><大于等于關(guān)系運(yùn)算符>-> > =由此可知，需將單詞分為五種：關(guān)鍵字i標(biāo)識符2常數(shù)3運(yùn)算符4分隔符5printfa0+5mai nb1intc2*(i

9、fstude nt3/)the nsum4=elsek5>returnm6<7>=8<=9!=(2)編碼實(shí)現(xiàn)a、#in elude <stdio.h>main (i nt argc,char *argv)int i,j,state,ERR0R=-1;/* state控制狀態(tài)的轉(zhuǎn)移1表示09數(shù)字，2表示字母，4表示af, 6表示H ,0為未輸入狀態(tài)* ERROR=-1表示未輸入任何字符串=1表示輸入出錯*/char c; /*暫時存放所取得的一個字符*/char *string="","Unsigned Integer"

10、,"Identifier","","","","Hex"/*輸出結(jié)果時用 */for(i=1;i<argc;i+)state=0;/* 初始態(tài)為 0 */ERROR=0;/*控制是否為可識別詞or非法字符*/for(j=0;(c=argvij)!='0'j+)switch(state)case 0:if(c>='0'&&c<='9')state=1;else if(c>='a'&&am

11、p;c<='z')|(c>='A'&&c<='Z') state=2;else ERROR=1;break;/* ERROR=1,表示當(dāng)前字符c為非法字符。*即此時無狀態(tài)可轉(zhuǎn)向。*/case 1:if(c>='0'&&c<='9')state=1;else if(c>='a'&&c<='f)|(c>='A'&&c<='F')state=4;el

12、se if (c='H')state=6;elseERROR=1;break;case 2: if(c>='a'&&c<='z')|(c>='A'&&c<='Z')|(c>='0'&&c<='9') state=2;elseERROR=1;break;case 4: if(c>='0'&&c<='9')|(c>='a'&

13、amp;&c<='f')|(c>='A'&&c<='F') state=4;else if(c='H') state=6;else ERROR=1;break;case 6:ERROR=1;break;/*end switch*/if(ERROR=1) break; /* 退出內(nèi) for 的循環(huán)，完成一個詞的分析。 */ /*end inside-for*/if(ERROR=1)printf("%-15s is a un-identify word!n",argvi);

14、else if(ERROR=0)printf("%-15s is a %sn",argvi,stringstate);/*end outside-for*/* 未輸入任何字符串時 (除文件名外 )*/ if(ERROR=-1) printf("You input nothing!n");exit(0); /* 正常退出程序 */*end main*/b、#include<string.h>#include<stdio.h>#include<stdlib.h>#include<ctype.h>/定義關(guān)鍵字ch

15、ar *table7="continue","main","int","if","then","else","return",TOKEN20,ch;bool zimu(char ch)/ 判斷是否為字母if(ch>='a'&&ch<='z'|ch>='A'&&ch<='Z')return true;elsereturn false;/判斷

16、是否為數(shù)字bool shuzi(char ch)if(ch>='0'&&ch<='9')return true;elsereturn false;int lookup(char *TOKEN) / 關(guān)鍵字匹配函數(shù) , 查詢所述程序中的關(guān)鍵字int m,i;for(i=0;i<6;i+) if(m=strcmp(TOKEN,tablei)=0) return 1;return 0;void out(int c,char *TOKEN)/ 輸出函數(shù) printf("(%d,%s)n",c,TOKEN);void

17、scanner(FILE *fp)/掃描函數(shù)char TOKEN20='0'char ch;int i;ch=fgetc(fp); /獲取字符，指針 fp 并自動指向下一個字符if(zimu(ch) /判斷該字符是否是字母，若 ch 指的是字母，返回非 0，否則返回 0 TOKEN0=ch;ch=fgetc(fp); /fgetc(fp) 從數(shù)據(jù)流中區(qū)下一個字符i=1;while(shuzi(ch)| zimu(ch) / 判斷該字符是否是字母或數(shù)字TOKENi=ch;ch=fgetc(fp);i+;fseek(fp,-1,1);if(lookup(TOKEN) / 判斷是關(guān)鍵

18、字還是普通的標(biāo)識符 out(1,TOKEN);elseout(2,TOKEN);else if(shuzi(ch)TOKEN0=ch;ch=fgetc(fp); /fgetc(fp) 從數(shù)據(jù)流中區(qū)下一個字符 i=1;while(shuzi(ch) / 判斷該字符是否是字母或數(shù)字TOKENi=ch; ch=fgetc(fp); i+;fseek(fp,-1,1); out(3,TOKEN);/判斷運(yùn)算符并輸出else if(ch='+')TOKEN0=ch;out(4,TOKEN);else if(ch='-')TOKEN0=ch;out(4,TOKEN);els

19、e if(ch='*')TOKEN0=ch;out(4,TOKEN);else if(ch='/')TOKEN0=ch;out(4,TOKEN);else if(ch='=')TOKEN0=ch;out(4,TOKEN);else if(ch='>')TOKEN0=ch;out(4,TOKEN);else if(ch='<')TOKEN0=ch;out(4,TOKEN);else if(ch='>=')TOKEN0=ch;out(4,TOKEN);else if(ch='&

20、lt;=')TOKEN0=ch;out(4,TOKEN);else if(ch='!=')TOKEN0=ch;out(4,TOKEN);/判斷分隔符并輸出else if(ch=',')TOKEN0=ch;out(5,TOKEN);else if(ch='')TOKEN0=ch;out(5,TOKEN);else if(ch='')TOKEN0=ch;out(5,TOKEN);else if(ch='')TOKEN0=ch;out(5,TOKEN);else if(ch='(')TOKEN0=

21、ch;out(5,TOKEN);else if(ch=')')TOKEN0=ch;out(5,TOKEN);main()FILE *fp;/ 讀取文件內(nèi)容，并返回文件指針，該指針指向文件的第一個字符 if(fp=fopen("E:222.txt","r")=NULL)fprintf(stderr,"error opening.n");exit(1); doch=fgetc(fp);if(ch='#')文件以#結(jié)尾，作為掃描結(jié)束條件break;if(ch='')如果是空格，自動跳到下個字符

22、sca nn er(fp);elsefseek(fp,-1,1);/如果不是空格，則回退一個字符并掃描sca nn er(fp);while(ch!='#');return 0;(3)系統(tǒng)調(diào)試a、tiello123 7AH 803Hhelloz 匚:WINDOWS5ystem3Zci123 7AH 0陰H n3 7chI dentif iei* Unsigned Integer HexHexIdentif ier un-identif y wordtb、5.實(shí)驗總結(jié)通過此次實(shí)驗，使我意識到在做實(shí)驗之前一定要認(rèn)真復(fù)習(xí)課本內(nèi)容和老師的要求以 此來確定該實(shí)驗要我們實(shí)現(xiàn)的是什么，怎么實(shí)

23、現(xiàn)，每一步的步驟都要按照流程圖認(rèn)真的去完成，做實(shí)驗不能有半點(diǎn)馬虎。此外，讓我了解到如何設(shè)計、編制并調(diào)試詞法分析程序，加深 對詞法分析原理的理解；實(shí)驗核心的部分在于如何識別初各個單詞的所屬類別，實(shí)驗前可先規(guī)劃一下試驗流程，這樣編寫起來比較方便容易。這次的實(shí)驗使我熟悉了構(gòu)造詞法分析程序的手工方式的相關(guān)原理，也鍛煉了自己編寫算法以及C語言的能力，雖然在試驗過程中存在著很多的不足，但經(jīng)過老師以及同學(xué)的指點(diǎn) 再加上自己的努力都一一克服了， 今后我也會經(jīng)常通過自己編寫此類的代碼來提高自己的能 力。附錄1Littlevprogram>:=<seque nce> vseque nce>

24、:=<se nten ce> <se nten ce> <se nten ce>:=<in put senten ce>|<output senten ce>|<evaluate senten ce>|<c on diti on senten ce>|<determ inacy loop senten ce>| <in determ inacy loop senten ce><in put senten ce>:=read<variable> <variab

25、le> voutput senten ce>:=write <variable> <variable> vevaluate senten ce>:=<variable>=<expressi on><con diti on senten ce>:=f vcompare expressi on ihenvseque nce> pls呱seque nce>i vdeterm inacy loop senten ce>:=o<expressi on >dovseque nce：end<in determ inacy loop senten ce>:=while<compare expressi on:dovseque nce>md vcompare expressi on> >:=<exp