自上而下预测分析

《自上而下预测分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、自上而下预测分析算法(C语言版)1:特别注意：文法输入到文件中一定不要输错了，不要多任何空格，换行，但最后一行是空行，也就是倒数第二行末尾有一个换行符，如果执行程序时有错，请仔细检查文法文件(d:grammar.txt)o2：源代码如下：/*自上而下预测分析完美C语言版*//*文法文件将此注释复制至d:grammar.txt文件，最后输入一个换行符+*()iEPTQFE->TPP->+TPp->$T->FQQ・>*FQQ・>$F->(E)F->i*//*$代表空集文法可以是任何符合自上而下分析的文法不要忘了最后输入一个换行符*/#include”stdio

2、.h“#include”string.h“#definenull0#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineN20intvtnum=0;//终结符数目intvnnum=0;〃非终结符数目char*vt;〃指向终结符数组char*vn;//指向非终结符数组intFirst[N][N]={0};//储存first集intFollow[N][N]={0};//储存follow集intpretable[N][N]={0};//预测分析表intflag[20]={0};//标识非终结符能否推出空集typ

3、edefstructVNode{intflag;//标识左部能否推出空集chardata;//左部非终结符intrightjength;〃记录产生式右部的长度char*firstarc;}VNode;VNode*vertices;//左部数组的头指针typedefstruct{charVN;charVT;typedefstruct{Sqv*top;Sqv*base;intstacksize;}Sqstack;SqstackinitStack(){Sqstacksq;sq.base=(Sqv*)malloc(STACK_INIT_SIZE*sizeof(Sqv)

4、);sq.top=sq.base;sq.stacksize=STACK_INIT_SIZE;returnsq;}〃初始化产生式栈voidpushStack(Sqstack*s.chare?charf){if(s->top-s->base>=s->stacksize-l){s->base(Sqv*)realloc((STACKINCREMENT+s->stacksize)*sizeof(Sqv));s->top=s->base+s->stacksize-l;}s->top->VN=e;s->top->VT=f;s・>top++;}voidpopStack(Sqs

5、tack*szchar*e.char*f){s->top-;*e=s->top->VN;*f=s->top->VT;}intinStack(Sqstacks,chare,charf){〃判断(巳f)是否在栈中charm’n;while(s.top!=s.base){s.top-;m=s.top->VN;n二s.top->VT;if((m==e)&&(n==f)){return1;}}return0;voidreadfile(){FILE*fp;inti,j;charch;fp=fopen("d:\grammar.txt,,,,,rt")；讦(fp==null

6、){printf("Errorinopeningthefile!");exit(O);}charstr[20];fgets(str,19,fp);vtnum=strlen(str)-l;//去掉换行符vt=(char*)malloc((vtnum+l)*sizeof(char));for(i=0;i

7、r[i];}intstrlength[20];for(;fgets(stG19,fp);){strlength[expnum]=strlen(str)-l;//储存每一个产生式的长度expnum++；//记录产生式的数目}rewind(fp);//将文件内部指针移至文件头fgets(str,19,fp);fgets(str,19,fp);vertices=(VNode*)malloc(expnum*sizeof(VNode));for(i=0;i

8、;fgetc(fp);fgetc(fp