編譯原理LL語(yǔ)法分析試驗(yàn)報(bào)告要點(diǎn)

1、學(xué)號(hào) 20102798實(shí)驗(yàn)日期 2013.04.08專(zhuān)業(yè)軟件工程教師簽字姓名薛建東成績(jī)實(shí)驗(yàn)報(bào)【實(shí)驗(yàn)名稱(chēng)】 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)容】根據(jù)某一文法編制調(diào)試LL ( 1 )分析程序，以便對(duì)任意輸入的符號(hào)串進(jìn)行分析。構(gòu)造預(yù)測(cè)分析表，并利用分析表和一個(gè)棧來(lái)實(shí)現(xiàn)對(duì)上述程序設(shè)計(jì)語(yǔ)言的分析程序。分析法的功能是利用 LL( 1)控制程序根據(jù)顯示棧棧頂內(nèi)容、向前看符號(hào)以及LL(1) 分析表，對(duì)輸入符號(hào)串自上而下的分析過(guò)程。【設(shè)計(jì)

2、思想】(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和SELLEC集,然后判斷是否為 LL(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)分析方法要求文法滿(mǎn)足如下條件：對(duì)于任一非終極符 A的兩個(gè)不同產(chǎn)生式 A : ,A 一都要滿(mǎn)足下面條件： SELECT(A :) A SELECT(A -)=.(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: VNX VT PU ErrorM(A, t) = Aa,當(dāng) t select(A a )，否則M(A, t) = Error其中P表示所有產(chǎn)生式的集合。(3)

4、 、語(yǔ)法分析程序構(gòu)造LL(1)分析中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(yíng)的產(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)X. VN時(shí)選相應(yīng)產(chǎn)生式的右部1去替換X。此時(shí)X出棧，逆序入棧。匹配：當(dāng)X VT時(shí)它與a進(jìn)行匹配，其

5、結(jié)果可能成功，也可能失敗，如果成功則符號(hào)棧 中將X退棧并將輸入流指針向前移動(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ò)誤提示信息?！玖鞒虉D】1.總體思路分析及流程圖給定一個(gè)正規(guī)文法 G,在LL(1)預(yù)測(cè)分析中，必須先求出First集和Follow集，然后求 出Select集，通過(guò)Select集判斷是否是LL1文法，如果是的話(huà)，構(gòu)造預(yù)測(cè)分析表。 求出預(yù) 測(cè)分析表之后，再輸入一個(gè)字符串，依據(jù)LL1分析表單步輸出字符串的分析過(guò)程

6、。12功能模塊分解圖(1)主程序流程圖(2)核心算法流程圖1.計(jì)算非終結(jié)符的First集的算法及流程：First集合的構(gòu)造算法：(1) 若 X VT,貝U First (X) =X。(2) 若X VN且有產(chǎn)生式 心a，則把a(bǔ)加入到First (X)中；若X £也是一條 產(chǎn)生式，則把&也加到First (X) 中。(3) 若XtY是一個(gè)產(chǎn)生式且Y VN則把First (Y) 中的所有非£ -元素都加到First (X)中；若 XY1Y2Yk是一個(gè)產(chǎn)生式，Y1,，Yi-1都是非終結(jié)符，而且，對(duì)于任 何j , K j w i-1 , First (Yj) 都含有£

7、; (即Y1Yi-1*£ ),則把First (Yj) 中的所有非元素都加到First (X)中；特別是，若所有的First (Yj)均含有£ , j=1,2,，k,則把& 加到 First (X)中。連續(xù)使用上面的規(guī)則，直至每個(gè)集合First不再增大為止。開(kāi)始2.計(jì)算非終結(jié)符的Follow集：Follow集合的具體構(gòu)造算法如下：(1) 對(duì)于文法的開(kāi)始符號(hào)S,置#于 Follow(S)中；(2) 若 2 a B3是一個(gè)產(chǎn)生式，則把First( 3 )| £ 加至Follow(B)中；(3) 若 2 a B是一個(gè)產(chǎn)生式，或At a B3是一個(gè)產(chǎn)生式而 3&#

8、163; (即& First( 3 ), 則把 Follow(A)加至 Follow(B)中。連續(xù)使用上面的規(guī)則，直至每個(gè)集合Follow不再增大為止。開(kāi)始取得一個(gè)非終結(jié)符V添加V*到V的Follow中將V*的First集加入到V的Follow集中3. 預(yù)測(cè)分析控制程序的算法流程出錯(cuò)【源代碼】#in clude<stdio.h>#in clude<stdlib.h>#in clude<stri ng.h>終結(jié)符 */ 非終結(jié)符 */#include<dos.h>char A20;/* 分析棧 */ char B20;/* 剩余串 */ c

9、har v120='i','+','*','(',')','#'/* char v220='E','G','T','S','F'/*int j=0,b=0,top=0,l;/*L為輸入串長(zhǎng)度 */typedef struct type/* char origin;/*char array5;/*產(chǎn)生式類(lèi)型定義 */大寫(xiě)字符 */ 產(chǎn)生式右邊字符 */int length;/* 字符個(gè)數(shù) */ type;type e,t,

10、g,g1,s,s1,f,f1;/* 結(jié)構(gòu)體變量 */ type C1010;/* 預(yù)測(cè)分析表 */ void print()/* 輸出分析棧 */ int a;/* 指針 */ for(a=0;a<=top+1;a+) printf("%c",Aa);printf("tt");/*print*/ void print1()/* 輸出剩余串 */int j;for(j=0;j<b;j+)/* 輸出對(duì)齊符 */ printf(" ");for(j=b;j<=l;j+)printf("%c",Bj);p

11、rintf("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(t.array,"FS");t.length=2;g.origin='G'strcpy(g.array,"+TG")

12、;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;

13、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=t;C31=s1;C32=s;C34=C35=s1;C40=f1;C43=f;printf("提示 : 本程序只能對(duì)由 'i','+','*','(',')'構(gòu)成的以 '#' 結(jié)束的字符串進(jìn)行分析,n");printf("

14、;請(qǐng)輸入要分析的字符串 :");do/* 讀入分析串 */scanf("%c",&ch);if (ch!='i') &&(ch!='+') &&(ch!='*')&&(ch!='(')&&(ch!=')')&&(ch!='#')printf(" 輸入串中有非法字符 n");exit(1);Bj=ch;j+; while(ch!='#'); l=j;

15、/* 分析串長(zhǎng)度 */ ch=B0;/* 當(dāng)前分析字符 */ Atop='#' A+top='E'/*'#','E' printf(" 步驟 tt do x=Atop-;/*x printf("%d",k+); printf("tt"); for(j=0;j<=5;j+)/* if(x=v1j) 進(jìn)棧 */分析棧 tt 剩余字符 tt 所用產(chǎn)生式 n");為當(dāng)前棧頂字符 */判斷是否為終結(jié)符 */flag=1; break;if(flag=1)/*if(x='

16、;#') 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 exit(1);/*else*/*if*/ else/* 非終結(jié)符處理如果是終結(jié)符 */*/出錯(cuò)

17、n",ch);/* 輸出出錯(cuò)終結(jié)符 */*/for(j=0;j<=4;j+) if(x=v2j) m=j;/* 行號(hào) */ break;for(j=0;j<=5;j+)if(ch=v1j)n=j;/* 列號(hào) */ break;cha=Cmn;if(cha.origin!='N')/* 判斷是否為空 */print();print1();printf("%c->",cha.origin);/* 輸出產(chǎn)生式 */for(j=0;j<cha.length;j+) printf("%c",cha.arrayj);

18、printf("n");for(j=(cha.length-1);j>=0;j-)/*產(chǎn)生式逆序入棧 */A+top=cha.arrayj;if(Atop='A')/* 為空則不進(jìn)棧 */ top-;/*if*/else/* 出錯(cuò)處理 */print();print1();printf("%c 出錯(cuò) n",x);/* 輸出出錯(cuò)非終結(jié)符 */exit(1);/*else*/*else*/while(finish=0);/*main*/【運(yùn)行結(jié)果】I = I' s I可 ' EXDebu g2 shiya n, e T分析棧ttE ttGT ttGSF ttGS>E< ttGS>E ttGS>GT «GS>GSF ttGS>GSi #GS>GS ttGS>G UGSJGT+ ttGS>GT >ess &ny key to continue10迪T 宀尸構(gòu)成的以“守串: