编译原理中间代码生成.ppt

machunyan 西北工业大学软件与微电子学院 1 词法分析程序 语法分析程序 语义分析程序 中间代码生成 代码优化程序 目标代码生成 源代码 目标代码 常数表 符号表 错误处理器 编译器逻辑结构的组成 machunyan 西北工业大学软件与微电子学院 2 第6章代码生成 6 1中间代码概览 6 2基本的代码生成技术 6 3数据结构引用的代码生成 6 4控制语句和逻辑表达式的代码生成 6 5过程和函数调用的代码生成 machunyan 西北工业大学软件与微电子学院 3 6 1中间代码概览 编译程序的任务是把源程序翻译成等价的目标程序 所谓等价 是指两者之间的语法结构不同 但它们表述的功能和结果是完全相同的 即语义相同 中间代码 也称中间语言 是复杂性介于源程序和目标程序之间的一种机内表达形式 它是编译程序产生的中间临时结果 中间代码程序同源程序和目标程序的关系也同样是等价的 即结构不同 但语义相同 machunyan 西北工业大学软件与微电子学院 4 尽管源程序可以直接翻译成目标语言 但使用与机器无关的中间代码形式具有如下优点 使编译程序的算法清晰 便于分工 修改 维护和移植等 中间代码使编译器更容易重定向 不同机器上的编译器可以在已有前端的基础上附加一个适合这这台新机器的后端来生成 可以在中间代码上进行与机器无关的代码优化 优化过程实际上是对程序的操作过程 对程序进行操作必须首先把程序转换成其结构便于操作的数据 而中间代码正是为此设计的一种程序的数据结构表示 两种常见的中间代码的普遍形式 三地址码和P 代码 6 1中间代码概览 续 machunyan 西北工业大学软件与微电子学院 5 6 1 1三地址码 6 1 2用于实现三地址码的数据结构 6 1 3P 代码 6 1中间代码概览 续 machunyan 西北工业大学软件与微电子学院 6 6 1 1三地址码 续 相应的三地址码为 t1 2 at2 b 3t3 t1 t2 三地址码是下列一般形式的语句序列 x yopz其中 x y及z是名字 常量或编译器生成的临时变量 op代表任何操作符 例6 1 算术表达式的2 a b 3 语法树如下 machunyan 西北工业大学软件与微电子学院 7 6 1 1三地址码 续 三地址码是语法树的从左到右的线性化表示 三地址码的生成所依据的是语言的语义规则 为适应标准程序语言的使用结构 在具体为每个结构生成三地址码时 必须为每个结构改变三地址码的形式 例如 为了生成数组引用的三地址码可以引入两个新的三地址指令 获取数组元素值的三地址指令 t2 a t1 给数组元素赋值的三地址指令 a t2 t1 machunyan 西北工业大学软件与微电子学院 8 6 1 1三地址码 6 1 2用于实现三地址码的数据结构 6 1 3P 代码 6 1中间代码概览 续 machunyan 西北工业大学软件与微电子学院 9 6 1 2用于实现三地址码的数据结构 三地址码是中间代码的一种抽象形式 在编译器中 这些语句可以以带有操作符和操作数域的记录来实现 三地址码常见的实现有四元式和三元式 四元式是带有四个域的记录结构 即op arg1 arg2 result 可以写成 op arg1 arg2 result arg1 arg2及result域的内容正常情况下是指这些域所代表的名字在符号表表项的指针 临时名字result在生成时一定要被填入符号表 四元式之间的联系是通过临时变量实现的 便于优化处理 machunyan 西北工业大学软件与微电子学院 10 三元式 为了避免临时名字被填入符号表中 可以通过临时值的语句位置来引用临时变量 可以用只包含三个域的记录表示 即用三元式来表示 三元式之间的联系是通过三元式编号实现的 对三元式表变动较为困难 花费较大的代价 6 1 2用于实现三地址码的数据结构 续 machunyan 西北工业大学软件与微电子学院 11 例6 2 6 1中算术表达式 2 a b 3 的三地址码 t1 2 at2 b 3t3 t1 t2四元式实现 2 a t1 b 3 t2 t1 t2 t3 三元式实现 0 2 a 1 b 3 2 0 1 6 1 2用于实现三地址码的数据结构 续 machunyan 西北工业大学软件与微电子学院 12 6 1 1三地址码 6 1 2用于实现三地址码的数据结构 6 1 3P 代码 6 1中间代码概览 续 machunyan 西北工业大学软件与微电子学院 13 6 1 3P 代码 在20世纪70年代和60年代早期 P 代码作为由许多Pascal编译器产生的标准目标汇编代码被设计成称作P 机器 P machine 的假想栈机器 Stackmachine 的实际代码 P 机器在不同的平台上由不同的解释器实现 该思想使得pascal编译器变得容易移植 只需对新平台重写P 机器解释器即可 machunyan 西北工业大学软件与微电子学院 14 例6 3 算术表达式 2 a b 3 的P 代码如下 ldc2 loadconstant2loda loadvalueofvariableampi integermultiplicationlodb loadvalueofvariablebldc3 loadconstant3sbi integersubtractionadi integeraddition 6 1 3P 代码 续 machunyan 西北工业大学软件与微电子学院 15 6 1中间代码概览 6 2基本的代码生成技术 6 3数据结构引用的代码生成 6 4控制语句和逻辑表达式的代码生成 6 5过程和函数调用的代码生成 第6章代码生成 续 machunyan 西北工业大学软件与微电子学院 16 6 2基本的代码生成技术 6 2 1作为合成属性的中间代码或目标代码生成方法 6 2 2实际的代码生成方法 6 2 3从中间代码生成目标代码 machunyan 西北工业大学软件与微电子学院 17 6 2 1作为合成属性的中间代码或目标代码生成方法 中间代码生成 或直接目标代码生成 可被看作属性计算 这类似于第5章中研究的许多属性问题 假如将生成的代码看作一个字符串属性 每条指令用换行符分隔 这个代码就成了一个合成属性并能用属性文法定义 并且能在语法分析期间直接生成或者通过语法树的后序遍历生成 machunyan 西北工业大学软件与微电子学院 18 例6 4 为表达式文法exp id exp aexpaexp aexp factor factorfactor exp num id写出计算三地址码的属性文法 tacode属性 表示文法的三地址码属性 name属性 表示参与三地址码运算的标示符 常量或编译器生成的临时变量 用 表示所连的符号串换行表示 表示相连的符号串之间用空格相隔 6 2 1作为合成属性的中间代码或目标代码生成方法 续 machunyan 西北工业大学软件与微电子学院 19 exp tacode t1 x 3x t1 exp tacode t1 x 3 6 2 1作为合成属性的中间代码或目标代码生成方法 续 表达式x x 3的tacode属性计算 machunyan 西北工业大学软件与微电子学院 20 exp1 id exp2 exp aexp 文法规则 语义规则 exp1 name exp2 name exp1 tacode exp2 tacode id strval exp2 name exp name aexp name exp tacode aexp tacode 6 2 1作为合成属性的中间代码或目标代码生成方法 续 machunyan 西北工业大学软件与微电子学院 21 aexp1 aexp2 factor aexp1 name newtemp aexp1 tacode aexp2 tacode factor tacode aexp1 name aexp2 name factor name 6 2 1作为合成属性的中间代码或目标代码生成方法 续 machunyan 西北工业大学软件与微电子学院 22 aexp factor factor exp factor num factor id 文法规则 语义规则 aexp name factor name aexp tacode factor tacode factor name exp name factor tacode exp tacode factor name num strval factor tacode factor name id strval factor tacode 6 2 1作为合成属性的中间代码或目标代码生成方法 续 machunyan 西北工业大学软件与微电子学院 23 exp tacode t1 x 3x t1 根据上述属性文法 表达式 x x 3 4的tacode属性计算如右 factor exp exp aexp factor factor num 3 aexp factor exp factor aexp id x id x num 4 exp tacode t1 x 3 aexp tacode t1 x 3x t1t2 t1 4 6 2 1作为合成属性的中间代码或目标代码生成方法 续 machunyan 西北工业大学软件与微电子学院 24 其中语义动作使用函数emit 将三地址语句输出到文件中 为其产生三地址码的翻译模式如下 对于表达式文法exp id exp aexpaexp aexp factor factorfactor exp num id 对于将文法符号同属性相关联的上下文无关文法 也可以将语义动作 包含在 中 插入产生式右部的某个位置 6 2 1作为合成属性的中间代码或目标代码生成方法 续 machunyan 西北工业大学软件与微电子学院 25 exp1 id exp2 exp aexp aexp1 aexp2 factor exp1 name exp2 nameemit id strval exp2 name exp name aexp name aexp1 name newtemp emit aexp1 name aexp2 name factor name 6 2 1作为合成属性的中间代码或目标代码生成方法 续 machunyan 西北工业大学软件与微电子学院 26 aexp factor factor exp factor num factor id factor name exp name aexp name factor name factor name id strval factor name num strval 6 2 1作为合成属性的中间代码或目标代码生成方法 续 machunyan 西北工业大学软件与微电子学院 27 为表达式文法exp exp term exp term termterm term factor factorfactor exp number写出计算三地址码的属性文法 tacode属性 表示文法的三地址码属性name属性 表示相应的标示符 常量或编译器生成的临时变量 6 2 1作为合成属性的中间代码或目标代码生成方法 续 machunyan 西北工业大学软件与微电子学院 28 6 2 1作为合成属性的中间代码或目标代码生成方法 6 2 2实际的代码生成方法 6 2 3从中间代码生成目标代码 自学内容 6 2基本的代码生成技术 machunyan 西北工业大学软件与微电子学院 29 6 2 2实际的代码生成方法 实际代码生成的基本算法由下面的递归过程描述 用于二叉树 但容易将其推广到节点子树多于2的情况 voidgenCode T treenode ifTisnotnil generatecodetoprepareforcodeofleftchildofT genCode leftchildofT generatecodetoprepareforcodeofrightchildofT genCode rightchildofT generatecodetoimplementtheactionofT 注 中间代码生成所依据的是语言的语义规则 即在遍历树生成代码之前 应该首先规定各节点对应代码生成的语义规则 machunyan 西北工业大学软件与微电子学院 30 对于上述简单表达式文法exp id exp aexpaexp aexp factor factorfactor exp num id考虑其三地址码的代码生成过程实现 6 2 2实际的代码生成方法 续 machunyan 西北工业大学软件与微电子学院 31 例6 5 表达式 x x 3 4相应的语法树如下 x 4 x 3 生成的相应的三地码如下 t1 x 3x t1t2 t1 4 6 2 2实际的代码生成 续 machunyan 西北工业大学软件与微电子学院 32 typedefenum Plus Assign Optype typedefenum OpKind ConstKind IdKind NodeKind typedefstructstreenode NodeKindkind Optypeop structstreenode lchild rchild char strval STreeNode typedefSTreeNode SyntaxTree 简单算术表达式抽象语法树的C语言定义 每个节点都有个名字属性 用该节点的strval域来存储其名字 假设数字也当作字符串保存在strval域中 6 2 2实际的代码生成 续 machunyan 西北工业大学软件与微电子学院 33 leftoperand rightoperand 上述表达式的语法树结构和节点中间代码的生成规则如下 t1 t leftchild strval t rightchild strval t strval t1 6 2 2实际的代码生成 续 machunyan 西北工业大学软件与微电子学院 34 leftoperand t strval t leftchild strval 6 2 2实际的代码生成 续 t strval t leftchild strval 生成的三地址码 赋值运算 machunyan 西北工业大学软件与微电子学院 35 中间代码生成的辅助函数 emit 函数emit 将三地址语句输出到文件中 Newtemp 函数Newtemp 产生一个临时名字系列t1 t2 t3 6 2 2实际的代码生成 续 machunyan 西北工业大学软件与微电子学院 36 VoidgenCode SyntaxTreet if t NULL switch t kind caseOpKind switch t op casePlus genCode t lchild genCode t rchild t strval newtemp emit t strval t lchild strval t rchild strval break 简单算术表达式的三地址码生成过程的实现 6 2 2实际的代码生成 续 machunyan 西北工业大学软件与微电子学院 37 caseAssign genCode t lchild emit t strval t lchild strval t strval t lchild strval break default emit error break 6 2 2实际的代码生成 续 machunyan 西北工业大学软件与微电子学院 38 break caseConstKind break caseIdKind break default emit error break 6 2 2实际的代码生成 续 machunyan 西北工业大学软件与微电子学院 39 x 4 x 3 根据上述三地址码的生成过程 表达式 x x 3 4相应的三地码如下 t1 x 3x t1t2 t1 4 6 2 2实际的代码生成 续 machunyan 西北工业大学软件与微电子学院 40 6 2基本的代码生成技术 6 2 1作为合成属性的中间代码或目标代码生成方法 6 2 2实际的代码生成方法 6 2 3从中间代码生成目标代码 自学内容 machunyan 西北工业大学软件与微电子学院 41 6 2 3从中间代码生成目标代码 续 如果编译器从一棵语法树产生了中间代码 下一步就是产生最后的目标代码 通常在对中间代码的进一步处理之后 目标代码的生成相当复杂 特别是当中间代码高度抽象 且只包含了很少或根本没包含目标机器和运行时环境的信息 在上述情况下 目标代码的生成必须支持变量和临时变量的实际定位 并增加支持运行时环境所必需的代码 现在仅讨论这个处理的通用技术 machunyan 西北工业大学软件与微电子学院 42 通常 从中间代码到目标代码的生成涉及了两个标准技术 宏扩展 macroexpansion 和静态模拟 宏扩展涉及到用一系列等效的目标代码指令代替每一种中间代码指令 静态模拟包括中间代码效果的直线模拟和生成匹配这些效果的目标代码 6 2 3从中间代码生成目标代码 续 machunyan 西北工业大学软件与微电子学院 43 用宏扩展来完成将三地址码到P 代码的翻译 例如一个三地址指令a b c可翻译成如下的P 代码指令序列 ldaalodb orldcbifbisaconstlodc orldccifcisaconstadisto 6 2 3从中间代码生成目标代码 续 machunyan 西北工业大学软件与微电子学院 44 用静态模拟来完成将P 代码到三地址码的翻译 例如 表达式 x x 3 4的P 代码如下 ldaxlodxldc3adistnldc4adi执行一个P 机器栈的静态模拟用以发现P 代码的三地址码等效式 6 2 3从中间代码生成目标代码 续 machunyan 西北工业大学软件与微电子学院 45 3 栈顶 x x的地址 现在当处理adi操作时 产生三地址指令t1 x 3栈的状态为 假定前三条P 代码语句执行后 栈的状态如下 栈顶 t1 x的地址 6 2 3从中间代码生成目标代码 续 machunyan 西北工业大学软件与微电子学院 46 下一条stn指令翻译为如下的三地址指令 x t1栈变成 下一条指令ldc4将常量4压入栈 最后指令adi生成三地址指令 t2 t1 4栈变成 6 2 3从中间代码生成目标代码 续 machunyan 西北工业大学软件与微电子学院 47 第6章代码生成 6 1中间代码概览 6 2基本的代码生成技术 6 3数据结构引用的中间代码生成 6 4控制语句和逻辑表达式的中间代码生成 6 5过程和函数调用的中间代码生成 machunyan 西北工业大学软件与微电子学院 48 6 3数据结构引用的中间代码生成 6 3 1地址计算 6 3 2数组引用的三地址码生成 6 3 3记录结构和指针引用 自学内容 machunyan 西北工业大学软件与微电子学院 49 6 3 1地址计算 为了定位实际地址 对于数组 记录域和指针引用的中间代码生成通常需要执行地址计算 引入用于地址计算的三地址码 假设把2存放在变量x所在位置加上10个字节的地址处 用三地址码表示如下 t1 x 10 t1 2 machunyan 西北工业大学软件与微电子学院 50 6 3数据结构引用的代码生成 6 3 1地址计算 6 3 2数组引用的三地址码生成 6 3 3记录结构和指针引用 自学内容 machunyan 西北工业大学软件与微电子学院 51 6 3 2数组引用的三地址码生成 例6 6 C数组引用a i 的地址是 base address a i sizeof int 赋值语句 t2 a t1 翻译成如下的三地址码 t3 t1 elem size a t4 a t3t2 t4 赋值语句 a t2 t1翻译成如下的三地址码 t3 t2 elem size a t4 a t3 t4 t1 返回数组元素所占字节数 machunyan 西北工业大学软件与微电子学院 52 考虑一维数组引用的简单算术表达式文法exp subs exp aexpaexp aexp factor factorfactor exp num subssubs id id exp 对应的三地址码的生成过程实现 6 3 2数组引用的三地址码生成 续 machunyan 西北工业大学软件与微电子学院 53 表达式 a i 1 2 a j 的语法树结构如下 i 1 a 2 a j 6 3 2数组引用的三地址码生成 续 t1 i 1 t2 t1 elem size a t3 a t2 t4 j elem size a t5 a t4 t6 t5 2 t3 2 machunyan 西北工业大学软件与微电子学院 54 typedefenum OpKind ConstKind IdKind NodeKind typedefenum Plus Assign Subs Optype typedefstructstreenode NodeKindkind Optypeop structstreenode lchild rchild char strval STreeNode typedefSTreeNode SyntaxTree 其语法树的c语言定义如下 6 3 2数组引用的三地址码生成 续 machunyan 西北工业大学软件与微电子学院 55 leftoperand rightoperand t1 t leftchild strval t rightchild strvalt strval t1t leftchild strval t rightchild strvalt strval t rightchild strval 6 3 2数组引用的三地址码生成 续 machunyan 西北工业大学软件与微电子学院 56 t1 t lchild strval elem size t strval t2 t strval t1t strval t2 subs id exp 6 3 2数组引用的三地址码生成 续 id 根节点进一步参与运算的名字属性 machunyan 西北工业大学软件与微电子学院 57 表达式 a i 1 2 a j 的语法树结构如下 i 1 a 2 a j t1 i 1 t2 t1 elem size a t3 a t2 t4 j elem size a t5 a t4 t6 t5 2 t3 2 6 3 2数组引用的三地址码生成 续 machunyan 西北工业大学软件与微电子学院 58 数组引用的算术表达式文法对应的三地址码的生成过程实现 VoidgenCode SyntaxTreet if t NULL switch t kind caseOpKind switch t op casePlus genCode t lchild genCode t rchild t strval newtemp emit t strval t lchild strval t rchild strval break 6 3 2数组引用的三地址码生成 续 machunyan 西北工业大学软件与微电子学院 59 caseAssign genCode t lchild genCode t rchild emit t lchild strval t rchild strval t strval t rchild strval break 6 3 2数组引用的三地址码生成 续 machunyan 西北工业大学软件与微电子学院 60 caseSubs genCode t lchild temp1 newtemp emit temp1 t lchild strval elem size t strval temp2 newtemp emit temp2 6 3 2数组引用的三地址码生成 续 machunyan 西北工业大学软件与微电子学院 61 break caseConstKind break caseIdKind break default emit error break 6 3 2数组引用的三地址码生成 续 machunyan 西北工业大学软件与微电子学院 62 根据上述三地址码的生成过程 表达式 a i 1 2 a j 相应的三地码如下 t1 i 1 t2 t1 elem size a t3 a t2 t4 j elem size a t5 a t4 t6 t5 2 t3 2 6 3 2数组引用的三地址码生成 续 machunyan 西北工业大学软件与微电子学院 63 subscriptexp1 subscriptexp2 6 3 2数组引用的三地址码生成 续 思考题 撰写下述简单算术表达式文法对应的三地址码生成的递归程序 exp subs exp aexpaexp aexp factor factorfactor exp num subssubs id id exp exp 二维下标运算的语法树 machunyan 西北工业大学软件与微电子学院 64 6 3数据结构引用的代码生成 6 3 1地址计算 6 3 2数组引用的三地址码生成 6 3 3记录结构和指针引用 自学内容 machunyan 西北工业大学软件与微电子学院 65 6 3 3记录结构和指针引用 计算记录结构的域地址提出了一个同计算下标数组地址相同的问题 首先 计算结构变量的基地址 然后 找到域偏移量 两者相加得到结果地址 例如 考虑C语言声明 typedefstructrec inti charc intj Rec Recx machunyan 西北工业大学软件与微电子学院 66 第一个参数是结构变量名 第二个参数是域名 函数的返回值是x j的偏移量 6 3 3记录结构和指针引用 续 用于域地址计算的三地址码 为了计算x j的地址并存入临时变量t1 使用如下的三地址指令 t1 被翻译成如下的三地址码 t1 x field offset x j t2 x field offset x i t1 t2 machunyan 西北工业大学软件与微电子学院 67 6 3 3记录结构和指针引用 续 对于指针引用 例如假设x被定义成整型指针 int x 假设i是一个普通整型变量 C赋值语句 x i 翻译成三地址指令 x i赋值语句i x 翻译成三地址指令i x machunyan 西北工业大学软件与微电子学院 68 C变量声明如下 typedefstructtreeNode intval structtreeNode lchild rchild TreeNode TreeNode p 6 3 3记录结构和指针引用 续 machunyan 西北工业大学软件与微电子学院 69 现在考虑两个典型的赋值p lchild p p p rchild 这些语句翻译成三地址码如下 t1 p field offset p lchild t1 pt2 p field offset p rchild p t2 6 3 3记录结构和指针引用 续 machunyan 西北工业大学软件与微电子学院 70 第6章代码生成 6 1中间代码概览 6 2基本的代码生成技术 6 3数据结构引用的代码生成 6 4控制语句和逻辑表达式的代码生成 6 5过程和函数调用的代码生成 machunyan 西北工业大学软件与微电子学院 71 6 4控制语句和逻辑表达式的代码生成 6 4 1if和while语句的代码生成6 4 2逻辑表达式的代码生成 自学内容 6 4 3if和while语句的代码生成过程举例 machunyan 西北工业大学软件与微电子学院 72 6 4 1if和while语句的代码生成 考虑下面两种if和while语句 他们的语法结构在很多不同的语言中都是相似的 现在给出的是类C语法 if stmt if exp stmt if exp stmtelsestmtwhile stmt while exp stmtIf和while语句代码生成的主要问题 将结构化的控制特性翻译成涉及转移的非结构化等价物 以被目标代码直接实现 machunyan 西北工业大学软件与微电子学院 73 编译器通常以一种标准次序安排if和while语句的中间代码生成 这种次序可以高效地使用转移子集 而且这种转移子集是目标系统所允许的 将if语句翻译为中间代码的典型代码排列如下 6 4 1if和while语句的代码生成 续 machunyan 西北工业大学软件与微电子学院 74 if stmt if exp stmt if exp stmtelsestmt 真 if语句生成的中间代码的典型排列 machunyan 西北工业大学软件与微电子学院 75 为了生成控制语句的三地址码 引入如下的三地址码指令 产生标号的三地址语句 label 例如 labelL1 labelL2 当测试条件为假时转移的三地址语句 if false goto例如 if falset1gotoL1无条件转移的三地址语句 goto 例如 gotoL1 6 4 1if和while语句的代码生成 续 machunyan 西北工业大学软件与微电子学院 76 if语句生成下面的代码模式 求逻辑表达式E的值的三地址码序列if falset1gotoL1 true情况下执行的三地址码序列gotoL2labelL1 false情况下执行的三地址码序列labelL2 if语句后的代码 if stmt if E S1 if E S1elseS2 6 4 1if和while语句的代码生成 续 将while语句翻译为中间代码的典型代码排列如下 machunyan 西北工业大学软件与微电子学院 77 6 4 1if和while语句的代码生成 续 while stmt while exp stmt machunyan 西北工业大学软件与微电子学院 78 while stmt while exp stmt 真 6 4 1while语句生成代码的典型排列 machunyan 西北工业大学软件与微电子学院 79 while语句生成下面的代码模式 labelL1 求逻辑表达式E的值的三地址码序列if falset1gotoL2 while循环体的代码执行序列gotoL1labelL2 While语句后的代码 while stmt while E S 6 4 1if和while语句的代码生成 续 下述是do while语句的简化语法dowhile stmt dostmtwhile exp 请给出do while语句生成中间代码 三地址码 的翻译模式 machunyan 西北工业大学软件与微电子学院 80 6 4 1if和while语句的代码生成 续 machunyan 西北工业大学软件与微电子学院 81 6 4控制语句和逻辑表达式的代码生成 6 4 1if和while语句的代码生成6 4 2逻辑表达式的代码生成 自学内容 6 4 3if和while语句的代码生成过程样例 表示逻辑表达式的值第一种方法可以用1表示真 用0表示假 逻辑表达从左到右按与算术表达式类似的方式完全计算 例如 aorbandnotc将被翻译成如下三地址序列 t1 notct2 bandt1t3 aort2 machunyan 西北工业大学软件与微电子学院 82 6 4 2逻辑表达式的代码生成 对于a b这样的关系表达式等价于条件语句ifa b1else0ifa b1else0被翻译成如下的三地码序列 if falsea bgotoL1t1 0gotoL2labelL1t1 1labelL2 machunyan 西北工业大学软件与微电子学院 83 6 4 2逻辑表达式的代码生成 续 machunyan 西北工业大学软件与微电子学院 84 例如表达式a borc dande f的翻译 试给出逻辑表达式文法E EorE EandE notE E idreropid true false用数值表示逻辑值的三地址码生成过程实现 其中rerop代表比较算符 or的优先级最低 其次是and 最后是not 6 4 2逻辑表达式的代码生成 续 machunyan 西北工业大学软件与微电子学院 85 表示逻辑表达式的值的第二种方法是通过控制流 即用程序到达的位置来表示逻辑表达式的值 例如 对于表达式EorE 如果确定了E是真 那么可以肯定整个表达式都是真 而不必再去计算E 详细资料参见 编译原理李建中姜守旭P316 6 4 2逻辑表达式的代码生成 续 machunyan 西北工业大学软件与微电子学院 86 6 4控制语句和逻辑表达式的代码生成 6 4 1if和while语句的代码生成6 4 2逻辑表达式的代码生成6 4 3if和while语句的代码生成过程样例 machunyan 西北工业大学软件与微电子学院 87 6 4 3if和while语句的代码生成过程样例 用如下简化的文法展示一个控制语句的代码生成过程 stmt if stmt while stmt break otherif stmt if exp stmt if exp stmtelsestmtwhile stmt while exp stmtexp true false machunyan 西北工业大学软件与微电子学院 88 6 4 3if和while语句的代码生成过程样例 续 machunyan 西北工业大学软件与微电子学院 89 下面的C声明 用来为上述文法实现一棵抽象语法树typedefenum ExpKind IfKind WhileKind BreakKind OtherKind NodeKind typedefstructstreenode NodeKindkind structstreenode child 3 intval usedwithExpKind char strval STreeNode typedefSTreeNode SyntaxTree 6 4 3if和while语句的代码生成过程样例 续 machunyan 西北工业大学软件与微电子学院 90 例如语句if true while true if false breakelseother有如下的语法树 6 4 3if和while语句的代码生成过程样例 续 machunyan 西北工业大学软件与微电子学院 91 上述简单控制语句的三地址码生成过程实现 voidgenCode SyntaxTree char lab1 lab2 if t NULL switch t kind caseExpKind t strval newtemp if t val 0 emit t strval false elseemit t strval true 6 4 3if和while语句的代码生成过程样例 续 machunyan 西北工业大学软件与微电子学院 92 caseIfKind genCode t child 0 lab1 genLabel emit if false t child 0 strval goto lab1 genCode t child 1 if t child 2 NULL lab2 genLabel emit goto lab2 emit label lab1 if t child 2 NULL genCode t child 2 emit label lab2 break 无参过程返回标号名 L1 L2 6 4 3if和while语句的代码生成过程样例 续 machunyan 西北工业大学软件与微电子学院 93 caseWhileKind lab1 genLabel emit label lab1 genCode t child 0 Lab2 genLabel emit if false t child 0 strval goto lab2 genCode t child 1 emit goto lab1 emit label lab2 break 6 4 3if和while语句的代码生成过程样例 续 machunyan 西北工业大学软件与微电子学院 94 caseBreakKind emit goto break caseOtherKind emit Other break default emit Error break 6 4 3if和while语句的代码生成过程样例 续 machunyan 西北工业大学软件与微电子学院 95 上述简单控制语句的三地址码生成过程实现 voidgenCode SyntaxTreet char label char lab1 lab2 if t NULL switch t kind caseExpKind t strval newtemp if t val 0 emit t strval false elseemit t strval true 初值为空 6 4 3if和while语句的代码生成过程样例 续 machunyan 西北工业大学软件与微电子学院 96 caseIfKind genCode t child 0 label lab1 genLabel emit if false t child 0 strval goto lab1 genCode t child 1 label if t child 2 NULL lab2 genLabel emit goto lab2 emit label lab1 if t child 2 NULL genCode t child 2 label emit label lab2 break 无参过程返回标号名 L1 L2 6 4 3if和while语句的代码生成过程样例 续 machunyan 西北工业大学软件与微电子学院 97 caseWhileKind lab1 genLabel emit label lab1 genCode t child 0 label Lab2 genLabel emit if false t child 0 strval goto lab2 genCode t child 1 lab2 emit goto lab1 emit label lab2 break 6 4 3if和while语句的代码生成过程样例 续 Lab2传递给break语句 machunyan 西北工业大学软件与微电子学院 98 caseBreakKind emit goto label break caseOtherKind emit Other break default emit Error break 6 4 3if和while语句的代码生成过程样例 续 machunyan 西北工业大学软件与微电子学院 99 根据代码生成的递归过程描述 语句if true while true if false breakelseother生成的三地址码 t3 false if falset3gotoL4 gotoL3 gotoL5 labelL4 other labelL5 labelL2 t2 true if falset2gotoL3 gotoL2 labelL3 t1 true if falset1gotoL1 labelL1 Break语句对应的三地址码 6 4 3if和while语句的代码生成过程样例 续 machunyan 西北工业大学软件与微电子学院 100 第6章代码生成 6 1中间代码概览 6 2基本的代码生成技术 6 3数据结构引用的代码生成 6 4控制语句和逻辑表达式的代码生成 6 5过程和函数调用的代码生成 machunyan 西北工业大学软件与微电子学院 101 6 5过程和函数调用的代码生成 6 5 1过程和函数的中间代码6 5 2函数定义和调用的代码生成过程 自学内容 函数定义包括函数名 参数和函数代码 函数定义的中间代码必须包括一条标志开始的指令 称函数代码的入口点 entrypoint 一条标志结束的指令 称为函数返回点 returnpoint 翻译模式如下 EntryinstructionReturninstruction machunyan 西北工业大学软件与微电子学院 102 6 5 1过程和函数的中间代码 续 machunyan 西北工业大学软件与微电子学院 103 例如 考虑C函数定义intf intx inty returnx y 1 翻译成如下的三地址码 entryft1 x yt2 t1 1returnt2 返回 6 5 1过程和函数的中间代码 续 入口指令需要给出一个函数入口点的名字 类似于label指令 引入entry作为函数入口的三地址指令 例如 entryf引入return作为三地址返回指令 假如有返回值 必须给出返回值的名字 例如 returnt1 machunyan 西北工业大学软件与微电子学院 104 6 5 1过程和函数的中间代码 续 函数调用首先产生参数的实际值 然后转去执行函数代码 函数调用的中间代码必须有一条指令指示参数计算的开始 为调用而准备的 然后实际调用指令指示已经构成了参数 到函数代码的实际转移可以发生了 翻译模式如下 Begin argument computationinstructionCallinstruction machunyan 西北工业大学软件与微电子学院 105 6 5 1过程和函数的中间代码 续 machunyan 西北工业大学软件与微电子学院 106 例如 假如上例中的函数f已经在C中定义 调用f 2 3 4 翻译成三地址码如下 begin argst1 2 3argt1arg4callf 返回 6 5 1过程和函数的中间代码 续 函数调用引入3个不同的三地址指令 一个标志参数计算的起点 引入begin args一个被用于重复说明参数值名字的指令arg调用指令 简单写成call machunyan 西北工业大学软件与微电子学院 107 6 5 1过程和函数的中间代码 续 machunyan 西北工业大学软件与微电子学院 108 6 5过程和函数调用的代码生成 6 5 1过程和函数的中间代码6 5 2函数定义和调用的代码生成过程 自学内容 machunyan 西北工业大学软件与微电子学院 109 函数定义和调用的文法如下 program decl listexpdecl list decl listdecl decl fnid param list expparam list param list id idexp exp exp call num idcall id arg list arg list arg list exp exp 6 5 2函数定义和调用的代码生成过程 machunyan 西北工业大学软件与微