編譯原理LL(1)語法分析實驗報告

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

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

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

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

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

6、計算非終結(jié)符的First集的算法及流程：First集合的構(gòu)造算法：（1）若XVT，則First（X）=X。（2）若XVN，且有產(chǎn)生式Xa，則把a加入到First (X)中；若X也是一條產(chǎn)生式，則把也加到First (X)中。（3）若XY是一個產(chǎn)生式且YVN，則把First (Y)中的所有非-元素都加到First (X)中；若XY1Y2Yk是一個產(chǎn)生式，Y1，Yi-1都是非終結(jié)符，而且，對于任何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ī)則，直至每個集合First不再增大為止。2.計算非終結(jié)符的Follow集：Follow集合的具體構(gòu)造算法如下：（1）對于文法的開始符號S，置#于Follow(S)中；（2）若AB是一個產(chǎn)生式，則把First()|加至Follow(B)中；（3）若AB是一個產(chǎn)生式，或AB是一個產(chǎn)生式而 （即First()），則把Follow(A)加至Follow(B)中。連續(xù)使用上面的規(guī)則，直至每個集合Follow不再增大為止。3.預測分析控制程序的算法流程【源代碼】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為輸入串長度 */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;/*預測分析表 */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+)/*輸出對齊符*/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;/*用來接受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(提示:本程序只能對由i,+,*,(,)構(gòu)成的以#結(jié)束的字符串進行分析,n); printf(請輸入要分析的字符串:); do/*讀入分析串*/ scanf(%c,&ch); if (ch!=i) &(ch!=+) &(ch!=*)&(ch!=()&(ch!=)&(ch!=#) printf(輸入串中有非法字符n); exit(1); Bj=ch; j+;

12、while(ch!=#); l=j;/*分析串長度*/ ch=B0;/*當前分析字符*/ Atop=#; A+top=E;/*#,E進棧*/ printf(步驟tt分析棧 tt剩余字符 tt所用產(chǎn)生式 n); do x=Atop-;/*x為當前棧頂字符*/ 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é)束標記*/ printf(acc!n);/*接受 */ getchar(); getchar(); exit(1); /*if*/ if(x=ch) print(); print1(); printf(%c匹配n,ch); ch=B+b;/*下一個輸入字符*/ flag=0;/*恢復標記*/ /*if*/ else/*出錯處理*/ print(); print1(); 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,ch