編譯原理LL(1)語(yǔ)法分析實(shí)驗(yàn)報(bào)告

1、學(xué)號(hào) 20102798 專業(yè) 軟件工程 姓名 薛建東 實(shí)驗(yàn)日期2013.04.08 教師簽字 成績(jī)實(shí) 驗(yàn) 報(bào) 告【實(shí)驗(yàn)名稱】 LL（1）語(yǔ)法分析【實(shí)驗(yàn)?zāi)康摹客ㄟ^(guò)完成預(yù)測(cè)分析法的語(yǔ)法分析程序，了解預(yù)測(cè)分析法和遞歸子程序法的區(qū)別和聯(lián)系。使了解語(yǔ)法分析的功能，掌握語(yǔ)法分析程序設(shè)計(jì)的原理和構(gòu)造方法，訓(xùn)練掌握開(kāi)發(fā)應(yīng)用程序的基本方法?！緦?shí)驗(yàn)內(nèi)容】u 根據(jù)某一文法編制調(diào)試 LL （ 1 ）分析程序，以便對(duì)任意輸入的符號(hào)串進(jìn)行分析。u 構(gòu)造預(yù)測(cè)分析表，并利用分析表和一個(gè)棧來(lái)實(shí)現(xiàn)對(duì)上述程序設(shè)計(jì)語(yǔ)言的分析程序。u 分析法的功能是利用LL（1）控制程序根據(jù)顯示棧棧頂內(nèi)容、向前看符號(hào)以及LL（1）分析表，對(duì)輸入符號(hào)串

2、自上而下的分析過(guò)程。 【設(shè)計(jì)思想】（1）、LL（1）文法的定義LL(1)分析法屬于確定的自頂向下分析方法。LL(1)的含義是：第一個(gè)L表明自頂向下分析是從左向右掃描輸入串，第2個(gè)L表明分析過(guò)程中將使用最左推導(dǎo)，1表明只需向右看一個(gè)符號(hào)便可決定如何推導(dǎo)，即選擇哪個(gè)產(chǎn)生式(規(guī)則)進(jìn)行推導(dǎo)。LL(1)文法的判別需要依次計(jì)算FIRST集、FOLLOW集和SELLECT集,然后判斷是否為L(zhǎng)L(1)文法,最后再進(jìn)行句子分析。需要預(yù)測(cè)分析器對(duì)所給句型進(jìn)行識(shí)別。即在LL(1)分析法中，每當(dāng)在符號(hào)棧的棧頂出現(xiàn)非終極符時(shí)，要預(yù)測(cè)用哪個(gè)產(chǎn)生式的右部去替換該非終極符；當(dāng)出現(xiàn)終結(jié)符時(shí)，判斷其與剩余輸入串的第一個(gè)字符是否

3、匹配，如果匹配，則繼續(xù)分析，否則報(bào)錯(cuò)。LL(1)分析方法要求文法滿足如下條件：對(duì)于任一非終極符A的兩個(gè)不同產(chǎn)生式Aa,Ab，都要滿足下面條件：SELECT(Aa)SELECT(Ab)=（2）、預(yù)測(cè)分析表構(gòu)造LL(1)分析表的作用是對(duì)當(dāng)前非終極符和輸入符號(hào)確定應(yīng)該選擇用哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo)。它的行對(duì)應(yīng)文法的非終極符，列對(duì)應(yīng)終極符，表中的值有兩種：一是產(chǎn)生式的右部的字符串，一是null。若用M表示LL(1)分析表，則M可表示如下：M: VNVTPErrorM(A, t) = A，當(dāng)tselect(A) ，否則M(A, t) = Error其中P表示所有產(chǎn)生式的集合。（3）、語(yǔ)法分析程序構(gòu)造LL(1)

4、分析中X為符號(hào)棧棧頂元素，a為輸入流當(dāng)前字符，E為給定測(cè)試數(shù)據(jù)的開(kāi)始符號(hào)，#為句子括號(hào)即輸入串的括號(hào)。分析表用一個(gè)二位數(shù)組M表示，數(shù)組元素MA，a中的下標(biāo)A表示非終結(jié)符，a為終結(jié)符或句子括號(hào)#，二維數(shù)組中存放的是一條關(guān)于A 的產(chǎn)生式，表明當(dāng)非終結(jié)符A向下推導(dǎo)時(shí)，面臨輸入符a時(shí)，所采用的候選產(chǎn)生式，當(dāng)元素內(nèi)容無(wú)產(chǎn)生式時(shí)，則表明用A 的左部向下推導(dǎo)時(shí)出現(xiàn)了不該出現(xiàn)的符號(hào)，因此元素內(nèi)容轉(zhuǎn)向出錯(cuò)處理的信息。LL(1)分析過(guò)程主要包括以下四個(gè)動(dòng)作：替換：當(dāng)XVN時(shí)選相應(yīng)產(chǎn)生式的右部b去替換X。此時(shí)X出棧，b逆序入棧。匹配：當(dāng)XVT時(shí)它與a進(jìn)行匹配，其結(jié)果可能成功，也可能失敗，如果成功則符號(hào)棧中將X退棧并

5、將輸入流指針向前移動(dòng)一位，否則報(bào)錯(cuò)。接受：當(dāng)格局為（#，空#）時(shí)報(bào)告分析成功。報(bào)錯(cuò)：出錯(cuò)后，停止分析。并給出相應(yīng)的錯(cuò)誤提示信息。【實(shí)驗(yàn)要求】1、編程時(shí)注意編程風(fēng)格：空行的使用、注釋的使用、縮進(jìn)的使用等。2、如果遇到錯(cuò)誤的表達(dá)式，應(yīng)輸出錯(cuò)誤提示信息。 【流程圖】1. 總體思路分析及流程圖給定一個(gè)正規(guī)文法G，在LL(1)預(yù)測(cè)分析中，必須先求出First集和Follow集，然后求出Select集，通過(guò)Select集判斷是否是LL1文法，如果是的話，構(gòu)造預(yù)測(cè)分析表。求出預(yù)測(cè)分析表之后，再輸入一個(gè)字符串，依據(jù)LL1分析表單步輸出字符串的分析過(guò)程。功能模塊分解圖（1）主程序流程圖（2）核心算法流程圖 1.

6、計(jì)算非終結(jié)符的First集的算法及流程：First集合的構(gòu)造算法：（1）若XVT，則First（X）=X。（2）若XVN，且有產(chǎn)生式Xa，則把a(bǔ)加入到First (X)中；若X也是一條產(chǎn)生式，則把也加到First (X)中。（3）若XY是一個(gè)產(chǎn)生式且YVN，則把First (Y)中的所有非-元素都加到First (X)中；若XY1Y2Yk是一個(gè)產(chǎn)生式，Y1，Yi-1都是非終結(jié)符，而且，對(duì)于任何j，1ji-1，F(xiàn)irst (Yj)都含有（即Y1Yi-1* ），則把First (Yj)中的所有非-元素都加到First (X)中；特別是，若所有的First (Yj)均含有，j=1,2,，k，則把加到

7、First (X)中。連續(xù)使用上面的規(guī)則，直至每個(gè)集合First不再增大為止。2.計(jì)算非終結(jié)符的Follow集：Follow集合的具體構(gòu)造算法如下：（1）對(duì)于文法的開(kāi)始符號(hào)S，置#于Follow(S)中；（2）若AB是一個(gè)產(chǎn)生式，則把First()|加至Follow(B)中；（3）若AB是一個(gè)產(chǎn)生式，或AB是一個(gè)產(chǎn)生式而 （即First()），則把Follow(A)加至Follow(B)中。連續(xù)使用上面的規(guī)則，直至每個(gè)集合Follow不再增大為止。3.預(yù)測(cè)分析控制程序的算法流程【源代碼】11#include#include#include#includechar A20;/*分析棧*/char

8、 B20;/*剩余串*/char v120=i,+,*,(,),#;/*終結(jié)符 */char v220=E,G,T,S,F;/*非終結(jié)符 */int j=0,b=0,top=0,l;/*L為輸入串長(zhǎng)度 */typedef struct type/*產(chǎn)生式類型定義 */char origin;/*大寫(xiě)字符 */char array5;/*產(chǎn)生式右邊字符 */int length;/*字符個(gè)數(shù) */type;type e,t,g,g1,s,s1,f,f1;/*結(jié)構(gòu)體變量 */type C1010;/*預(yù)測(cè)分析表 */void print()/*輸出分析棧 */int a;/*指針*/for(a=0

9、;a=top+1;a+)printf(%c,Aa);printf(tt);/*print*/void print1()/*輸出剩余串*/int j;for(j=0;jb;j+)/*輸出對(duì)齊符*/printf( );for(j=b;j=l;j+)printf(%c,Bj);printf(ttt);/*print1*/void main()int m,n,k=0,flag=0,finish=0;char ch,x;type cha;/*用來(lái)接受Cmn*/*把文法產(chǎn)生式賦值結(jié)構(gòu)體*/e.origin=E;strcpy(e.array,TG);e.length=2;t.origin=T;strcpy(

10、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;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.o

11、rigin=N;/*全部賦為空*/ /*填充分析表*/ C00=e;C03=e; C11=g;C14=g1;C15=g1; C20=t;C23=t; C31=s1;C32=s;C34=C35=s1; C40=f1;C43=f; printf(提示:本程序只能對(duì)由i,+,*,(,)構(gòu)成的以#結(jié)束的字符串進(jìn)行分析,n); printf(請(qǐng)輸入要分析的字符串:); do/*讀入分析串*/ scanf(%c,&ch); if (ch!=i) &(ch!=+) &(ch!=*)&(ch!=()&(ch!=)&(ch!=#) printf(輸入串中有非法字符n); exit(1); Bj=ch; j+;

12、while(ch!=#); l=j;/*分析串長(zhǎng)度*/ 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é)符*/ if(x=#) finish=1;/*結(jié)束標(biāo)記*/ printf(acc!n);/*接受 */ getchar(); getchar(); exit(1); /*if*/ if(x=ch) print(); print1(); printf(%c匹配n,ch); ch=B+b;/*下一個(gè)輸入字符*/ flag=0;/*恢復(fù)標(biāo)記*/ /*if*/ else/*出錯(cuò)處理*/ print(); print1(); printf(%c出錯(cuò)n,ch);/*輸出出錯(cuò)終結(jié)符*/ exit(1); /*else*/ /*if*/ else/*非終結(jié)符處理*/ for(j=0;j=4;j+)if(x=v2j)m=j;/*行號(hào)*/break; for(j=0;j,ch