LL1語法分析器試驗(yàn)報告

1、南京信息工程大學(xué)實(shí)驗(yàn)（實(shí)習(xí)）報告實(shí)驗(yàn)（實(shí)習(xí)）名稱 LL （1）文法語法分析設(shè)計 實(shí)驗(yàn)（實(shí)習(xí)）日期 11月 28日 得分 指導(dǎo)教師 林美華 系 計算機(jī) 專業(yè) 計算機(jī)科學(xué)與技術(shù) 年級 2011 班次 計科 3 班 姓名 王欣 學(xué)號 20112308915實(shí)驗(yàn)?zāi)康?熟悉判斷 LL （1）文法的方法及對某一輸入串的分析過程。 2學(xué)會構(gòu)造表達(dá)式文法的預(yù)測分析表。二 實(shí)驗(yàn)內(nèi)容編寫一個語法分析程序，對于給定的輸入串，能夠判斷識別該串是否為給定文法的句型。三 實(shí)驗(yàn)步驟從鍵盤讀入輸入串，并判斷正誤；若無誤，由程序自動構(gòu)造 FIRST、 FOLLOW集以及 SELECT集合，判斷是否為 LL（1）文法； 若符合

2、LL（ 1）文法，由程序自動構(gòu)造 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 pRNode/* 產(chǎn)生式右部結(jié)構(gòu) */int rCursor;/* 右部序號 */struct pRNode *next;struct pNode/* 產(chǎn)生式結(jié)點(diǎn)結(jié)構(gòu) *

3、/int lCursor;/* 左部符號序號 */int rLength;/* 右部長度 */* 注當(dāng) rLength = 1 時， rCursor = -1 為空產(chǎn)生式 */struct pRNode *rHead; /* 右部結(jié)點(diǎn)頭指針 */;char VnMaxVnNum + 1;/* 非終結(jié)符集 */int vnNum;char VtMaxVtNum + 1;/* 終結(jié)符集 */int vtNum;struct pNode PMaxRuleNum;/* 產(chǎn)生式 */int PNum; /* 產(chǎn)生式實(shí)際個數(shù) */ char bufferMaxPLength + 1;char ch; /*

4、 符號或 string ch;*/char stMaxStLength; /* 要分析的符號串 */struct collectNode/* 集合元素結(jié)點(diǎn)結(jié)構(gòu) */int nVt;/* 在終結(jié)符集中的下標(biāo) */struct collectNode *next;struct collectNode* firstMaxVnNum + 1;/*first 集 */struct collectNode* followMaxVnNum + 1;/*follow 集 */ int analyseTableMaxVnNum + 1MaxVtNum + 1 + 1;/* 預(yù)測分析表存放為產(chǎn)生式的編號， +1用

5、于存放結(jié)束符，多 +1用于存放 #(-1)*/int analyseStackMaxStackDepth + 1; /* 分析棧 */int topAnalyse; /* 分析棧頂 */*int reverseStackMaxStackDepth + 1; /* 顛倒順序棧 */*int topReverse; /* 倒敘棧頂 */ void Init();/* 初始化 */int IndexCh(char ch);/* 返回 Vn在 Vn表中的位置 +100、 Vt 在 Vt 表中的位置， -1 表示未找到 */void InputVt();/* 輸入終結(jié)符 */void InputVn()

6、;/*輸入非終結(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);/* 計算 first 集 ,U-xx.*/void AddFirst(int U, int nCh);/* 加入 first 集 */bool HaveEmpty(int nVn); /* 判斷 first 集中是否有空 (-1)*/void Follow(int V);/* 計算 follo

7、w 集 */void AddFollow(int V, int nCh, int kind);/*加入 follow 集，kind = 0 表加入 follow 集， kind = 1 加入 first 集 */void ShowCollect(struct collectNode *collect);/*輸出 first 或 follow 集 */void FirstFollow();/* 計算 first 和 follow*/void CreateAT();/* 構(gòu)造預(yù)測分析表 */void ShowAT();/* 輸出分析表 */void Identify(char *st);/*主控程

8、序 , 為操作方便 */* 分析過程顯示操作為本行變換所用，與教程的顯示方式不同 */void InitStack();/* 初始化棧及符號串 */void ShowStack();/* 顯示符號棧中內(nèi)容 */void Pop();/* 棧頂出棧 */ void Push(int r);/*使用產(chǎn)生式入棧操作 */#include LL1.h void main(void)char todo,ch;Init();InputVn(); InputVt();InputP(); getchar();FirstFollow(); printf( 所得 first 集為： ); ShowCollect(

9、first);printf( 所得 follow 集為： ); ShowCollect(follow);CreateAT(); ShowAT(); todo = y; while(y = todo)printf(n 是否繼續(xù)進(jìn)行句型分析？ (y / n):); todo = getchar();while(y != todo & n != todo) printf(n(y / n)? ); todo = getchar();if(y = todo) int i; InitStack(); printf( 請輸入符號串 (以#結(jié)束 ) : ); ch = getchar();i = 0; whi

10、le(# != 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; i = MaxVnNum; i+)Vni = 0;for(i = 0; i = MaxVtNum; i+)Vti = 0;for(i = 0; i MaxRuleNum; i

11、+)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 + 1; j+) analyseTableij = -1;-1 表示未找到 */* 返回 Vn在 Vn表中的位置 +100、 Vt 在 Vt 表中的位置， int IndexCh(c

12、har 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 ShowChArray(char* collect)int k = 0;while(0 != collectk)printf( %c , collectk+);printf(n);/* 輸入非終結(jié)符 */void Inp

13、utVn()int inErr = 1;int n,k;char ch;while(inErr)printf(n 請輸入所有的非終結(jié)符，注意： ); printf( 請將開始符放在第一位，并以 #號結(jié)束 :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 = #;/* 以“ #”標(biāo)志結(jié)束用于判斷長度是否合法 */k =

14、n; /*k 用于記錄 n 以便改 Vnn=0*/ if(# != ch)if( # != (ch = getchar()while(# != (ch = getchar()printf(n 符號數(shù)目超過限制！ n);inErr = 1; continue;/* 正確性確認(rèn)，正確則，執(zhí)行下下面，否則重新輸入 */ Vnk = 0;ShowChArray(Vn);ch = ;while(y != ch & n != ch)if(n != ch)printf( 輸入正確確認(rèn) ?(y/n):); scanf(%c, &ch);if(n = ch)printf( 錄入錯誤重新輸入！ n); inErr

15、 = 1;elseinErr = 0;/* 輸入終結(jié)符 */void InputVt()int inErr = 1;int n,k;char ch;while(inErr)printf(n 請輸入所有的終結(jié)符，注意： );printf( 以 #號結(jié)束 :n);ch = ;n = 0;/* 初始化數(shù)組 */while(n MaxVtNum)Vtn+ = 0;n = 0;while(# != ch) & (n MaxVtNum)if( != ch & n != ch & -1 = IndexCh(ch)Vtn+ = ch;vtNum+;ch = getchar();Vtn = #; /* 以“ #

16、”標(biāo)志結(jié)束 */k = n; /*k 用于記錄 n 以便改 Vtn=0*/if(# != ch)if( # != (ch = getchar()while(# != (ch = getchar()printf(n 符號數(shù)目超過限制！ n);inErr = 1;continue;/* 正確性確認(rèn)，正確則，執(zhí)行下下面，否則重新輸入 */ Vtk = 0;ShowChArray(Vt);ch = ;while(y != ch & n != ch)if(n != ch) printf( 輸入正確確認(rèn) ?(y/n):); scanf(%c, &ch);if(n = ch)printf( 錄入錯誤重新輸入

17、！ 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(); /* 消除回車符 */, num);printf(n 請輸入文法的 %d個產(chǎn)生式 , 并以回車分隔每個產(chǎn)生式： printf(n);while(i num)printf( 第%d個： , i);/* 初始化 */for(n =0; n MaxPLength; n+)buffern = 0;/* 輸入產(chǎn)生式串 */ch

18、= ;n = 0;while(n != (ch = getchar() & n 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 = n - 3;i+;/* 調(diào)試時使用 */elsen);printf( 輸入符號含非法在成分，請重新輸入！ /* 判

19、斷產(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;/*first & follow*/* 計算 first 集 ,U-xx.*/void First(int U)int i,j;for(i = 0; i PNum; i+)if(Pi.lCursor = U)stru

20、ct pRNode* pt;pt = Pi.rHead;j = 0;while(j pt-rCursor)/* 注: 此處因編程出錯 , 使空產(chǎn)生式時 rlength 同樣是 1, 故此處同樣可處理空產(chǎn)生式 */ 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.rLength) /* 當(dāng)產(chǎn)生式右部都能推出

21、空時 */ AddFirst(U, -1);/* 加入 first 集 */void AddFirst(int U, int nCh)/* 當(dāng)數(shù)值小于 100 時 nCh 為 Vt*/* 當(dāng)處理非終結(jié)符時 ,AddFirst 不添加空項 (-1)*/struct collectNode *pt, *qt;int ch;/* 用于處理 Vn*/pt = NULL;qt = NULL;if(nCh nVt = nCh)break;elseqt = pt;pt = pt-next;if(NULL = pt)pt = (struct collectNode *)malloc(sizeof(struct

22、 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;/* 判斷 first 集中是否有空 (-1)*/bool HaveEmpty(int nVn)if(nVn nVt) retur

23、n true; pt = pt-next;return false;/* 計算 follow 集, 例： U-xVy,U-xV.( 注：初始符必含 # -1)*/ void Follow(int V)int i;struct pRNode *pt ;if(100 = V)/* 當(dāng)為初始符時 */AddFollow(V, -1, 0 );for(i = 0; i rCursor != V) /*注此不能處理： U-xVyVz 的情況 */pt = pt-next;if(NULL != pt)pt = pt-next; /*V 右側(cè)的符號 */if(NULL = pt) /* 當(dāng) V 后為空時 V

24、-xV，將左符的 follow 集并入 V 的 follow 集中 */if(NULL = followPi.lCursor - 100 & Pi.lCursor != V) Follow(Pi.lCursor);AddFollow(V, Pi.lCursor, 0);集 */else /* 不為空時 V-xVy,( 注意： y-) ，調(diào)用 AddFollow 加入 Vt 或 y 的 first while(NULL != pt & HaveEmpty(pt-rCursor)AddFollow(V, pt-rCursor, 1); /*y 的前綴中有空時，加如 first 集 */ pt =

25、pt-next;if(NULL = pt) /* 當(dāng)后面的字符可以推出空時 */if(NULL = followPi.lCursor - 100 & Pi.lCursor != V)Follow(Pi.lCursor);AddFollow(V, Pi.lCursor, 0);else /* 發(fā)現(xiàn)不為空的字符時 */AddFollow(V, pt-rCursor, 1);/* 當(dāng)數(shù)值小于 100 時 nCh 為 Vt*/*# 用-1 表示 ,kind 用于區(qū)分是并入符號的 first 集，還是 follow 集kind = 0 表加入 follow 集， kind = 1 加入 first 集

26、*/void AddFollow(int V, int nCh, int kind)struct collectNode *pt, *qt;int ch;/* 用于處理 Vn*/pt = NULL;qt = NULL;if(nCh nVt = nCh)break;elseqt = 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 =

27、pt;elseqt-next = pt;/*qt 指向 follow 集的最后一個元素 */pt = pt-next;else /* 為非終結(jié)符時，要區(qū)分是加 first 還是 follow*/if(0 = kind)pt = follownCh - 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;/* 輸出 firs

28、t 或 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, Vtpt-nVt); else printf( #);pt = pt-next; i+; printf(n);/* 計算 first 和 follow*/ void FirstFollow()int

29、 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ù)測分析表 , 例： U:xyz=*/ void CreateAT()int i;struct pRNode *pt;struct collectNode *ct;for(i = 0; i rCursor)/* 處理非終結(jié)符，當(dāng)為終結(jié)符時，定含空為假跳出 */ ct = firstpt-rCursor - 100;while(NULL !=

30、 ct)if(-1 != ct-nVt) analyseTablePi.lCursor - 100ct-nVt = i;ct = ct-next;pt = pt-next; if(NULL = pt)/*NULL = pt ，說明 xyz-, 用到 follow 中的符號 */ ct = followPi.lCursor - 100;while(NULL != ct)if(-1 != ct-nVt) analyseTablePi.lCursor - 100ct-nVt = i;else /* 當(dāng)含有 #號時 */ analyseTablePi.lCursor - 100vtNum = i;ct

31、 = ct-next;elseif(100 rCursor) /* 不含空的非終結(jié)符 */ct = firstpt-rCursor - 100; while(NULL != ct) analyseTablePi.lCursor - 100ct-nVt = i; ct = ct-next;else /* 終結(jié)符或者空 */if(-1 = pt-rCursor) /*-1 為空產(chǎn)生式時 */ ct = followPi.lCursor - 100;while(NULL != ct)if(-1 != ct-nVt)analyseTablePi.lCursor - 100ct-nVt = i; els

32、e /* 當(dāng)含有 #號時 */analyseTablePi.lCursor - 100vtNum = i; ct = ct-next;else /* 為終結(jié)符 */analyseTablePi.lCursor - 100pt-rCursor = i; /* 輸出分析表 */void ShowAT()int i,j;1 printf( 構(gòu)造預(yù)測分析表如下： n); printf(t|t);for(i = 0; i vtNum; i+) printf(%ct, Vti); printf(#tn);2 printf(- - -t|- - -t);for(i = 0; i = vtNum; i+) p

33、rintf(- - -t);printf(n);3 for(i = 0; i vnNum; i+)printf(%ct|t, Vni);for(j = 0; j analyseStacktopAnalyse) /* 當(dāng)為終結(jié)符時 */if(analyseStacktopAnalyse = IndexCh(stcurrent)/* 匹配出棧，指示器后移 */Pop(); current+; step+;printf(%dt, step);ShowStack(); printf(tt%ctt 出棧、后移 n, stcurrent);elseprintf(%c-%c 不匹配！ , analyseSt

34、acktopAnalyse, stcurrent); printf( 此串不是此文法的句子！ n);return;else /* 當(dāng)為非終結(jié)符時 */r = analyseTableanalyseStacktopAnalyse- 100IndexCh(stcurrent);if(-1 != r)Push(r); /* 產(chǎn)生式右部代替左部，指示器不移動 */ step+;printf(%dt, step);ShowStack(); printf(tt%ctt%dn, stcurrent, r);elseprintf( 無可用產(chǎn)生式，此串不是此文法的句子！ n); return;if(# = stcurrent