實(shí)驗(yàn)三語法分析的C語言實(shí)現(xiàn)(DOC)

1、實(shí)驗(yàn)三語法分析的C語言實(shí)現(xiàn)一、 實(shí)驗(yàn)?zāi)康募由顚?duì)語法分析器工作過程的理解；能夠采用一種編程語言實(shí)現(xiàn)簡(jiǎn)單的語法分析程序; 能夠使用自己編寫的分析程序?qū)?jiǎn)單的程序段進(jìn)行語法分析。一、實(shí)驗(yàn)要求1、在實(shí)驗(yàn)一(用C語言實(shí)現(xiàn)詞法分析的程序 )的基礎(chǔ)上，實(shí)現(xiàn)編寫語法分析程序，語法 分析程序的實(shí)現(xiàn)可以采用任何一種編程工具。2、對(duì)語法規(guī)則有明確的定義；3、編寫的分析程序能夠?qū)?shí)驗(yàn)一的結(jié)果進(jìn)行正確的語法分析；4、對(duì)于遇到的 語法錯(cuò)誤，能夠做出簡(jiǎn)單的錯(cuò)誤處理，給出簡(jiǎn)單的錯(cuò)誤提示，保證順利 完成語法分析過程；、實(shí)驗(yàn)分工個(gè)人完成四、程序說明 有文法 GE: E->TGT->FSG->+TG| S->

2、;*FS|=E| F->(E)|i1.1判斷LL(1)文法當(dāng)我們需選用自頂向下分析技術(shù)時(shí)，首先必須判別所給文法是否是LL(1)文法，分析所給文法可知文法中不含左公因子，也不存在左遞歸，因而再對(duì)給定文法計(jì)算First集、Follow集以及Select集，對(duì)于求出的每個(gè)產(chǎn)生式的 Select 集，看對(duì)于同一個(gè)左部非終結(jié)符是否存在交集，如果它們的交為空則表示所給文法是LL(1)文法，否則不是L(1)文法。若所給文法是LL(1)文法，再根據(jù)求得的 Select集合構(gòu)造預(yù)測(cè)分析表，對(duì)于一個(gè)輸入串，根據(jù)已知的預(yù)測(cè)分析表分析它 是否是文法的句子。各非終結(jié)符的First集以及Follow集如下表所示：表

3、1-1VNFirst 集Follow 集E(,i#,)T(,i+,#,)G+, e#,)F(,i*，+，=，#S*, = , e +,#,)各產(chǎn)生式的Select集:Select(E->TG)=(,iSelect(T->FS)=(,i£ )=#，)£ )=+,#,) Select(S->=E)=每個(gè)非終結(jié)符的Select集交集為空，則可以Select(G->+TG)=+ Select(G-> Select(S->*FS)=* Select(S-> Select(F->(E)=( Select(F->i)=i 由各產(chǎn)生式的

4、Select集可以看出， 確定該文法是LL(1)文法。1.2構(gòu)造預(yù)測(cè)分析表表1-2i+*()#=E->TG->TG->TGT->FS->FS->FSG->+TG-> £-> £F-> £->*FS-> £-> £S->i->(E)->=E程序流程圖主要函數(shù)介紹：1、 void print();輸出分析棧2、 void print1();輸出剩余串3、int main();程序主函數(shù)，在其中調(diào)用自定義函數(shù)，完成文法產(chǎn)生式的賦值, 預(yù)測(cè)分析表的構(gòu)建，以及

5、對(duì)輸入串的分析等主要功能。程序主要代碼：1、初始化程序即分析棧、剩余串、非終結(jié)符與終結(jié)符的初始化char A20;/* 分析棧 */ char B20;/* 剩余串 */ char v120='i','+','*','(',')','#','','='/* char v220='E','G','T','S','F'/* int j=0,b=0,top=0,l;/*L 為輸入串長(zhǎng)度 2、結(jié)構(gòu)

6、體的定義及結(jié)構(gòu)體變量定義 typedef struct type/* 產(chǎn)生式類型定義 char origin;/* char array5;/* int length;/* type;終結(jié)符 */非終結(jié)符 */*/*/大寫字符 */ 產(chǎn)生式右邊字符 */ 字符個(gè)數(shù) */type c,e,t,g,g1,s,s1,f,f1,s2;/* 結(jié)構(gòu)體變量 */ type C1010;/* 預(yù)測(cè)分析表 */ 3、輸出分析棧函數(shù)定義 void print() int a; for(a=0;a<=top+1;a+) printf("%c",Aa); printf("tt&qu

7、ot;);4、輸出剩余串函數(shù)定義 void print1() int j; for(j=0;j<b;j+) printf(" "); for(j=b;j<=l;j+) printf("%c",Bj); printf("ttt");5、在 main 函數(shù)中定義結(jié)構(gòu)體，把文法產(chǎn)生式賦值給結(jié)構(gòu)體 /* 把文法產(chǎn)生式賦值結(jié)構(gòu)體 */e. origin='E' strcpy(e.array,"TG");e. length=2; t.origin='T' strcpy(t.array

8、,"FS"); t.length=2; g.origin='G' strcpy(g.array,"+TG");g.length=3; g1.origin='G'g1.array0-A'g1.length=1;s.origin='S'strcpy(s.array,"*FS");s.length=3;s1.origin='S's1.array0-A's1.length=1;f. origin='F'strcpy(f.array,"(E

9、)");f. length=3;f1.origin='F'f1.array0='i'f1.length=1; s2.origin='S'strcpy(s2.array,"=E");s2.length=2;6、預(yù)測(cè)分析表的初始化及構(gòu)造for(m=0;m<=7;m+)/* 初始化分析表 */for(n=0;n<=7;n+)全部賦為空 */Cmn.origin='N'/*/* 填充分析表 */C00=e;C03=e;C11=g;C14=g1;C15=C17=g1;C20=t;C23=t;C31=

10、s1;C32=s;C34=C35=s1;C37=s2;C40=f1;C43=f;7、讀入分析串，對(duì)輸入串進(jìn)行分析，判斷輸入串是否符合文法的定義，是否有 非法字符，是否在分析過程中出現(xiàn)錯(cuò)誤信息，是否被接受為文法的句子 dox=Atop-;/*x為當(dāng)前棧頂字符 */printf("%d",k+); printf("tt");判斷是否為終結(jié)符 */for(j=0;j<=7;j+)/*if(x=v1j)flag=1;break;if(flag=1)/* 如果是終結(jié)符 */if(x='#')finish=1;/* 結(jié)束標(biāo)記 */ printf

11、("accept!n");/*接受 */getchar(); getchar(); exit(1);匹配 n",ch);下一個(gè)輸入字符 */ 恢復(fù)標(biāo)記 */ if(x=ch) print(); print1(); printf("%c ch=B+b;/* flag=0;/* /*if*/else/* 出錯(cuò)處理 */ print(); print1();printf("%c 出錯(cuò)n",ch);/*輸出出錯(cuò)終結(jié)符*/exit(1);/*else*/ /*if*/ else/* 非終結(jié)符處理 */ for(j=0;j<=7;j+) i

12、f(x=v2j) m=j;/* 行號(hào)*/ break; for(j=0;j<=7;j+) if(ch=v1j) n=j;/* 列號(hào)*/ break;判斷是否為空 */ cha=Cmn; if(cha.origin!='N')/*輸出產(chǎn)生式 */print(); print1(); printf("%c->",cha.origin);/* for(j=0;j<cha.length;j+) printf("%c",cha.arrayj);產(chǎn)生式逆序入棧 */printf("n"); for(j=(cha.

13、length-1);j>=0;j-)/* A+top=cha.arrayj;if(Atop='")/*為空則不進(jìn)棧*/top-;/*if*/else/* 出錯(cuò)處理 */print(); print1();*/printf("%c 出錯(cuò) n",x);/* 輸出出錯(cuò)非終結(jié)符 exit(1);while(finish=0); 編程中遇到的問題： 棧的判斷出錯(cuò)，無法對(duì)應(yīng)和自行從終結(jié)符中提取 預(yù)測(cè)分析表出錯(cuò)，定義后無法識(shí)別總有很多問題卡住，于是根 替換所有的字母數(shù)字可改進(jìn)的地方： 1、由于一個(gè)人實(shí)驗(yàn)，工作量實(shí)在太大，實(shí)力不足， 據(jù)書本先行使用書本文法進(jìn)行編輯，

14、先行使用 i2、由于時(shí)間關(guān)系，沒法對(duì) i 進(jìn)行改動(dòng)區(qū)分開所有的字母數(shù)字，仍舊使用 i 進(jìn)行 操作判斷3、由于沒對(duì) i 進(jìn)行編輯改動(dòng)， 導(dǎo)致了 while 以及 if 語句未能插入代碼中， 只能 識(shí)別出賦值語句4、做這份代碼是太多太多的辛酸，認(rèn)識(shí)到了實(shí)力不足時(shí)團(tuán)隊(duì)的重要性，還望老 師諒解 五、截圖亡"iUR：J hEyJZiocijrricntiC-FrrtT«iTipV*m湼亍:十匡Z只菱對(duì)白"分析的抑舉:f：/ 另析棧 占£ iGT iGSF 城£i 崛£ iGE= UGl iGGT CGSF (CGS)EC MCGS)E iCGS

15、)GT acCS)CSF iCCS)CSi tjCCS)CS iGCS)G iGCSjCT+ iGCSjGT iGCSJCSF iGGSJG 呂 i iGGSJGS iGGSJG iGGSJ iGGS iGCSF* iGGSF iGCSitsti = (i*i>itf i=(i*i)*i« =(i*i)*i« =(i+i)*i#產(chǎn)生式或匹配E->TCT-?FS F->i i匹配101112IS1415IT1勺輕2122232i?5P6tf tf -1 rl rl i * + * *).f=-.P r _ _ _ ' 'L ：UEjrsJnh

16、ir. .p-z-turr.zntt'.C -RrecTzr.tiGE= 那 iGGT iGGSF iGG31E< iGGSlE 期GGGT iGGSlGSF iGGGGSi iGCS)CS iGCS)G itCGS)GT (CGS)GT iCdSjGSF iCGSjCSi iCCSjCS iCCS)C flCCS) iGCS iGCSF* iGGEF iGCSj UGGS iGG 崛 asept!*iKHitai+L)+L# i+i) *訶tJ*L#L)+Lff L)+ Lff=匹配 E->TC T->rs F->(E) (ra £->TC T

17、->FSS-> Q-y-mT->rs）匹配 S->*FS *匹配 F->i i匹配=5紀(jì) E-yre T->FS F-XE) (匹配 E->TC T->FSG-HGT->F£s->+rs *兀配 r->iF->i i匹配+匹配F->i i匹配F-i i匹配*匹配F->i i匹配六、#in cludevstdio.h>#in clude<iostream>#in clude<stdlib.h>#in clude<dos.h>#in clude<stri n

18、g>using n ames pace std;char A20;/* 分析棧 */char B20;/* 剩余串 */char v120='i','+','*','(',')',#,'','='/* 終結(jié)符 */ char v220='E','G',T,'S','F'/* 非終結(jié)符 */int j=0,b=0,top=0,l;/*L 為輸入串長(zhǎng)度 */ typ edef struct typ e/*產(chǎn)生式類型定義

19、 */char origin;/* 大寫字符 */char array5 ;/*產(chǎn)生式右邊字符*/int length;/* 字符個(gè)數(shù) */type;type C,e,t,g,g1,s,s1,f,f1,s2;/結(jié)構(gòu)體變量 */type C1010;/* 預(yù)測(cè)分析表 */ void print()/* 輸出分析棧 */int a;/* 指針*/ for(a=0;a<=top+1;a+) printf("%c",Aa); printf("tt");void print1 ()/*輸出剩余串 */int j;for(j=0;j<b;j+)/* 輸出

20、對(duì)齊符 */printf(" ");for(j=b;j<=l;j+)printf("%c",Bj);printf("ttt");int main()int m,n,k=0,flag=0,finish=0; char ch,x;type Cha;/*用來接受 Cmn*/*把文法產(chǎn)生式賦值結(jié)構(gòu)體 */ e.origin='E'strCpy(e.array,"TG");e.length=2;t.origin='T' strCpy(t.array,"FS");t.l

21、ength=2;g. origin='G' strCpy(g.array,"+TG");g. length=3;g1.origin='G'g1.array0-A'g1.length=1;s.origin='S'strcpy(s.array,"*FS");s.length=3;s1.origin='S's1.array0='A's1.length=1;f.origin='F'strcpy(f.array,"(E)");f.length

22、=3;f1.origin='F'f1.array0='i'f1.length=1;s2.origin='S'strcpy(s2.array,"=E");s2.length=2;for(m=0;m<=7;m+)/* 初始化分析表 */for(n=0;n<=7;n+)Cmn.origin='N'/* 全部賦為空 */* 填充分析表 */C00=e;C03=e;C11=g;C14=g1;C15=C17=g1;C20=t;C23=t;C31=s1;C32=s;C34=C35=s1;C37=s2;C40=f1

23、;C43=f;printf("提示:本程序只能對(duì)由i','+','*','(',')'構(gòu)成的以#結(jié)束的字符串進(jìn)行分析，n"); printf(" 請(qǐng)輸入要分析的字符串 :");FILE * fpin;char in_fn30;/存放地址for(;)cin>>in_fn;if(fpin=fopen(in_fn,"r")!=NULL) / 判斷文件是否存在break;elsecoutvv"文件路徑錯(cuò)誤！" do/* 讀入分析串 */ c

24、h=fgetc(fpin); if (ch!='i') &&(ch!='+') &&(ch!='*')&&(ch!='(')&&(ch!=')')&&(ch!='#')&&(ch!='=')&&(ch!='')printf(" 輸入串中有非法字符 n");exit(1);Bj=ch;j+;while(ch!='#');l=

25、j;/* 分析串長(zhǎng)度 */ ch=B0;/* 當(dāng)前分析字符 */Atop='#' A+top='E'/*'#','E' 進(jìn)棧*/printf("步驟tt分析棧tt剩余字符tt產(chǎn)生式或匹配n"); dox=Atop-;/*x 為當(dāng)前棧頂字符 */printf("%d",k+);printf("tt");for(j=0;j<=7;j+)/* 判斷是否為終結(jié)符 */if(x=v1j) flag=1;break;if(flag=1)/* 如果是終結(jié)符 */if(x='#')finish=1;/* 結(jié)束標(biāo)記*/printf("accept!n");/* 接受 */get