编译原理实验报告6 逆波兰式的翻译和计算

实验6逆波兰式的翻译和计算一、实验目的通过实验加深对语法指导翻译原理的理解，掌握算符优先分析的方法，将语法分析所识别的表达式变换成中间代码的翻译方法。二、实验内容设计一个表示能把普通表达式（中缀式）翻译成后缀式，并计算出结果的程序。三、实验要求1、给出文法如下：G[E]E-T|E+T;T-F|T*F;F-i(E);对应的转化为逆波兰式的语义动作如下：E-E(1)opE(2){E.CODE:=E(1).CODE||E(2).CODE||op}E-(E(1)){E.CODE:=E(1).CODE}E-id{E.CODE:=id}2、利用实验5中的算符优先分析算法，结合上面给出的语义动作实现逆波兰式的构造；3、利用栈，计算生成的逆波兰式，步骤如下：1）中缀表达式，从文本文件读入，每一行存放一个表达式，为了降低难度，表达式采用常数表达式；2）利用结合语法制导翻译的算符优先分析，构造逆波兰式；3）利用栈计算出后缀式的结果，并输出；四、实验环境PC微机DOS操作系统或Windows操作系统TurboC程序集成环境或VisualC++程序集成环境五、实验步骤1、了解语法制导翻译的方法，学习后缀式构造的语义动作；2、结合实验5的算符优先程序，设计程序构造后缀式；3、利用栈，编程实现后缀式的计算；4、测试程序运行效果：从文本文件中读表达式，在屏幕上输出，检查输出结果。六、测试数据输入数据：编辑一个文本文文件expression.txt，在文件中输入如下内容：正确结果：（1）1+2;输出：1,2,+3（2）(1+2)*3;输出：1,2,+,3,*9（3）(10+20)*30+(50+60*70)输出：10,20,+30,*50,60,70,*,+,+5150七、实验报告要求实验报告应包括以下几个部分：1、构造逆波兰式的语义动作；2、结合算符优先分析构造逆波兰式的算法和过程；3、语法制导翻译的运行方法；4、程序的测试结果和问题；5、实验总结。八、实验内容源代码：#includeiostream#includestdio.h#includemath.husingnamespacestd;#definemax100charex[max];intn;charGetBC(FILE*fp){//读取文件的字符直至ch不是空白charch;do{ch=fgetc(fp);}while(ch==''||ch=='\t'||ch=='\n');returnch;}voidacquire(FILE*fp){1+2;(1+2)*3;(10+20)*30+(50+60*70);charstr[max];charstack[max];charch;intsum,i,j,t,top=0;i=0;/*读取一行表达式*/GetBC(fp);if(feof(fp))return;else{fseek(fp,-1L,1);printf(\n(%d),n);n++;}do{i++;str[i]=GetBC(fp);}while(str[i]!=';'&&i!=max);sum=i;t=1;i=1;ch=str[i];i++;while(ch!=';'){switch(ch){case'(':top++;stack[top]=ch;break;case')':while(stack[top]!='('){ex[t]=stack[top];top--;t++;}top--;break;case'+':case'-':while(top!=0&&stack[top]!='('){ex[t]=stack[top];top--;t++;}top++;stack[top]=ch;break;case'*':case'/':while(stack[top]=='*'||stack[top]=='/'){ex[t]=stack[top];top--;t++;}top++;stack[top]=ch;break;case'':break;default:while(ch='0'&&ch='9'){ex[t]=ch;t++;/*ex[]中存放逆波兰式*/ch=str[i];i++;/*str[]中存放中缀表达式*/}i--;ex[t]=',';t++;break;}ch=str[i];i++;}/*当中缀表达式扫描完毕，检查ω栈是否为空，若不空则一一退栈*/while(top!=0){ex[t]=stack[top];t++;top--;}ex[t]=';';for(j=1;jsum;j++)printf(%c,str[j]);printf(\n输出：);for(j=1;jt;j++)printf(%c,ex[j]);}voidgetValue(){floatstack[max],d;charch;intt=1,top=0;ch=ex[t];t++;while(ch!=';'){switch(ch){case'+':stack[top-1]=stack[top-1]+stack[top];top--;break;case'-':stack[top-1]=stack[top-1]-stack[top];top--;break;case'*':stack[top-1]=stack[top-1]*stack[top];top--;break;case'/':if(stack[top]!=0)stack[top-1]=stack[top-1]/stack[top];else{printf(除零错误\n);break;/*异常退出*/}top--;break;/*将数字字符转化为对应的数值*/default:d=0;while(ch='0'&&ch='9'){d=10*d+ch-'0';ch=ex[t];t++;}top++;stack[top]=d;}ch=ex[t];t++;}printf(\t%g\n,stack[top]);}voidmain(){FILE*fp;errno_terr;if((err=fopen_s(&fp,C:\\Users\\Administrator\\Desktop\\expression.txt,r))!=NULL){//以只读方式打开文件，失败则退出程序printf(filecannotopen!);exit(0);}n=1;printf(逆波兰式的翻译和计算结果如下：\n);while(1){acquire(fp);if(feof(fp))break;getValue();}fclose(fp);fp=NULL;}实验结果：问题：这次实验较之之前不同，在设计算法与数据结构上花的时间较少，因为之前在数据结构课程里做过使用堆栈完成表达式的计算，也学过中缀式和后缀式，所以代码编得较快，但是其中的算法其实是较复杂的，调试时显得更复杂而编程时我用的是VS，在调试开始时，断点是不能增加的，这样影响了调试的进度，其实之前做实验就注意到了，只是没有特别在意，但这个实验的算法较复杂，断点设得较多，这让我想到使用JAVA，也许使用java开发会更容易，调试的问题也可以解决，主要是使用现在对于C++的熟练程度远不如Java,如果能充分使用类和对象的特点，各种算法的实现将更加有条理，更易读易修改。实验总结：这是最后一个实验了，较之之前的实验难一些，但有着之前的实验作基础，加上理论课的知识，又使用堆栈这个极佳的数据结构，算法也是之前数据结构课程里接触过的，所以只要认真仔细，之后做好调试，也可以做得很快。经过这次实验再加上实验五的算符优先程序，对于算符优先文法的了解更深刻了，能感觉到对于表达式，使用算符优先文法是非常合适的，句型里不存在两个非终结符相邻，两个非终结符之间至少含有一个终结符，这个算符优先文法的特点是最主要的。九、思考题1、语法制导翻译的工作方式？答：对文法中的每个产生式都附加一个语义动作或语义子程序，语法分析程序除执行相应的语法分析动作外，还要执行相应的语义动作或调用相应的语义子程序。2、为什么编译程序要设计生成中间代码方式？答：有三点；1.编译程序结构在逻辑上更为简单明确，前端——中间代码——后端；2.便于编译系统的建立和编译系统的移植，使编译程序改变目标机更容易。3.使目标代码的优化比较容易实现。