編譯原理LL1文法源代碼實(shí)驗(yàn)三

1、一、實(shí)驗(yàn)?zāi)康募耙?掌握LL(1)分析法的基本原理； 2掌握LL(1)分析表的構(gòu)造方法；3用LL（1）分析法分析高級(jí)語(yǔ)言表達(dá)式。4、了解LL（1）分析器的工作過(guò)程。文法：無(wú)二義性的算術(shù)表達(dá)式的文法（1）把詞法分析作為語(yǔ)法分析的子程序?qū)崿F(xiàn)（5分）（2）獨(dú)立的語(yǔ)法分析程序（4分）（3）對(duì)表達(dá)式文法消除左遞歸、構(gòu)造LL（1）分析表（4）LL（1）分析表可以直接輸入（4分），也可以用程序?qū)崿F(xiàn)（5分）（5）給一個(gè)表達(dá)式，給出分析過(guò)程（分析棧、輸入串、所用規(guī)則）（4分）（6）生成一個(gè)棵語(yǔ)法樹(shù)（5分）用二叉樹(shù)的形式表示出來(lái)2、 實(shí)驗(yàn)內(nèi)容及原理 1、 實(shí)驗(yàn)原理（1）、LL（1）文法的定義LL(1)分析法屬于確

2、定的自頂向下分析方法。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è)字符是否匹配，如果匹配，則繼續(xù)分析，否則報(bào)錯(cuò)。LL(1)分析方法要求文法滿足如下條件：對(duì)于任

3、一非終極符A的兩個(gè)不同產(chǎn)生式Aàa,Aàb，都要滿足下面條件：SELECT(Aàa)SELECT(Aàb)=Æ（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: VN×VTàPErrorM(A, t) = Aà，當(dāng)tÎselect(Aà) ，否則M(A, t) = Error其中P表示所有產(chǎn)生式的集合

4、。（3）、語(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 的產(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)生式的右部b去替換X。此時(shí)X出棧，b逆序入棧。匹配：當(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ò)誤提示信息。2、實(shí)驗(yàn)內(nèi)容根據(jù)某一文法編制調(diào)試LL（1）分析程序，以便對(duì)任意輸入的符號(hào)串進(jìn)行分析。本次實(shí)驗(yàn)的目的主要是加深對(duì)預(yù)測(cè)分析LL（1）分析法的理解。 對(duì)下列文法，用LL（1）分析法對(duì)任意輸入的符號(hào)串進(jìn)行分析：（1）E->TG（2）G->+TG（3）G->（4）T->FS（5）S->*FS（6）S->（7）F->(E)（8）F->i程序輸入一以#結(jié)束的符號(hào)串(包括+*（

6、）i#)，如：i+i*i#。3、 實(shí)驗(yàn)過(guò)程及步驟1. 總體思路分析及流程圖給定一個(gè)正規(guī)文法G，在LL(1)預(yù)測(cè)分析中，必須先求出First集和Follow集， 構(gòu)造預(yù)測(cè)分析表。求出預(yù)測(cè)分析表之后，再輸入一個(gè)字符串，依據(jù)LL1分析表單步輸出字符串的分析過(guò)程。功能模塊分解圖（1）主程序流程圖（2）核心算法流程圖 1.計(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)中的所

7、有非-元素都加到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，則把加到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）若A

8、B是一個(gè)產(chǎn)生式，或AB是一個(gè)產(chǎn)生式而 （即First()），則把Follow(A)加至Follow(B)中。連續(xù)使用上面的規(guī)則，直至每個(gè)集合Follow不再增大為止。3.預(yù)測(cè)分析控制程序的算法流程 LL（1）文法（源代碼）#include "stdio.h"#include "stdlib.h"#define MaxRuleNum 8#define MaxVnNum 5#define MaxVtNum 5#define MaxStackDepth 20#define MaxPLength 20#define MaxStLength 50struct pR

9、Node /*產(chǎn)生式右部結(jié)構(gòu)*/ int rCursor; struct pRNode *next;struct pNode int lCursor; int rLength; /*右部長(zhǎng)度*/ struct pRNode *rHead; /*右部結(jié)點(diǎn)頭指針*/;char VnMaxVnNum + 1; /*非終結(jié)符集*/int vnNum;char VtMaxVtNum + 1; /*終結(jié)符集*/int vtNum;struct pNode PMaxRuleNum; int PNum; char bufferMaxPLength + 1;char ch; char stMaxStLength

10、; /*要分析的符號(hào)串*/struct collectNode int nVt; struct collectNode *next;struct collectNode* firstMaxVnNum + 1; /*first集*/struct collectNode* followMaxVnNum + 1; /*follow集*/int analyseTableMaxVnNum + 1MaxVtNum + 1 + 1;int analyseStackMaxStackDepth + 1; /*分析棧*/int topAnalyse; /*分析棧頂*/void Init();/*初始化*/int

11、IndexCh(char ch);void InputVt(); /*輸入終結(jié)符*/void InputVn();/*輸入非終結(jié)符*/void ShowChArray(char* collect, int num);/*輸出Vn或Vt的內(nèi)容*/void InputP();/*產(chǎn)生式輸入*/bool CheckP(char * st);/*判斷產(chǎn)生式正確性*/void First(int U);void AddFirst(int U, int nCh); /*加入first集*/bool HaveEmpty(int nVn); void Follow(int V);/*計(jì)算follow集*/vo

12、id AddFollow(int V, int nCh, int kind);void ShowCollect(struct collectNode *collect);/*輸出first或follow集*/void FirstFollow();/*計(jì)算first和follow*/void CreateAT();/*構(gòu)造預(yù)測(cè)分析表*/void ShowAT();/*輸出分析表*/void Identify(char *st);void InitStack();void ShowStack();void Pop();void Push(int r);void main(void) char to

13、do,ch; Init(); InputVn(); InputVt(); InputP(); getchar(); FirstFollow(); printf("所得first集為："); ShowCollect(first); printf("所得follow集為："); ShowCollect(follow); CreateAT(); ShowAT(); todo = 'y' while('y' = todo) printf("n是否繼續(xù)進(jìn)行句型分析？(y / n):"); todo = getch

14、ar(); while('y' != todo && 'n' != todo) printf("n(y / n)? "); todo = getchar(); if('y' = todo) int i; InitStack(); printf("請(qǐng)輸入符號(hào)串(以#結(jié)束) : "); ch = getchar(); i = 0; while('#' != ch && i < MaxStLength) if(' ' != ch &&a

15、mp; 'n' != ch) sti+ = ch; ch = getchar(); if('#' = ch && i < MaxStLength) sti = ch; Identify(st); else printf("輸入出錯(cuò)！n"); getchar();void Init() int i,j; vnNum = 0; vtNum = 0; PNum = 0; for(i = 0; i <= MaxVnNum; i+) Vni = '0' for(i = 0; i <= MaxVtNum;

16、 i+) Vti = '0' for(i = 0; i < MaxRuleNum; i+) Pi.lCursor = NULL; Pi.rHead = NULL; Pi.rLength = 0; PNum = 0; for(i = 0; i <= MaxPLength; i+) bufferi = '0' for(i = 0; i < MaxVnNum; i+) firsti = NULL; followi = NULL; for(i = 0; i <= MaxVnNum; i+) for(j = 0; j <= MaxVnNum

17、+ 1; j+) analyseTableij = -1; int IndexCh(char ch) int n; n = 0; /*is Vn?*/ while(ch != Vnn && '0' != Vnn) n+; if('0' != Vnn) return 100 + n; n = 0; /*is Vt?*/ while(ch != Vtn && '0' != Vtn) n+; if('0' != Vtn) return n; return -1;/*輸出Vn或Vt的內(nèi)容*/void Sho

18、wChArray(char* collect) int k = 0; while('0' != collectk) printf(" %c ", collectk+); printf("n");/*輸入非終結(jié)符*/void InputVn() int inErr = 1; int n,k; char ch; while(inErr) printf("n請(qǐng)輸入所有的非終結(jié)符，注意："); printf("請(qǐng)將開(kāi)始符放在第一位，并以#號(hào)結(jié)束:n"); ch = ' ' n = 0; /*

19、初始化數(shù)組*/ while(n < MaxVnNum) Vnn+ = '0' n = 0; while('#' != ch) && (n < MaxVnNum) if(' ' != ch && 'n' != ch && -1 = IndexCh(ch) Vnn+ = ch; vnNum+; ch = getchar(); Vnn = '#' /*以“#”標(biāo)志結(jié)束用于判斷長(zhǎng)度是否合法*/ k = n; if('#' != ch) if( &#

20、39;#' != (ch = getchar() while('#' != (ch = getchar() ; printf("n符號(hào)數(shù)目超過(guò)限制！n"); inErr = 1; continue; /*正確性確認(rèn)，正確則，執(zhí)行下下面，否則重新輸入*/ Vnk = '0' ShowChArray(Vn); ch = ' ' while('y' != ch && 'n' != ch) if('n' != ch) printf("輸入正確確認(rèn)?(y/

21、n):"); scanf("%c", &ch); if('n' = ch) printf("錄入錯(cuò)誤重新輸入！n"); inErr = 1; else inErr = 0; /*輸入終結(jié)符*/void InputVt() int inErr = 1; int n,k; char ch; while(inErr) printf("n請(qǐng)輸入所有的終結(jié)符，注意："); printf("以#號(hào)結(jié)束:n"); ch = ' ' n = 0; /*初始化數(shù)組*/ while(n

22、 < MaxVtNum) Vtn+ = '0' n = 0; while('#' != ch) && (n < MaxVtNum) if(' ' != ch && 'n' != ch && -1 = IndexCh(ch) Vtn+ = ch; vtNum+; ch = getchar(); Vtn = '#' k = n; if('#' != ch) if( '#' != (ch = getchar() while(

23、9;#' != (ch = getchar() ; printf("n符號(hào)數(shù)目超過(guò)限制！n"); inErr = 1; continue; Vtk = '0' ShowChArray(Vt); ch = ' ' while('y' != ch && 'n' != ch) if('n' != ch) printf("輸入正確確認(rèn)?(y/n):"); scanf("%c", &ch); if('n' = ch)

24、printf("錄入錯(cuò)誤重新輸入！n"); inErr = 1; else inErr = 0; /*產(chǎn)生式輸入*/void InputP() char ch; int i = 0, n,num; printf("請(qǐng)輸入文法產(chǎn)生式的個(gè)數(shù)："); scanf("%d", &num); PNum = num; getchar(); /*消除回車符*/ printf("n請(qǐng)輸入文法的%d個(gè)產(chǎn)生式,并以回車分隔每個(gè)產(chǎn)生式：", num); printf("n"); while(i < nu

25、m) printf("第%d個(gè)：", i); /*初始化*/ for(n =0; n < MaxPLength; n+) buffern = '0' /*輸入產(chǎn)生式串*/ ch = ' ' n = 0; while('n' != (ch = getchar() && n < MaxPLength) if(' ' != ch) buffern+ = ch; buffern = '0' if(CheckP(buffer) pRNode *pt, *qt; Pi.lCurs

26、or = IndexCh(buffer0); pt = (pRNode*)malloc(sizeof(pRNode); pt->rCursor = IndexCh(buffer3); pt->next = NULL; Pi.rHead = pt; n = 4; while('0' != buffern) qt = (pRNode*)malloc(sizeof(pRNode); qt->rCursor = IndexCh(buffern); qt->next = NULL; pt->next = qt; pt = qt; n+; Pi.rLength

27、 = n - 3; i+; else printf("輸入符號(hào)含非法在成分，請(qǐng)重新輸入！n"); /*判斷產(chǎn)生式正確性*/bool CheckP(char * st) int n; if(100 > IndexCh(st0) return false; if('-' != st1) return false; if('>' != st2) return false; for(n = 3; '0' != stn; n +) if(-1 = IndexCh(stn) return false; return true;

28、void First(int U) int i,j; for(i = 0; i < PNum; i+) if(Pi.lCursor = U) struct pRNode* pt; pt = Pi.rHead; j = 0; while(j < Pi.rLength) if(100 > pt->rCursor) AddFirst(U, pt->rCursor); break; else if(NULL = firstpt->rCursor - 100) First(pt->rCursor); AddFirst(U, pt->rCursor); if

29、(!HaveEmpty(pt->rCursor) break; else pt = pt->next; j+; if(j >= Pi.rLength) /*當(dāng)產(chǎn)生式右部都能推出空時(shí)*/ AddFirst(U, -1); /*加入first集*/void AddFirst(int U, int nCh) struct collectNode *pt, *qt; int ch; /*用于處理Vn*/ pt = NULL; qt = NULL; if(nCh < 100) pt = firstU - 100; while(NULL != pt) if(pt->nVt =

30、 nCh) break; else qt = pt; pt = pt->next; if(NULL = pt) pt = (struct collectNode *)malloc(sizeof(struct collectNode); pt->nVt = nCh; pt->next = NULL; if(NULL = firstU - 100) firstU - 100 = pt; else qt->next = pt; /*qt指向first集的最后一個(gè)元素*/ pt = pt->next; else pt = firstnCh - 100; while(NUL

31、L != pt) ch = pt->nVt; if(-1 != ch) AddFirst(U, ch); pt = pt->next; bool HaveEmpty(int nVn) if(nVn < 100) return false; struct collectNode *pt; pt = firstnVn - 100; while(NULL != pt) if(-1 = pt->nVt) return true; pt = pt->next; return false;void Follow(int V) int i; struct pRNode *pt

32、; if(100 = V) /*當(dāng)為初始符時(shí)*/ AddFollow(V, -1, 0 ); for(i = 0; i < PNum; i+) pt = Pi.rHead; while(NULL != pt && pt->rCursor != V) pt = pt->next; if(NULL != pt) pt = pt->next; if(NULL = pt) if(NULL = followPi.lCursor - 100 && Pi.lCursor != V) Follow(Pi.lCursor); AddFollow(V, Pi

33、.lCursor, 0); else while(NULL != pt && HaveEmpty(pt->rCursor) AddFollow(V, pt->rCursor, 1); pt = pt->next; if(NULL = pt) if(NULL = followPi.lCursor - 100 && Pi.lCursor != V) Follow(Pi.lCursor); AddFollow(V, Pi.lCursor, 0); else AddFollow(V, pt->rCursor, 1); void AddFollow

34、(int V, int nCh, int kind) struct collectNode *pt, *qt; int ch; pt = NULL; qt = NULL; if(nCh < 100) /*為終結(jié)符時(shí)*/ pt = followV - 100; while(NULL != pt) if(pt->nVt = nCh) break; else qt = pt; pt = pt->next; if(NULL = pt) pt = (struct collectNode *)malloc(sizeof(struct collectNode); pt->nVt =

35、nCh; pt->next = NULL; if(NULL = followV - 100) followV - 100 = pt; else qt->next = pt; /*qt指向follow集的最后一個(gè)元素*/ pt = pt->next; else if(0 = kind) pt = follownCh - 100; while(NULL != pt) ch = pt->nVt; AddFollow(V, ch, 0); pt = pt->next; else pt = firstnCh - 100; while(NULL != pt) ch = pt-

36、>nVt; if(-1 != ch) AddFollow(V, ch, 1); pt = pt->next; /*輸出first或follow集*/void ShowCollect(struct collectNode *collect) int i; struct collectNode *pt; i = 0; while(NULL != collecti) pt = collecti; printf("n%c:t", Vni); while(NULL != pt) if(-1 != pt->nVt) printf(" %c", Vt

37、pt->nVt); else printf(" #"); pt = pt->next; i+; printf("n");/*計(jì)算first和follow*/void FirstFollow() int i; i = 0; while('0' != Vni) if(NULL = firsti) First(100 + i); i+; i = 0; while('0' != Vni) if(NULL = followi) Follow(100 + i); i+; /*構(gòu)造預(yù)測(cè)分析表*/void CreateAT()

38、 int i; struct pRNode *pt; struct collectNode *ct; for(i = 0; i < PNum; i+) pt = Pi.rHead; while(NULL != pt && HaveEmpty(pt->rCursor) ct = firstpt->rCursor - 100; while(NULL != ct) if(-1 != ct->nVt) analyseTablePi.lCursor - 100ct->nVt = i; ct = ct->next; pt = pt->next; i

39、f(NULL = pt) ct = followPi.lCursor - 100; while(NULL != ct) if(-1 != ct->nVt) analyseTablePi.lCursor - 100ct->nVt = i; else analyseTablePi.lCursor - 100vtNum = i; ct = ct->next; else if(100 <= pt->rCursor) /*不含空的非終結(jié)符*/ ct = firstpt->rCursor - 100; while(NULL != ct) analyseTablePi.l

40、Cursor - 100ct->nVt = i; ct = ct->next; else /*終結(jié)符或者空*/ if(-1 = pt->rCursor) ct = followPi.lCursor - 100; while(NULL != ct) if(-1 != ct->nVt) analyseTablePi.lCursor - 100ct->nVt = i; else /*當(dāng)含有#號(hào)時(shí)*/ analyseTablePi.lCursor - 100vtNum = i; ct = ct->next; else /*為終結(jié)符*/ analyseTablePi.

41、lCursor - 100pt->rCursor = i; /*輸出分析表*/void ShowAT() int i,j; printf("構(gòu)造預(yù)測(cè)分析表如下：n"); printf("t|t"); for(i = 0; i < vtNum; i+) printf("%ct", Vti); printf("#tn"); printf("- - -t|- - -t"); for(i = 0; i <= vtNum; i+) printf("- - -t");

42、printf("n"); for(i = 0; i < vnNum; i+) printf("%ct|t", Vni); for(j = 0; j <= vtNum; j+) if(-1 != analyseTableij) printf("R(%d)t", analyseTableij); else printf("errort"); printf("n"); void Identify(char *st) int current,step,r; /*r表使用的產(chǎn)生式的序號(hào)*/ p

43、rintf("n%s的分析過(guò)程：n", st); printf("步驟t分析符號(hào)棧t當(dāng)前指示字符t使用產(chǎn)生式序號(hào)n"); step = 0; current = 0; printf("%dt",step); ShowStack(); printf("tt%ctt- -n", stcurrent); while('#' != stcurrent) if(100 > analyseStacktopAnalyse) if(analyseStacktopAnalyse = IndexCh(stcurr

44、ent) Pop(); current+; step+; printf("%dt", step); ShowStack(); printf("tt%ctt出棧、后移n", stcurrent); else printf("%c-%c不匹配！", analyseStacktopAnalyse, stcurrent); printf("此串不是此文法的句子！n"); return; else /*當(dāng)為非終結(jié)符時(shí)*/ r = analyseTableanalyseStacktopAnalyse - 100IndexCh(stcurrent); if(-1 != r) Push(r); step+; printf("%dt", step); ShowStack(); print