编译原理-分析中间代码生成程序

编译原理实验报告一、实验目的本次编译原理实验的主要目的是通过实践加深对编译原理中词法分析、语法分析、语义分析和代码生成等关键环节的理解，并提高实际动手能力和问题解决能力。

二、实验环境本次实验使用的编程语言为 C/C+＋，开发工具为 Visual Studio 2019，操作系统为 Windows 10。

三、实验内容（一）词法分析器的设计与实现词法分析是编译过程的第一个阶段，其任务是从输入的源程序中识别出一个个具有独立意义的单词符号。

在本次实验中，我们使用有限自动机的理论来设计词法分析器。

首先，我们定义了单词的种类，包括关键字、标识符、常量、运算符和分隔符等。

然后，根据这些定义，构建了相应的状态转换图，并将其转换为程序代码。

在实现过程中，我们使用了字符扫描和状态转移的方法，逐步读取输入的字符，判断其所属的单词类型，并将其输出。

（二）语法分析器的设计与实现语法分析是编译过程的核心环节之一，其任务是在词法分析的基础上，根据给定的语法规则，判断输入的单词序列是否构成一个合法的句子。

在本次实验中，我们采用了自顶向下的递归下降分析法来实现语法分析器。

首先，我们根据给定的语法规则，编写了相应的递归函数。

每个函数对应一种语法结构，通过对输入单词的判断和递归调用，来确定语法的正确性。

在实现过程中，我们遇到了一些语法歧义的问题，通过仔细分析语法规则和调整函数的实现逻辑，最终解决了这些问题。

（三）语义分析与中间代码生成语义分析的任务是对语法分析所产生的语法树进行语义检查，并生成中间代码。

在本次实验中，我们使用了四元式作为中间代码的表示形式。

在语义分析过程中，我们检查了变量的定义和使用是否合法，类型是否匹配等问题。

同时，根据语法树的结构，生成相应的四元式中间代码。

（四）代码优化代码优化的目的是提高生成代码的质量和效率。

在本次实验中，我们实现了一些基本的代码优化算法，如常量折叠、公共子表达式消除等。

通过对中间代码进行分析和转换，减少了代码的冗余和计算量，提高了代码的执行效率。

编译原理中间代码生成在编译原理中，中间代码生成是编译器的重要阶段之一、在这个阶段，编译器将源代码转换成一种中间表示形式，这种中间表示形式通常比源代码抽象得多，同时又比目标代码具体得多。

中间代码既能够方便地进行优化，又能够方便地转换成目标代码。

为什么需要中间代码呢？其一，中间代码可以方便地进行编译器优化。

编译器优化是编译器的一个核心功能，它能够对中间代码进行优化，以产生更高效的目标代码。

在中间代码生成阶段，编译器可以根据源代码特性进行一些优化，例如常量折叠、公共子表达式消除、循环不变式移动等。

其二，中间代码可以方便地进行目标代码生成。

中间代码通常比较高级，比目标代码更具有表达力。

通过中间代码，编译器可以将源代码转换成与目标机器无关的形式，然后再根据目标机器的特性进行进一步的优化和转换，最终生成目标代码。

中间代码生成的过程通常可以分为以下几步：1.词法分析和语法分析：首先需要将源代码转换成抽象语法树。

这个过程涉及到词法分析和语法分析两个步骤。

词法分析将源代码划分成一个个的词法单元，例如标识符、关键字、运算符等等。

语法分析将词法单元组成树状结构，形成抽象语法树。

2.语义分析：在语义分析阶段，编译器会对抽象语法树进行静态语义检查，以确保源代码符合语言的语义规定。

同时，还会进行类型检查和类型推导等操作。

3.中间代码生成：在中间代码生成阶段，编译器会将抽象语法树转换成一种中间表示形式，例如三地址码、四元式、特定的中间代码形式等。

这种中间表示形式通常比较高级，能够方便进行编译器的优化和转换。

4.中间代码优化：中间代码生成的结果通常不是最优的，因为生成中间代码时考虑的主要是功能的正确性，并没有考虑性能的问题。

在中间代码生成之后，编译器会对中间代码进行各种优化，以产生更高效的代码。

例如常量折叠、循环优化、死代码删除等等。

5.中间代码转换：在完成了中间代码的优化之后，编译器还可以对中间代码进行进一步的转换。

这个转换的目的是将中间代码转换成更具体、更低级的形式，例如目标机器的汇编代码。

编译原理中的中间代码生成编译原理是计算机科学的一门重要课程。

在编译器的构造过程中，中间代码生成是其核心部分之一。

它是将源代码翻译为目标代码的重要中间阶段。

中间代码生成的过程涉及到链表、树，生成三元式、四元式等多种中间形式。

本文将介绍中间代码生成的过程和其在编译中的作用。

一、中间代码的概念中间代码是指在源程序和目标程序之间所生成的一系列指令的集合。

目标代码是指机器可执行的二进制代码，而中间代码则是一种可传递、可处理和可修改的编译代码形式。

中间代码属于一种中间状态，它不是源代码也不是目标代码，但可以被转换成目标代码。

中间代码可以基于语法树、语法分析栈、语法分析表进行生成，生成的中间代码需要满足语言语法结构和语义规则。

二、中间代码生成的流程在编译过程中，中间代码生成是指将源代码转换成中间代码的过程。

它是在词法分析、语法分析和语义分析阶段之后完成的。

下面介绍一下中间代码生成的流程。

1.源代码转换为语法树编译器通过词法分析和语法分析将源代码转换成语法树。

语法树是一种树形结构，它记录了源代码中各个语句的组成情况。

2.语法树进行语义分析在语法分析之后，编译器进行语义分析，检查语法树的合法性，然后根据语言的语义规则对语法树进行标注。

标注的内容包括符号表信息、数据类型等。

3.中间代码的生成在语义分析后，编译器进入中间代码的生成阶段，生成语句的中间代码。

中间代码通常采用三元式或四元式等形式。

三元式包含操作符、操作数以及结果的地址，四元式中还包括了类型信息。

4.中间代码优化在中间代码生成的过程中，编译器会尽可能地优化中间代码。

可以对中间代码进行多种优化，如常量合并、变量替换、公共子表达式消除等。

5.中间代码转换为目标代码在中间代码生成后，编译器将中间代码转换为目标代码。

目标代码可以是汇编代码或机器代码等不同形式的二进制代码。

三、中间代码生成优化的意义编译器中间代码优化的目标是提高程序的执行效率和降低其资源消耗。

执行效率的提高可以通过以下方式实现：1.减少内存使用编译器可以通过删除冗余代码、去除死代码和不必要的变量等方式来减少中间代码的内存使用。

实验四中间代码生成一．实验目的：掌握中间代码的四种形式（逆波兰式、语法树、三元式、四元式）。

二．实验内容：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. 逆波兰式：
逆波兰式
中缀表达式转逆波兰式：按照算术表达式的计算顺序根据操作数1、（操作数2）、运算符的顺序化成⼀个部分的后缀式，将这个后缀式在算术表达式中看成⼀个操作数继续按照上⾯⽅法分析。

逆波兰式转中缀表达式：根据逆波兰式的序列从左向右找运算符，找到后从这个运算符开始向前找出紧邻的操作数2、操作数1并化成算术表达式，将这个算术表达式看成⼀个操作数，继续往后寻找操作符，重复以上步骤。

注意：操作数均由⼀个字母表⽰。

1. 抽象语法树AST：
抽象语法树中每⼀个⼦树的根结点都对应⼀种动作或运算，它的所有⼦结点对应该动作或运算的参数或运算数。

参数或运算数也可以是另⼀⼦树，代表另⼀动作或运算。

将AST中相同的⼦树合并，这种改进的AST叫做有向⽆环图DAG；
AST与DAG
1. 三地址码TAC
x=y op z或者四元组的形式（op,y,z,x）
TAC
其他TAC语句
常⽤语句的语法制导翻译 :
语义过程GEN表⽰产⽣⼀个TAC或四元式，并且填⼊TAC或四元式表中。

语义过程Newtemp表⽰⽣成⼀个临时变量，每调⽤⼀次，⽣成⼀新的临时变量。

语义变量E. place，⽤来存放 E 的值的存储位置。

语义变量id.place , id 对应的存储位置。

1. 简单赋值语句的翻译 :
赋值语句
1. 布尔表达式的翻译 :
布尔表达式
拉链与回填：
拉链与回填
=拉链与回填。