實(shí)驗(yàn)4-算符優(yōu)先分析法

實(shí)驗(yàn)名稱(chēng)：實(shí)驗(yàn)任務(wù)：對(duì)下述描述算符表達(dá)式的算符優(yōu)先文法G[E],給出算符優(yōu)先分析的實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)內(nèi)容：有上下無(wú)關(guān)文法如下：E->E+T|E-T|TT->T*F|T/F|FF->(E)|i說(shuō)明：優(yōu)先關(guān)系矩陣的構(gòu)造過(guò)程：（1）=關(guān)系由產(chǎn)生式F->(E)知‘（’=‘）’FIRSTVT集及LASTVT集FIRSTVT(E)={+,-,*,/,(,i}FIRSTVT(F)={(,i}FIRSTVT(T)={*,/,(,i}LASTVT(E)={+,-,*,/,),i}LASTVT(F)={),i}LASTVT(T)={*,/,),i}(2)<關(guān)系+T則有：+<FIRSTVT(T)-T則有：-<FIRSTVT(T)*F則有：*<FIRSTVT(F)/F則有：/<FIRSTVT(F)(E則有：(<FIRSTVT(E)(3)>關(guān)系E+則有：LASTVT(E)>+E-則有：LASTVT(E)>-T*則有：LASTVT(T)>*T/則有：LASTVT(T)>/E)則有：LASTVT(E)>)(4)請(qǐng)大家畫(huà)出優(yōu)先關(guān)系矩陣終結(jié)符之間的優(yōu)先關(guān)系是唯一的，所以該文法是算符優(yōu)先文法。程序的功能描述：程序由文件讀入字符串（以#結(jié)束），然后進(jìn)行算符優(yōu)先分析，分析過(guò)程中如有錯(cuò)誤，則終止程序并報(bào)告錯(cuò)誤位置，最終向屏幕輸出移近——規(guī)約過(guò)程。 last[i][0]=0; } for(i=0;i<r;i++)//判斷文法是否合法 { for(j=0;st[i][j]!='\0';j++) { if(st[i][0]<'A'||st[i][0]>'Z') { printf("不是算符文法!\n"); exit(-1); } if(st[i][j]>='A'&&st[i][j]<='Z') { if(st[i][j+1]>='A'&&st[i][j+1]<='Z') { printf("不是算符文法!\n"); exit(-1); } } } }for(i=0;i<r;i++) { for(j=0;st[i][j]!='\0';j++) { if((st[i][j]<'A'||st[i][j]>'Z')&&st[i][j]!='-'&&st[i][j]!='>'&&st[i][j]!='|') lable[k++]=st[i][j]; } } lable[k]='#'; lable[k+1]='\0'; table(); printf("每個(gè)非終結(jié)符的FIRSTVT集為：\n");//輸出每個(gè)非終結(jié)符的FIRSTVT集 for(i=0;i<r;i++) { printf("%c:",st[i][0]); for(j=0;j<first[i][0];j++) { printf("%c",first[i][j+1]); } printf("\n"); } printf("每個(gè)非終結(jié)符的LASTVT集為：\n");//輸出每個(gè)非終結(jié)符的LASTVT集 for(i=0;i<r;i++) { printf("%c:",st[i][0]); for(j=0;j<last[i][0];j++) { printf("%c",last[i][j+1]); } printf("\n"); } printf("算符優(yōu)先分析表如下:\n"); for(i=0;lable[i]!='\0';i++) printf("\t%c",lable[i]); printf("\n"); for(i=0;i<k+1;i++) { printf("%c\t",lable[i]); for(j=0;j<k+1;j++) { printf("%c\t",data[i][j]); } printf("\n"); } printf("請(qǐng)輸入文法輸入符號(hào)串以#結(jié)束:"); scanf("%s",input); deal();}voidtable(){ chartext[20][10]; inti,j,k,t,l,x=0,y=0; intm,n; x=0; for(i=0;i<r;i++) { firstvt(st[i][0]); lastvt(st[i][0]); } for(i=0;i<r;i++) { text[x][y]=st[i][0]; y++; for(j=1;st[i][j]!='\0';j++) { if(st[i][j]=='|') { text[x][y]='\0'; x++; y=0; text[x][y]=st[i][0]; y++; text[x][y++]='-'; text[x][y++]='>'; } else { text[x][y]=st[i][j]; y++; } } text[x][y]='\0'; x++; y=0; } r1=x; printf("轉(zhuǎn)化后的文法為:\n"); for(i=0;i<x;i++)//輸出轉(zhuǎn)化后的文法規(guī)則串 { printf("%s\n",text[i]); } for(i=0;i<x;i++)/*求每個(gè)終結(jié)符的推導(dǎo)結(jié)果(去掉"->"后的轉(zhuǎn)化文法，用于最后的規(guī)約)*/ { string[i][0]=text[i][0]; for(j=3,l=1;text[i][j]!='\0';j++,l++) string[i][l]=text[i][j]; string[i][l]='\0'; } for(i=0;i<x;i++) { for(j=1;text[i][j+1]!='\0';j++) { if(zhongjie(text[i][j])&&zhongjie(text[i][j+1])) { m=xiabiao(text[i][j]); n=xiabiao(text[i][j+1]); data[m][n]='='; } if(text[i][j+2]!='\0'&&zhongjie(text[i][j])&&zhongjie(text[i][j+2])&&!zhongjie(text[i][j+1])) { m=xiabiao(text[i][j]); n=xiabiao(text[i][j+2]); data[m][n]='='; } if(zhongjie(text[i][j])&&!zhongjie(text[i][j+1])) { for(k=0;k<r;k++) { if(st[k][0]==text[i][j+1]) break; } m=xiabiao(text[i][j]); for(t=0;t<first[k][0];t++) { n=xiabiao(first[k][t+1]); data[m][n]='<'; } } if(!zhongjie(text[i][j])&&zhongjie(text[i][j+1])) { for(k=0;k<r;k++) { if(st[k][0]==text[i][j]) break; } n=xiabiao(text[i][j+1]); for(t=0;t<last[k][0];t++) { m=xiabiao(last[k][t+1]); data[m][n]='>'; } } } } m=xiabiao('#'); for(t=0;t<first[0][0];t++) { n=xiabiao(first[0][t+1]); data[m][n]='<'; } n=xiabiao('#'); for(t=0;t<last[0][0];t++) { m=xiabiao(last[0][t+1]); data[m][n]='>'; } data[n][n]='=';}voidfirstvt(charc)//求FIRSTVT集{ inti,j,k,m,n; for(i=0;i<r;i++) { if(st[i][0]==c) break; } if(fflag[i]==0) { n=first[i][0]+1; m=0; do { if(m==2||st[i][m]=='|') { if(zhongjie(st[i][m+1])) { first[i][n]=st[i][m+1]; n++; } else { if(zhongjie(st[i][m+2])) { first[i][n]=st[i][m+2]; n++; } if(st[i][m+1]!=c) { firstvt(st[i][m+1]); for(j=0;j<r;j++) { if(st[j][0]==st[i][m+1]) break; } for(k=0;k<first[j][0];k++) { intt; for(t=0;t<n;t++) { if(first[i][t]==first[j][k+1]) break; } if(t==n) { first[i][n]=first[j][k+1]; n++; } } } } } m++; }while(st[i][m]!='\0'); first[i][n]='\0'; first[i][0]=--n; fflag[i]=1; }}voidlastvt(charc)//求LASTVT集{ inti,j,k,m,n; for(i=0;i<r;i++) { if(st[i][0]==c) break; } if(lflag[i]==0) { n=last[i][0]+1; m=0; do { if(st[i][m+1]=='\0'||st[i][m+1]=='|') { if(zhongjie(st[i][m])) { last[i][n]=st[i][m]; n++; } else { if(zhongjie(st[i][m-1])) { last[i][n]=st[i][m-1]; n++; } if(st[i][m]!=c) { lastvt(st[i][m]); for(j=0;j<r;j++) { if(st[j][0]==st[i][m]) break; } for(k=0;k<last[j][0];k++) { intt; for(t=0;t<n;t++) { if(last[i][t]==last[j][k+1]) break; } if(t==n) { last[i][n]=last[j][k+1]; n++; } } } } } m++; }while(st[i][m]!='\0'); last[i][n]='\0'; last[i][0]=--n; lflag[i]=1; }}intdeal(){ inti,j; intx,y; intz;//輸入串的長(zhǎng)度 k=1; s[k]='#';//棧置初值 for(i=0;input[i]!='\0';i++);//計(jì)算輸入串的長(zhǎng)度 z=i--; i=0; while((a=input[i])!='\0') { if(zhongjie(s[k])) j=k; else j=k-1; x=xiabiao(s[j]); y=xiabiao(a); if(data[x][y]=='>') { out(1,k,s); printf("%c",a); out(i+1,z,input); printf("規(guī)約\n"); do { q=s[j]; if(zhongjie(s[j-1])) j=j-1; elsej=j-2; x=xiabiao(s[j]); y=xiabiao(q); }while(data[x][y]!='<'); intm,n,N; for(m=j+1;m<=k;m++) { for(N=0;N<r1;N++) for(n=1;string[N][n]!='\0';n++) { if(!zhongjie(s[m])&&!zhongjie(string[N][n])){if(zhongjie(s[m+1])&&zhongjie(string[N][n+1])&&s[m+1]==string[N][n+1]) { s[j+1]=string[N][0]; break; } } else if(zhongjie(s[m])) if(s[m]==string[N][n]) { s[j+1]=string[N][0]; break; } } }k=j+1; if(k==2&&a=='#') { out(1,k,s); printf("%c",a); out(i+1,z,input); printf("結(jié)束\n"); printf("輸入串符合文法的定義！\n"); return1;