中国科学技术大学：《编译原理与技术》课程教学资源（课件讲稿）第6章 中间代码生成

第6章 中间代码生成 号 分析 中间 中 代码 代码 码 生 器 器 生成 器 器 本章内容 介绍几种常用的中间表示：后缀表示、图形表示 和三地址代码 用语法制导定义和翻译方案来说明源语言的各种 构造怎样被翻译成中间形式

第6章 中间代码生成 静态 中间 记号 中间 代码 分析 器 静态 检查 器 中间 代码 生成 中间 代码 记号 流 代码 生成 器 器 生成 器 器 流 代码 器 本章内容 – 介绍几种常用的中间表示：后缀表示、图形表示 和三地址代码 – 用语法制导定义和翻译方案来说明源语言的各种 构造怎样被翻译成中间形式

6.1中间语言 6.1.1后缀表示 表达式E的后缀表示可以如下归纳定义 如果E是变量或常数，那么E的后缀表示就是 E本身 如果E是形式为EopE,的表达式，那么E的后 缀表示是E'E2'op,其中E1和E2'分别是E,和 E,的后缀表示 如果E是形式为(E)的表达式，那么E的后缀 表示也是E的后缀表示

6 1. 中 间 语 言 6.1.1 后缀表示 表达式E的后缀表示可以如下归纳定义 • 如果E是变量或常数，那么E的后缀表示就是 的后缀表示就是 E本身 • 如果E是形式为E1 opE2的表达式，那么E的后 缀表示是E1 E2 op，其中E1和E2 缀表示是E1 E2 op，其中E1 和E2分别是E1和 E2的后缀表示 • 如果E是形式为(E1)的表达式，那么E1的后缀 表示也是E的后缀表示

6.1中间语言 ·后缀表示不需要括号 (8-5)+2的后缀表示是85-2+ ·后缀表示的最大优点是便于计算机处理表达 式 计算栈 输入串 85-2+ 8 5-2+ 85 -2+ 3 2+ 32 + 5

6 1. 中 间 语 言 • 后缀表示不需要括号 (8  5) + 2 的后缀表示是8 5 2 + • 后缀表示的最大优点是便于计算机处理表达 式 计算栈 输入串 8 5 2 + 8 5 2 + 8 5 2 + 3 2 + 3 2 + 5

6.1中间语言 ”后缀表示不需要括号 (8-5)+2的后缀表示是85-2+ ·后缀表示的最大优点是便于计算机处理表达 式 后缀表示很容易拓广到含一元算符的表达式 后缀表示也可以拓广到表示赋值语句和控制 语句，但很难用栈来描述它的计算

6 1. 中 间 语 言 • 后缀表示不需要括号 (8  5) + 2 的后缀表示是8 5 2 + • 后缀表示的最大优点是便于计算机处理表达 式 • 后缀表示很容易拓广到含一元算符的表达式 • 后缀表示也可以拓广到表示赋值语句和控制 语句，但很难用栈来描述它的计算

6.1中间语言 6.1.2 图形表示 语法树是一种图形化的中间表示 有向无环图(DAG)也是一种中间表示 assign assign uminus uminus (a)语法树 (b)DAG a=(-b+c*d+c*d的图形表示

6 1. 中 间 语 言 6.1.2 图形表示 • 语法树是 种图形化的中间表示 语法树是一种图形化的中间表示 • 有向无环图（DAG）也是 种中间表示 一 assign assign a + + a + +  c d uminus +   c d uminus c d b c d (b) DAG b c d (a) 语法树 ( ) a = (b + cd) + cd的图形表示

6.1中间语言 构造赋值语句语法树的翻译方案 修改构造结点的函数可生成有向无环图 产生式 语义动作 S→id=E {S.nptr mkNode('assign', mkLeaf (id,id.entry),E.nptr); E→E1+E2 {E.nptr mkNode(+'E.nptr,E2.nptr); E→E1*E2 {E.nptr=mkNode(‘*’,E nptr,E2nptr) E→-E {E.nptr mkUNode(uminus',E.nptr); E→(E) {E.nptr=E.nptr; E→id {E.nptr mkLeaf (id,id.entry);)

6 1. 中 间 语 言 构造赋值语句语法树的翻译方案 修改构造结点的函数可生成有向无环图 产生式 语义动作 S  id =E {S.nptr = mkNode(‘assign’, mkLeaf (id id ,.entry), E.nptr);} E  E1 +E2 {E.nptr = mkNode( ‘+’, E1.nptr, E2.nptr);} E  E1 E2 {E.nptr = mkNode( ‘’, E1.nptr, E2.nptr);} E  E {E nptr = mkUNode( ‘uminus’ E nptr);} 1 {E.nptr = mkUNode( ‘uminus’, E1.nptr);} E  (E1) {E.nptr = E1.nptr;} E  id {E.nptr = mkLeaf (id, id.entry);}

6.1中间语言 6.1.3三地址代码 一 般形式：x=ypz ·例表达式x十y*翻译成的三地址语句序列是 t=y* t=x+t

6 1. 中 间 语 言 6.1.3 三地址代码 一般形式：x = y op z • 例 表达式x + y  z翻译成的三地址语句序列是 t1 = y  z t + 2 = x t1

6.1中间语言 三地址代码是语法树或DAG的一种线性表示 例a=(-b+c*d)+c*d 语法树的代码 t1=-b b=c*d assign t3=t1+t2 t=c*d uminus ts=ts+t a=ts

6 1. 中 间 语 言 • 三地址代码是语法树或DAG的一种线性表示 • 例 a = (b + cd ) + cd 语法树的代码 t1 = b t  d 2 = c  d t3 = t1 + t 3 2 t4 = c  d uminus t5 = t3 + t4 a = t5

6.1中间语言 ·三地址代码是语法树或DAG的一种线性表示 例a=(-b+c*d)+c*d 语法树的代码 DAG的代码 t1=-b 1=-b assign b=c*d t=c*d t3=t1+t2 巧3=t1+t2 t=c*d t4=巧3+t2 uminus ts=ts+t 0=t4 a=ts

6 1. 中 间 语 言 • 三地址代码是语法树或DAG的一种线性表示 • 例 a = (b + cd ) + cd 语法树的代码 DAG的代码 t1 = b t1 = b t  d t  d assign t2 = c  d t2 = c  d t3 = t1 + t2 t3 = t1 + t2 a + 3 1 2 3 1 2 t4 = c  d t4 = t3 + t2 +  d uminus t5 = t3 + t4 a = t4 a = t b c d a 5

6.1中间语言 本书常用的三地址语句 赋值语句x=y0叩乙，x=0py,X=y 无条件转移goto L 条件转移ifx relo叩y goto L 。 过程调用param x和call p,n 过程返回return y 索引赋值x=y和x川=Jy 地址和指针赋值x=&y,x=*y和*x=Jy

6 1. 中 间 语 言 本书常用的三地址语句 • 赋值语句x = y op z， x = op y， x = y • 无条件转移goto L • 条件转移if x relop y goto L • 过程调用param x 和call p, n • 过程返回 return y • 索引赋值x = y[i]和 x[i] = y • 地址和指针赋值x = &y，x = y和x = y