下载文档原格式
实验四中间代码生成一．实验目的：掌握中间代码的四种形式（逆波兰式、语法树、三元式、四元式）。
二．实验内容：1、逆波兰式定义:将运算对象写在前面，而把运算符号写在后面。
用这种表示法表示的表达式也称做后缀式。
2、抽象（语法）树：运算对象作为叶子结点，运算符作为内部结点。
3、三元式：形式序号：（op,arg1,arg2）4、四元式：形式（op,arg1,arg2,result）三、以逆波兰式为例的实验设计思想及算法(1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。
(2)读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。
(3)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。
(4)如果不是数字，该字符则是运算符，此时需比较优先关系。
做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。
如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。
倘若不是的话，则将此运算符栈顶的运算符从栈中弹出，将该字符入栈。
(5)重复上述操作(1)-(2)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。
四、程序代码：//这是一个由中缀式生成后缀式的程序#include<iostream.h>#include<string.h>#include<math.h>#include<ctype.h>#define maxbuffer 64void main(){char display_out(char out_ch[maxbuffer], char ch[32]);//int caculate_array(char out_ch[32]);static int i=0;static int j=0;char ch[maxbuffer],s[maxbuffer],out[maxbuffer];cout<<"请输入中缀表达式: ";cin>>ch;for(i=0;i<maxbuffer;i++){out[i]=ch[i];}cout<<"请确认您输入的表达式："; while(out[j]!='#'){cout<<out[j];j++;}cout<<'#'<<endl;display_out(s,out);//caculate_array;}char display_out(char out_ch[32],char ch[]) {int top=-1;int i=0,data[maxbuffer],n;int j=0;char sta[20];while(ch[i]!='#'){if(isalnum(ch[i])){while(isalnum(ch[i])){out_ch[j]=ch[i];j++;i++;}out_ch[j]=' ';j++;}else{switch(ch[i]){case '+':case '-': if(sta[top]=='('||top==-1){top++;sta[top]=ch[i];i++;}else{//j--;out_ch[j]=sta[top];j++;top--;//i++;}break;//break;case '*':case '/':if(sta[top]=='*'&&sta[top]=='/'){out_ch[j]=sta[top];j++;//i++;top--;}else{top++;sta[top]=ch[i];i++;}break ;//break;case '(':top++;sta[top]=ch[i];i++;break;case ')':if(sta[top]=='('){top--;i++;}if(top==-1){//cout<<"错误: 第"<<j<<"个位置的")"没有找到与之匹配的"(""; ch[i]='#';j=0;}else{//while(sta[top]!=‘(‘){out_ch[j]=sta[top];top--;j++;//}break;}break;/*case ‘#‘: out_ch[j]=‘#‘;j++;break;*/default:cout<<" your input is error"<<endl; ch[i]='#';j=0;break;}}}while(top!=-1){out_ch[j]=sta[top];j++;top--;}out_ch[j]='#';n=0;cout<<"逆波兰表达式为: ";while(out_ch[n]!='#'){cout<<out_ch[n];n++;}cout<<endl;j=0;return out_ch[maxbuffer];}五、实验结果：要求：自己给出3个测试用例，观察结果。
编译原理中的中间代码生成编译原理是计算机科学的一门重要课程。
在编译器的构造过程中，中间代码生成是其核心部分之一。
它是将源代码翻译为目标代码的重要中间阶段。
中间代码生成的过程涉及到链表、树，生成三元式、四元式等多种中间形式。
本文将介绍中间代码生成的过程和其在编译中的作用。
一、中间代码的概念中间代码是指在源程序和目标程序之间所生成的一系列指令的集合。
目标代码是指机器可执行的二进制代码，而中间代码则是一种可传递、可处理和可修改的编译代码形式。
中间代码属于一种中间状态，它不是源代码也不是目标代码，但可以被转换成目标代码。
中间代码可以基于语法树、语法分析栈、语法分析表进行生成，生成的中间代码需要满足语言语法结构和语义规则。
二、中间代码生成的流程在编译过程中，中间代码生成是指将源代码转换成中间代码的过程。
它是在词法分析、语法分析和语义分析阶段之后完成的。
下面介绍一下中间代码生成的流程。
1.源代码转换为语法树编译器通过词法分析和语法分析将源代码转换成语法树。
语法树是一种树形结构，它记录了源代码中各个语句的组成情况。
2.语法树进行语义分析在语法分析之后，编译器进行语义分析，检查语法树的合法性，然后根据语言的语义规则对语法树进行标注。
标注的内容包括符号表信息、数据类型等。
3.中间代码的生成在语义分析后，编译器进入中间代码的生成阶段，生成语句的中间代码。
中间代码通常采用三元式或四元式等形式。
三元式包含操作符、操作数以及结果的地址，四元式中还包括了类型信息。
4.中间代码优化在中间代码生成的过程中，编译器会尽可能地优化中间代码。
可以对中间代码进行多种优化，如常量合并、变量替换、公共子表达式消除等。
5.中间代码转换为目标代码在中间代码生成后，编译器将中间代码转换为目标代码。
目标代码可以是汇编代码或机器代码等不同形式的二进制代码。
三、中间代码生成优化的意义编译器中间代码优化的目标是提高程序的执行效率和降低其资源消耗。
执行效率的提高可以通过以下方式实现：1.减少内存使用编译器可以通过删除冗余代码、去除死代码和不必要的变量等方式来减少中间代码的内存使用。
一、实验目的通过在实验二的基础上，增加中间代码生成部分，使程序能够对实验二中的识别出的赋值语句，if语句和while语句进行语义分析，生成四元式中间代码。
二、实验方法实验程序由c语言完成，在Turboc 2.0环境中调试通过。
语义分析程序的基本做法是对文法中的每个产生式分别编写一个语义分析子程序，当程序语法部分进行推倒或规约时，就分别调用各自的语义分析程序。
当语法分析结束时，语义分析也就结束了。
在本实验程序中，当语法分析部分识别出语法正确的句子时，就进入content函数（当语法分析识别出不正确的句子时，不进入content函数，也就是不进行语义分析），然后根据句子的类型进行分类，进入不同的语义处理部分。
对于赋值语句，关键是产生正确的处理算术表达式E的四元式。
程序中的ec函数的功能就是产生算术表达式的四元式，在ec函数中使用了两个栈idshed，opshed，分别是算术表达式的数据栈和符号栈。
每次提取一个数字和一个算符，然后将算符与与栈顶算符进行优先级比较，优先级高则将单前数字和算符进栈，低或者相等的话则将当前栈顶元素进行合并，产生四元式。
直至整个算术表达式结束。
其中还有一些细节问题，具体的做法可以参看程序。
对于实验给定的if语句的文法格式，条件判断式C只中可能是>或者<=两种关系，不可能是布尔表达式，这样程序就简单的多了。
通过ec函数可以产生条件判断式C中的E的四元式，然后只要加上转向四元式就可以了。
本实验程序中只给出真出口的转向四元式，没有给出假出口的转向四元式，这在实际中是不可以的，但在本实验中，实际上是对每条独立的语句进行语法分析，给出假出口转向四元式实际上意义不大，而且假出口转向语句的转移目标必须要到整个语句分析结束以后才可以知道，这样就要建立栈，然后回填，这样会使程序复杂很多，所以没有加上假出口转向四元式。
对于while语句，具体的做法和if语句差不多，所不同的是当while语句结束时，要多出一条无条件转向四元式，重新转到条件判断式C的第一条四元式。
编译方法实验报告2011年10月word文档可自由复制编辑实验目的熟悉算术表达式的语法分析与中间代码生成原理。
实验内容1)2)(3) 法，设计语法制导翻译生成表达式的四元式的算法；编写代码并上机调试运行通过。
输入——算术表达式；输出——语法分析结果；相应的四元式序列。
设计LL(1)分析法或LR(0)分析法的属性翻译文法，并根据这些属性翻译文使用扩展的语法分析器实现语法制导翻译。
实验原理及基本步骤•算术表达式文法：G(E)：o0T | T T•文法变换：T { F co•属性翻译文法：o0 “push(SYNw, )” TE “QUAT”}•递归下降子程序：数据结构： SYN —算符栈；SEM —语义栈；E:入口FrF T:入口1F1四、数据结构设计QUAT QUATF使用递归的结构进行四元式的设计，同时，运用堆栈结构将四元式的输出序列打印出来while ( exp [i]=='+'|| exp[ i]=='-'){syn[++i_s yn]=ex p[i];i++; T();quatO;}while ( ex p[i]=='*' || exp[ i]==7'){ syn[++i_s yn]=ex p[i];i++; F();quat();}void quat(){strcpy(qt[j],"(,//push(SYN,w)//read(w)//push(SYN,w)//read(w))")；//QT[j]:=(SYN[k],SEM[s-1],SEM[s],temp);qt[j][1]=syn[i_syn];qt[j][3]=sem[i_sem-1];qt[j][5]=sem[i_sem];qt[j][7]=temp;j++;i_syn--;i_sem--;i_sem--;sem[++i_sem]=temp; temp++;} //pop(SYN);//pop(SEM);//pop(SEM);//push(SEM,temp);五、关键代码分析(带注释)及运行结果#include <iostream>#include "string.h"#include "stdio.h"using namespace std;char syn[10];int i_syn;char sem[10];int i_sem;char exp[50];int i;char qt[30][15];int j=0;char temp='q';int E();int T();int F();void quat();int main(int argc, char* argv[]){ printf("please input yourexpression:"); scanf("%s",exp);i=0;E();if (exp[i]=='\0')for (i=0;i<j;i++)printf("%s\n",qt[i]);//文法符号栈//运算对象栈//算术表达式区//四元式区//临时变量，取值为 r--z//生成四元式函数//输入四元式//read(w)//输出四元式序列elseprintf("err");return 0;}int E(){T();while ( exp[i]=='+' || exp[i]=='-'){ syn[++i_syn]=exp[i]; i++; T(); quat();} return 1;} int T(){ F(); while ( exp[i]=='*' ||exp[i]=='/'){ syn[++i_syn]=exp[i]; i++; F(); quat();} return 1;} int F(){ if ( exp[i]=='('){ i++; E(); if( exp[i]!=')'){ printf("err"); return 0;}}else if ((exp[i]>='a' && exp[i]<='p')||(exp[i]>='0' &&exp[i]<='9')){ sem[++i_sem]=exp[i]; } else{ printf("err"); return 0;} i++; return 1;} void quat(){ strcpy(qt[j],"( , //QT[j]:=(SYN[k],SEM[s-1],SEM[s],temp); qt[j][1]=syn[i_syn]; qt[j][3]=sem[i_sem-1]; qt[j][5]=sem[i_sem]; qt[j][7]=temp; j++; i_syn--; i_sem--; i_sem--; sem[++i_sem]=temp; temp++;}//push(SYN,w)//read(w) //push(SYN,w) //read(w) //read(w)//push(SEM,w) //read(w))");//pop(SYN); //pop(SEM);//pop(SEM);//push(SEM,temp);■ ■ *QAProgfflm 百fe貞Ptugrarnmablc Pnogroms\WorkSpjcc\'CMk「*Q:\PmgraTn fites\Ptagr*mrT>ablc Pnc>groms\WorkSpflcc\<™fc blocks\'sryuons>ii\b!'n\DrtMjg-..〔_■n '"GAProgra-m rile^\Prograrnmable PrDgrami5\WairtSpac<\cQde blocksXsiybianshi^binyDebug.^.邑_)*<j;\Program Fiks\Progrflmfnabk PrDgrams\WorkSpacc\todc bloci£5\^!yuan4hi\bin\Debug- _旦J 邑 '我们知道，定义一种语言除了要求定义语法外， 还要求定义语义，即对语言 的各种语法单位赋予具体的意义。
语义分析及中间代码生成程序设计原理与实现技术XXX 1028XXX2 计科1XXX班1.程序功能描述完成以下描述赋值语句和算术表达式文法的语法制导生成中间代码四元式的过程。
G[A]:A→V:=EE→E+T∣E-T∣T→T*F∣T/F∣FF→(E)∣iV→i说明：终结符号i 为用户定义的简单变量,即标识符的定义。
2. 设计要求（1）给出每一产生式对应的语义动作；（2）设计中间代码四元式的结构（暂不与符号表有关）。
（3）输入串应是词法分析的输出二元式序列，即某算术表达式“实验项目一”的输出结果。
输出为输入串的四元式序列中间文件。
（4）设计两个测试用例（尽可能完备），并给出程序执行结果四元式序列。
3.主要数据结构描述：本程序采用的是算符优先文法，文法以及算符优先矩阵是根据第四次实验来修改的，所以主要的数据结构也跟第四次差不多，主要为文法的表示，FirstVT集和LastVT集以及算符优先矩阵：算符优先矩阵采用二维字符数组表示的：char mtr[9][9]; //算符优先矩阵4.程序结构描述：本程序一共有8功能函数：void get(); //获取文法void print(); //打印文法void fun(); //求FirstVT 和 LastVTvoid matrix(); //求算符优先矩阵void test(); //测试文法int cmp(char a,char b); 比较两个运算符的优先级 1 0 -1void out(char now,int avg1,int avg2); //打印四元式int ope(char op,int a,int b); //定义四元式计算方法5.实验代码详见附件6.程序测试6.1 功能测试程序运行显示如下功能菜单：选择打印文法：选择构造FirstVt集和LastVT集：选择构造算符优先矩阵：6.2 文法测试测试1:1+2*3测试2:2+3+4*5+(6/2)7.学习总结本次实验完成了语义及中间代码生成的设计原理与实现，所采用的方法为算符优先分析方法，首先根据文法求出此文法的FirstVT集和LastVT集，然后根据他们求出此文法的算符优先矩阵。
中间代码生成-四元式设计文档实验任务:在实验4的基础上，完成以下描述赋值语句和算数表达式文法G[A]的语法制导生成中间代码四元式的过程。
A-->V:=E V--><标识符> E,E+T|E-T|TT,T*F|T/F|F F,(E)|<标识符> 说明:标识符的定义参见实验一程序的功能描述从文件中读入表达式，输出其四元式的结果序列本程序只能生成赋值语句及算数表达式中间代码的四元式不能生成逻辑表达式及其他复杂语句中间代码的四元式，其功能还需要进一步完善。
程序结构描述打开文件成功 NY 结束调用scan()函数从文件读入表达式输出所读入的表达式调用生成四元式函数siyuanshi()表达式中是否有括号 NY处理括号内的处理乘除加减和赋值运算sum=0NY输出成功输出错误提示结束程序测试方案测试用例一:d=a+b*(3*n)/(b-a)测试用例二:x=x*(x+y-(x-y)/(z+x)-y)实验总结此程序基本达到了实验要求，能够生成简单的赋值及算数表达式中间代码的四元式，但其功能实在是过于简单。
第一次调试通过后程序还存在以下不足:(1) 此程序只能从文件中读入一个表达式，读入多个则会出错;(2) 所读入的表达式中若含有多于一个括号，程序会出错;(3) 括号内若多于一个表达式则会出错;(4) 在测试用例二中的分析过程明显是错误的，这足以看出程序的漏洞很多但经过进一步优化算法，以上问题基本解决，但程序中仍然存在很多不足，例如时间效率和空间效率方面做的还不够好，要改善这些不足还需要进一步完善程序，在以后的学习生活中我会根据所学知识的不断深入而不断完善此程序，争取使其功能更加强大。
经过这次实验我更加深刻的理解了生成中间代码的算法思想，及时的将所学知识用于实践，更加深刻的掌握了所学知识。
附录#include<stdlib.h> #include<fstream> #include<iostream> using namespace std;#define MAX 100int m=0,sum=0;//sum用于计算运算符的个数//m用于标记输入表达式中字符的个数char JG='A';char str[MAX];//用于存输入表达式int token=0;//左括号的标志/***********用于更改计算后数组中的值**************/ void change(int e) {int f=e+2;char ch=str[f];if(ch>='A'&&ch<='Z'){for(int l=0;l<m+10;l++){if(str[l]==ch)str[l]=JG;}}if(str[e]>='A'&&str[e]<='Z'){for(int i=0;i<m;i++){if(str[i]==str[e])str[i]=JG;}}}void chengchuchuli(int i,int m) {i++;for( ;i<=m-1;i++)//处理乘除运算{if(str[i]=='*'||str[i]=='/'){cout<<"("<<str[i]<<" "<<str[i-1]<<" "<<str[i+1]<<" "<<JG<<")"<<endl; change(i-1);str[i-1]=str[i]=str[i+1]=JG;sum--;JG=(char)(int)JG++;}}}void jiajianchuli(int j,int m) {j++;for( ;j<=m-1;j++)//处理加减运算{if(str[j]=='+'||str[j]=='-'){cout<<"("<<str[j]<<" "<<str[j-1]<<" "<<str[j+1]<<" "<<JG<<")"<<endl; change(j-1);str[j-1]=str[j]=str[j+1]=JG;sum--;JG=(char)(int)JG++;}}}/*扫描一遍从文件中读入表达式*/void scan(FILE *fin){int p[MAX];char ch='a';int c=-1,q=0;while(ch!=EOF){ch=getc(fin);while(ch==' '||ch=='\n'||ch=='\t') ch=getc(fin);//消除空格和换行符str[m++]=ch;if(ch=='='||ch=='+'||ch=='-'||ch=='*'||ch=='/') sum++;else if(ch=='('){p[++c]=m-1;}else if(ch==')'){q=m-1;chengchuchuli(p[c],q);//从左括号处理到又括号jiajianchuli(p[c],q);JG=(char)(int)JG--;str[p[c]]=str[m-1]=JG;c--;JG=(char)(int)JG++;}}}/*对表达是进行处理并输出部分四元式*/void siyuanshi(){for(int i=0;i<=m-1;i++)//处理乘除运算{if(str[i]=='*'||str[i]=='/'){cout<<"("<<str[i]<<" "<<str[i-1]<<" "<<str[i+1]<<" "<<JG<<")"<<endl; change(i-1);str[i-1]=str[i]=str[i+1]=JG;sum--;JG=(char)(int)JG++;}}for(int j=0;j<=m-1;j++)//处理加减运算{if(str[j]=='+'||str[j]=='-'){cout<<"("<<str[j]<<" "<<str[j-1]<<" "<<str[j+1]<<" "<<JG<<")"<<endl; change(j-1);str[j-1]=str[j]=str[j+1]=JG;sum--;JG=(char)(int)JG++;}}for(int k=0;k<=m-1;k++)//处理赋值运算{if(str[k]=='='){JG=(char)(int)--JG;cout<<"("<<str[k]<<" "<<str[k+1]<<" "<<" "<<" "<<str[k-1]<<")"<<endl; sum--;change(k+1);str[k-1]=JG;}}}/***************主函数*******************/ void main(){char in[MAX]; //用于接收输入输出文件名FILE *fin; //用于指向输入输出文件的指针cout<<"请输入源程序文件名(例如ceshi.txt):";cin>>in;cout<<endl;if ((fin=fopen(in,"r"))==NULL) //判断输入文件名是否正确{cout<<endl<<"打开词法分析输入文件出错!"<<endl;}cout<<"四元式如下:"<<endl;scan(fin);//调用函数从文件中读入表达式/********调用生成四元式的函数********/siyuanshi();/*********判断是否成功**********/if(sum==0) cout<<"成功～"<<endl;else cout<<"有错误～"<<endl;//关闭文件fclose(fin);}。
