-
2020-02-26 20:46:48
- 词法分析程序:读字符流的源程序、识别单词
- 语法分析程序:层次分析,把源程序的单词序列组成语法短语(表示成语法树).
- 语义分析程序:语义审查(静态语义)
上下文相关性
类型匹配
类型转换 - 中间代码生成程序:源程序的内部(中间)表示
三元式、四元式、P-Code、C-Code、 U-Code、bytecode - 代码优化程序: 优化中间代码,节省时间、空间
- 目标代码生成程序 :转换为机器指令上的绝对指令代码
- 符号表管理程序:记录源程序中使用的名字
收集每个名字的各种属性信息
类型、作用域、分配存储信息
这几种程序的主要任务可以用一张图表示如下:
其中没写出来的程序任务:
- 符号表管理:记录源程序中使用的名字。收集每个名字的各种属性信息(类型、作用域、分配存储信息)。
- 出错管理:检查错误、报告出错信息、排错、恢复编译工作。
更多相关内容 -
【编译原理/类C编译器】(四)中间代码生成+目标代码生成
2019-06-25 09:54:19目标代码:mips代码 接上篇:【编译原理/类C编译器】(三)语法分析 运行界面 说明 语法制导翻译(在语法分析过程中,随着分析的步步进展,在使用某个产生式进行推导或归约时便执行相应的语义子程序,完成既定的...说在前面
- 使用语言:javascript
- 语法分析:LL(1)
- 中间代码生成:三地址码 语法制导翻译
- 目标代码:mips代码
- 接上篇:【编译原理/类C编译器】(三)语法分析
运行界面
说明
语法制导翻译(在语法分析过程中,随着分析的步步进展,在使用某个产生式进行推导或归约时便执行相应的语义子程序,完成既定的翻译工作,生成中间代码)
写不动了,有时间再写,github在第一篇
-
编译原理课程设计——目标代码生成器
2011-09-13 14:50:48能完成指定寄存器个数的情况下降一中间代码程序段翻译成会变语言目标代码(汇编指令应包括加、减、乘、除),要求指令条数最少的情况下,尽量使用寄存器,尽量少访问内存,这样才能做到运行效率高。 -
【编译原理】中间代码(一)
2017-12-05 15:08:56在编译器的分析-综合模型中,前端对源程序进行分析并产生中间表示,后端在此基础上生成目标代码。...和中间代码相关的内容包括中间代码表示、静态类型检查和中间代码生成,本文将讨论关于中间代码表示的内容。在编译器的分析-综合模型中,前端对源程序进行分析并产生中间表示,后端在此基础上生成目标代码。理想情况下,和源语言相关的细节在前端分析中处理,而关于目标机器的细节则在后端处理。和中间代码相关的内容包括中间代码表示、静态类型检查和中间代码生成,本文将讨论关于中间代码表示的内容。
有向无环图
表达式的有向无环图(Directed Acyclic Graph,简称DAG)与语法分析树类似,一个DAG的叶子结点对应于原子运算分量,内部结点对应于运算符。与语法分析树不同的是,如果DAG中一个结点N表示一个公共子表达式,那么N可能有多个父结点。举个例子,表达式
a+a*(b-c)+(b-c)*d
的DAG如下:DAG的每个结点通常作为一条记录被存放在数组中,一个记录包括的结点信息有:
- 结点标号:如果记录表示叶子结点,那么结点标号是该结点的文法符号;如果记录表示内部结点,那么结点标号是运算符;
- 词法值:如果记录表示叶子结点,那么记录还包括该结点的词法值,通常是一个指向符号表的指针或者一个常量;
- 左右子结点:如果记录表示内部结点,那么记录还包括该结点的左右子结点。
由于一个DAG的结点都会保存在一个记录数组中,因此我们可以通过数组下标引用某个记录从而获取结点信息,这个数组下标称为相应结点的值编码。
对图1的DAG,它的记录数组为:
其中,左边的下标是每个结点的值编码,并且在某些记录中可以包括值编码。例如:对于第5条记录,它表示内部结点”-“,该结点左边的子结点是叶子结点”b”,右边的子结点是叶子结点”c”,由于代表b和c的记录已经存在并且它们的值编码分别为2和3,因此内部结点”-“的记录为(-, 2, 3)。
三地址代码
三地址代码是形如
x = y op z
的指令集合,之所以名为“三地址代码”,是因为指令x = y op z
具有三个地址:两个运算分量y和z,一个结果变量x。由于三地址代码会对多运算符算术表达式和控制流语句的嵌套结构进行拆分,因此适用于目标代码的生成和优化。三地址代码基于两个基本的概念:地址和指令。简单地说,地址就是运算分量,指令就是运算符,一个地址的表现形式可以是变量名、常量或者编译器生成的临时变量。下面是几种常见的三地址指令形式:
除此之外,另一种方式是用记录表示三地址代码中的每条指令,四元式、三元式和间接三元式是三种用记录表示三地址代码的方式。
四元式
一个四元式是一条表示三地址指令的记录,它有4个字段:
- op:表示一个运算符;
- arg1:表示第一个运算分量;
- arg2:表示第二个运算分量;
- result:表示结果变量。
一个四元式中可能用到了所有4个字段,也可能只用到了其中几个字段,它的几个特例如下:
- 形如
x = minus y
的单目运算符指令不使用arg2字段,”minus”表示单目减运算符; - 形如
x = y
的赋值指令不使用arg2字段,并且它的op字段是”=”; - 形如
param x
的参数传递指令不使用arg2和result字段; - 条件和非条件转移指令将目标标号放入result字段。
下图是一个例子,左边给出了三地址代码,右边是对应的四元式表示:
三元式
通过图2我们发现,一段三地址代码对应的四元式被存放在一个记录数组中,这一点和DAG结点的记录数组很像;另外,四元式中的result字段主要被用于保存临时变量名,这个临时变量是由编译器生成的。如果我们仿照DAG的记录数组用值编码表示临时变量的地址,那么就可以省略四元式中的result字段,三元式就是由此而来的。
一个三元式只有3个字段:op、arg1和arg2,它们的含义和在四元式中相同。为了取代四元式中的result字段,三元式用值编码表示结果变量的地址。图2中三地址代码的三元式表示如下:
在图3(b)中,表格左边的数字是值编码,它表示三元式的结果变量的地址,并且这些值编码可以在三元式中被使用(使用的时候用括号括起来)。另外,对形如
x=y
的赋值指令,和四元式不同的是,三元式的op字段是”=”,arg1字段是”x”,arg2字段是”y”。间接三元式
三地址代码的三元式表示存在一个问题,如果记录数组中的某条记录R的位置发生改变,那么所有使用到记录R的值编码的记录都需要更新。举个例子,在图3(b)中,如果把第1和第2条记录的位置互换,那么第3和第4条记录的内容都会发生改变。为了解决这个问题,提出了用间接三元式来表示三地址代码。
一个间接三元式在三元式的基础上增加了一个列表,这个列表包含了指向三元式的指针。仍以例子说明,下图是图3中三元式的间接三元式:
图4(a)是图3(b)的间接三元式,它使用了一个instruction数组保存要执行的指令,每条指令是一个指向某个三元式的指针。这样的话,当我们改变指令顺序时,就不用再更新三元式了,如图4(b)所示。
静态单赋值形式
静态单赋值(Static Single Assignment,简称SSA)形式是另一种中间表示形式,它和三地址代码的主要区别在于:
第一,SSA中的所有赋值都是针对具有不同名字的变量的,这也是“静态单赋值”名字的由来。这一特性如下图中表示:
第二,由于同一个变量可能在两个不同的控制流路径中被定值,因此SSA使用一种被称为φ函数的表示规则将这个变量的两处定值合并起来。这一特性如下图所示:
欢迎关注微信公众号fightingZhヾ(◍°∇°◍)ノ゙ -
编译原理--中间代码生成
2020-01-08 15:25:16文章目录基础DAG三地址代码问题声明语句的翻译表达式和赋值语句的翻译控制流翻译布尔表达式的翻译switch 语句的翻译过程调用的翻译回填 基础 DAG 语法树是一种图形化的中间表示。但语法树中,公共子表达式每出现一次...基础
DAG
语法树是一种图形化的中间表示。但语法树中,公共子表达式每出现一次,就有一个对应的子树,产生了大量冗余,
因此定义了另一种中间表示:有向无环图(Directed Acyclic Graph, DAG)
有向无环图的构造与抽象语法树类似。
三地址代码
一般包括一个运算符和之多三个运算分量(地址),所以叫做三地址代码。这里的地址包括:变量、常量、临时变量。
- 指令集合
- 运算/赋值指令:x=y op z ,x = op y
- 复制指令:x=y
- 无条件转移指令:goto L
- 条件转移指令:if x goto L ,ifFalse x goto L
- 条件转移指令:if x relop y goto L
- 过程调用/返回 p(x1, x2, …, xn)
• param x1 //设置参数
• param x2
• …
• param xn
• call p, n //调用子过程p,n为参数个数 - 带下标的复制指令:x=y[i] x[i]=y • 注意:i表示离开数组位置第i个字节,而不是数组的第i个元素
- 地址/指针赋值指令: • x=&y x=*y *x=y
- 三地址代码的四元式表示
格式(字段): op arg1 arg2 result
如:+ x y z
对于有些指令,一些参数是空缺的,如
param x1 null null
[if goto] x null L
- 三地址代码的三元式表示
op arg1 arg2
使用三元式的位置来引用三元式的运算结果
- 三地址代码的间接三元式表示
包含了一个指向三元式的指针的列表 我们可以对这个列表进行操作,完成优化功能;操作时不 需要修改三元式中的参数
- 静态单赋值SAA
问题
声明语句的翻译
PPT 24-54
表达式和赋值语句的翻译
- 数组引用生成代码的翻译方案
非终结符号L的三个综合属性
- L.addr指示一个临时变量,计算数组引用的偏移量 ij * wj
- L.array是一个指向数组名字对应的符号表条目的指针, L.array.base为该数组的基地址
- L.type是L生成的子数组的类型,对于任何数组类型t,其宽度由 t.width给出,t.elem给出其数组元素的类型
控制流翻译
- 文法:B表示布尔表达式,S代表语句 S → if (B) S1 ; S → if (B) S1 else S2 ;S → while (B) S1 . 代码的布局见下图
- 继承属性
- B.true:B为真的跳转目标
- B.false:B为假的跳转目标
- S.next:S执行完毕时的跳转目标
例: S ⟶ i f B t h e n S 1 S\longrightarrow if\ B\ then\ S_1 S⟶if B then S1
布尔表达式的翻译
- 当布尔表达式的计算用于跳转分治
布尔表达式翻译的主要语义动作是跳转,而跳转的标签主要根据短路规则来确定。
- 当布尔表达式的计算用于赋值
采用临时变量的方法
switch 语句的翻译
过程调用的翻译
回填
布尔表达式用于语句的控制流时,它总是在取值true时和取值false 时分别跳转到某个位置
-
引入两个综合属性
- truelist: 包含跳转指令(位置)的列表,这些指令在取值true时执行
- falselist:包含跳转指令(位置)的列表,这些指令在取值false时执行
-
辅助函数
- Makelist(i):创建一个只包含i的列表
- Merge(p1,p2):将p1和p2指向的列表合并
- Backpatch(p,i):将i作为目标标号插入到p所指列表中的各指令中
-
控制转移语句的回填
M的作用就是用M.instr记录下一个指令的位置 • N的作用是生成goto指令坯,N.nextlist只包含这个指令 的位置
- 指令集合
-
编译原理完整学习笔记(八):目标代码生成
2020-08-19 10:37:42文章目录目标代码生成一、目标代码生成概述1.1 任务1.2 输入1.3 输出二、抽象计算机模型三、...将分析、翻译、优化后的中间代码变换成目标代码 1.2 输入 源程序的中间表示,以及符号表中的信息 类型检查均已完成 1.3 -
编译原理-中间代码生成
2019-04-17 10:43:52如果不生成中间代码而是直接生成机器语言或者汇编语言形式的目标代码,优点是编译时间短,缺点是目标代码执行效率和质量都比较低,移植性差。 1.2 表示形式 逆波兰式(后缀式)、三地址码(三元式、四元式)、... -
编译原理(十六)——中间代码优化(1)
2020-10-23 11:38:21编译器后端对目标代码进行优化 两个编译器必须等价,编译的结果必须是正确的,即使有99.99%的可能性是不正确的,但是效率很好也不行,正确性是根本。 二、中间代码优化的分类 从优化的种类来看,中间代码的优化可... -
编译原理 第七章复习题 语法制导翻译和中间代码
2019-06-18 08:53:20中间代码是介于源语言程序和什么之间的一种代码?(D)。 A 源代码 B 机器语言 C 汇编语言 D 目标代码 在编译程序中与生成中间代码的目的无关的是(B)。 A 便于目标代码优化 B 便于存储空间的组织 C 便于目标代码... -
编译原理(十三)——中间代码生成(1)
2020-10-12 23:40:35让生成的目标代码效率更高 优化不等同于对代码的精简和算法的优化 (对于高级程序设计语言中可能不能继续进行优化,但是仍然可以在编译中进行优化) 比方说多维下标变量地址计算过程,比方说a[i][j]和 a[i][k],我们... -
内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成
2010-04-28 17:22:48内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成 -
编译实验(三)目标代码生成
2018-01-28 17:00:09而代码生成则是通过四元式来完成。我们先从简单开始做起。 编译实验项目下载链接:http://download.csdn.net/download/supersmart_dong/10224159 例如四元式(j,0,0,7)这样的,代码生成只需要一个goto语句;(j=,A,B... -
编译原理之中间代码生成
2020-04-07 12:35:44如果不生成中间代码而是直接生成机器语言或者汇编语言形式的目标代码,优点是编译时间短,缺点是目标代码执行效率和质量都比较低,移植性差。 为什么不直接翻译成机器码呢,而多此一举生成中间代码再转换?(代码的... -
编译原理(十五)——中间代码生成(3)
2020-10-19 21:52:03一、过程调用和函数调用的中间代码 1. 背景信息 形参种类: 值参、变量参数、函数参数 需要的信息: 形参的种类、传送的内容、偏移、传送的个数、函数类型(实在函数、形式函数) 过程调用和函数调用的语法形式 ... -
中间代码生成及编译器后端概述
2020-08-15 10:13:05中间代码生成及编译器后端概述 中间代码的生成 经过了词法分析,语法分析,语义分析之后就到了中间代码生成阶段 中间代码有两种形式: ...目标代码的生成 中间代码生成之后会对其代码进行一定程度的优化,然后就进入 -
一张图解释编译过程词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成
2017-10-04 11:00:31编译过程概述 -
【编译原理】中间代码(二)
2017-12-13 09:37:46本文是关于中间代码的第二篇文章。在第一篇文章中,我们介绍了3种表示中间代码的方式,本文将接着介绍和静态类型检查以及中间代码生成相关的内容。 -
【编译原理】语义分析及中间代码生成(C/C++源码+实验报告)
2021-10-23 16:47:03文章目录1 实验目的和内容1.1 实验目的1.2 实验内容...(1)通过上机实习,加深对语法制导翻译原理的理解,掌握将语法分析 所识别的语法范畴变换为某种中间代码的语义翻译方法。 (2)掌握目前普遍采用的语义分析方法─ -
编译原理-中间代码的生成
2020-03-30 19:17:46一、中间代码简介 中间代码应具备的特性: 1)便于语法制导翻译 2)既与机器指令的结构相近,又与具体机器无关 使用中间代码的好处: 1)一是便于编译器程序的开发和移植 2)二是代码进行优化处理 中间代码的... -
【编译原理】中间代码优化(一) 优化技术大观
2020-05-31 18:07:27这是因为中间代码的形式不依赖于具体的计算机,它可以是三地址码的形式,所以相应的对于中间代码的优化也不依赖于具体的计算机。另一类优化是在生成目标代码时进行的,它很大程序上依赖于具体的计算机。中间代码的... -
中间代码生成之四元式
2020-07-10 23:43:42中间代码之四元式 四元式定义 四元式是一种“三地址语句”的等价表示。一般形式:( op , arg1 , arg2 , result ) 即<操作符>,<操作数1>,<操作数2>,<结果> 其中,op为一个二元(也可是... -
语义分析及中间代码生成
2020-11-08 09:40:46实验四 语义分析及中间代码生成 1.实验目的 (1)通过上机实习,加深对语法制导翻译原理的理解,掌握将语法分析 所识别的语法范畴变换为某种中间代码的语义翻译方法。 (2)掌握目前普遍采用的语义分析方法──语法... -
编译原理:中间代码生成
2020-08-22 15:42:19(2)使编译程序改变目标机更容易;易于编译器的移植 (3)使编译程序的结构在逻辑上更为简单明确,以中间语言为界面,编译前端和后端的接口更清晰。 中间语言的形式:后缀式,图表示法,三元式 编译过程中... -
编译原理课程设计 目标代码生成器
2012-10-29 12:55:50代码生成器。它依次把每条中间代码变换成目标代码,并且在一个基本块范围内考虑如何充分利用寄存器的问题。 -
编译原理——中间代码生成
2016-03-28 22:37:22源语言->中间代码->目标语言 中间代码(Intermediate Representation或者IR):复杂性介于源程序语言和机器语言的一种表示形式。 编译程序锁使用的中间代码有多种形式。常见的有逆波兰记号,三元式,四元式,和树形... -
编译原理(二十)——目标代码生成
2020-11-04 22:36:44一、目标代码 二、虚拟目标机的指令系统 三、虚拟目标机的寄存器 四、四元式转化为目标指令 五、多寄存器的分配 六、对目标程序的评价 -
BIT-Minicc编译原理实验-MIPS汇编目标代码生成最傻瓜的思路+问题记录
2020-06-26 22:42:26编译原理课程实验要求为BIT-Minicc编译器开发目标代码生成部分,本文针对...中间代码生成目标代码比直接从AST要方便许多,前提是中间代码生成时要解决变量读取和运算过程中临时变量的问题,即将所有操作数都放入寄存器 -
【编译原理】第11讲 中间代码生成(习题答案)——MOOC哈尔滨工业大学陈鄞
2020-06-02 16:29:12中间代码生成时所依据的是( )。 A. 语法规则 B. 词法规则 C. 语义规则 D. 等价变换规则 C 2 在编译程序中与中间代码生成无关的是( )。 A. 便于目标代码的优化 B. 便于... -
什么是编译程序(含翻译程序、解释程序和中间代码的定义介绍)
2020-12-16 15:40:53要在计算机上执行用高级语言(或汇编语言)编写的程序,必须通过...通常所说的翻译程序是指这样的一个程序,它能够把某一种语言程序(称为源语言程序或源程序)转换成另一种语言程序(称为目标语言程序或目标程序) 1. -
编译原理习题(含答案)——11-14中间代码生成——哈工大陈鄞配套版本
2018-06-14 11:49:22中间代码生成_11 中间代码生成时所依据的是( )。... 便于目标代码的移植 3 以下说法不正确的是( )。A. 对于声明语句,语义分析的主要任务就是收集标识符的类型等属性信息,为每一个名字分配一个相对地址B. 从变量类...