LL1語法分析c++實現,first集,follow集,分析表,分析棧

1、/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 /*產生式右部結構*/ int rCursor; struct pRNode *next;struct pNode int lCursor; int rLength; /*右部長度*/

2、struct pRNode *rHead; /*右部結點頭指針*/;char VnMaxVnNum + 1; /*非終結符集*/int vnNum;char VtMaxVtNum + 1; /*終結符集*/int vtNum;struct pNode PMaxRuleNum; int PNum; char bufferMaxPLength + 1;char ch; char stMaxStLength; /*要分析的符號串*/struct collectNode int nVt; struct collectNode *next;struct collectNode* firstMaxVnNu

3、m + 1; /*first集*/struct collectNode* followMaxVnNum + 1; /*follow集*/int analyseTableMaxVnNum + 1MaxVtNum + 1 + 1;int analyseStackMaxStackDepth + 1; /*分析棧*/int topAnalyse; /*分析棧頂*/void Init();/*初始化*/int IndexCh(char ch);void InputVt(); /*輸入終結符*/void InputVn();/*輸入非終結符*/void ShowChArray(char* collect,

4、 int num);/*輸出Vn或Vt的內容*/void InputP();/*產生式輸入*/bool CheckP(char * st);/*判斷產生式正確性*/void First(int U);void AddFirst(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或fol

5、low集*/void FirstFollow();/*計算first和follow*/void CreateAT();/*構造預測分析表*/void ShowAT();/*輸出分析表*/void Identify(char *st);void InitStack();void ShowStack();void Pop();void Push(int r);int main() char todo,ch; Init(); InputVn(); InputVt(); InputP(); getchar(); FirstFollow(); printf("所得first集為：")

6、; ShowCollect(first); printf("所得follow集為："); ShowCollect(follow); CreateAT(); ShowAT(); todo = 'y' while('y' = todo) printf("n是否繼續(xù)進行句型分析？(y / n):"); todo = getchar(); while('y' != todo && 'n' != todo) printf("n(y / n)? "); todo =

7、getchar(); if('y' = todo) int i; InitStack(); printf("請輸入符號串(以#結束) : "); ch = getchar(); i = 0; while('#' != ch && i < MaxStLength) if(' ' != ch && 'n' != ch) sti+ = ch; ch = getchar(); if('#' = ch && i < MaxStLength) st

8、i = ch; Identify(st); else printf("輸入出錯！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+) Pi.lCursor = NULL; Pi.rHead = NULL; Pi.rLength

9、 = 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; int IndexCh(char ch) int n; n = 0; /*is Vn?*/ while(ch != Vnn &&

10、'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的內容*/void ShowChArray(char* collect) int k = 0; while('0' != collectk) printf(" %c ", collectk+);

11、printf("n");/*輸入非終結符*/void InputVn() int inErr = 1; int n,k; char ch; while(inErr) printf("n請輸入所有的非終結符，注意："); printf("請將開始符放在第一位，并以#號結束:n"); ch = ' ' n = 0; /*初始化數組*/ while(n < MaxVnNum) Vnn+ = '0' n = 0; while('#' != ch) && (n < Ma

12、xVnNum) if(' ' != ch && 'n' != ch && -1 = IndexCh(ch) Vnn+ = ch; vnNum+; ch = getchar(); Vnn = '#' /*以“#”標志結束用于判斷長度是否合法*/ k = n; if('#' != ch) if( '#' != (ch = getchar() while('#' != (ch = getchar() ; printf("n符號數目超過限制！n"); in

13、Err = 1; continue; /*正確性確認，正確則，執(zhí)行下下面，否則重新輸入*/ Vnk = '0' ShowChArray(Vn); ch = ' ' while('y' != ch && 'n' != ch) if('n' != ch) printf("輸入正確確認?(y/n):"); scanf("%c", &ch); if('n' = ch) printf("錄入錯誤重新輸入！n"); inErr

14、= 1; else inErr = 0; /*輸入終結符*/void InputVt() int inErr = 1; int n,k; char ch; while(inErr) printf("n請輸入所有的終結符，注意："); printf("以#號結束:n"); ch = ' ' n = 0; /*初始化數組*/ while(n < MaxVtNum) Vtn+ = '0' n = 0; while('#' != ch) && (n < MaxVtNum) if('

15、; ' != ch && 'n' != ch && -1 = IndexCh(ch) Vtn+ = ch; vtNum+; ch = getchar(); Vtn = '#' k = n; if('#' != ch) if( '#' != (ch = getchar() while('#' != (ch = getchar() ; printf("n符號數目超過限制！n"); inErr = 1; continue; Vtk = '0' S

16、howChArray(Vt); ch = ' ' while('y' != ch && 'n' != ch) if('n' != ch) printf("輸入正確確認?(y/n):"); scanf("%c", &ch); if('n' = ch) printf("錄入錯誤重新輸入！n"); inErr = 1; else inErr = 0; /*產生式輸入*/void InputP() char ch; int i = 0, n

17、,num; printf("請輸入文法產生式的個數："); scanf("%d", &num); PNum = num; getchar(); /*消除回車符*/ printf("n請輸入文法的%d個產生式,并以回車分隔每個產生式：", num); printf("n"); while(i < num) printf("第%d個：", i); /*初始化*/ for(n =0; n < MaxPLength; n+) buffern = '0' /*輸入產生式

18、串*/ ch = ' ' n = 0; while('n' != (ch = getchar() && n < MaxPLength) if(' ' != ch) buffern+ = ch; buffern = '0' if(CheckP(buffer) pRNode *pt, *qt; Pi.lCursor = IndexCh(buffer0); pt = (pRNode*)malloc(sizeof(pRNode); pt->rCursor = IndexCh(buffer3); pt->n

19、ext = 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+; else printf("輸入符號含非法在成分，請重新輸入！n"); /*判斷產生式正確性*/bool CheckP(char * st) int n; if

20、(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.lCursor = U) struct pRNode* pt; pt = Pi.rH

21、ead; 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(!HaveEmpty(pt->rCursor) break; else pt = pt->next; j+; if(j >= Pi.rLength) /*當產生式右部都能推出空時*/ A

22、ddFirst(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; else qt = pt; pt = pt->next; if(NULL = pt) pt = (struct collectNode *)malloc(sizeof(str

23、uct collectNode); pt->nVt = nCh; pt->next = NULL; if(NULL = firstU - 100) firstU - 100 = pt; else qt->next = pt; /*qt指向first集的最后一個元素*/ pt = pt->next; else pt = firstnCh - 100; while(NULL != pt) ch = pt->nVt; if(-1 != ch) AddFirst(U, ch); pt = pt->next; bool HaveEmpty(int nVn) if(nV

24、n < 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 !=

25、 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.lCursor, 0); else while(NULL != pt && HaveEmpty(pt->rCursor) AddFollow(V, pt->rCursor, 1

26、); 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(int V, int nCh, int kind) struct collectNode *pt, *qt; int ch; pt = NULL; qt = NULL; if(nCh < 100)

27、/*為終結符時*/ 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 = nCh; pt->next = NULL; if(NULL = followV - 100) followV - 100 = pt; else qt->next = pt; /*qt指向foll

28、ow集的最后一個元素*/ 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->nVt; if(-1 != ch) AddFollow(V, ch, 1); pt = pt->next; /*輸出first或follow集*/void ShowCollect(struct

29、 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*

30、/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+; /*構造預測分析表*/void CreateAT() int i; struct pRNode *pt; struct collectNode *ct; for(i = 0; i < PNum; i+) pt = Pi.rHead; while(NUL

31、L != 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; if(NULL = pt) ct = followPi.lCursor - 100; while(NULL != ct) if(-1 != ct->nVt) analyseTablePi.lCursor

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

33、rsor - 100; while(NULL != ct) if(-1 != ct->nVt) analyseTablePi.lCursor - 100ct->nVt = i; else /*當含有#號時*/ analyseTablePi.lCursor - 100vtNum = i; ct = ct->next; else /*為終結符*/ analyseTablePi.lCursor - 100pt->rCursor = i; /*輸出分析表*/void ShowAT() int i,j; printf("構造預測分析表如下：n"); print

34、f("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 <=

35、vtNum; j+) if(-1 != analyseTableij) printf("R(%d)t", analyseTableij); else printf("errort"); printf("n"); void Identify(char *st) int current,step,r; /*r表使用的產生式的序號*/ printf("n%s的分析過程：n", st); printf("步驟t分析符號棧t當前指示字符t使用產生式序號n"); step = 0; current = 0;

36、 printf("%dt",step); ShowStack(); printf("tt%ctt- -n", stcurrent); while('#' != stcurrent) if(100 > analyseStacktopAnalyse) if(analyseStacktopAnalyse = IndexCh(stcurrent) Pop(); current+; step+; printf("%dt", step); ShowStack(); printf("tt%ctt出棧、后移n"

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