LL1语法分析c++实现,first集,follow集,分析表,分析栈

1、/LL (1) 文法(源代码 )#i nclude 八stdio.h#include ,r std l ib.h M#dcfine MaxRuleNum 8#define MaxVnNum 5#dcfine MaxVtNuni 5#dcfine MaxStackDepth 20#dcfine MaxPLength 20#dcfine MaxStLength 50struct pRNode /* 产生式右部结构卸int rCursor;stmct pRNode *next;struct pNodeint lCursor;int rLength;/* 右部长度 *7struct pRNode *r

2、Hcad; /* 右部结点头指针 */;char Vn( MaxVnNum + 1; 尸非终结符集打int vnNum;char VtfMaxVtNum + 1; /* 终结符集 */int vtNum;struct pNode PMaxRuleNum;int PNum;char bufferfMaxPLength + 1;char ch;char stfMaxStLcngth;/* 要分析的符号串 */ struct collectNodeint nVt;struct collectNode *next;；stmct collectNode* firstMaxVnNum + 1; /*fir

3、st 集 */ stmct collectNode* followMax VnNum + 1; follow集 */int analyseTableMaxVnNum + lMaxVtNum + 1 + 1;int analyseStacklMaxStackDepth + 1; /* 分析栈 */int topAnalyse; /* 分析栈顶 *7void Init( )y*初始化 */int IndexCh(char ch);void InputVtO; /* 输入终结符引void InputVn( )y*输入非终结符*/void ShowChArray(char* collect, int

4、num);/* 输出 Vn 或 Vt 的内容 */void InputPO;/* 产生式输入引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 ShowCoIlect(stnict collectNode *collect);/* 输出

5、first 或 follow 集*/void FirstFollow();/*it 算 first 和 follow*/void CreateATO;/* 构造预测分析表 */void ShowATO;/* 输出分析表 =*7void Identify(char *st);void InitStackO;void ShowStackO;void Pop();void Push(int r);int main()char todo.ch;Init():Input Vn();InputVtO;InputPO;getcharO;FirstFollow();printf ( 所得 first 集为：

6、) ；ShowCollect(first); printf ( 所得 follow 集为： ) ； ShowCollect(follow);CreateAT();ShowATO;todo = y; whilc(y = todo)printfCXii 是否继续进行句型分析 ? (y/n): H); todo = getcharO; while (y != todo & n* != todo)printf( Hn(y/n)? H);todo = getchar();if(y = todo)int i;InitStackO;printf ( 请输入符号串 (以#结束 ): );ch = getcha

7、r();i = 0;whilc(# != ch & i v MaxStLength)iff 1 != ch & *ir != ch)sti+ = ch;ch = getchar():if(# = ch & i v MaxStLcngth)sti = ch;Identify(st);)elseprintfC 输入出错！ 】门； getcharO;)void Init() int i j;vnNum = 0;vtNum = 0;PNum = 0;for(i = 0; i = MaxVnNum; i+) Vni =for(i = 0; i = MaxVtNum: i+)Vti =for(i = 0;

8、 i MaxRuleNum; i+)Pi.lCursor = NULL:Pi.rHead = NULL:Pi.rLength = 0;PNum = 0;for(i = 0; i = MaxPLength; i 卄 ) buffer! i =for(i = 0;i MaxVnNum: i+) firstfi = 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?*

9、/while(ch != Vnn & AO 1 != VnnJ) n+;if(T != Vnn)return 100+ n;n = 0; /*is Vt?*/while(ch != Vtn &!= Vtn)n+;if(O* != Vt|n)return n;return -1;)/* 输出 Vn 或 Vl 的内容可void ShowChArray(char* collect)int k = 0;while(A0 , != collectk)printf( M %c collectk+J);printf( Hn M);/* 输入非终结符引void InputVn()int inErr = 1;i

10、nt n,k;char ch;while( inErr)printf( Hn 请输入所有的非终结符 . 注意： ) ；printf ( 请将开始符放在第一位，并以 #号结束 : n); ch= 1 ?; n = 0;/* 初始化数组 */while(n MaxVnNum)Vnn 卄 =n = 0;whiIe(T != ch) & (n MaxVnNum)iff != ch & An != ch & -1 = IndexCh(ch)Vnn+ = ch: vnNum+;ch = getchar();Vn|n = T;/* 以“ #标志结朿用于判断长度是否合法 */ k = n; if(# != c

11、h)if( # != (ch = getchar()while(# != (ch = getchar()?printf(n 符号数目超过限制！n；)inErr = 1;continue;/* 正确性确认，正确那么，执行下下面，否那么重新输入 */Vnk =ShowChArray(Vn);ch = * *;while (y != ch & n* != ch)if(W != ch)printf ( 输入正确确认 ?(y/n): H);scanf(,%c, &ch);if(n = ch)printf( ,f 录入错误重新输入！ n H);inErr = 1;elseinErr = 0;/* 输入终结

12、符 */void InputVt()int inErr = 1;int n,k;char ch;while(inErr)printf ( 请输入所有的终结符，注意： H); print? #号结束 : n);ch = * *; n = 0:/* 初始化数组 */ while(n MaxVtNum)Vtn+ = AO1; n = 0;whilc(# !=&c&h)(n MaxVtNum)iff 1 != ch & W != ch & -1 = IndexCh(ch)Vtn+ = ch; vtNuni+;ch = getchar():Vtn = k = n;if(# ! 二 ch)if( # !=

13、 (ch = getchar()while(# != (ch = getchar()printfCXn 符号数目超过限制 ! n); inErr = 1;continue;VtkJ = 0 ：ShowChArray(Vt);ch = ? *;while (y != ch & n9 != ch)if(W != ch)printf( 输入正确确认 ?(y/n): H); scanf(u%cM, &ch);if(n = ch)printf( M 录入错误重新输入 ! n H);inErr = 1;elseinErr = 0;/* 产生式输入 */ void InputPOchar ch;int i

14、= 0, n.num;printf ( 请输入文法产生式的个数： ) ； scanf(u%dM, &num);: num);PNum = num; getchar(); /* 消除回车符 */ printf( Hii 请输入文法的 d 个产生式，并以回车分隔每个产生式printf( Hn H); while(i num) print 第 d 个：，i);/* 初始化 */for(n =0: n MaxPLength; n+) buffern = AO 1; /* 输入产生式串 */ ch = * *;n = 0;while(n* != (ch = getcharO) & n rCursor =

15、 IndexCh(buffer3J); pt-ncxt = NULL;Pi.rHead = pt; n = 4;whilc(Vy != buffer!n)qt = (pRNode*)malIoc(sizeof(pRNode); qt-rCursor = IndexCh(buffern); qt-next = NULL;pt-next = qt;pt = qt；n+;Pi.rLcngth = n ? 3;i+；elseprintfC 输入符号含非法在成分，请重新输入！n);/* 判断产生式正确性 */bool CheckP(char * st)int n;if(100 IndexCh(st(O)

16、return false:if != stl)return false;if(、 != st2)return false;for(n = 3; AO* != stn; n +) if(-l = IndexCh(stn)return false;return true;void First(int U)int ij;for(i = 0; i PNuni: i+)if(Pi.lCursor= U)struct pRNode* pt;pt = Pi.rHead;j = 0;while(j pt-rCursor)AddFirst(U, pt-rCursor);break;elseif(NULL = f

17、irstpt-rCursor -100)First(pt-rCursor);AddFirst(U, pt-rCursor);if(! HaveEmpty(pt-rCursor)break;elsept = pt-next;j+;if(j = Pi.rLcngth) /* 当产生式右部都能推出空时 */ AddFirst(U, -1);严参加 first 集可void AddFirst(int U, int nCh)stmct collectNode *pt, *qt; int ch; /* 用于处理 Vn*/ pt = NULL;qt = NULL;if(nCh nVt = nCh) brea

18、k; 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;elseqt-next = pt; /*qt 指向 first 集的最后一个元素 */ pt = pt-next;elsept = first|nCh -100; whi!e(NULL != pt)ch = pt-nVt;if(-l != ch)A

19、ddFirst(U. ch);pt = pt-next:)bool HaveEmpty(int nVn)(if(nVn nVt) return tme;pt = pt-next;return false;void Follow(int V)int i;struct pRNode *pt;if(100 = V) 当为初始符时 *7AddFollow(V,0);for(i = 0; i rCursor != V)pt = pt-next;if(NULL != pt) pt = pt-next;if(NULL = pt)if(NULL = followPi.lCursor - 100) & Pi.l

20、Cursor != V)Folio w(Pi.lCursor);AddFollow(V, Pi.lCursor, 0);elsewhile(NULL != pt & HaveEmpty(pt-rCursor)AddFollow(V, pt-rCursor, 1); pt = pt-next; if(NULL = pt)if(NULL = followPi.lCursor - 100 & P|i.lCursor != V)Follow(Pi.lCursor);AddFollow(V, Pi.lCurson 0);elseAddFollow(V, pt-rCursor, 1);void AddFo

21、llow(int V, int nCh. int kind)struct collectNode *pt, *qt;int ch;pt = NULL;qt = NULL;if(nCh nVt = nCh) break;elseqt = pt ；pt = pt-next;if(NULL = pt)pt = (struct collectNode *)malloc zcof(slrucl collectNode);pt-nVt = nCh; pt-next = NULL; if(NULL=followV - 1001) followV - 100 = pt:elseqt-ncxt = pt; /*

22、qt 指向 follow 集的最后一个元素 */pt = pt-next;elseif(0 = kind)pt = follow nCh -100;while(NULL != pt)ch = pt-nVt;AddFollow(V, ch, 0); pt = pt-ncxt;elsept = firstnCh -100; whi!e(NULL != pt)ch = pt-nVt;if(-l != ch)AddFollow(V, ch, 1);pt = pt-ncxt;/* 输出 first 或 follow 集*/void ShowCollect(stmct collectNodc 枠 coll

23、ect)int i;stmet collectNodc *pt;i = 0;while(NULL != collectfi)pt = collecti;printf( Hn%c:t H, Vni); while(NULL != pt) if(-l != pt-nVt)printf( H %c Vtpt-nVt);elseprintf( H #H);pt = pt-next;printf( Hn H);)/* 计算 first 和 follow*/void FirstFollow()int i;i = 0; while(A0 , != Vni)if(NULL = firstfi) Hrst(lO

24、O + i);i+；i = O;0 != Vni) if(NULL=folIowi)Follow(100 + i);i+；/* 构造预测分析表 */ void CreateATOint i;struct pRNode *pt;stmct collcctNodc *ct;for(i = 0; i rCursor)ct = first pt-rCursor ? 100; while(NULL != ct) if(-l != ct-nVt)analyseTablePi.lCursor - 100ct-nVt = i;ct = ct-next; pt = pt-next; if(NULL = pt)

25、ct = fbllowPi.lCursor -100; while(NULL != ct) if(-l != ct-nVt) analyseTableP|i.lCursor - 100ct-nVt = i;elseanalyseTab!ePi.lCursor - 100vtNum = i;ct = ct-next;elseif(100 rCursor) /* 不含空的非终结符旬 ct = first pt-rCursor -100; while(NULL != ct) analyseTablePi.lCursor - 100ct-nVt = i;ct = ct-ncxt; else /* 终结

26、符或者空 */if(-l = pt-rCursor)ct = followPi.lCursor -100; while(NULL != ct) if(-l != ct-nVt) analyseTabIePi.lCursor - 100ct-nVt = i;else /* 当含有 #号时 */ analyseTablePi.lCursor - 100vtNum = i;ct = ct-next;else /* 为终结符旬analyseTabIePi.lCursor - 100pt-rCursor = i;/* 输出分析表 */void ShowATOint ij ；printf( 构造预测分析表

27、如下： n；) printf( Htlt u);for(i = 0; i vtNum; i+)printf( N%ct , VtiJ);printf( H#tir r);printf( N tl t ,r);for(i = 0; i = vtNum; i+)printf( H ) ；printf( ,n H);for(i = 0; i vnNum: i+)printf( N%ctlf Vni);for(j = 0; j analyseStackf top Analyse)if(analyseStackftopAnalyse = IndexCh(stcurrent)Pop(); current+

28、; stcp+: printf( M%dt step); ShowStack();printf( Htt%ctt 出栈、后移 n， stcurrent);elseprintf( M%c-%c 不匹配 ! analyseStacktopAnalyse, stcurrent);printf( 此串不是此文法的句子！ n) ；return;else /* 当为非终结符时引r = analyseTableanaIyseStacktopAnalyse - 100 IndexCh(stcurrent);if(-l != r)Push(r);step 卄： printf( H%dt step);ShowStackO;printf( Htt%ct