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

2、表；由算法判斷輸入符號(hào)串是否為該文法的句型【源代碼】#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;/*右部序號(hào)*/struct pRNode *next;struct pNode/*產(chǎn)生式結(jié)點(diǎn)結(jié)構(gòu)*/int lCursor;/*左部符號(hào)序號(hào)*/int rLeng

3、th;/*右部長(zhǎng)度*/*注當(dāng)rLength = 1 時(shí)，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í)際個(gè)數(shù)*/char bufferMaxPLength + 1;char ch;/*符號(hào)或string ch;*/char stMaxStLength; /*要分析的符號(hào)串*/struct co

4、llectNode/*集合元素結(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ù)測(cè)分析表存放為產(chǎn)生式的編號(hào)，+1用于存放結(jié)束符，多+1用于存放#(-1)*/int analyseStackMaxStackDepth + 1;/*分析棧*/int topA

5、nalyse;/*分析棧頂*/*int reverseStackMaxStackDepth + 1;/*顛倒順序棧*/*int topReverse;/*倒敘棧頂*/void Init();/*初始化*/int IndexCh(char ch);/*返回Vn在Vn表中的位置+100、Vt在Vt表中的位置，-1表示未找到*/void InputVt();/*輸入終結(jié)符*/void InputVn();/*輸入非終結(jié)符*/void ShowChArray(char* collect, int num);/*輸出Vn或Vt的內(nèi)容*/void InputP();/*產(chǎn)生式輸入*/bool CheckP

6、(char * st);/*判斷產(chǎn)生式正確性*/void First(int U);/*計(jì)算first集,U-xx.*/void AddFirst(int U, int nCh);/*加入first集*/bool HaveEmpty(int nVn); /*判斷first集中是否有空(-1)*/void Follow(int V);/*計(jì)算follow集*/void AddFollow(int V, int nCh, int kind);/*加入follow集，kind = 0表加入follow集，kind = 1加入first集*/void ShowCollect(struct collec

7、tNode *collect);/*輸出first或follow集*/void FirstFollow();/*計(jì)算first和follow*/void CreateAT();/*構(gòu)造預(yù)測(cè)分析表*/void ShowAT();/*輸出分析表*/void Identify(char *st);/*主控程序,為操作方便*/*分析過(guò)程顯示操作為本行變換所用，與教程的顯示方式不同*/void InitStack();/*初始化棧及符號(hào)串*/void ShowStack();/*顯示符號(hào)棧中內(nèi)容*/void Pop();/*棧頂出棧*/void Push(int r);/*使用產(chǎn)生式入棧操作*/#inc

8、lude LL1.hvoid main(void)char todo,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 = getchar();while(y != todo & n != todo)printf

9、(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 & 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;PNu

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

11、j = MaxVnNum + 1; j+)analyseTableij = -1;/*返回Vn在Vn表中的位置+100、Vt在Vt表中的位置，-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 ShowChArray(char* collect

12、)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;/*初始化數(shù)組*/while(n MaxVnNum)Vnn+ = 0;n = 0;while(# != ch) & (n MaxVnNum)if( != ch & n != ch & -1 = IndexCh(

13、ch)Vnn+ = ch;vnNum+;ch = getchar();Vnn = #;/*以“#”標(biāo)志結(jié)束用于判斷長(zhǎng)度是否合法*/k = n;/*k用于記錄n以便改Vnn=0*/if(# != ch)if( # != (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/n)

14、:);scanf(%c, &ch);if(n = ch)printf(錄入錯(cuò)誤重新輸入！n);inErr = 1;elseinErr = 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 MaxVtNum)Vtn+ = 0;n = 0;while(# != ch) & (n MaxVtNum)if( != ch & n != ch & -1 = IndexCh(ch)Vtn+

15、= ch;vtNum+;ch = getchar();Vtn = #;/*以“#”標(biāo)志結(jié)束*/k = n;/*k用于記錄n以便改Vtn=0*/if(# != ch)if( # != (ch = getchar()while(# != (ch = getchar()printf(n符號(hào)數(shù)目超過(guò)限制！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);i

16、f(n = ch)printf(錄入錯(cuò)誤重新輸入！n);inErr = 1;elseinErr = 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 num)printf(第%d個(gè)：, i);/*初始化*/for(n =0; n MaxPLength; n+)buffern = 0;/*輸入產(chǎn)生式串*

17、/ch = ;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)試時(shí)使用*/elseprintf(輸入符號(hào)含非法在成分，請(qǐng)重新輸入！n);/*判斷產(chǎn)生式正

18、確性*/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=*/*計(jì)算first集,U-xx.*/void First(int U)int i,j;for(i = 0; i PNum; i+)if(Pi.lCursor = U)struct pRNode*

19、pt;pt = Pi.rHead;j = 0;while(j pt-rCursor)/*注:此處因編程出錯(cuò),使空產(chǎn)生式時(shí)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)生式右部都能推出空時(shí)*/AddFirst(U, -1);/*加入f

20、irst集*/void AddFirst(int U, int nCh)/*當(dāng)數(shù)值小于100時(shí)nCh為Vt*/*當(dāng)處理非終結(jié)符時(shí),AddFirst不添加空項(xiàng)(-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 collectNode);pt-nVt = nCh;pt-next = NULL;i

21、f(NULL = firstU - 100)firstU - 100 = pt;elseqt-next = pt;/*qt指向first集的最后一個(gè)元素*/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)return true;pt = pt-next;return false;/*計(jì)算follow集,例：U-xVy,U-

22、xV.(注：初始符必含#-1)*/void Follow(int V)int i;struct pRNode *pt;if(100 = V)/*當(dāng)為初始符時(shí)*/AddFollow(V, -1, 0 );for(i = 0; i rCursor != V) /*注此不能處理：U-xVyVz的情況*/pt = pt-next;if(NULL != pt)pt = pt-next;/*V右側(cè)的符號(hào)*/if(NULL = pt)/*當(dāng)V后為空時(shí)V-xV，將左符的follow集并入V的follow集中*/if(NULL = followPi.lCursor - 100 & Pi.lCursor != V

23、)Follow(Pi.lCursor);AddFollow(V, Pi.lCursor, 0);else/*不為空時(shí)V-xVy,(注意：y-)，調(diào)用AddFollow加入Vt或y的first集*/while(NULL != pt & HaveEmpty(pt-rCursor)AddFollow(V, pt-rCursor, 1);/*y的前綴中有空時(shí)，加如first集*/pt = pt-next;if(NULL = pt)/*當(dāng)后面的字符可以推出空時(shí)*/if(NULL = followPi.lCursor - 100 & Pi.lCursor != V)Follow(Pi.lCursor);A

24、ddFollow(V, Pi.lCursor, 0);else/*發(fā)現(xiàn)不為空的字符時(shí)*/AddFollow(V, pt-rCursor, 1);/*當(dāng)數(shù)值小于100時(shí)nCh為Vt*/*#用-1表示,kind用于區(qū)分是并入符號(hào)的first集，還是follow集kind = 0表加入follow集，kind = 1加入first集*/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

25、 = 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集的最后一個(gè)元素*/pt = pt-next;else/*為非終結(jié)符時(shí)，要區(qū)分是加first還是follow*/if(0 = kind)pt = follownCh - 100;while(NULL != pt)c

26、h = 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 != collecti)pt = collecti;printf(n%c:t, Vni);whi

27、le(NULL != pt)if(-1 != pt-nVt)printf( %c, Vtpt-nVt);elseprintf( #);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è)分析表,例：U:xyz=*/void CreateAT()int i;struct pR

28、Node *pt;struct collectNode *ct;for(i = 0; i rCursor)/*處理非終結(jié)符，當(dāng)為終結(jié)符時(shí)，定含空為假跳出*/ct = firstpt-rCursor - 100;while(NULL != ct)if(-1 != ct-nVt)analyseTablePi.lCursor - 100ct-nVt = i;ct = ct-next;pt = pt-next;if(NULL = pt)/*NULL = pt，說(shuō)明xyz-,用到follow中的符號(hào)*/ct = followPi.lCursor - 100;while(NULL != ct)if(-1

29、!= ct-nVt)analyseTablePi.lCursor - 100ct-nVt = i;else/*當(dāng)含有#號(hào)時(shí)*/analyseTablePi.lCursor - 100vtNum = i;ct = 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)生式時(shí)*/ct = followPi.

30、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.lCursor - 100pt-rCursor = i;/*輸出分析表*/void ShowAT()int i,j;1 printf(構(gòu)造預(yù)測(cè)分析表如下：n);printf(t|t);for(i = 0; i vtNum; i+)printf(

31、%ct, Vti);printf(#tn);2 printf(- - -t|- - -t);for(i = 0; i = vtNum; i+)printf(- - -t);printf(n);3 for(i = 0; i vnNum; i+)printf(%ct|t, Vni);for(j = 0; j analyseStacktopAnalyse)/*當(dāng)為終結(jié)符時(shí)*/if(analyseStacktopAnalyse = IndexCh(stcurrent)/*匹配出棧，指示器后移*/Pop();current+;step+;printf(%dt, step);ShowStack();pri

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