實驗二LL(1)預測分析

1、實驗二LL(1)分析的設計與實現(xiàn)開課實驗室：A201 , A207實驗項目LL(1)分析的設計與實現(xiàn)實驗類型設計實驗學時4一、實驗目的根據(jù)某一文法編制調試LL(1)分析程序，以便對任意輸入的符號串進行分析。掌握LL(1)分析法的基本原理，LL(1)分析表的構造方法，LL(1)驅動程序的構造方法。二、設備與環(huán)境1 .硬件設備：PC機一臺2 .軟件環(huán)境：安裝Windows操作系統(tǒng)或者Linux操作系統(tǒng)，并安裝相關的程序開發(fā)環(huán)境, 如C C+Java等編程語言環(huán)境。三、實驗要求1 .輸入文法G的非終結符、終結符和產(chǎn)生式；(1)輸出非終結符的FIRST集；(2)輸出非終結符的 FOLLOW 集；(3)

2、構造文法G的預測分析表；(4)對輸入符號串進行分析。2、編程語言不限。四、實驗原理1 .程序功能(流程圖參考)：第1頁共24頁2 .計算FIRST集合：First集合最終是對產(chǎn)生式右部的字符串而言的，但其關鍵是求出非終結符的First集合，由于終結符的First集合就是它自己，所以求出非終結符的First集合后，就可很直觀地得到每個字符串的First集合。直接收取：對形如 U a的產(chǎn)生式(其中 a是終結符)，把a收入到First(U)中 反復傳送：對形入 U P的產(chǎn)生式(其中 P是非終結符)，應把First(P)中的全部內容 傳送到First(U)中。算法描述：見教材 P80)若 XC Vt,

3、則 FIRST(X)=X;)若XCVn,且有產(chǎn)生式 X->a，aCVt,則aC FIRST(X);)若 XCVn,X->，則 C FIRST(X)若 X,Y1,Y2,Y3,Y4 Yn 都 Vn,而產(chǎn)生式 X->Y1,Y2 Yn.當Y1,Y2,Y3,Y4 Yn 者8能=> ,那么 FIRST(X)=并集的 FIRST(Yi)- (0<=i<=n)若 Yi=> (i=1,2,3 )，則 FIRST(X)=并集的 FIRST(Yi)- 并上 3 .計算FOLLOW 集合：Follow集合是針對非終結符而言的，F(xiàn)ollow(U)所表達的是句型中非終結符U所有可

4、能的后隨終結符號的集合，特別地，“#"是識別符號的后隨符。直接收?。鹤⒁猱a(chǎn)生式右部的每一個形如J-Ua”的組合，把a直接收入到Follow(U)1直接收?。河中稳纭?UP”(P是非終結符)的組合，把First(P)直接收入到Follow(U)直接收?。喝魹槲姆ㄩ_始符號S,則把#收入FOLLOW(S);反復傳送：對形如U P的產(chǎn)生式(其中P是非終結符)，應把Follow(U)中的全部內 容傳送到Follow(P)中。算法描述：見教材 P82)若為文法開始符號 S,則FOLLOW(S尸#)若為文法 A->aBb是一個產(chǎn)生式，則把 FIRST ( b)的非空元素加入 FOLLOW(B

5、) 中。如果b->則把FOLLOW(A)也加入FOLLOW(B)中。4 .構造預測分析表：(1)對于文法的每條產(chǎn)生式A ，若a FIRST(),則MA, a = A(2)若 FIRST( ), b FOLLOW()則 MA, b = A ;(3)分析表M的其他元素均為出錯標志error。5 .預測分析程序流圖：見課本P93-P94五、程序源碼#include "stdio.h"#include 'stdlib.h"# define MaxRuleNum 8# define MaxVnNum 5# define MaxVtNum 5# define M

6、axStackDepth 20# define MaxPLength 20# define MaxStLength 50struct pRNode /*產(chǎn)生式右部結構 */int rCursor;struct pRNode *next;struct pNodeint lCursor;int rLength; /* 右部長度 */struct pRNode *rHead; /* 右部結點頭指針 */;char VnMaxVnNum + 1;/* 非終結符集 */int vnNum;char VtMaxVtNum + 1; /* 終結符集 */int vtNum;struct pNode PMax

7、RuleNum;int PNum;char bufferMaxPLength + 1;char ch;char stMaxStLength;/* 要分析的符號串 */struct collectNodeint nVt;struct collectNode *next;struct collectNode* firstMaxVnNum + 1; /*first 集*/struct collectNode* followMaxVnNum + 1; /*follow 集 */int analyseTableMaxVnNum + 1MaxVtNum + 1 + 1;int analyseStackMa

8、xStackDepth + 1; /* 分析棧 */int topAnalyse; /* 分析棧頂 */void Init();/* 初始化 */int IndexCh(char ch);void InputVt(); /* 輸入終結符 */void InputVn();/*輸入非終結符*/void ShowChArray(char* collect, int num);/* 輸出 Vn 或 Vt 的內容 */void InputP();/* 產(chǎn)生式輸入 */bool CheckP(char * st);/*判斷產(chǎn)生式正確性 */void First(int U);void AddFirst(

9、int U, int nCh); /* 加入 first 集*/bool HaveEmpty(int nVn);void Follow(int V);/* 計算 follow 集*/void AddFollow(int V , int nCh, int kind);void ShowCollect(struct collectNode *collect);/* 輸出 first 或 follow 集*/void FirstFollow();/* 計算 first 和 follow*/void CreateAT();/*構造預測分析表*/void ShowAT();/* 輸出分析表 */void

10、 Identify(char *st);void InitStack();void ShowStack();void Pop();void Push(int r);void main(void)char todo,ch;Init();InputVn();InputVt();InputP();getchar();FirstFollow();printf("所得 first 集為:");ShowCollect(first);printf("所得 follow 集為：");ShowCollect(follow);CreateAT();ShowAT();todo

11、 = 'y'while('y' = todo)printf("n是否繼續(xù)進行句型分析？(y / n):");todo = getchar();while('y' != todo && 'n' != todo)printf("n(y / n)?");todo = getchar();if('y' = todo)int i;InitStack();printf("請輸入符號串(以#結束)：");ch = getchar();i = 0;whil

12、e('#' != ch && i < MaxStLength)if(' ' != ch && ''n' != ch)sti+ = ch;ch = getchar();if('#' = ch && i < MaxStLength)sti = ch;Identify(st);elseprintf("輸入出錯！n");getchar();void Init()int i,j;vnNum = 0;vtNum = 0;PNum = 0;for(i = 0

13、; i <= MaxVnNum; i+)Vni = '0'for(i = 0; i <= MaxVtNum; 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(

14、i = 0; i <= MaxVnNum; i+)for(j = 0; j <= MaxVnNum + 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

15、(''0' != Vtn) return n;return -1;/*輸出Vn或Vt的內容*/void ShowChArray(char* collect)int k = 0;while(''0' != collectk)printf(" %c ", collectk+);printf("n");/*輸入非終結符*/void InputVn()int inErr = 1;int n,k;char ch;while(inErr)printf("n請輸入所有的非終結符，注意： ”)； printf(&

16、quot;請將開始符放在第一位，并以#結束：n");ch =''n = 0;/*初始化數(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 = '#' /*以“#”標志結束用于判

17、斷長度是否合法*/k = n;if('#' != ch)if( '#' != (ch = getchar()while('#' != (ch = getchar() ;printf("n符號數(shù)目超過限制！ n");inErr = 1;continue;/*正確性確認，正確則，執(zhí)行下下面，否則重新輸入 */Vnk = '0'ShowChArray(Vn);ch =''while('y' != ch && 'n' != ch)if('n'

18、; != ch)printf("輸入正確確認？(y/n):");scanf("%c", &ch);if('n' = ch)printf("錄入錯誤重新輸入！n");inErr = 1;elseinErr = 0;/*輸入終結符*/void InputVt()int inErr = 1;int n,k;char ch;while(inErr)printf("n請輸入所有的終結符，注意： ”);printf("以#結束:n");ch =''n = 0;/*初始化數(shù)組*/

19、while(n < 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('#&#

20、39; != (ch = getchar()；printf("n符號數(shù)目超過限制！ n");inErr = 1;continue;Vtk = '0'ShowChArray(Vt);ch =''while('y' != ch && 'n' != ch)if(''n' != ch)printf("輸入正確確認？(y/n):");scanf("%c", &ch);if('n' = ch)printf("錄

21、入錯誤重新輸入！ n");inErr = 1;elseinErr = 0;/*產(chǎn)生式輸入*/void InputP()char ch;int i = 0, n,num;printf("請輸入文法產(chǎn)生式的個數(shù)：")；scanf("%d", &num);PNum = num;getchar(); /*消除回車符*/printf("n請輸入文法的d個產(chǎn)生式，并以回車分隔每個產(chǎn)生式： ", num);printf("n");while(i < num)printf("第 d 個:"

22、;,i);/*初始化*/for(n =0; n < MaxPLength; n+) bufern = '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.lCursor = IndexCh(bufer0);pt = (pRNode*)malloc

23、(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(bufern);qt->next = NULL;pt->next = qt;pt = qt;n+;Pi.rLength = n - 3;i+;elseprintf("輸入符號含非法在成分，請重新輸入！ n&qu

24、ot;);/*判斷產(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;void First(int U)int i,j;for(i = 0; i < PNum; i+)if(Pi.

25、lCursor = U)struct pRNode* pt;pt = Pi.rHead;j = 0;while(j < Pi.rLength)if(100 > pt->rCursor)AddFirst(U, pt->rCursor);break;elseif(NULL = firstpt->rCursor - 100)First(pt->rCursor);AddFirst(U, pt->rCursor);if(!HaveEmpty(pt->rCursor)break;elsept = pt->next;j+;if(j >= Pi.rL

26、ength) /*當產(chǎn)生式右部都能推出空時*/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 = nCh) break;elseqt = pt;pt = pt->next;if(NULL = pt)pt = (struct collectNode *)malloc

27、(sizeof(struct collectNode);pt->nVt = nCh;pt->next = NULL;if(NULL = firstU - 100)firstU - 100 = pt;elseqt->next = pt; /*qt指向first集的最后一個元素 */pt = pt->next;elsept = firstnCh - 100;while(NULL != pt)ch = pt->nVt;if(-1 != ch)AddFirst(U, ch);pt = pt->next;bool HaveEmpty(int nVn)if(nVn &l

28、t; 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 ;if(100 = V)/*當為初始符時*/AddFollow(V, -1,0 );for(i = 0; i < PNum; i+)pt = Pi.rHead;while(NULL != pt && pt->

29、;rCursor != V)pt = pt->next;if(NULL != pt)pt = pt->next;if(NULL = pt)if(NULL = followPi.lCursor - 100 && Pi.lCurson= V)Follow(Pi.lCursor);AddFollow(V, Pi.lCursor, 0);elsewhile(NULL != pt && HaveEmpty(pt->rCursor)AddFollow(V, pt->rCursor, 1);pt = pt->next;if(NULL = pt)i

30、f(NULL = followPi.lCursor - 100 && Pi.lCursor != V)Follow(Pi.lCursor);AddFollow(V, Pi.lCursor, 0);elseAddFollow(V, pt->rCursor, 1); void AddFollow(int V , int nCh, int kind) struct collectNode *pt, *qt;int ch;pt = NULL;qt = NULL;if(nCh < 100) /*為終結符時*/pt = followV - 100;while(NULL != p

31、t)if(pt->nVt = 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 = followV - 100)followV - 100 = pt;elseqt->next = pt;/*qt指向follow 集的最后一個元素 */pt = pt->next;elseif(0 = kind)pt = follow

32、nCh - 100;while(NULL != pt)ch = pt->nVt;AddFollow(V, ch, 0);pt = pt->next;elsept = firstnCh - 100;while(NULL != pt)ch = pt->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

33、 != collect。)pt = collect。;printf("n%c:t", Vni);while(NULL != pt)if(-1 != pt->nVt)printf(" %c", Vtpt->nVt);elseprintf(" #");pt = pt->next;i+;printf("n");/* 計算 first 和 follow*/void FirstFollow()int i;i = 0;while(''0' != Vni)if(NULL = firsti

34、)First(100 + i);i+;i = 0;while(''0' != Vni)if(NULL = followi)Follow(100 + i);i+;/*構造預測分析表*/void CreateAT()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

35、 != ct)if(-1 != ct->nVt)analyseTablePi.lCursor - 100ct->nVt = i; ct = ct->next;pt = pt->next;if(NULL = pt)ct = followPi.lCursor - 100;while(NULL != ct)if(-1 != ct->nVt)analyseTablePi.lCursor - 100ct->nVt = i; elseanalyseTablePi.lCursor - 100vtNum = i; ct = ct->next;elseif(100 &l

36、t;= pt->rCursor) /*不含空的非終結符 */ct = firstpt->rCursor -100;while(NULL != ct)analyseTablePi.lCursor - 100ct->nVt = i; ct = ct->next;else /*終結符或者空*/if(-1 = pt->rCursor)ct = followPi.lCursor -100;while(NULL != ct) if(-1 != ct->nVt)analyseTablePi.lCursor - 100ct->nVt = i;else /*當含有#號時

37、*/analyseTablePi.lCursor - 100vtNum = i;ct = ct->next;else /*為終結符*/analyseTablePi.lCursor - 100pt->rCursor = i;/*輸出分析表*/void ShowAT()int i,j;printf("構造預測分析表如下：n");printf("t|t");for(i = 0; i < vtNum; i+)printf("%ct", Vti);printf("#t'n");printf(&quo

38、t;- - -t|- - -t");for(i = 0; i <= vtNum; i+) printf("- - -t");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);elseprintf("errort"); printf(&qu

39、ot;n");void Identify(char *st)int current,step,r;/*r表使用的產(chǎn)生式的序號*/printf("n%s 的分析過程：n", st);printf("步驟t分析符號棧t當前指示字符t使用產(chǎn)生式序號n");step = 0;current = 0;printf("%dt",step);ShowStack();printf("tt%ctt- -n", stcurrent);while('#' != stcurrent) if(100 > an

40、alyseStacktopAnalyse) if(analyseStacktopAnalyse = IndexCh(stcurrent) Pop();current+; step+; printf("%dt", step); ShowStack();printf("tt%ctt 出棧、后移 n", stcurrent); else printf("%c-%c 不匹配！", analyseStacktopAnalyse, stcurrent);printf("此串不是此文法的句子！n");return;else /*

41、當為非終結符時*/r = analyseTableanalyseStacktopAnalyse - 100IndexCh(stcurrent); if(-1 != r) Push(r); step+; printf("%dt", step);ShowStack();printf("tt%ctt%dn", stcurrent, r); elseprintf("此串不是此文法的句子！n");return;if('#' = stcurrent)if(0 = topAnalyse && #' = stcurrent)step+;printf("%dt", ste