实验二--语法分析(算符优先)

实验二语法分析算符优先分析程序一．实验要求⑴选择最有代表性的语法分析方法，如算符优先法、递归子程序法或LR分析法⑵选择对各种常见程序语言都用的语法结构，如赋值语句（尤指表达式）作为分析对象，并且与所选语法分析方法要比较贴切。⑶实习时间为6学时二．实验内容及要求（1）根据给定文法，先求出FirstVt和LastVt集合，构造算符优先关系表（要求算符优先关系表输出到屏幕或者输出到文件）；（2）根据算法和优先关系表分析给定表达式是否是该文法识别的正确的算术表达式（要求输出归约过程）（3）给定表达式文法为：G(E’):E’→#E#E→E+T|TT→T*F|FF→(E)|i(4)分析的句子为:(i+i)*i和i+i)*i三、实验主要代码#defineMAX100char*SR;//输入串charSY[MAX];//移近或规约后剩余串charS[MAX];//堆栈chargrammer[10][30];//保存输入的语法规则charchanshengshi[20][10];charfeizhongjie[10];//存放非终结符charzhongjie[15];//存放终结符intnumf=0;//非终结符个数intnum=0;//终结符个数intM=0;//转换后产生式个数charRelation[6][6];//存放优先关系intFIRSTVT[3][6];//存放firstvt集intLASTVT[3][6];//存放lastvt集inttype(chars)//在终结符串里查找字符a若a在其中返回下标，否则返回-1{intlen=strlen(zhongjie);inttp=-1;for(inti=0;ilen;i++){if(s==zhongjie[i]){tp=i;break;}}returntp;}inttype_fei(chars){intlen=strlen(feizhongjie);inttp=-1;for(inti=0;ilen;i++){if(s==feizhongjie[i]){tp=i;break;}}returntp;}voidtransproduct(intn)//原始产生式处理{intx=0,y=0;for(inti=0;in;i++){for(intj=0;grammer[i][j]!='\0';j++){if(grammer[i][0]'A'||grammer[i][0]'Z'){cout该文法不是算符文发!endl;return;}else{if(type_fei(grammer[i][0])0)feizhongjie[numf++]=grammer[i][0];//获取非终结符符号}if(grammer[i][j]='A'&&grammer[i][j]='Z'){if(grammer[i][j+1]='A'&&grammer[i][j+1]='Z'){cout该文法不是算符文发!endl;return;}}}}for(i=0;in;i++){for(intj=0;grammer[i][j]!='\0';j++){if((grammer[i][j]'Z'||grammer[i][j]'A')&&grammer[i][j]!='-'&&grammer[i][j]!=''&&grammer[i][j]!='|'){if(type(grammer[i][j])0)zhongjie[num++]=grammer[i][j];//获取终结符符号}}}zhongjie[num]='#';zhongjie[num+1]='\0';x=1;for(i=0;in;i++)//转换产生式从第二行开始存{chanshengshi[x][y]=grammer[i][0];y++;for(intj=1;grammer[i][j]!='\0';j++){if(grammer[i][j]=='|'){chanshengshi[x][y]='\0';x++;y=0;chanshengshi[x][y]=grammer[i][0];y++;chanshengshi[x][y++]='-';chanshengshi[x][y++]='';}else{chanshengshi[x][y]=grammer[i][j];y++;}}chanshengshi[x][y]='\0';x++;y=0;}chanshengshi[0][0]=feizhongjie[0];//将开始符号以#_#形式存入第一行产生式数组，以便优先关系构造时使用chanshengshi[0][1]='-';chanshengshi[0][2]='';chanshengshi[0][3]='#';chanshengshi[0][4]=feizhongjie[0];chanshengshi[0][5]='#';chanshengshi[0][6]='\0';M=x;cout转换后产生式如下：endl;for(intj=0;jx;j++){coutchanshengshi[j]endl;}cout产生式包含的终结符有：;for(i=0;i=num;i++){coutzhongjie[i];}coutendl;cout产生式包含的非终结符有：;for(i=0;inumf;i++){coutfeizhongjie[i];}coutendl;}voidfristvt()//计算firstvt集并填入FIRSTVT中{intr1,x,y;for(inti=0;inumf;i++){for(intj=0;jnum;j++)FIRSTVT[i][j]=0;}for(i=1;i=M;i++){r1=type_fei(chanshengshi[i][0]);x=type(chanshengshi[i][3]);y=type(chanshengshi[i][4]);if(x=0){FIRSTVT[r1][x]=1;}else{if(y=0)FIRSTVT[r1][y]=1;}}for(i=M;i=1;i--){inty=type(chanshengshi[i][3]);if(y0){intm=type_fei(chanshengshi[i][0]);intm1=type_fei(chanshengshi[i][3]);if(m!=m1){for(intt=0;tnum;t++)if(FIRSTVT[m1][t]!=0){FIRSTVT[m][t]=FIRSTVT[m1][t];}}}}cout非终结符的firstvt集：endl;for(i=0;inumf;i++){coutfeizhongjie[i];for(intj=0;jnum;j++){if(FIRSTVT[i][j]!=0){coutzhongjie[j];}}coutendl;}}voidlastvt()//求非终结符的lastvt集{intd=0,r1,x,y;for(inti=0;inumf;i++){for(intj=0;jnum;j++)LASTVT[i][j]=0;}for(i=1;i=M;i++){r1=type_fei(chanshengshi[i][0]);//判断是否为非终结符for(intcl=0;chanshengshi[i][cl]!='\0';cl++){d=cl;}x=type(chanshengshi[i][d]);y=type(chanshengshi[i][d-1]);if(x=0){LASTVT[r1][x]=1;}else{if(y=0)LASTVT[r1][y]=1;}}for(i=M;i=1;i--){inty=type(chanshengshi[i][3]);if(y0){intm=type_fei(chanshengshi[i][0]);intm1=type_fei(chanshengshi[i][3]);if(m!=m1){for(intt=0;tnum;t++)if(LASTVT[m1][t]!=0){LASTVT[m][t]=LASTVT[m1][t];}}}}cout非终结符的lastvt集：endl;for(i=0;inumf;i++){coutfeizhongjie[i];for(intj=0;jnum;j++){if(LASTVT[i][j]!=0){coutzhongjie[j];}}coutendl;}}voidcreatRelation()///创建优先关系表{inta=strlen(feizhongjie),b=strlen(zhongjie),c=strlen(*chanshengshi),x,x1,y,y1,f;for(inti=0;i=c;i++){intj=strlen(chanshengshi[i]);for(intv=3;vj;v++){x=type(chanshengshi[i][v]);x1=type_fei(chanshengshi[i][v]);y=type(chanshengshi[i][v+1]);y1=type_fei(chanshengshi[i][v+1]);f=type(chanshengshi[i][v+2]);if((x=0)&&(y=0)){Relation[x][y]='=';}if((v=(j-2))&&x=0&&f=0&&y0){Relation[x][f]='=';}if(x=0&&y0){for(inth=0;hb;h++)if(FIRSTVT[y1][h]==1){Relation[x][h]='';}}if(x0&&y=0){for(intg=0;gb;g++){if(LASTVT[x1][g]==1){Relation[g][y]='';}}}}}}charcharcomplete(chara,charb)//优先关系比较，返回优先关系，若无返回${charret='$';intx=type(a),y=type(b);if(x=0&&y=0)ret=Relation[x][y];returnret;}voiddeelSY()//剩余串向前移一位{inti,j;i=strlen(SY);for(j=0;ji;j++){SY[j]=SY[j+1];}SY[i-1]='\0';}voidmain(){intnumP=0;cout请输入产生式规则数：;cinnumP;cout请输入产生式：endl;for(inti=0;inumP;i++){cingrammer[i];}transproduct(numP);fristvt();lastvt();creatRelation();cout产生式的终结符对应的优先关系如下：endl;printRelent();//输出优先关系FILE*fp;charstr[20];cout请输入原文件名（包括后缀名）：;while(true){cinstr;if((fp=fopen(str,r))==NULL;cout输入错误，请检查文件名endl;elsebreak;}fseek(fp,0,SEEK_END);intn=ftell(fp),p=0;charch;SR=newchar[n];fseek(fp,0,SEEK_SET);while(ch!=EOF){ch=fgetc(fp);SR[p]=ch;SY[p]=ch;p++;}chara,Q,N,B;intstep=0;cout步骤\t符号栈\t\t输入串\t\t\t动作endl;intk=1,j=0,m=1,R,r=strlen(*chanshengshi);S[k]='#';a=SR[k];B=cha