編譯原理法分析語法分析試驗報告

1、編譯原理實驗報告一.LL（1）文法分析1. 設(shè)計要求（1） 對輸入文法，它能判斷是否為 LL（1）文法，若是，則轉(zhuǎn)（2）;否則報錯并 終止；（2）輸入已知文法，由程序自動生成它的 LL（1）分析表；（3）對于給定的輸入串，應(yīng)能判斷識別該串是否為給定文法的句型。2. 分析該程序可分為如下幾步：（1）讀入文法（2）判斷正誤（3）若無誤，判斷是否為LL（1）文法（4）若是，構(gòu)造分析表；（5）由總控算法判斷輸入符號串是否為該文法的句型。3. 流程圖4.源程序/* 語法分析程序作者： xxx學(xué)號： xxx*#include#include#include/*int count=0; int number

2、; char start;char termin50;/* 分解的產(chǎn)生式的個數(shù) */* 所有終結(jié)符和非終結(jié)符的總數(shù) */* 開始符號 */* 終結(jié)符號 */char non_ter50;char v50;char left50;/* 非終結(jié)符號 */* 所有符號 */* 左部 */char right5050;/*右部 */char first5050,follow5050;/* 各產(chǎn)生式右部的 FIRST 和左部的 FOLLOW 集合 */char first15050; char select5050;char f50,F50;char empty20;char TEMP50;/*所有單個

3、符號的 FIRST 集合 */*各單個產(chǎn)生式的 SELECT 集合*/* 記錄各符號的 FIRST 和 FOLLOW 是否已求過 */ /*記錄可直接推出A的符號*/*求 FOLLOW 時存放某一符號串的 FIRST 集合*/int validity=1;int ll=1;int M2020;/*表示輸入文法是否有效 */* 表示輸入文法是否為 LL(1) 文法 */*分析表 */char choose;char empt20;char fo20;/*用戶輸入時使用 */*求_emp()時使用*/* 求 FOLLOW 集合時使用 */*判斷一個字符是否在指定字符串中* int in(char

4、c,char *p)int i;if(strlen(p)=0)return(0);for(i=0;i+)if(pi=c) return(1);/* 若在，返回 1*/if(i=strlen(p)return(0);/* 若不在，返回 0*/* 得到一個不是非終結(jié)符的符號*/char c()char c=A;while(in(c,non_ter)=1) c+;return(c); /* 分解含有左遞歸的產(chǎn)生式*/ void recur(char *point)/* 完整的產(chǎn)生式在 point 中*/int j,m=0,n=3,k;char temp20,ch;ch=c(); /* 得到一個非終結(jié)

5、符 */k=strlen(non_ter);non_terk=ch;non_terk+1=0;for(j=0;j=strlen(point)-1;j+)if(pointn=point0)/* 如果 |后的首符號和左部相同 */for(j=n+1;j=strlen(point)-1;j+)while(pointj!=|&pointj!=0)tempm+=pointj+;leftcount=ch;memcpy(rightcount,temp,m);rightcountm=ch;rightcountm+1=0;m=0;count+;if(pointj=|)n=j+1;break;else/* 如果

6、|后的首符號和左部不同*/leftcount=ch;rightcount0=A;rightcount1=0;count+;for(j=n;j=strlen(point)-1;j+)if(pointj!=|)tempm+=pointj;elseleftcount=point0; memcpy(rightcount,temp,m);rightcountm=ch;rightcountm+1=0;printf( count=%d ,count);m=0;count+;leftcount=point0; memcpy(rightcount,temp,m); rightcountm=ch; rightco

7、untm+1=0; count+;m=0;/*分解不含有左遞歸的產(chǎn)生式*/void non_re(char *point)int m=0,j;char temp20;for(j=3;j=strlen(point)-1;j+)if(pointj!=|)tempm+=pointj;elseleftcount=point0; memcpy(rightcount,temp,m); rightcountm=0;m=0;count+;leftcount=point0;memcpy(rightcount,temp,m);rightcountm=0;count+;m=0;/*讀入一個文法 */ char gr

8、ammer(char *t,char *n,char *left,char right5050) char vn50,vt50;char s;char p5050;int i,j,k;printf(n 請輸入文法的非終結(jié)符號串： ); scanf(%s,vn);getchar();i=strlen(vn);memcpy(n,vn,i);ni=0;printf( 請輸入文法的終結(jié)符號串： );scanf(%s,vt);getchar();i=strlen(vt);memcpy(t,vt,i);ti=0;printf( 請輸入文法的開始符號： );scanf(%c,&s);getchar();pr

9、intf( 請輸入文法產(chǎn)生式的條數(shù)： );scanf(%d,&i);getchar();for(j=1;j=i;j+)printf(”請輸入文法的第 %d條(共%d條)產(chǎn)生式： scanf(%s,pj-1);getchar();for(j=0;j) printf(ninput error!);validity=0;return(0);/* 檢測輸入錯誤 */for(k=0;k=i-1;k+)/* 分解輸入的各產(chǎn)生式 */if(pk3=pk0)recur(pk);else non_re(pk); return(s);/* 將單個符號或符號串并入另一符號串*/void merge(char *d,

10、char *s,int type)A 一并并入目串；/*d是目標符號串，s是源串，type= 1,源串中的type= 2，源串中的人不并入目串*/int i,j;for(i=0;i=strlen(s)-1;i+)if(type=2&si=A)Jelsefor(j=0;j+)if(jstrlen(d)&si=dj) break;if(j=strlen(d)dj=si;dj+1=0;break;/*求所有能直接推出A的符號* void emp(char c)/*即求所有由A 推出的符號*/char temp10;int i;for(i=0;i=count-1;i+)if(righti0=c&str

11、len(righti)=1)temp0=lefti;temp1=0;merge(empty,temp,1);emp(lefti);求某一符號能否推出 A*int _emp(char c)/*若能推出，返回1；否則，返回 0*/int i,j,k,result=1,mark=0;char temp20;temp0=c;temp1=0;merge(empt,temp,1);if(in(c,empty)=1)return(1);for(i=0;i+)if(i=count)return(0);if(lefti=c)/*找一個左部為c的產(chǎn)生式*/j=strlen(righti); /*j 為右部的長度

12、*/if(j=1&in(righti0,empty)=1)return(1);else if(j=1&in(righti0,termin)=1)return(0);elsefor(k=0;k=j-1;k+)if(in(rightik,empt)=1)mark=1;if(mark=1)continue;elsefor(k=0;k=j-1;k+) result*=_emp(rightik); temp0=rightik; temp1=0; merge(empt,temp,1);if(result=0&icount)continue;else if(result=1&icount)return(1)

13、; /*判斷讀入的文法是否正確 */ int judge()int i,j;for(i=0;i=count-1;i+)if(in(lefti,non_ter)=0) /* 若左部不在非終結(jié)符中，報錯 */ printf(nerror1!);validity=0;return(0);for(j=0;j=strlen(righti)-1;j+)if(in(rightij,non_ter)=0&in(righ tij,termin)=O&rightij!=A)A ，報錯 */ /* 若右部某一符號不在非終結(jié)符、終結(jié)符中且不為printf(nerror2!);validity=0;return(0);

14、return(1);/*求單個符號的 FIRST*/void first2(int i)/*i 為符號在所有輸入符號中的序號 */char c,temp20;int j,k,m;c=vi;char ch=A;emp(ch);if(in(c,termin)=1)/*若為終結(jié)符 */first1i0=c;first1i1=0;else if(in(c,non_ter)=1)/*若為非終結(jié)符 */for(j=0;j=count-1;j+)if(leftj=c)if(in(rightj0,termin)=1|rightj0=A)temp0=rightj0;temp1=0;merge(first1i,t

15、emp,1);else if(in(rightj0,non_ter)=1)if(rightj0=c)continue;for(k=0;k+)if(vk=rightj0)break;if(fk=0)first2(k);fk=1;merge(first1i,first1k,2);for(k=0;k=strlen(rightj)-1;k+)empt0=0;if(_emp(rightjk)=1&k=O)firstiO=A： firsti1=O;elseTEMPO=a：TEMP1=O;elsefor(j=O;j+)if(vj=pO)break;if(i=O)memcpy(firsti,first1j,s

16、trlen(first1j); firstistrlen(first1j)=O;elsememcpy(TEMP,first1j,strlen(first1j); TEMPstrlen(first1j)=O;else/* 如果右部為符號串 */for(j=O;j+)if(vj=pO) break;if(i=O) merge(firsti,first1j,2);elsemerge(TEMP,first1j,2); for(k=O;k=length-1;k+)empt0=0;if(_emp(pk)=1&k=0) merge(firsti,first1m,2);elsemerge(TEMP,first

17、1m,2);else if(_emp(pk)=1&k=length-1)tempO=A：temp1=0;if(i=O)merge(firsti,temp,1);elsemerge(TEMP,temp,1);else if(_emp(pk)=O)break;/*求各產(chǎn)生式左部的 FOLLOW*/void FOLLOW(int i)int j,k,m,n,result=1;char c,temp2O;c=non_teri;/*c 為待求的非終結(jié)符 */tempO=c;temp1=O;merge(fo,temp,1);if(c=start) /* 若為開始符號 */tempO=#;temp1=O;m

18、erge(followi,temp,1);for(j=O;j=count-1;j+)if(in(c,rightj)=1)/*找一個右部含有c的產(chǎn)生式*/ for(k=0;k+)if(rightjk=c)break;/*k 為 c 在該產(chǎn)生式右部的序號 */for(m=0;m+)if(vm=leftj)break;/*m 為產(chǎn)生式左部非終結(jié)符在所有符號中的序號 */if(k=strlen(rightj)-1)/*如果c在產(chǎn)生式右部的最后*/if(in(vm,fo)=1)merge(followi,followm,1);continue;if(Fm=0)FOLLOW(m); Fm=1; merge

19、(followi,followm,1);else/*如果c不在產(chǎn)生式右部的最后*/for(n=k+1;n=strlen(rightj)-1;n+)empt0=0; result*=_emp(rightjn);if(result=1)/*如果右部c后面的符號串能推出A*/if(in(vm,fo)=1) /*避免循環(huán)遞歸 */merge(followi,followm,1);continue;if(Fm=0)FOLLOW(m);Fm=1;merge(followi,followm,1);for(n=k+1;n=strlen(rightj)-1;n+)tempn-k-1=rightjn;tempst

20、rlen(rightj)-k-1=0;FIRST(-1,temp);merge(followi,TEMP,2);Fi=1;/*判斷讀入文法是否為一個 LL(1) 文法*/int ll1()int i,j,length,result=1;char temp50;for(j=0;j=49;j+)/* 初始化 */firstj0=0;followj0=0;first1j0=0;selectj0=0;TEMPj=0;tempj=0;fj=0;Fj=0;for(j=0;j=strlen(v)-1;j+)first2(j);/*求單個符號的 FIRST 集合 */printf(nfirst1:);for(

21、j=0;j=strlen(v)-1;j+)printf(%c:%s ,vj,first1j);printf(nempty:%s,empty);printf(n:n_emp:);for(j=0;j=strlen(v)-1;j+)printf(%d ,_emp(vj);for(i=0;i=count-1;i+)FIRST(i,righti); /* 求 FIRST*/printf(n);for(j=0;j=strlen(non_ter)-1;j+)/* 求 FOLLOW*/if(foj=0)fo0=0; FOLLOW(j); printf(nfirst:);for(i=0;i=count-1;i+

22、)printf(%s ,firsti); printf(nfollow:); for(i=0;i=strlen(non_ter)-1;i+)printf(%s ,followi); for(i=0;i=count-1;i+) /* 求每一產(chǎn)生式的 SELECT 集合 */ memcpy(selecti,firsti,strlen(firsti);selectistrlen(firsti)=0; for(j=0;j=strlen(righti)-1;j+) result*=_emp(rightij);if(strlen(righ ti)=1 &rightiO=A) result=1;if(res

23、ult=1) for(j=O;j+)if(vj=lefti) break;merge(selecti,followj,1); printf(nselect:); for(i=O;i=count-1;i+)printf(%s ,selecti); memcpy(temp,selectO,strlen(selectO); tempstrlen(selectO)=O; for(i=1;i=count-1;i+) /* 判斷輸入文法是否為 LL(1) 文法 */ length=strlen(temp);if(lefti=lefti-1) merge(temp,selecti,1); if(strlen

24、(temp)length+strlen(selecti) return(O);elsetempO=O;memcpy(temp,selecti,strlen(selecti);tempstrlen(selecti)=0; return(1);/*構(gòu)造分析表 M*/void MM()int i,j,k,m;for(i=0;i=19;i+)for(j=0;j=19;j+) Mij=-1;i=strlen(termin);termini=#;/* 將 #加入終結(jié)符數(shù)組 */termini+1=0;for(i=0;i=count-1;i+)for(m=0;m+)if(non_term=lefti)bre

25、ak; /*m 為產(chǎn)生式左部非終結(jié)符的序號 */ for(j=0;j=O;n-)Sp+=rightmn;Sq+strlen(rightm)=O;printf(nS:%s str:,S);for(p=j;p=strlen(str)-1;p+)printf(%c,strp);printf( );/*一個用戶調(diào)用函數(shù)*/void menu()syntax();printf(n 是否繼續(xù)？ (y or n):);scanf(%c,&choose);getchar();while(choose=y)menu();/*主函數(shù)*/void main()int i,j;start=grammer(termin

26、,non_ter,left,right); /* 讀入一個文法 */ printf(count=%d,count);printf(nstart:%c,start);strcpy(v,non_ter);strcat(v,termin);printf(nv:%s,v);printf(nnon_ter:%s,non_ter);printf(ntermin:%s,termin);printf(nright:);for(i=0;i=count-1;i+)printf(%s ,righti);printf(nleft:);for(i=0;i=count-1;i+)printf(%c ,lefti);if(

27、validity=1)validity=judge();printf(nvalidity=%d,validity);if(validity=1)printf(n 文法有效 );ll=ll1();printf(nll=%d,ll);if(ll=0)printf(n 該文法不是一個 LL1 文法！ );elseMM();printf(n);for(i=0;i=19;i+)for(j=0;j=0)printf(M%d%d=%d ,i,j,Mij);printf(n);menu();5.執(zhí)行結(jié)果(1)輸入一個文法畫女-123 的的產(chǎn)的的的 .iil 文文文文文文nn_te ： ETFfiB BifTi

28、in : -i:ETFAB+-*/*()itart ：E匸+: +-see八MiirbocSXPehugXsynai. eie*i 式式式 匕 -I匕 F c 二 El-z產(chǎn)戶產(chǎn) s - EITS:數(shù)知如知E-E+r SE-T ：TA*FBF9EDBBF-Tfthl0H4J-J M 9 3(6 1-3 M：1I41=7J-7 MC21 E*1 J-S Iir2 JCC J9 MOJISJ-B MCami-lH13JI51-2 nt3JI7J-2 HL43101-6 ML4311J-6 HE4J21-4 14113J-5 H14JI5J-& nL4J71-6 涯培 X滄剛一alldllty=l

29、irstl：E：P： + B 11 0 0Ci * / * (itt+- +t-*z tt +#- m x / nit- ci(2 )輸入一個符號串(3)再次輸入一個符號串，然后退出程序二詞法分析一、問題描述識別簡單語言的單詞符號識別簡單語言的基本字、標識符、無符號整數(shù)、運算符和界符。1題目選擇計算機高級程序語言之一 一一C語言，運用恰當?shù)脑~法分析技術(shù)線路，設(shè)計和實現(xiàn)其對應(yīng)的詞法分析器。單詞符號begi nifthe n while do end l ( l I d )2.要求1).給出一簡單語言單詞符號的種別編碼種別編碼12345610112) .詞法分析程序的功能輸入是源程序字符串，以 #

30、結(jié)束。輸出是單詞符號的二元組。分析器輸出結(jié)果存入到磁盤文件中，具有出錯處理功能3) .建議和提示：技術(shù)線路選擇如下兩種之一：正則式T NF2DFAtmin DFL程序設(shè)計或 正則文法NFAtDFAtmin DFAt程序設(shè)計系統(tǒng)分析詞法分析器對應(yīng)的正則文法表達如下：S 一標示符或關(guān)鍵字|數(shù)字字符|運算符標示符或關(guān)鍵字一 character AA character |number| （標示符或關(guān)鍵字要以字母開 頭）數(shù)字字符number| :（數(shù)字字符只能由數(shù)字組成）character a|b|c |y|z|A|B|C |Y|Znu mber -0|1|2|3|4|5|6|7|8|9運算符 Y|v

31、|v=|=|：|：=|+|-|*|/|=|；|（|）|n該詞法分析程序要識別的字符類別包括關(guān)鍵字，標示符， 數(shù)字字符，運算符，結(jié)束符這里把關(guān)鍵字和標示符歸為同 一類，識別完之后根據(jù)查標示符表得到是標示符還是關(guān)鍵字。 因此對于自動機DFA來說，有幾個相應(yīng)的狀態(tài)，對應(yīng)識別不同 單詞串。當然詞法分析程序還要有過濾空格字符，注釋符號， 回車換行符等一些特殊字符。當詞法分析器遇到符號的時候 就表示詞法分析已經(jīng)完成，程序結(jié)束。三、系統(tǒng)設(shè)計基于以上的討論，我設(shè)計了本實驗詞法分析器的有限自動機的每當讀入完一個字符串后，自動機回到開始狀態(tài) S,讀入下一個字符串的第一個字母。這里所說的字符串是指標示符或 者關(guān)鍵字

32、或者數(shù)字或者特殊符號。當讀入的第一個字符是字母的時候說明這個狀態(tài)機要識別 的是標示符或者字符串，后面的字符可以是字母或者數(shù)字。所 以在標示符或關(guān)鍵字狀態(tài)的時候讀入的下一個字符是字母或者 是數(shù)字的時候其狀態(tài)還是會轉(zhuǎn)向自己；當讀入的下個字符是回 車或空格的時候表示識別完成；當讀入的下個字符是特殊符號的時候（非字母或數(shù)字）按正常思維狀態(tài)應(yīng)轉(zhuǎn)向出錯處理，不過由于本實驗是詞法分析，標示符不合法應(yīng)該是語義分析階段做的事，所以本程序沒有給出出錯處理。識別字符串后還應(yīng)區(qū)分這個單詞是標示符還是關(guān)鍵字。實現(xiàn)過程是查關(guān)鍵字表，將識別的字符串同關(guān)鍵字表中的每一個元素比較，若有相同則說 明識別的是關(guān)鍵字，否則是標示符。

33、當讀入的第一個字符是數(shù)字的時候說明這個狀態(tài)機要識別 的是數(shù)字。后面的字符可以是數(shù)字，表示多位數(shù)。所以在數(shù)字 狀態(tài)的時候讀入的下一個字符是數(shù)字的時候其狀態(tài)還是會轉(zhuǎn)向 自己；當讀入的下個字符是回車或空格的時候表示識別完成； 當讀入的下個字符非數(shù)字時候，會發(fā)生語義錯誤，本程序是詞 法分析所以沒有給出。當讀入的第一個字符是特殊字符的時候說明這個狀態(tài)機要 識別的是特殊字符。雙目特殊字符 （ 如:=,=等 ）后面的字符還可 以是特殊字符。所以在特殊字符狀態(tài)的時候讀入的下一個字符 是特殊字符的時候其狀態(tài)還是會轉(zhuǎn)向自己；當讀入的下個字符 是回車或空格的時候表示識別完成；當讀入的下個字符非數(shù)字 時候，狀態(tài)機理應(yīng)

34、轉(zhuǎn)向出錯處理，不過本程序同樣沒有給出。最后程序讀入符號 #時，說明源程序讀入完畢，程序結(jié)束。四.系統(tǒng)實現(xiàn)程序流程圖如下所示:打開要識別的源程序文件, 初始化關(guān)鍵字表。調(diào)用掃描子程序，對每個字 符串掃描，識別所屬類型。輸出每個單詞二元組。其中syn=O,表示讀到的字符是 #。關(guān)鍵字表設(shè)置代碼如下：“whilechar *rwtab6=“ begin ”， “ if ” ,“thendo” ,“ end” ;這里只給出了六個常用的關(guān)鍵字，真正的編譯器的話應(yīng)該給出所有的關(guān)鍵字。掃描子程序算法:關(guān)鍵字 標示符置 Syn=1-6置syn=10程序源代碼如下：#in clude#in cludechar

35、prog80, toke n8;/prog存儲源程序字符串，token存儲單個字符char ch;FILE * fp;int syn, p, m, n ,sum ;char *rwtab6= begin,if,then,while,do,end ;void scaner();void main(int argc,char* argv)p=0;fp=fopen(./input.txt,r);if(!fp) printf(File open error!n);do ch=getc(fp);progp+=ch ; while ( ch!=#);p=0;fp=fopen(./output.txt,w)

36、;if(!fp) printf(File open error!n);doscaner();switch(syn)case 11:fprintf (fp,%2d,syn);fprintf (fp,%8dn,sum);break; /輸出數(shù)字case -1:fprintf(fp,inpu t errorn); break;/ 出錯case 29: break;/過濾回車default:fprintf (fp,%2d,syn); /輸出保留字或者標識 符fprintf (fp,%8sn,token);while (syn!=0);fclose(fp);void scaner() / 詞法掃描子程序

37、m=0,sum=0;for ( n=0; n=A&ch=a&ch=A&ch=a&ch=0&ch=9)/ 為字母字符或數(shù)字字符tokenm+=ch; ch=progp+;tokenm+=0; / 插入空格p-;syn=10;/種別編碼for (n=0 ; n=0&ch=0&ch=9)sum=sum*10+ch-0;ch=progp+;p- ;syn=11;/數(shù)字的 syn 為 11 elseswitch(ch) case ) /字符為 syn=21; tokenm+=ch; else if (ch=) /字符為 = syn=22; tokenm+=ch;else syn=20; /字符就是 :m=0; tokenm+=ch; ch=progp+;if (ch=) /字符為 = syn=24; tokenm+=ch; syn=23;p-;break;case :m=0; tokenm+=ch; ch=progp+;if (ch=) /字符為 := syn=18; tokenm+=ch; else/ 字符為： syn=18; p-; break;case +: syn=13; token0=ch; break; case -: syn=14; token0=ch;