編譯原理課程設(shè)計LL文法

1、前 言本次課程設(shè)計主要是介紹LL(1)文法的一般原理，根據(jù)給定的一文法編制調(diào)試LL(1)文法語法分析程序，以便對任意輸入的符號串進(jìn)行分析。本次課程設(shè)計的目的主要是加深對預(yù)測分析LL(1)文法語法分析的理解，加深對自頂向下語法分析方法的認(rèn)識。具體如下：1、 對語法規(guī)則有明確的定義；2、 編寫的分析程序能夠?qū)o定文法進(jìn)行正確的語法分析；3、 對輸入給定的文法，手工計算First、Follow集合以及各產(chǎn)生式的Select 集合，再根據(jù)Select集合構(gòu)造出預(yù)測分析表；4、 對于輸入串，應(yīng)能根據(jù)預(yù)測分析表判斷識別該輸入串是否為給定文法的句子；5、 對于遇到的錯誤，給出簡單的錯誤信息提示，保證能夠順利

2、完成語法分析過程。目 錄前言- 目錄- 1、 系統(tǒng)分析- 1 1.1 判斷LL(1)文法- 1 1.2 構(gòu)造預(yù)測分析表- 1二、系統(tǒng)設(shè)計- 2 2.1 基本設(shè)計- 2 2.2 程序流程圖- 2三、系統(tǒng)實(shí)現(xiàn)- 3 3.1 程序主要函數(shù)- 3 3.2 程序主要代碼- 34、 系統(tǒng)測試- 75、 總結(jié)- 8參考文獻(xiàn)- 91、 系統(tǒng)分析有文法GE：E->TG T->FS G->+TG| S->*FS| F->(E)|i1.1 判斷LL(1)文法 當(dāng)我們需選用自頂向下分析技術(shù)時，首先必須判別所給文法是否是LL(1)文法，分析所給文法可知文法中不含左公因子，也不存在左遞歸，因

3、而再對給定文法計算First集、Follow集以及Select集，對于求出的每個產(chǎn)生式的Select集，看對于同一個左部非終結(jié)符是否存在交集，如果它們的交為空則表示所給文法是LL(1)文法，否則不是L(1)文法。若所給文法是LL(1)文法，再根據(jù)求得的Select集合構(gòu)造預(yù)測分析表，對于一個輸入串，根據(jù)已知的預(yù)測分析表分析它是否是文法的句子。各非終結(jié)符的First集以及Follow集如下表所示：集合表1-1VNFirst集Follow集E(,i#,)T(,i+,#,)G+,#,)F(,i*,+,#S*,+,#,)各產(chǎn)生式的Select集：Select(E->TG)=(,iSelect(T

4、->FS)=(,iSelect(G->+TG)=+ Select(G->)=#,)Select(S->*FS)=* Select(S->)=+,#,)Select(F->(E)=( Select(F->i)=i由各產(chǎn)生式的Select集可以看出，每個非終結(jié)符的Select集交集為空，則可以確定該文法是LL(1)文法。1.2 構(gòu)造預(yù)測分析表表1-2VNVT+*i()#E->TG->TGT->FS->FSG->+TG->->F->->*FS->->S->i->(E)2、 系統(tǒng)設(shè)計

5、2.1 基本設(shè)計 在程序中有構(gòu)造預(yù)測分析表，在對每個輸入字符進(jìn)行分析的時候與預(yù)測分析表比較，在分析棧中初始元素是#與開始符E，當(dāng)分析棧棧頂元素遇到輸入串棧的棧頂元素時搜索預(yù)測分析表，看是否有相應(yīng)的產(chǎn)生式，若有產(chǎn)生式則用產(chǎn)生式右部符號串代替分析棧中的棧頂元素，不過是以倒序形式壓入分析棧，再進(jìn)行下一步的分析，若是分析棧棧頂元素與輸入串棧頂元素匹配則將分析棧與輸入串棧頂元素出棧，再進(jìn)行下一步的分析，如果不匹配且沒有找到相應(yīng)的產(chǎn)生式，則停止分析，并給出提示錯誤信息。開始2.2 程序流程圖結(jié)構(gòu)體賦值預(yù)測分析表構(gòu)造讀入分析串有非法字符T提示錯誤F為終結(jié)符FTTF產(chǎn)生式T匹配提示錯誤出棧FFT為空提示錯誤不

6、入棧逆序入棧T分析成功FTF匹配分析結(jié)束提示錯誤圖2-13、 系統(tǒng)實(shí)現(xiàn)3.1 程序主要函數(shù)1、 void print()；輸出分析棧2、 void print1()；輸出剩余串3、 int main()；程序主函數(shù)，在其中調(diào)用自定義函數(shù)，完成文法產(chǎn)生式的賦值，預(yù)測分析表的構(gòu)建，以及對輸入串的分析等主要功能。3.2 程序主要代碼1、初始化程序即分析棧、剩余串、非終結(jié)符與終結(jié)符的初始化char A20;/*分析棧*/ char B20;/*剩余串*/ char v120='i','+','*','(',')','

7、;#'/*終結(jié)符 */ char v220='E','G','T','S','F'/*非終結(jié)符 */ int j=0,b=0,top=0,l;2、結(jié)構(gòu)體的定義及結(jié)構(gòu)體變量定義 typedef struct type char origin;/*大寫字符 */ char array5;/*產(chǎn)生式右邊字符 */ int length;/*字符個數(shù) */ type; type e,t,g,g1,s,s1,f,f1;/*結(jié)構(gòu)體變量 */ type C1010;/*預(yù)測分析表 */ 3、輸出分析棧函數(shù)定義void p

8、rint() int a; for(a=0;a<=top+1;a+) printf("%c",Aa); printf("tt"); 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)體 e.origin='E' strcpy(e.array,

9、"TG"); e.length=2; t.origin='T' strcpy(t.array,"FS"); t.length=2; g.origin='G' strcpy(g.array,"+TG"); g.length=3; g1.origin='G' g1.array0='' g1.length=1; s.origin='S' strcpy(s.array,"*FS"); s.length=3; s1.origin='S&#

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

11、=t; C31=s1;C32=s;C34=C35=s1; C40=f1;C43=f; 7、讀入分析串，對輸入串進(jìn)行分析，判斷輸入串是否符合文法的定義，是否有非法字符，是否在分析過程中出現(xiàn)錯誤信息，是否被接受為文法的句子 do scanf("%c",&ch); if(ch!='i')&&(ch!='+')&&(ch!='*')&&(ch!='(')&&(ch!=')')&&(ch!='#') p

12、rintf("輸入串中有非法字符n"); exit(1); Bj=ch; j+; while(ch!='#'); l=j;/*分析串長度*/ ch=B0;/*當(dāng)前分析字符*/ Atop='#' A+top='E'/*'#','E'進(jìn)棧*/ printf("步驟tt分析棧 tt剩余字符 tt產(chǎn)生式或匹配 n"); do x=Atop-;/*x為當(dāng)前棧頂字符*/ printf("%d",k+); printf("tt"); for(j=0;

13、j<=5;j+)/*判斷是否為終結(jié)符*/ if(x=v1j) flag=1; break; if(flag=1)/*如果是終結(jié)符*/ if(x='#') finish=1;/*結(jié)束標(biāo)記*/ printf("accept!n");/*接受 */ getchar(); getchar(); exit(1); if(x=ch) print(); print1(); printf("%c匹配n",ch); ch=B+b;/*下一個輸入字符*/ flag=0;/*恢復(fù)標(biāo)記*/ /*if*/ else/*出錯處理*/ print(); prin

14、t1(); printf("%c出錯n",ch);/*輸出出錯終結(jié)符*/ exit(1); /*else*/ /*if*/ else/*非終結(jié)符處理*/ for(j=0;j<=4;j+) if(x=v2j) m=j;/*行號*/ break; for(j=0;j<=5;j+) if(ch=v1j) n=j;/*列號*/ break; cha=Cmn; if(cha.origin!='N')/*判斷是否為空*/ print(); print1(); printf("%c->",cha.origin);/*輸出產(chǎn)生式*/ f

15、or(j=0;j<cha.length;j+) printf("%c",cha.arrayj); printf("n"); for(j=(cha.length-1);j>=0;j-)/*產(chǎn)生式逆序入棧*/ A+top=cha.arrayj; if(Atop='')/*為空則不進(jìn)棧*/ top-; /*if*/ else/*出錯處理*/ print(); print1(); printf("%c出錯n",x);/*輸出出錯非終結(jié)符*/ exit(1); while(finish=0); 4、 系統(tǒng)測試1、 輸

16、入非法字符，提示輸入串中有非法字符圖4-12、 分析過程出錯，提示出錯信息圖4-23、 分析成功，提示accept！圖4-35、 總結(jié)經(jīng)過學(xué)習(xí)實(shí)現(xiàn)了對LL(1)文法語法分析，我比原來更加了解了LL(1)文法的分析過程及實(shí)現(xiàn)方法，學(xué)會設(shè)計、編制、調(diào)試語法及語義分析程序，加深了對語法及語義分析原理的理解，并且能夠?qū)斎氲姆柎M(jìn)行LL(1)文法分析，經(jīng)過對輸入串與分析棧的比較，可以知道輸入的符號串是不是定義文法的句。在實(shí)驗(yàn)的過程中，有遇到些許問題，最后在同學(xué)和指導(dǎo)老師的幫助下得以解決。經(jīng)過這次課程設(shè)計的練習(xí)，我感覺自己對于C語言有了更深層次的認(rèn)識，不論是在編程實(shí)踐上還是理論學(xué)習(xí)上都有一定的提高，自

17、身的能力得到了鍛煉，是一次很好的實(shí)踐活動，對以后的學(xué)習(xí)有很大的幫助。在寫課程設(shè)計文檔的時候，主要是根據(jù)所學(xué)習(xí)的軟件工程開發(fā)步驟一步一步實(shí)現(xiàn)的，軟件工程對于軟件開發(fā)的整體過程有很好的控制與指導(dǎo)，所以通過這次的學(xué)習(xí)對軟件開發(fā)一般的模式也有了更進(jìn)一步的了解。個人覺得在整個設(shè)計還不是很完美，對于一專業(yè)知識掌握地還不是很好，一些很基本的編程要求有時候一時還想不起來，所以平時還是要多學(xué)習(xí)，多多練習(xí)，提高編程實(shí)戰(zhàn)經(jīng)驗(yàn)，以便取得更好的進(jìn)步！參考文獻(xiàn)2 王雷，劉志成等.編譯原理課程設(shè)計M.北京:電子工業(yè)出版社,20023 何炎祥等.編譯程序構(gòu)造M.武漢:武漢大學(xué)出版社,19885 Holub A.Compile

18、r Design in CM.Prentice-Hall,1990源程序代碼#include<stdio.h> #include<stdlib.h> #include<string.h> #include<dos.h> char A20;/*分析棧*/ char B20;/*剩余串*/ char v120='i','+','*','(',')','#'/*終結(jié)符 */ char v220='E','G','T&#

19、39;,'S','F'/*非終結(jié)符 */ int j=0,b=0,top=0,l;/*L為輸入串長度 */ typedef struct type/*產(chǎn)生式類型定義 */ char origin;/*大寫字符 */ char array5;/*產(chǎn)生式右邊字符 */ int length;/*字符個數(shù) */ type; type e,t,g,g1,s,s1,f,f1;/*結(jié)構(gòu)體變量 */ type C1010;/*預(yù)測分析表 */ void print()/*輸出分析棧 */ int a;/*指針*/ for(a=0;a<=top+1;a+) printf(

20、"%c",Aa); printf("tt"); void print1()/*輸出剩余串*/ int j; for(j=0;j<b;j+)/*輸出對齊符*/ 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

21、' strcpy(e.array,"TG"); e.length=2; t.origin='T' strcpy(t.array,"FS"); t.length=2; g.origin='G' strcpy(g.array,"+TG"); g.length=3; g1.origin='G' g1.array0='' g1.length=1; s.origin='S' strcpy(s.array,"*FS"); s.length=

22、3; s1.origin='S' s1.array0='' s1.length=1; f.origin='F' strcpy(f.array,"(E)"); f.length=3; f1.origin='F' f1.array0='i' f1.length=1; for(m=0;m<=4;m+)/*初始化分析表*/ for(n=0;n<=5;n+) Cmn.origin='N'/*全部賦為空*/ /*填充分析表*/ C00=e;C03=e; C11=g;C14=g1;

23、C15=g1; C20=t;C23=t; C31=s1;C32=s;C34=C35=s1; C40=f1;C43=f; printf("提示:本程序只能對由'i','+','*','(',')'構(gòu)成的以'#'結(jié)束的字符串進(jìn)行分析,n"); printf("請輸入要分析的字符串:"); do/*讀入分析串*/ scanf("%c",&ch); if (ch!='i') &&(ch!='+'

24、;) &&(ch!='*')&&(ch!='(')&&(ch!=')')&&(ch!='#') printf("輸入串中有非法字符n"); exit(1); Bj=ch; j+; while(ch!='#'); l=j;/*分析串長度*/ ch=B0;/*當(dāng)前分析字符*/ Atop='#' A+top='E'/*'#','E'進(jìn)棧*/ printf("步驟tt分析棧 tt剩余字符 tt產(chǎn)生式或匹配 n"); do x=Atop-;/*x為當(dāng)前棧頂字符*/ printf("%d",k+); printf("tt"); for(j=0;j<=5;j+)/*判斷是否為終結(jié)符*/ if(x=v1j) flag=1; break; if(flag=1)/*如果是終結(jié)符*/