输出预测表和语法分析树

#include "stdio.h" #include "stdlib.h" #define MaxRuleNum 8 #define MaxVnNum 5 #define MaxVtNum 5 #define MaxStackDepth 20 #define MaxPLength 20 #define MaxStLength 50 /*-----------------main struct define-----------------*/ /* 声明：非终结符序号 = 100 + Vn的下标 终结符序号 = Vn的下标 */ /*++++++++++文法结构++++++++++*/ struct pRNode /*产生式右部结构*/ { int rCursor; /*右部序号*/ struct pRNode *next; }; struct pNode /*产生式结点结构*/ { int lCursor; /*左部符号序号*/ int rLength; /*右部长度*/ /*注当rLength = 1 时，rCursor = -1为空产生式*/ struct pRNode *rHead; /*右部结点头指针*/ }; char Vn[MaxVnNum + 1]; /*非终结符集*/ int vnNum; char Vt[MaxVtNum + 1]; /*终结符集*/ int vtNum; struct pNode P[MaxRuleNum]; /*产生式*/ int PNum; /*产生式实际个数*/ char buffer[MaxPLength + 1]; char ch; /*符号或string ch;*/ char st[MaxStLength]; /*要分析的符号串*/ /*++first and follow collect struct++*/ struct collectNode /*集合元素结点结构*/ { int nVt; /*在终结符集中的下标*/ struct collectNode *next; }; struct collectNode* first[MaxVnNum + 1]; /*first集*/ struct collectNode* follow[MaxVnNum + 1]; /*follow集*/ /*+++++++++++++analysis table struct++++++++++++++++*/ int analyseTable[MaxVnNum + 1][MaxVtNum + 1 + 1]; /*预测分析表存放为产生式的编号，+1用于存放结束符，多+1用于存放#(-1)*/ /*+++++++++++++++analysis stack struct++++++++++++++*/ int analyseStack[MaxStackDepth + 1]; /*分析栈*/ int topAnalyse; /*分析栈顶*/ /*int reverseStack[MaxStackDepth + 1]; /*颠倒顺序栈*/ /*int topReverse; /*倒叙栈顶*/ /*------------------function declare---------------*/ void Init();/*初始化*/ int IndexCh(char ch); /*返回Vn在Vn表中的位置+100、Vt在Vt表中的位置，-1表示未找到*/ void InputVt(); /*输入终结符*/ void InputVn();/*输入非终结符*/ void ShowChArray(char* collect, int num);/*输出Vn或Vt的内容*/ void InputP();/*产生式输入*/ bool CheckP(char * st);/*判断产生式正确性*/ void First(int U);/*计算first集,U->xx...*/ void AddFirst(int U, int nCh); /*加入first集*/ bool HaveEmpty(int nVn); /*判断first集中是否有空(-1)*/ void Follow(int V);/*计算follow集*/ 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();/*构造预测分析表*/ void ShowAT();/*输出分析表*/ void Identify(char *st);/*主控程序,为操作方便*/ /*分析过程显示操作为本行变换所用，与教程的显示方式不同*/ void InitStack();/*初始化栈及符号串*/ void ShowStack();/*显示符号栈中内容*/ void Pop();/*栈顶出栈*/ void Push(int r);/*使用产生式入栈操作*/ /********************************* LL1.CPP *************************************/ /*-----------------------------------------------*/ /*-------------------main function--------------------*/ void 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是否继续进行句型分析？(y / n):"); todo = getchar(); while('y' != todo && 'n' != todo) { printf("\n(y / n)? "); todo = getchar(); } if('y' == todo) { int i; InitStack(); printf("请输入符号串(以#结束) : "); ch = getchar(); i = 0; while('#' != ch && i < MaxStLength) { if(' ' != ch && '\n' != ch) { st[i++] = ch; } ch = getchar(); } if('#' == ch && i < MaxStLength) { st[i] = ch; Identify(st); } else printf("输入出错！\n"); } } getchar(); } /*---------------function definition------------------*/ void Init() { int i,j; vnNum = 0; vtNum = 0; PNum = 0; for(i = 0; i <= MaxVnNum; i++) Vn[i] = '\0'; for(i = 0; i <= MaxVtNum; i++) Vt[i] = '\0'; for(i = 0; i < MaxRuleNum; i++) { P[i].lCursor = NULL; P[i].rHead = NULL; P[i].rLength = 0; } PNum = 0; for(i = 0; i <= MaxPLength; i++) buffer[i] = '\0'; for(i = 0; i < MaxVnNum; i++) { first[i] = NULL; follow[i] = NULL; } for(i = 0; i <= MaxVnNum; i++) { for(j = 0; j <= MaxVnNum + 1; j++) analyseTable[i][j] = -1; } } /*返回Vn在Vn表中的位置+100、Vt在Vt表中的位置，-1表示未找到*/ int IndexCh(char ch) { int n; n = 0; /*is Vn?*/ while(ch != Vn[n] && '\0' != Vn[n]) n++; if('\0' != Vn[n]) return 100 + n; n = 0; /*is Vt?*/ while(ch != Vt[n] && '\0' != Vt[n]) n++; if('\0' != Vt[n]) return n; return -1; } /*输出Vn或Vt的内容*/ void ShowChArray(char* collect) { int k = 0; while('\0' != collect[k]) { printf(" %c ", collect[k++]); } printf("\n"); } /*输入非终结符*/ void InputVn() { int inErr = 1; int n,k; char ch; while(inErr) { printf("\n请输入所有的非终结符，注意："); printf("请将开始符放在第一位，并以#号结束:\n"); ch = ' '; n = 0; /*初始化数组*/ while(n < MaxVnNum) { Vn[n++] = '\0'; } n = 0; while(('#' != ch) && (n < MaxVnNum)) { if(' ' != ch && '\n' != ch && -1 == IndexCh(ch)) { Vn[n++] = ch; vnNum++; } ch = getchar(); } Vn[n] = '#'; /*以“#”标志结束用于判断长度是否合法*/ k = n; /*k用于记录n以便改Vn[n]='\0'*/ if('#' != ch) { if( '#' != (ch = getchar())) { while('#' != (ch = getchar())) ; printf("\n符号数目超过限制！\n"); inErr = 1; continue; } } /*正确性确认，正确则，执行下下面，否则重新输入*/ Vn[k] = '\0'; ShowChArray(Vn); 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 InputVt() { int inErr = 1; int n,k; char ch; while(inErr) { printf("\n请输入所有的终结符，注意："); printf("以#号结束:\n"); ch = ' '; n = 0; /*初始化数组*/ while(n < MaxVtNum) { Vt[n++] = '\0'; } n = 0; while(('#' != ch) && (n < MaxVtNum)) { if(' ' != ch && '\n' != ch && -1 == IndexCh(ch)) { Vt[n++] = ch; vtNum++; } ch = getchar(); } Vt[n] = '#'; /*以“#”标志结束*/ k = n; /*k用于记录n以便改Vt[n]='\0'*/ if('#' != ch) { if( '#' != (ch = getchar())) { while('#' != (ch = getchar())) ; printf("\n符号数目超过限制！\n"); inErr = 1; continue; } } /*正确性确认，正确则，执行下下面，否则重新输入*/ Vt[k] = '\0'; ShowChArray(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,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++) buffer[n] = '\0'; /*输入产生式串*/ ch = ' '; n = 0; while('\n' != (ch = getchar()) && n < MaxPLength) { if(' ' != ch) buffer[n++] = ch; } buffer[n] = '\0'; /* printf("%s", buffer);*/ if(CheckP(buffer)) { /*填写入产生式结构体*/ pRNode *pt, *qt; P[i].lCursor = IndexCh(buffer[0]); pt = (pRNode*)malloc(sizeof(pRNode)); pt->rCursor = IndexCh(buffer[3]); pt->next = NULL; P[i].rHead = pt; n = 4; while('\0' != buffer[n]) { qt = (pRNode*)malloc(sizeof(pRNode)); qt->rCursor = IndexCh(buffer[n]); qt->next = NULL; pt->next = qt; pt = qt; n++; } P[i].rLength = n - 3; i++; /*调�