LL語法分析程序設(shè)計(jì)

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; /*右部序號(hào)*/ struct pRNode *next;struct pNode /*產(chǎn)生式結(jié)點(diǎn)結(jié)構(gòu)*/ int lCursor; /*左部符號(hào)序號(hào)*/ int rLength; /*右部長度*/ /*注當(dāng)r

2、Length = 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 collectNod

3、e /*集合元素結(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 topAn

4、alyse; /*分析棧頂*/*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 Che

5、ckP(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 c

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

7、/#include LL1.hvoid main() char todo,ch; void 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 !=

8、 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 & n != ch) sti+ = ch; ch = getchar(); if(# = ch & i MaxStLength) sti = ch; Identify(st); else printf(輸入出錯(cuò)！n); getchar();v

9、oid 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+) 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 = N

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

11、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 InputVn() int inErr = 1; int n,k; char ch; while(inErr) printf(n請(qǐng)輸入所有的非終結(jié)符，注意：); printf(請(qǐng)將開始符放在第一位，并以#號(hào)結(jié)束:n); ch = ; n = 0; /*初始化數(shù)組*/ while

12、(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 = n; /*k用于記錄n以便改Vnn=0*/ if(# != ch) if( # != (ch = getchar() while(# != (ch = getchar() ; printf(n符號(hào)數(shù)目超過限制！n); inErr = 1; continue; /*

13、正確性確認(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(錄入錯(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

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

15、rr = 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(錄入錯(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);

16、 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)生式串*/ ch = ; n = 0; while(n != (ch = getchar() & n rCursor = IndexCh(buffer3); pt-next = NULL; Pi.rHead = pt; n = 4; while(0 != b

17、uffern) 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í)使用*/ 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)

18、 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* pt; pt = Pi.rHead; j = 0; while(j pt-rCursor) /*注:此處因編程出錯(cuò),使空產(chǎn)生式時(shí) rlength同樣是1,故此處同樣可處理空產(chǎn)生式*/

19、 AddFirst(U, pt-rCursor); break; else if(NULL = firstpt-rCursor - 100) First(pt-rCursor); AddFirst(U, pt-rCursor); if(!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) /*當(dāng)數(shù)值小于100時(shí)nCh為Vt*/*當(dāng)處理非終結(jié)符時(shí),AddFi

20、rst不添加空項(xiàng)(-1)*/ struct collectNode *pt, *qt; int ch; /*用于處理Vn*/ pt = NULL; qt = NULL; if(nCh 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 = firstU - 100) firstU - 100 = pt; else qt-next

21、= pt; /*qt指向first集的最后一個(gè)元素*/ pt = pt-next; else pt = 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-xV.(注：初始符必含#-1)*/void Follow(int V) in

22、t 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) Follow(Pi.lCursor); Ad

23、dFollow(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); AddFollow(V,

24、 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; else

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

26、while(NULL != pt) ch = pt-nVt; AddFollow(V, ch, 0); pt = pt-next; else pt = 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

27、 = 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);/*計(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);

28、i+; /*=構(gòu)造預(yù)測(cè)分析表,例：U:xyz=*/void CreateAT() int i; struct pRNode *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，說明xy

29、z-,用到follow中的符號(hào)*/ 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 if(100 rCursor) /*不含空的非終結(jié)符*/ ct = firstpt-rCursor - 100; while(NULL != ct) analyseTablePi.lCursor - 100c

30、t-nVt = i; ct = ct-next; else /*終結(jié)符或者空*/ if(-1 = pt-rCursor) /*-1為空產(chǎn)生式時(shí)*/ 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.lCursor - 100pt-rCursor

31、= 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); printf(n); for(i = 0; i vnNum; i+) printf(%ct|t, Vni); for(j = 0; j analyseStacktopAnalyse) /*當(dāng)為終結(jié)符時(shí)*/ if(ana

32、lyseStacktopAnalyse = IndexCh(stcurrent) /*匹配出棧，指示器后移*/ 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