语法分析器C源代码_动态建表_非递归预测分析

#include "yufafenxi.h" void main() { char todo,ch; Init(); //初始化 Input_Vn(); //输入非终结符 Input_Vt(); //输入终结符 Input_Pro(); //输入产生式 getchar(); FirstFollow(); printf("所得first集为："); ShowCollect(first); printf("所得follow集为："); ShowCollect(follow); CreateAT(); ShowAT(); todo = 'y'; while(todo=='y') { printf("\n是否继续进行句型分析？(y / n):"); todo = getchar(); while(todo!='y'&&todo!='n') { printf("\n(y / n)? "); todo = getchar(); } if(todo=='y') { 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(); } //初始化函数 void Init() { int i,j; VnNum = 0; VtNum = 0; ProNum = 0; for(i=0; i<=Max_VnNum; i++) Vn[i] = '\0'; for(i=0; i<=Max_VtNum; i++) Vt[i] = '\0'; for(i=0; i<Max_ProNum; i++) { ProNode[i].lCursor = NULL; ProNode[i].rHead = NULL; ProNode[i].rLength = 0; } ProNum = 0; for(i = 0; i <= MaxPLength; i++) buffer[i] = '\0'; for(i = 0; i < Max_VnNum; i++) { first[i] = NULL; follow[i] = NULL; } for(i = 0; i <= Max_VnNum; i++) { for(j = 0; j <= Max_VnNum + 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(collect[k]!='\0') printf(" %c ", collect[k++]); printf("\n"); } //输入非终结符 void Input_Vn() { int inErr = 1; int n,k; char ch; while(inErr) { printf("请输入所有的非终结符,"); printf("请将开始符放在第一位，并以#号结束:\n"); ch = ' '; n = 0; //初始化数组 while(n<Max_VnNum) { Vn[n++] = '\0'; } n = 0; while((ch!='#')&&(n<Max_VnNum)) { if(ch!=' ' && ch!='\n' && IndexCh(ch)==-1 ) { Vn[n++] = ch; VnNum++; } ch = getchar(); } Vn[n]='#'; /*以“#”标志结束用于判断长度是否合法*/ k = n; /*k用于记录n以便改Vn[n]='\0'*/ if(ch!='#') { printf("\n符号数目超过限制!请重新输入:\n"); inErr = 1; } //正确性确认，正确则，执行下下面，否则重新输入 Vn[k] = '\0'; ShowChArray(Vn); ch = ' '; while(ch!='y' && ch!='n') { if(ch!='\n') { printf("输入正确确认?(y/n):"); } scanf("%c", &ch); } if(ch=='n') { printf("输入错误重新输入!\n"); inErr = 1; } else { inErr = 0; } } } //输入终结符 void Input_Vt() { int inErr = 1; int n,k; char ch; while(inErr) { printf("\n请输入所有的终结符，注意："); printf("以#号结束:\n"); ch = ' '; n = 0; /*初始化数组*/ while(n < Max_VtNum) { Vt[n++] = '\0'; } n = 0; while(('#' != ch) && (n < Max_VtNum)) { if(' ' != ch && '\n' != ch && -1 == IndexCh(ch)) { Vt[n++] = ch; VtNum++; } ch = getchar(); } Vt[n] = '#'; /*以“#”标志结束*/ k = n; /*k用于记录n以便改Vt[n]='\0'*/ if('#' != ch) { printf("\n符号数目超过限制! 请重新输入：\n"); inErr = 1; } /*正确性确认，正确则，执行下下面，否则重新输入*/ 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 Input_Pro() { char ch; int i=0, n,pronum; printf("请输入文法产生式的个数："); scanf("%d", &pronum); ProNum=pronum; getchar(); printf("\n请输入文法的%d个产生式,并以回车分隔每个产生式:", pronum); printf("\n"); while(i<pronum) { printf("第%d个: ", i); for(n =0; n < MaxPLength; n++) buffer[n] = '\0'; ch = ' '; n = 0; while((ch=getchar())!='\n'&& n < MaxPLength) { if(ch!=' ') buffer[n++] = ch; } buffer[n] = '\0'; if(CheckP(buffer)) { //写入产生式结构体 pRNode *pt, *qt; ProNode[i].lCursor = IndexCh(buffer[0]); pt = (pRNode*)malloc(sizeof(pRNode)); pt->rCursor = IndexCh(buffer[3]); pt->next = NULL; ProNode[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++; } ProNode[i].rLength = n - 3; i++; } else printf("输入符号含非法在成分，请重新输入：\n"); } } //判断产生式正确性 bool CheckP(char * st) { int n; if(IndexCh(st[0])<100)//如果产生式左部是终结符 return false; if('-' != st[1]) return false; if('>' != st[2]) return false; for(n = 3;st[n]!='\0'; n ++) { if(IndexCh(st[n])==-1) return false; } return true; } //计算first集合 void First(int U) { int i,j; for(i = 0; i < ProNum; i++) { if(ProNode[i].lCursor == U) { struct pRNode* pt; pt = ProNode[i].rHead; j = 0; while(j < ProNode[i].rLength) { if(pt->rCursor<100)//如果是终结符，直接加入First集合 { AddFirst(U, pt->rCursor); break; } else { if(NULL == first[pt->rCursor - 100]) { First(pt->rCursor); } AddFirst(U, pt->rCursor); if(!HaveEmpty(pt->rCursor)) { break; } else { pt = pt->next; } } j++; } if(j >= ProNode[i].rLength) /*当产生式右部都能推出空时*/ AddFirst(U, -1); } } } //加入first集合 void AddFirst(int U, int nCh) /*当处理非终结符时,AddFirst不添加空项(-1)*/ { struct collectNode *pt, *qt; int ch; /*用于处理Vn*/ pt = NULL; qt = NULL; if(nCh < 100) { pt = first[U - 100]; while(NULL != pt) { if(pt->nVt == nCh) break; else { qt = pt; pt = pt->next; } } if(pt==NULL) { pt = (struct collectNode *)malloc(sizeof(struct collectNode)); pt->nVt = nCh; pt->next = NULL; if(NULL == first[U - 100]) { first[U - 100] = pt; } else { qt->next = pt; /*qt指向first集的最后一个元素*/ } pt = pt->next; } } else { pt = first[nCh - 100]; while(NULL != pt) { ch = pt->nVt; if(-1 != ch) { AddFirst(U, ch); } pt = pt->next; } } } //判断first集中是否有空(-1) bool HaveEmpty(int nVn) { if(nVn < 100) //为终结符时(含-1)，在follow集中用到 return false; struct collectNode *pt; pt = first[nVn - 100]; while(pt!=NULL) { if(pt->nVt==-1) return true; pt = pt->next; } return false; } //计算follow集,例：U->xVy,U->xV.(注：初始符必含#——"-1") void Follow(int V) { int i; struct pRNode *pt ; if(100 == V) /*当为初始符时*/ AddFollow(V, -1, 0 ); for(i = 0; i < ProNum; i++) { pt = ProNode[i].rHead; while(NULL != pt && pt->rCursor != V) /*注此不能处理：U->xVyVz的情况*/ pt = pt->next; if(NULL != pt) { pt = pt->next; /*V右侧的符号*/ if(NULL == pt) /*当V后为空时V->xV，将左符的follow集并入V的follow集中*/ { if(NULL == follow[ProNode[i].lCursor - 100] && ProNode[i].lCursor != V) { Follow(ProNode[i].lCursor); } AddFollow(V, ProNode[i].lCursor, 0); } else /*不为空时V->xVy,(注意：y->)，调用AddFollow加入Vt或y的first集*/ { while(NULL != pt && HaveEmpty(pt->rCursor)) { AddFollow(V, pt->rCursor, 1); /*y的前缀中有空时，加如first集*/