实 验 报 告
【实验名称】 算符优先文法分析
【实验目的】
掌握算符优先分析法的原理，利用算符优先分析法将赋值语句进行语法分析，翻译成等价的四元式表示。
【实验内容】
1.算术表达式的文法可以是： （1）S->#E# （2）E->E+T （3）E->T （4）T->T*F （5）T->F
2.根据算符优先分析法，将表达式进行语法分析，判断一个表达式是否正确。
（6）F->P^F （7）F->P （8）P->(E) （9）P->i
【设计思想】
（1）定义部分：定义常量、变量、数据结构。
（2）初始化：设立算符优先关系表、初始化变量空间（包括堆栈、结构体、数组、临时变量等）；
（3）控制部分：从键盘输入一个表达式符号串；
（4）利用算符优先文法分析算法进行表达式处理：根据优先关系表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示错误信息。
【流程图】
【源代码】
#include char Grammar[20][10]; char VN[10],VT[10]; char BoolArray[10][10]; char FirstBoolArray[10][10]; char LastBoolArray[10][10]; char RelationShip[10][10]; #define StackSize 100; int vtNum,vnNum; int grammarNum; int scount=0; int VNum[20]; int GF[2][10]; typedef struct { char vt; char vn; }array; typedef struct { array *base; array *top; int stacksize; }SqStack; typedef struct{ char s[20]; int step; char curInVt; }CharType; typedef struct{ CharType *base; CharType *top; }Stack; 1 typedef struct { int x; int y; }Position; SqStack S; Stack CS; SqStack InitStack() { int i,j; S.base=(array *)malloc(100*sizeof(array)); if(!S.base)exit(1); S.top=S.base; S.stacksize=StackSize; array temp; printf(\"初始化栈：\\n\"); for(i=1;i<=vnNum;i++) { for(j=1;j<=vtNum;j++) { if(BoolArray[i][j]=='1') { temp.vt=BoolArray[0][j]; temp.vn=BoolArray[i][0]; *S.top=temp; S.top++; printf(\"%c,%c\\n\ } } } return S; } int vNumCount() { for(int i=0;i<=grammarNum;i++) { int j=1; while(Grammar[i][j]!='\\0') { j++; } VNum[i]=j; printf(\"%d \ } printf(\"\\n\"); return 0; } int ScanGrammar() { FILE *fp=fopen(\"算符优先文法.txt\ FILE *tp; char singleChar,nextChar; int i=0,j=0,k,count; while(!feof(fp)) { fscanf(fp,\"%c\ if(singleChar=='?') { Grammar[i][j]='\\0'; break; } if(singleChar=='\\n') { Grammar[i][j]='\\0'; i++; j=0; continue; } if(singleChar=='-') { tp=fp; fscanf(tp,\"%c\ if(nextChar=='>') { fp=tp; continue; } } if(singleChar=='|') { 2 Grammar[i+1][0]=Grammar[i][0]; Grammar[i][j]='\\0'; i++; j=1; continue; } Grammar[i][j]=singleChar; if(singleChar>='A'&&singleChar<='Z') { count=0; while(VN[count]!=singleChar&&VN[count]!='\\0') { count++; } if(VN[count]=='\\0') { VN[count]=singleChar; vnNum=count+1; } } else { count=0; while(VT[count]!=singleChar&&VT[count]!='\\0') { count++; } if(VT[count]=='\\0') { VT[count]=singleChar; vtNum=count+1; } } j++; } printf(\"输入的文法：\\n\"); for(k=0;k<=i;k++) { j=0; while(Grammar[k][j]!='\\0') { if(j==1) { printf(\"->\"); } printf(\"%c\ j++; } printf(\"\\n\"); } printf(\"vnNum:%d\\n\ printf(\"vtNum:%d\\n\ printf(\"%d\\nVN:\ count=0; while(VN[count]!='\\0') { BoolArray[count+1][0]=VN[count]; LastBoolArray[count+1][0]=VN[count]; printf(\"%d%c \ count++; } printf(\"\\nVT:\"); count=0; while(VT[count]!='\\0') { BoolArray[0][count+1]=VT[count]; LastBoolArray[0][count+1]=VT[count]; printf(\"%d%c \ count++; } printf(\"\\n\"); fclose(fp); return i; } int print() 3 { for(int i=1;i<=vnNum;i++) for(int j=1;j<=vtNum;j++) { if(BoolArray[i][j]=='1') printf(\"%c %c\\n\ay[0][j]); } return 0; } int printlast() { for(int i=1;i<=vnNum;i++) for(int j=1;j<=vtNum;j++) { if(LastBoolArray[i][j]=='1') printf(\"%c %c\\nBoolArray[0][j]); } return 0; } int BoolArrayInitial(char vn,char vt) { int row=1,column=1; while(BoolArray[row][0]!=vn) { row++; } while(BoolArray[0][column]!=vt) { column++; } if(BoolArray[row][column]=='1') { return 0; } BoolArray[row][column]='1'; printf(\"%d %d\\n\ return 0; } int LastBoolArrayInitial(char vn,char vt) { int row=1,column=1; while(LastBoolArray[row][0]!=vn) { row++; } while(LastBoolArray[0][column]!=vt) { column++; } if(LastBoolArray[row][column]=='1') { return 0; } LastBoolArray[row][column]='1'; printf(\"%d %d\\n\ return 0; } int FirstInitial(int grammarNum) { int i; for(i=0;i<=grammarNum;i++) { if(Grammar[i][1]<'A'||Grammar[i][1]>'Z') { BoolArrayInitial(Grammar[i][0],Grammar[i][1]); continue; } if(Grammar[i][1]>='A'&&Grammar[i][1]<='Z'&&Grammar[i][2]!='\\0') { if(Grammar[i][2]<'A'||Grammar[i][2]>'Z') BoolArrayInitial(Grammar[i][0],Grammar[i][2]); } 4 } printf(\"文法表中各行文法字符数：\"); vNumCount(); return 0; } int LastInitial(int grammarNum) { int i,count; for(i=0;i<=grammarNum;i++) { count=VNum[i]-1; if(Grammar[i][count]<'A'||Grammar[i][count]>'Z') { LastBoolArrayInitial(Grammar[i][0],Grammar[i][count]); continue; } if(count<=1)continue; if(Grammar[i][count]>='A'&&Grammar[i][count]<='Z'&&Grammar[i][count-1]!='\\0') { if(Grammar[i][count-1]<'A'||Grammar[i][count-1]>'Z') LastBoolArrayInitial(Grammar[i][0],Grammar[i][count-1]); } } printlast(); return 0; } Position GetPos(array temp) { for(int i=1;i<=vnNum;i++) { if(BoolArray[i][0]==temp.vn) break; } for(int j=1;j<=vtNum;j++) { if(BoolArray[0][j]==temp.vt) break; } Position pos; pos.x=i; pos.y=j; return pos; } int PrintStack() { array *p=S.top,scan; scount++; printf(\"scount %d:\\n\ while(p!=S.base) { scan=*p; printf(\"%c %c\\n\ p--; } return 0; } int Insert(array pushTemp) { Position pos; array scan; pos=GetPos(pushTemp); if(BoolArray[pos.x][pos.y]=='\\0') { BoolArray[pos.x][pos.y]='1'; array *p=S.base; while(p!=S.top) { scan=*p; if(scan.vn==pushTemp.vn && scan.vt==pushTemp.vt) break; p++; } if(p==S.top) 5 { S.top++; *S.top=pushTemp; PrintStack(); } } return 1; } int PushPop() { int i; array temp,pushTemp; while(S.top!=S.base) { temp=*S.top; S.top--; for(i=0;i<=grammarNum;i++) { if(Grammar[i][1]==temp.vn) { pushTemp.vn=Grammar[i][0]; pushTemp.vt=temp.vt; Insert(pushTemp); } } } print(); return 0; } int LastPushPop() { int i,count; array temp,pushTemp; while(S.top!=S.base) { temp=*S.top; S.top--; for(i=0;i<=grammarNum;i++) { count=VNum[i]-1; if(Grammar[i][count]==temp.vn) { pushTemp.vn=Grammar[i][0]; pushTemp.vt=temp.vt; Insert(pushTemp); } } } print(); return 0; } int ResetStack() { int i,j; array temp; while(S.top!=S.base) { S.top--; } printf(\"\\n\"); for(i=1;i<=vnNum;i++) { for(j=1;j<=vtNum;j++) { if(BoolArray[i][j]=='1') { temp.vt=BoolArray[0][j]; temp.vn=BoolArray[i][0]; *S.top=temp; S.top++; printf(\"%c,%c\\n\ } } } return 0; } int Judge(int i,int j) { if(Grammar[i][j+1]=='\\0')return -1; 6 if(Grammar[i][j]>='A'&&Grammar[i][j]<='Z'&&(Grammar[i][j+1]<'A'||Grammar[i][j+1]>'Z')) return 0; else return 1; } Position GetOpPos(char vni,char vnj) { for(int i=1;i<=vtNum;i++) if(RelationShip[i][0]==vni) break; for(int j=1;j<=vtNum;j++) { if(RelationShip[0][j]==vnj) break; } Position pos; pos.x=i; pos.y=j; return pos; } int GetVtPos(char vt) { for(int i=1;i<=vtNum;i++) if(LastBoolArray[i][0]==vt) break; return i; } int RelEqual() { Position pos; int j; for(int i=0;i<=grammarNum;i++) { j=1; while(Grammar[i][j]!='\\0') { if(Grammar[i][j+2]=='\\0')break; if((Grammar[i][j]<'A'||Grammar[i][j]>'Z')&&(Grammar[i][j+2]<'A'||Grammar[i][j+2]>'Z')) { pos=GetOpPos(Grammar[i][j],Grammar[i][j+2]); RelationShip[pos.x][pos.y]='=';//2表示= } j++; } } return 0; } int RelShBlanket() { int row; Position pos; int i,j; for(i=1;i<=vtNum;i++) { RelationShip[i][0]=BoolArray[0][i]; RelationShip[0][i]=BoolArray[0][i]; } for(i=0;i<=grammarNum;i++) { j=1; while(Grammar[i][j]!='\\0') { if(Judge(i,j)==-1)break; if(Judge(i,j)==0) { row=GetVtPos(Grammar[i][j]); for(int ii=1;ii<=9;ii++) { if(LastBoolArray[row][ii]=='1') { pos=GetOpPos(LastBoolArray[0][ii],Grammar[i][j+1]); RelationShip[pos.x][pos.y]='>';//3表示大于 7 } } } if(Judge(i,j)==1) { row=GetVtPos(Grammar[i][j+1]); for(int ii=1;ii<=9;ii++) { if(FirstBoolArray[row][ii]=='1') { pos=GetOpPos(Grammar[i][j],FirstBool Array[0][ii]); RelationShip[pos.x][pos.y]='<';//1表示 小于 } } } j++; } } RelEqual(); printf(\"表达式文法算符优先关系表： \\n\"); RelationShip[0][0]=' '; for(i=0;i<=vtNum;i++) { for(int j=0;j<=vtNum;j++) { if(RelationShip[i][j]=='\\0') RelationShip[i][j]='0'; printf(\"%4c \ } printf(\"\\n\"); } return 0; } int ChangeValue() { 8 int change=0; int i,j; for(i=1;i<=vtNum;i++) for(j=1;j<=vtNum;j++) { if(RelationShip[i][j]=='>') { if(GF[0][i]<=GF[1][j]) { GF[0][i]=GF[1][j]+1; change=1; } } if(RelationShip[i][j]=='<') { if(GF[0][i]>=GF[1][j]) { GF[1][j]=GF[0][i]+1; change=1; } } if(RelationShip[i][j]=='=') { if(GF[0][i]!=GF[1][j]) { if(GF[0][i]>GF[1][j]) { GF[1][j]=GF[0][i]; change=1; } if(GF[0][i] int PreFunction() { int change=0,j; for(int i=1;i<=vtNum;i++) { GF[0][i]=1; GF[1][i]=1; } ChangeValue(); printf(\"优先函数:\\n\"); for(i=0;i<=1;i++) { for(j=1;j<=vtNum;j++) { printf(\"%3d\ } printf(\"\\n\"); } return 0; } int PrintCStack() { CharType *p=CS.top,scan; while(p!=CS.base) { scan=*p; printf(\"%d %c %s\\n\Vt,scan.s); p--; } return 0; } int JudgeVt(char a) { for(int j=1;j<=vtNum;j++) { if(a==BoolArray[0][j]) return 1; } return 0; } int JudgeRela(char a,char b)//判断优先关系 { int apos,bpos; for(int i=1;i<=vtNum;i++) { if(a==BoolArray[0][i])apos=i; if(b==BoolArray[0][i])bpos=i; } if(GF[0][apos]>GF[1][bpos])return 1; if(GF[0][apos] 9 while(p!=j) { S[p]='\\0'; p--; } k=j+1; S[k]='N'; } else goto L; } if(sign==0) { if(JudgeRela(S[j],'#')==0) { memcpy(operate,\"接受\// break; } k++; S[k]=Input[i]; memcpy(operate,\"移进\ } if(sign==-1) { k++; S[k]=Input[i]; memcpy(operate,\"移进\ } if(sign==1)prerela='>'; if(sign==0)prerela='='; if(sign==-1)prerela='<'; printf(\"%d\%s\%c\\%c\%s\\%s\\n\count,S,prerela,Input[i],Input,operate); count++; i++; } printf(\"规约结束！\"); return 0; } int main() { grammarNum=ScanGrammar(); FirstInitial(grammarNum); InitStack(); PushPop(); memcpy(FirstBoolArray,BoolArray,100*sizeof(char)); LastInitial(grammarNum); memcpy(BoolArray,LastBoolArray,100*sizeof(char)); scount=0; ResetStack(); LastPushPop(); memcpy(LastBoolArray,BoolArray,100*sizeof(char)); RelShBlanket(); PreFunction(); Reduction(); return 0; } 10 【运行结果】 11 因篇幅问题不能全部显示，请点此查看更多更全内容