第七章 中间代码生成 静态 中间 分析 检查 代码 记号流 器 生成 本章内容 介绍几种常用的中间表示:后缀表示、图形表示和三地址代码

Slides:



Advertisements
Similar presentations
编 译 原 理 指导教师:杨建国 二零一零年三月.
Advertisements

第五章 语法制导的翻译 赵建华 南京大学计算机系 2010年3月.
编译原理第二次习题课 王静.
Tool Command Language --11级ACM班 金天行.
上課囉 職場甘苦談 小資男孩向錢衝 育碁數位科技 呂宗益/副理.
第六章 中间代码生成 赵建华 南京大学计算机系.
第 5 章 流程控制 (一): 條件分支.
Chapter 4 流程控制.
新世代計算機概論 第14章 程式語言.
第9章 运行时的存储组织 重点:符号表的内容、组织,过程调用实现, 难点:参数传递,过程说明语句代码结构,
编译原理与技术 中间代码生成 2018/9/17 《编译原理与技术》讲义.
EBNF与操作语义 请用扩展的 BNF 描述 javascript语言里语句的结构;并用操作语义的方法描述对应的语义规则
第八章 符号表 符号表的作用: 一致性检查和作用域分析; 辅助代码生成..
7 Intermediate Representation
编译原理与技术 第7章 中间代码生成 3学时.
EBNF 请用扩展的 BNF 描述 C语言里语句的结构; 请用扩展的 BNF 描述 C++语言里类声明的结构;
编译原理与技术 类型检查 2018/11/21 《编译原理与技术》-类型检查.
第3章 語法入門 第一個Java程式 文字模式下與程式互動 資料、運算 流程控制.
第四章 语法制导的翻译 本章内容 1、介绍语义描述的一种形式方法:语法制导的翻译,它包括两种具体形式 语法制导的定义 翻译方案
第六章 运行时存储空间的组织和管理 术语 本章内容 讨论一个活动记录中的数据布局 程序执行过程中,所有活动记录的组织方式 过程的活动
6 下标变量的中间代码生成 下标:数组;变量: 下标变量:即数组分量: 简单变量:id,其地址可查到;
编译原理课程设计.
走进编程 程序的顺序结构(二).
Zhao4zhong1 (赵中) C语言指针与汇编语言地址.
第一单元 初识C程序与C程序开发平台搭建 ---观其大略
第三章 栈和队列.
编译原理实践 5.给定语法的语法分析程序构造.
7.4 布尔表达式和控制流语句 布尔表达式有两个基本目的 计算逻辑值 c = (a > b) && a > 1
第七章 语义分析和中间代码产生 静态语义检查 类型检查 控制流检查 一致性检查 相关名字检查 名字的作用域分析 语法分 析器 静态检 查器
第二章 Java语言基础.
中间代码生成.
第2章 PL/0编译程序 2.1 PL/0语言和类pcode的描述 2.2 PL/0编译程序的结构 2.3 PL/0编译程序的语法语义分析
语法制导的翻译 (Syntax-Directed Translation)
《编译原理与技术》 期末复习 计算机科学与技术学院 郑启龙 李 诚 25/12/2018.
陳維魁 博士 儒林圖書公司 第五章 控制結構 陳維魁 博士 儒林圖書公司.
第七章 操作符重载 胡昊 南京大学计算机系软件所.
第3,4次课 一个简单的语法制导翻译器 2.3~2.5.
第4章 PHP流程控制语句.
C++语言程序设计 C++语言程序设计 第七章 类与对象 第十一组 C++语言程序设计.
编译原理与技术 第4章 语法制导的翻译 6学时.
1.3 C语言的语句和关键字 一、C语言的语句 与其它高级语言一样,C语言也是利用函数体中的可执行 语句,向计算机系统发出操作命令。按照语句功能或构成的不 同,可将C语言的语句分为五类。 goto, return.
第七章 语义分析和中间代码生成 本章内容 介绍几种常用的中间表示:后缀表示、图形表示和三地址代码
C语言程序设计 主讲教师:陆幼利.
EBNF与操作语义 请用扩展的 BNF 描述 javascript语言里语句的结构;并用操作语义的方法描述对应的语义规则
简单介绍 用C++实现简单的模板数据结构 ArrayList(数组, 类似std::vector)
$9 泛型基础.
程式結構&語法.
顺序表的删除.
4 條件選擇 4.1 程式基本結構 循序式結構 選擇式結構 重複式結構 4-3
第六章 语法制导的翻译 本章内容 介绍一种语义描述方法:语法制导的翻译,介绍语法制导的翻译的实现方法。
C语言程序设计 第一章 数据类型, 运算符与表达式 第二章 顺序程序设计 第三章 选择结构程序设计 第四章 循环控制 第五章 数组.
開放電腦計劃 報告人:陳鍾誠 2011 年 8 月 20 日 台灣開源人年會 COSCUP 2011 – 中研院
信号量(Semaphore).
第4章 Excel电子表格制作软件 4.4 函数(一).
习题课 编译原理与技术 计算机科学与技术学院 李诚.
第二章 Java语法基础.
第九节 赋值运算符和赋值表达式.
3.16 枚举算法及其程序实现 ——数组的作用.
College of Computer Science & Technology
多层循环 Private Sub Command1_Click() Dim i As Integer, j As Integer
問題解決與流程圖 高慧君 台北市立南港高中 2006年12月22日.
第二章 Java基本语法 讲师:复凡.
临界区问题的硬件指令解决方案 (Synchronization Hardware)
第1章 数据结构基础概论 本章主要介绍以下内容 数据结构研究的主要内容 数据结构中涉及的基本概念 算法的概念、描述方法以及评价标准.
Go 语言编程 —— 平台研发部 吴植民.
C++语言程序设计 C++语言程序设计 第一章 C++语言概述 第十一组 C++语言程序设计.
第6章 PHP基本語法介紹.
第三节 数量积 向量积 混合积 一、向量的数量积 二、向量的向量积 三、向量的混合积 四、小结 思考题.
第三章 流程控制 程序的运行流程 选择结构语句 循环结构语句 主讲:李祥 时间:2015年10月.
编译原理实践 6.程序设计语言PL/0.
Presentation transcript:

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

7.1 中 间 语 言 7.1.1 后缀表示 E  E opE | uopE | (E) | id | num 7.1 中 间 语 言 7.1.1 后缀表示 E  E opE | 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 的后缀表示是8 5 2 + 后缀表示的最大优点是便于计算机处理表达式 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 的后缀表示是8 5 2 + 后缀表示的最大优点是便于计算机处理表达式 7.1 中 间 语 言 后缀表示不需要括号 (8  5) + 2 的后缀表示是8 5 2 + 后缀表示的最大优点是便于计算机处理表达式 后缀表示也可以拓广到表示赋值语句和控制语句,但很难用栈来描述控制语句的计算

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

7.1 中 间 语 言 构造赋值语句语法树的语法制导定义 修改构造结点的函数可生成有向无环图 产 生 式 语 义 规 则 S  id =E 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 = y op z 例 表达式x + y  z翻译成的三地址语句序列是 7.1 中 间 语 言 7.1.3 三地址代码 一般形式:x = y op z 例 表达式x + y  z翻译成的三地址语句序列是 t1 = y  z t2 = x + t1

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

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

7.1 中 间 语 言 本书常用的三地址语句 赋值语句x = y op z, x = op y, x = y 无条件转移goto L 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

7.1 中 间 语 言 7.1.4 静态单赋值形式 一种便于某些代码优化的中间表示 和三地址代码的主要区别 7.1 中 间 语 言 7.1.4 静态单赋值形式 一种便于某些代码优化的中间表示 和三地址代码的主要区别 所有赋值指令都是对不同名字的变量的赋值 三地址代码 静态单赋值形式 p = a +b p1 = a +b q = p  c q1 = p1  c p = q  d p2 = q1  d p = e  p p3 = e  p2 q = p + q q2 = p3 + q1

7.1 中 间 语 言 7.1.4 静态单赋值形式 一种便于某些代码优化的中间表示 和三地址代码的主要区别 7.1 中 间 语 言 7.1.4 静态单赋值形式 一种便于某些代码优化的中间表示 和三地址代码的主要区别 所有赋值指令都是对不同名字的变量的赋值 一个变量在不同路径上都定值的解决办法 if (flag) x = 1; else x = 1; y = x  a; 改成 if (flag) x1 = 1; else x2 = 1; x3 =  (x1, x2); //由flag的值决定用x1还是x2

7.2 声 明 语 句 本节介绍 为局部名字建立符号表条目 为它分配存储单元 符号表中包含名字的类型和分配给它的存储单元的相对地址等信息

7.2 声 明 语 句 7.2.1 过程中的声明

7.2 声 明 语 句 计算被声明名字的类型和相对地址 P  {offset = 0} D; S D  D ; D D  id : T {enter ( id.lexeme, T.type, offset); offset = offset + T.width } T  integer {T.type = integer; T.width = 4 } T real {T.type = real; T.width = 8 } T array [ num ] of T1 {T.type = array (num.val, T1.type); T.width = num.val  T1.width} T T1 {T.type = pointer (T1.type); T.width = 4 }

7.2 声 明 语 句 计算被声明名字的类型和相对地址 P  {offset = 0} D; S D  D ; D D  id : T {enter ( id.lexeme, T.type, offset); offset = offset + T.width } T  integer {T.type = integer; T.width = 4 } T real {T.type = real; T.width = 8 } T array [ num ] of T1 {T.type = array (num.val, T1.type); T.width = num.val  T1.width} T T1 {T.type = pointer (T1.type); T.width = 4 }

7.2 声 明 语 句 7.2.2 作用域信息的保存 所讨论语言的文法 P  D; S sort var a:…; x:…; D  D ; D | id : T | proc id ; D ; S sort var a:…; x:…; readarray var i:…; exchange quicksort var k, v:…; partition var i, j:…; 图6.14的程序 参数被略去

7.2 声 明 语 句 符号表实例 sort sort 空 表 头 readarray a exchange quicksort x partition v k i 指向exchange sort readarray exchange quicksort partition 符号表实例

7.2 声 明 语 句 符号表的特点 语义动作用到的函数 sort 各过程有各自的符号表 var a:…; x:…; readarray 符号表之间有双向链 构造符号表时需要符号表栈 构造符号表需要活动记录栈 语义动作用到的函数 mkTable(previous) enter(table, name, type, offset) addWidth(table, width) enterProc(table, name, newtable) sort var a:…; x:…; readarray var i:…; exchange quicksort var k, v:…; partition var i, j:…; 图6.14的程序 参数被略去

7.2 声 明 语 句 P  M D; S {addWidth (top (tblptr), top (offset)); pop(tblptr); pop (offset) } M   {t = mkTable (nil); push(t, tblprt); push (0, offset) } D  D1 ; D2 D  proc id ; N D1; S {t = top(tblptr); addWidth(t, top(offset) ); pop(tblptr); pop(offset); enterProc(top(tblptr), id.lexeme, t) } Did :T {enter(top(tblptr), id.lexeme, T.type, top(offset)); top(offset) = top(offset) + T.width } N   {t = mkTable(top(tblptr) ); push(t, tblptr); push(0, offset) }

7.2 声 明 语 句 P  M D; S {addWidth (top (tblptr), top (offset)); pop(tblptr); pop (offset) } M   {t = mkTable (nil); push(t, tblprt); push (0, offset) } D  D1 ; D2 D  proc id ; N D1; S {t = top(tblptr); addWidth(t, top(offset) ); pop(tblptr); pop(offset); enterProc(top(tblptr), id.lexeme, t) } Did :T {enter(top(tblptr), id.lexeme, T.type, top(offset)); top(offset) = top(offset) + T.width } N   {t = mkTable(top(tblptr) ); push(t, tblptr); push(0, offset) }

7.2 声 明 语 句 P  M D; S {addWidth (top (tblptr), top (offset)); pop(tblptr); pop (offset) } M   {t = mkTable (nil); push(t, tblprt); push (0, offset) } D  D1 ; D2 D  proc id ; N D1; S {t = top(tblptr); addWidth(t, top(offset) ); pop(tblptr); pop(offset); enterProc(top(tblptr), id.lexeme, t) } Did :T {enter(top(tblptr), id.lexeme, T.type, top(offset)); top(offset) = top(offset) + T.width } N   {t = mkTable(top(tblptr) ); push(t, tblptr); push(0, offset) }

7.2 声 明 语 句 7.2.3 记录的域名 T  record D end 记录类型单独建符号表,作为类型表达式的 主要部分,域的相对地址从0开始 T  record L D end {T.type = record (top(tblptr) ); T.width = top(offset); pop(tblptr); pop(offset) } L  {t = mkTable(nil); push(t, tblprt); push(0, offset) } record a :…; r : record i :…; . . . end; k : …; end

7.3 赋 值 语 句 7.3.1 符号表中的名字 S  id := E {p = lookup(id.lexeme); if p != nil then emit ( p, ‘=’, E.place) else error } E  E1 + E2 {E.place = newTemp(); emit (E.place, ‘=’, E1.place, ‘+’, E2.place) }

7.3 赋 值 语 句 7.3.1 符号表中的名字 E  E1 {E.place = newTemp(); emit (E.place, ‘=’, ‘uminus’, E1.place) } E  (E1) {E.place = E1.place } E  id {p = lookup(id.lexeme); if p != nil then E.place = p else error }

7.3 赋 值 语 句 7.3.2 数组元素的地址计算 一维数组A的第i个元素的地址计算 base + ( i  low )  w 变换成 i  w + (base  low  w) 减少了运行时的计算

7.3 赋 值 语 句 二维数组 A: array[1..2, 1..3] of T A[1,1] A[1,2] A[1,3] 列为主 A[1, 1], A[2, 1], A[1, 2], A[2, 2], A[1, 3], A[2, 3] 行为主 A[1, 1], A[1, 2], A[1, 3], A[2, 1], A[2, 2], A[2, 3]

7.3 赋 值 语 句 二维数组 A: array[1..2, 1..3] of T i2  A[1,1] A[1,2] … … … … 二维数组 A: array[1..2, 1..3] of T 列为主 A[1, 1], A[2, 1], A[1, 2], A[2, 2], A[1, 3], A[2, 3] 行为主 A[1, 1], A[1, 2], A[1, 3], A[2, 1], A[2, 2], A[2, 3] base + ( (i1  low1)  n2 + (i2  low2 ) )  w (A[i1, i2]的地址,其中n2 = high2  low2 + 1) 变换成 ( (i1  n2 ) + i2 )  w + (base  ( (low1  n2 ) + low2 )  w) i1

7.3 赋 值 语 句 多维数组下标变量A[i1, i2, ..., ik ]的地址表达式 ( (… ( (i1  n2 + i2 )  n3 + i3 ) … )  nk + ik)  w + base  ( ( … ( (low1  n2 + low2)  n3 + low3) … )  nk + lowk )  w

7.3 赋 值 语 句 7.3.3 数组元素地址计算的翻译方案 下标变量访问的产生式 L  id [ Elist ] | id Elist  Elist, E | E 不便于在处理下标表达式时到符号表取信息 为便于写语义动作,改成等价的 L  Elist ] | id Elist  Elist, E | id [E

7.3 赋 值 语 句 所有产生式 S  L := E E  E + E E  (E ) E  L L  Elist ] L  id Elist  Elist, E Elist  id [ E

7.3 赋 值 语 句 L  id {L.place = id.place; L.offset = null } Elist  id [ E {Elist.place = E.place; Elist.ndim = 1; Elist.array = id.place } Elist  Elist1, E { t = newTemp(); m = Elist1.ndim + 1; emit (t, ‘=’, Elist1.place, ‘’, limit(Elist1.array, m) ); emit (t, ‘=’, t, ‘+’, E.place); Elist.array = Elist1.array; Elist.place = t; Elist.ndim = m} L  Elist ] { L.place = newTemp(); emit (L.place, ‘=’, base(Elist.array), ‘’, invariant (Elist.array) ); L.offset = newTemp(); emit (L.offset, ‘=’, Elist.place,‘’,width(Elist.array))}

7.3 赋 值 语 句 E  L{if L.offset == null then / L是简单变量 / E.place = L.place else begin E.place = newTemp(); emit (E.place, ‘=’, L.place, ‘[’, L.offset, ‘]’) end } E  E1 + E2{E.place = newTemp(); emit (E.place, ‘=’, E1.place , ‘+’, E2.place) } E  (E1 ){E.place = E1.place } S  L = E {if L.offset == null then / L是简单变量 / emit (L.place, ‘= ’, E.place) else emit (L.place , ‘[’, L.offset, ‘]’, ‘=’, E.place) }

7.3 赋 值 语 句 A[10, 20] S := L.place = x L.offset = null x E.place = t4 L.place = t2 L.offset = t3 Elist.place = t1 Elist.ndim = 2 Elist.array = A , Elist.place = y Elist.ndim = 1 E.place = z L.place = z E.place = y L.place = y A [ z ] y x := A[ y, z ]的注释分析树 x = t4 t4 = t2 [t3 ] t2 = c t3 = 4  t1 t1 = y  20 t1 = t1 + z 注:c =A  84 A[10, 20]

7.3 赋 值 语 句 7.3.4 类型转换 例 x = y + i  j (x和y的类型是real,i和j的类型是integer) 中间代码 t1 = i int j t2 = inttoreal t1 t3 = y real+ t2 x = t3

7.3 赋 值 语 句 E  E1 + E2 E.place = newTemp(); if E1.type == integer && E2.type == integer then begin emit (E.place, ‘=’, E1.place, ‘int+’, E2.place); E.type = integer end else if E1.type == integer && E2.type == real then begin u = newTemp(); emit (u, ‘=’, ‘inttoreal’, E1.place); emit (E.place, ‘=’, u, ‘real+’, E2.place); E.type = real . . .

7.4 布尔表达式和控制流语句 7.4.1 布尔表达式 布尔表达式有两个基本目的 本节所用的布尔表达式文法 计算逻辑值 在控制流语句中用作条件表达式 本节所用的布尔表达式文法 B  B or B | B and B | not B | ( B ) | E relop E | true | false

7.4 布尔表达式和控制流语句 7.4.1 布尔表达式 布尔表达式的完全计算 布尔表达式的“短路”计算 值的表示数值化 其计算类似于算术表达式的计算 布尔表达式的“短路”计算 B1 or B2 定义成 if B1 then true else B2 B1 and B2 定义成 if B1 then B2 else false 用控制流来实现计算,即用程序中的位置来表示值,因为布尔表达式通常用来决定控制流走向 两种不同计算方式会导致程序的结果不一样

7.4 布尔表达式和控制流语句 7.4.2 控制流语句的翻译 S  if B then S1 | if B then S1 else S2 | while B do S1 | S1; S2

7.4 布尔表达式和控制流语句 指向B.true B.code 指向B.false B.true: S1.code . . . (a) if-then B.false: goto S.next S2.code (b) if-then-else goto S.begin S.begin: (c) while-do S1.next: (d) S1; S2

7.4 布尔表达式和控制流语句 If-then若改成下面形式,会产生冗余跳转指令 指向B.true B.code 指向B.false S1.code B.true: . . . 指向B.true 指向B.false B.false: goto S.next S2.code (b) if-then-else (a) if-then goto S.begin S.begin: (c) while-do S1.next: (d) S1; S2

7.4 布尔表达式和控制流语句 S  if B then S1 {B.true = newLabel(); B.false = S.next; S1.next = S.next; S.code = B.code || gen(B.true, ‘:’) || S1.code } B.code S1.code B.true: . . . 指向B.true 指向B.false (a) if-then

7.4 布尔表达式和控制流语句 S  if B then S1 else S2 {B.true = newLabel(); B.false = newLabel(); S1.next = S.next; S2.next = S.next; S.code = B.code || gen(B.true, ‘:’) || S1.code || gen(‘goto’, S.next) || gen(B.false, ‘:’) || S2.code} B.code S1.code B.true: . . . 指向B.true 指向B.false B.false: goto S.next S2.code (b) if-then-else

7.4 布尔表达式和控制流语句 S  while B do S1 {S.begin = newLabel(); B.true = newLabel(); B.false = S.next; S1.next = S.begin; S.code = gen(S.begin, ‘:’) || B.code || gen(B.true, ‘:’) || S1.code || gen(‘goto’, S.begin) } B.code S1.code B.true: . . . 指向B.true 指向B.false goto S.begin S.begin: (c) while-do

7.4 布尔表达式和控制流语句 S  S1; S2 {S1.next = newLabel(); S2.next = S.next; S.code = S1.code || gen(S1.next, ‘:’) || S2.code } S1.code S2.code S1.next: . . . (d) S1; S2

7.4 布尔表达式和控制流语句 7.4.3 布尔表达式的控制流翻译 如果B是a < b的形式, 那么代码是: if a < b goto B.true goto B.false

7.4 布尔表达式和控制流语句 例 表达式 a < b or c < d and e < f 的代码是: 例 表达式 a < b or c < d and e < f 的代码是: if a < b goto Ltrue goto L1 L1: if c < d goto L2 goto Lfalse L2: if e < f goto Ltrue

7.4 布尔表达式和控制流语句 B  B1 or B2 {B1.true = B.true; B1.false = newLabel(); B2.false = B.false; B.code = B1.code || gen(B1.false, ‘:’) || B2.code } B  not B1 {B1.true = B.false; B1.false = B.true; B.code = B1.code }

7.4 布尔表达式和控制流语句 B  B1 and B2 {B1.true = newLabel(); B1.false = B.false; B2.true = B.true; B2.false = B.false; B.code = B1.code || gen(B1.true, ‘:’) || B2.code } B  (B1) {B1.true = B.true; B.code = B1.code }

7.4 布尔表达式和控制流语句 B  E1 relop E2 {B.code = E1.code || E2.code || gen(‘if’, E1.place, relop.op, E2.place, ‘goto’, B.true) || gen(‘goto’, B.false) } B  true {B.code = gen(‘goto’, B.true)} B  false {B.code = gen(‘goto’, B.false)}

7.4 布尔表达式和控制流语句 7.4.4 开关语句的翻译 switch E begin case V1: S1 case V2: S2 . . . case Vn - 1: Sn – 1 default: Sn end

7.4 布尔表达式和控制流语句 分支数较少时 t = E的代码 | Ln-2: if t != Vn-1 goto Ln-1 if t != V1 goto L1 | Sn -1的代码 S1的代码 | goto next goto next | Ln-1: Sn的代码 L1: if t != V2 goto L2 | next: S2的代码 goto next L2: . . . . . .

7.4 布尔表达式和控制流语句 分支较多时,将分支测试代码集中在一起,便于生成较好的分支测试代码 t = E的代码 | Ln: Sn的代码 goto test | goto next L1: S1的代码 |test: if t == V1 goto L1 goto next | if t == V2 goto L2 L2: S2的代码 | . . . goto next | if t == Vn-1 goto Ln-1 . . . | goto Ln Ln-1: Sn -1的代码 | next: goto next

7.4 布尔表达式和控制流语句 中间代码增加一种case语句,便于代码生成器对它进行特别处理 test: case V1 L1 . . . case Vn-1 Ln-1 case t Ln next: 一个生成:  用二分查找确定该执行的分支  直接找到该执行的分支 的例子见第244页习题 8.8

7.4 布尔表达式和控制流语句 7.4.5 过程调用的翻译 S  call id (Elist) Elist  Elist, E

7.4 布尔表达式和控制流语句 过程调用id(E1, E2, …, En)的中间代码结构 E1.place = E1的代码 . . . En.place = En的代码 param E1.place param E2.place param En.place call id.place, n

7.4 布尔表达式和控制流语句 S  call id (Elist) {为长度为n的队列中的每个E.place, emit(‘param’, E.place); emit(‘call’, id.plase, n) } Elist  Elist, E {把E.place放入队列末尾} Elist  E {将队列初始化,并让它仅含E.place}

本 章 要 点 中间代码的几种形式,它们之间的相互转换 符号表的组织和作用域信息的保存 数组元素定址的翻译方案,布尔表达式的两种不同实现方式 本 章 要 点 中间代码的几种形式,它们之间的相互转换 符号表的组织和作用域信息的保存 数组元素定址的翻译方案,布尔表达式的两种不同实现方式 赋值语句和各种控制流语句的中间代码格式和生成中间代码的翻译方案 过程调用的中间代码格式和生成中间代码的翻译方案

例 题 1 Pascal语言的标准将for语句 for v := initial to final do stmt 例 题 1 Pascal语言的标准将for语句 for v := initial to final do stmt 定义成和下面的代码序列有同样的含义: begin t1 := initial; t2 := final; if t1<= t2 then begin v := t1; stmt; while v <> t2 do begin v := succ(v); stmt end

例 题 1 Pascal语言的标准将for语句 for v := initial to final do stmt 例 题 1 Pascal语言的标准将for语句 for v := initial to final do stmt 能否定义成和下面的代码序列有同样的含义? begin t1 := initial; t2 := final; v := t1; while v <= t2 do begin stmt; v := succ(v) end

例 题 1 Pascal语言for语句 for v := initial to final do stmt 的中间代码结构如下: 例 题 1 Pascal语言for语句 for v := initial to final do stmt 的中间代码结构如下: t1 = initial t2 = final if t1 > t2 goto L1 v = t1 L2: stmt if v == t2 goto L1 v = v + 1 goto L2 L1:

例 题 2 C语言的for语句有下列形式 for (e1;e2;e3) stmt 它和 e1; while (e2)do begin 例 题 2 C语言的for语句有下列形式 for (e1;e2;e3) stmt 它和 e1; while (e2)do begin stmt; e3; end 有同样的语义

例 题 2 C语言的for语句for (e1;e2;e3) stmt的中间代码 结构如下 e1的代码 L1: e2的代码 L2: e3的代码 例 题 2 C语言的for语句for (e1;e2;e3) stmt的中间代码 结构如下 e1的代码 L1: e2的代码 L2: e3的代码 goto L1 stmt的代码 goto L2 真转 假转,由外层语句决定

例 题 3 Pascal语言 var a,b : array[1..100] of integer; a:=b // 允许数组之间赋值 例 题 3 Pascal语言 var a,b : array[1..100] of integer; a:=b // 允许数组之间赋值 若a和b是同一类型记录,也允许 C语言 数组类型不行,结构体类型可以 为这种赋值选用或设计一种三地址语句,它要便于生成目标代码

例 题 3 Pascal语言 var a,b : array[1..100] of integer; a:=b // 允许数组之间赋值 例 题 3 Pascal语言 var a,b : array[1..100] of integer; a:=b // 允许数组之间赋值 若a和b是同一类型记录,也允许 仍然用中间代码复写语句 x = y,在生成目标代码时,必须根据它们类型的size,产生一连串的值传送指令

例 题 4 下面的翻译方案使用了变量offset,请重写该翻译方案,它完成同样的事情,但只使用文法符号的属性,而不使用变量offset 例 题 4 下面的翻译方案使用了变量offset,请重写该翻译方案,它完成同样的事情,但只使用文法符号的属性,而不使用变量offset P  {offset = 0} D D  D ; D D  id : T { enter(id.lexeme, T.type, offset); offset = offset + T.width } T  integer {T.type = integer; T.width = 4 } T real {T.type = real; T.width = 8 }

例 题 4 P  {D.offset1 = 0} D { P.offset = D.offset2} 例 题 4 P  {D.offset1 = 0} D { P.offset = D.offset2} D  {D1.offset1 = D.offset1 } D1 ; {D2.offset1 = D1.offset2 }D2 {D.offset2 = D2.offset2 } D  id :T{enter ( id.lexeme, T.type, D.offset1); D.offset2 = D.offset1 + T.width } T  integer {T.type = integer; T.width = 4 } T real {T.type = real; T.width = 8 }

习 题 第一次:7.1 第二次:7.4, 7.8, 7.10 68