搜索
算符优先语法分析设计原理与实现技术XXX1028XXX计科1XXX班功能描述能够有效识别以下算符优先文法E→E+T|E-TT→T*F|T/F|FF→(E)|i所描述算术表达式．主要数据结构描述数据结构功能描述string[]存储该算符优先文法，对栈顶元素进行规约时要用到mapchar,int符号表中的元素映射成整数mapint,int将用整数表示的符号映射到响应的行或列mapint,char将整数映射成相应的字母表中的符号int[]分析栈程序结构描述设计方法1.由文法构造算符优先矩阵+-*/()i#+-*/(=)i#=2.根据算符优先矩阵算数表达式的词法分析结果进行语法分析，分析算法为：数据结构：符号栈S---存放所有读进的符号（计数i）K---符号栈使用深度a---工作单元R,Q---变量分析算法：先找最左素短语的尾部（）再找最左素短语的头部（）以分析表达式i+i*i为例，详细过程如下：函数定义函数原型功能描述voidinit()各种初始化操作，主要是建立符号与整数、整数与行列号、整数与符号之间的映射，也包括各全局变量的初始化voidisVt(int)判断某整数所代表的符号是否是终结符号或’#’voidcomp(inta,intb)比较两整数所代表的字符的优先关系voidadvance()从输入文件中读入一个词boolparser()算符优先分析函数，根据算符优先矩阵进行语法分析intmain(intargc,char*argv[])主函数，参数argv[1]代表输入文件函数调用关系程序执行图maininitisVtadvanceparsercomp程序测试测试用例一：(a+b*c)+d+e+a*c/b首先调用实验一的词法分析程序，得到如下分析结果：(19,'(')(12,'a')(14,'+')(12,'b')(16,'*')(12,'c')(20,')')(14,'+')(12,'d')(14,'+')(12,'e')(14,'+')(12,'a')(16,'*')(12,'c')(17,'/')(12,'b')在以此分析结果作为本程序实验结果的输入，得到如下分析结果：该结果显示了详细的分析过程，且表明该表达式是一个符合该文法的表达式测试用例二：(a+b*c)+d*-a*c+(a+b同样调用实验一的词法分析程序，得到如下结果：(19,'(')(12,'a')(14,'+')(12,'b')(16,'*')(12,'c')(20,')')(14,'+')(12,'d')(16,'*')(15,'-')(12,'a')(16,'*')(12,'c')(14,'+')(19,'(')(12,'a')(14,'+')(12,'b')以此分析结果作为本实验程序的输入，得到如下语法分析结果：实验结果表明，在分析过程中出现了错误，分析过程未完成，该样例是一个非法的表达式．学习总结按算符优先关系所确定的应被规约的子串恰好是当前举行的最左素短语．尽管算符优先分析也属于自底向上语法分析的范畴，但却不是严格的从左至右的规范分析，每步所得的句型自然也不是一个规范句型．采用上述策略进行算符优先分析时，尽管我们也指出了每一最左素短语应规约到的非终结符号，然而每次在查找最左素短语时，起主导作用的是终结符号间的优先关系，两终结符号之间究竟是哪个非终结符号无关宏旨．//operator_prior.cpp:Definestheentrypointfortheconsoleapplication.//#includestdafx.h#includestdio.h#includectype.h#includemap#includevector#includestring#defineID12#defineADD14#defineSUB15#defineMUL16#defineDIV17#defineLP19#defineRP20#defineEOI31#defineSHARP32#defineEQ0#defineBT1#defineLT2#defineUD3#defineN_Base1000usingnamespacestd;FILE*fp;intlookahead,yylineno;boolsuccess;mapint,intintToint;mapchar,intcharToint;mapint,charintTochar;stringgrammer[8]={E+T,E-T,T,T*F,T/F,F,(E),i};intprior_matrix[9][9]={{BT,BT,LT,LT,LT,BT,LT,BT},{BT,BT,LT,LT,LT,BT,LT,BT},{BT,BT,BT,BT,LT,BT,LT,BT},{BT,BT,BT,BT,LT,BT,LT,BT},{LT,LT,LT,LT,LT,EQ,LT,UD},{BT,BT,BT,BT,UD,BT,UD,BT},{BT,BT,BT,BT,UD,BT,UD,BT},{LT,LT,LT,LT,LT,UD,LT,EQ}};voidinit(){success=true;yylineno=0;intToint[ADD]=0;intToint[SUB]=1;intToint[MUL]=2;intToint[DIV]=3;intToint[LP]=4;intToint[RP]=5;intToint[ID]=6;intToint[SHARP]=7;charToint['+']=ADD;charToint['-']=SUB;charToint['*']=MUL;charToint['/']=DIV;charToint['(']=LP;charToint[')']=RP;charToint['i']=ID;intTochar[ADD]='+';intTochar[SUB]='-';intTochar[MUL]='*';intTochar[DIV]='/';intTochar[LP]='(';intTochar[RP]=')';intTochar[ID]='i';intTochar[SHARP]='#';intTochar[N_Base]='N';}boolisVt(inta){if(a=N_Base)returnfalse;elsereturntrue;}intcomp(inta,intb){intx=intToint[a];inty=intToint[b];returnprior_matrix[x][y];}voidadvance(){if(fscanf(fp,(%d,&lookahead)==EOF){lookahead=SHARP;}else{charch;do{ch=fgetc(fp);if(ch=='\n'||ch==EOF)break;}while(true);}yylineno++;}voidparser(){intstack[100],top=0;inti,j,k,ii,jj;stack[top++]=SHARP;advance();do{for(i=0;itop;i++){printf(%c,intTochar[stack[i]]);}printf(\t%c\n,intTochar[lookahead]);for(i=top-1;i=0;i--){if(isVt(stack[i]))break;}intres=comp(stack[i],lookahead);if(res==LT||res==EQ){stack[top++]=lookahead;advance();}elseif(res==BT){inttemp=stack[i];for(j=i-1;j=0;j--){if(isVt(stack[j])){if(comp(stack[j],temp)==LT){break;}else{temp=stack[j];}}}for(k=0;k8;k++){if((int)grammer[k].length()==top-1-j){ii=j+1;jj=0;do{if(grammer[k].at(jj)='A'&&grammer[k].at(jj)='Z'){if(isVt(stack[ii]))break;}else{if(charToint[grammer[k].at(jj)]!=stack[ii])break;}ii++;jj++;}while(iitop&&jj(int)grammer[k].length());if(ii=top)break;}}if(k=8){success=false;return;}top=j+1;stack[top++]=N_Base;}else{success=false;return;}if(stack[0]==SHARP&&stack[1]==N_Base&&stack[2]==SHARP){printf(#N#\n);break;}}while(true);success=true;}intmain(intargc,char*argv[]){if(argc==2){fp=fopen(argv[1],r);init();parser();if(success)printf(Thisisalegalexpression.);elseprintf(Thisisaillegalexpression.);}else{printf(参数错误！\n);}return0;}