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

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

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

7.1中间语言 7.1.1后缀表示 E->EopE uopE (E)id num 表达式E的后缀表示可以如下归纳定义： 表达式E 后缀式E id id num num E opE2 E'E2'op uopE E'uop (E) E

7.1 中 间 语 言 7.1.1 后缀表示 E → EopE | uopE | (E) | id | num 表达式E的后缀表示可以如下归纳定义： 表达式E 后缀式E  id id num num E1 opE2 E1  E2  op uopE Euop (E) E

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

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

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

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

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

7.1 中 间 语 言 7.1.2 图形表示 • 语法树是一种图形化的中间表示 • 有向无环图也是一种中间表示 assign a + +  b c d uminus (b) DAG assign a + +   b c d uminus c d (a) 语法树 a = (−b + cd) + cd的图形表示

71中间语言 构造赋值语句语法树的语法制导定义 修改构造结点的函数可生成有向无环图 产生式 语义规则 S→id=E S.nptr mkNode('assign',mkLeaf (id, id.entry),E.nptr) E-→E1+E2 E.nptr mkNode(+',E.nptr,E2.nptr) E→E*E2 E.nptr=mkNode(*'E.nptr,E2.nptr) E→-E1 E.nptr mkUNode('uminus',E.nptr) E→(E) E.nptr E.nptr F→id E.nptr mkLeaf (id,id.entry)

7.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 → −E1 E.nptr = mkUNode( ‘uminus’, E1 .nptr) E → (E1 ) E.nptr = E1 .nptr F → id E.nptr = mkLeaf (id, id.entry)

7.1中间语言 7.1.3三地址代码 一般形式：x=y0pz ·例表达式x+y*翻译成的三地址语句序列是 t1=Jy*乙 t=x+t

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

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

7.1 中 间 语 言 • 三地址代码是语法树或DAG的一种线性表示 • 例 a = (−b + cd ) + cd 语法树的代码 t 1 = −b t 2 = c  d t 3 = t 1 + t 2 t 4 = c  d t 5 = t 3 + t 4 a = t 5 uminus

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

7.1 中 间 语 言 • 三地址代码是语法树或DAG的一种线性表示 • 例 a = (−b + cd ) + cd 语法树的代码 DAG的代码 t 1 = −b t 1 = −b t 2 = c  d t 2 = c  d t 3 = t 1 + t 2 t 3 = t 1 + t 2 t 4 = c  d t 4 = t 3 + t 2 t 5 = t 3 + t 4 a = t 4 a = t 5 assign a + +  b c d uminus

7.1中间语言 本书常用的三地址语句 赋值语句x=y0pz, x=opy, x=y 无条件转移goto L 条件转移ifx relopy goto L 过程调用paramx和call p,n 过程返回return y 索引赋值x=y训和x[订=y 地址和指针赋值x=&y,x=*y和*x=Jy

7.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