《编译原理》课程教学资源（PPT课件讲稿）中间代码生成

中间代码生成 语法 静态检 中间代码L中间 代码 分析器 查程序 生成器 代码 生成器 前端 后端

中间代码生成

本章内容 ·介绍几种常用的中间代码表示 抽象语法树(上一章已介绍) 有向无环图 三地址代码 ·用语法制导定义和翻译方案来说明源语言的各种 构造怎样被翻译成中间表示 声明(和类型) 表达式和赋值 类型检查和类型转换 控制流 过程

本章内容 • 介绍几种常用的中间代码表示 • 抽象语法树（上一章已介绍） • 有向无环图 • 三地址代码 • 用语法制导定义和翻译方案来说明源语言的各种 构造怎样被翻译成中间表示 • 声明（和类型） • 表达式和赋值 • 类型检查和类型转换 • 控制流 • 过程

编译器的前端 前端是对源语言进行分析并产生中间表示 处理与源语言相关的细节,与目标机器无关 ·前端后端分开的好处:不同的源语言、不同的机 器可以得到不同的编译器组合 语法 静态检 中间代码[中间 代码 分析器 查程序 生成器 代码 生成器 前端 后端 图6-1一个编译器前端的逻辑结构

编译器的前端 • 前端是对源语言进行分析并产生中间表示 • 处理与源语言相关的细节，与目标机器无关 • 前端后端分开的好处：不同的源语言、不同的机 器可以得到不同的编译器组合

建立组合编译的做法 Source program Source program in Language-1 in Language-2 Language -1 front end Language-2 Front End Non- optimized Intermediate code Intermediate-code optimizer Optimized Intermediate code Target-1 Code Generator Target-2 Code Generator arget-1 machine code Target-2 machine code

建立组合编译的做法 Target-1 Code Generator Target-2 Code Generator Intermediate-code Optimizer Language-1 Front End Source program in Language-1 Language-2 Front End Source program in Language-2 Non-optimized Intermediate Code Optimized Intermediate Code Target-1 machine code Target-2 machine code

中间代码表示及其好处 ·形式 多种中间表示,不同层次 抽象语法树 三地址代码 ·重定位 为新的机器建编译器,只需要做从中间代码到新的目 标代码的翻译器(前端独立) 抽象”的编译优化 优化与源语言和目标机器都无关

中间代码表示及其好处 • 形式 • 多种中间表示，不同层次 • 抽象语法树 • 三地址代码 • 重定位 • 为新的机器建编译器，只需要做从中间代码到新的目 标代码的翻译器（前端独立） • “抽象”的编译优化 • 优化与源语言和目标机器都无关

抽象语法树回顾 产生式」 语义规则 E→E1+TE,n0le= new node(“+,E1,nOdl,T,node) E>E-TEnode= new Node("-',E,, node, Tnode) E→T E node= tnode T→T1*FT.node= new nodel(“*2,T1,nOdl,F,noe) T→F Tnode= f node F→(E) F,node= enode F→id Fnode= new leaf (id, identry) F→num F node= new leaf (num, num. val) 例:a+a*(b-c)+(b-c)*

抽象语法树回顾 例：a + a * (b – c) + (b – c) * d 产 生 式 语 义 规 则 E → E1 +T E.node = new Node(‘+’, E1 .node, T.node) E → E1 −T E.node = new Node(‘−’, E1 .node, T.node) E → T E.node = T.node T → T1 F T.node = new Node( ‘’, T1 .node, F.node) T → F T.node = F.node F → (E) F.node = E.node F → id F.node = new Leaf (id, id.entry) F → num F.node = new Leaf (num, num.val)

有向无环图( Directed Acyclic Graph, DAG) 语法树中,公共子表达式每出现一次,就有一个对应的 子树 表达式的有向无环图能够指出表达式中的公共子表达式, 更简洁地表示表达式 例:a+a*(b-c)+(b-C)*d

有向无环图（Directed Acyclic Graph, DAG） • 语法树中，公共子表达式每出现一次，就有一个对应的 子树 • 表达式的有向无环图能够指出表达式中的公共子表达式， 更简洁地表示表达式 例：a + a * (b – c) + (b – c) * d

构造赋值语句语法树/DAG的语法制 导定义 ·修改构造结点的函数Node和Leaf可生成DAG:构 造新节点前先检查是否已存在同样的节点,如果 已经存在,则返回这个已有的节点 生式 语义规则 E,,+T Enode= new Node(+, Er, node, Tnode) E→E1-TE. node= new node(“-,E1,node, T node) E→T|Emle=rmhe T→T* FTnode= new node(“*,T1,node,F,nodl) T→F Tnode= fnode F→(E) Fnode= enode F→)id Fnode= new Leaf (id, id entry) F→num Fnode= new Leaf (num, num.val)

构造赋值语句语法树/DAG的语法制 导定义 • 修改构造结点的函数Node和Leaf可生成DAG：构 造新节点前先检查是否已存在同样的节点，如果 已经存在，则返回这个已有的节点 产 生 式 语 义 规 则 E → E1 +T E.node = new Node(‘+’, E1 .node, T.node) E → E1 −T E.node = new Node(‘−’, E1 .node, T.node) E → T E.node = T.node T → T1 F T.node = new Node( ‘’, T1 .node,F.node) T → F T.node = F.node F → (E) F.node = E.node F → id F.node = new Leaf (id, id.entry) F → num F.node = new Leaf (num, num.val)

a+a*(b-c)+(b-c)*d的DAG的构造 「产生式 语义规则 E→E1+TE. node= new node(“+,E1,nole, Tnode) E,E1-T Enode= new Node(-, Er- node, T node Enode= tnode →T1* F Tnode= new node(*’,T,node, F node) T→F Tnode= fnode F→(E) Anode= enode F→id Fnode= new Leaf(id, id entry) F→Ⅲum| Fnode= new Leaf(mum, num.val) a

a + a * (b – c) + (b – c) * d的DAG的构造 + + * * – d b c a 产 生 式 语 义 规 则 E → E1 +T E.node = new Node(‘+’, E1 .node, T.node) E → E1 −T E.node = new Node(‘−’, E1 .node, T.node) E → T E.node = T.node T → T1 F T.node = new Node( ‘’, T1 .node, F.node) T → F T.node = F.node F → (E) F.node = E.node F → id F.node = new Leaf (id, id.entry) F → num F.node = new Leaf (num, num.val)

三地址代码 般形式:x=yopz 条指令右侧最多有一个运算符 三地址代码拆分了多运算符表达式和控制流语句的嵌 套结构,所以适用于目标代码的生成 例表达式x+y*z翻译成的三地址语句序列是 ,=y*Z

三地址代码 • 一般形式：x = y op z • 一条指令右侧最多有一个运算符 • 三地址代码拆分了多运算符表达式和控制流语句的嵌 套结构，所以适用于目标代码的生成 • 例 表达式x + y  z翻译成的三地址语句序列是 t1 = y  z t2 = x + t1