编译原理：第6章 语义分析与中间代码生成

1、 课 程 内 容第 1 章 编 译 引 论第 2 章 形式语言与自动机基础第 3 章 词法分析 (Lexical Analysis)第 4 章 语法分析(Syntax Analysis) 自上而下分析法第 5 章 语法分析(Syntax Analysis) 自下而上分析法第 6 章 语义分析与中间代码生成第 7 章 运 行 环 境第 8 章 代码优化（optimization）第 6 章 语义分析与中间代码生成 6.1 语义分析综述 6.2 语法制导翻译与属性文法 6.3 中间语言 6.4 符号表 6.5 类型检查（自学） 6.6 语句翻译与中间代码生成 Ch6 语义分析与中间代码生成 6.1

2、 语义分析综述 语义分析的地位Front end ( 分析 )Back end ( 综合 )语义处理 编译程序最实质性的工作； 第一次对源程序的语义作出解释，引 起源程序质的变化。 Ch6 语义分析与中间代码生成 6.1 语义分析综述 语义分析的任务 按照语法分析器识别的语法范畴进行语义检查和处理，产生相应的中间代码或目标代码。 中间代码 介于源语言和目标代码之间的一种代码。 Ch6 语义分析与中间代码生成 6.1 语义分析综述 引入中间代码的目的 1. 方便生成目标代码； 2. 便于优化； 3. 便于移植。第 6 章 语义分析与中间代码生成 6.1 语义分析综述 6.2 语法制导翻译与属性文

3、法 6.3 中间语言 6.4 符号表 6.5 类型检查（自学） 6.6 语句翻译与中间代码生成 Ch6 语义分析与中间代码生成 6.2 语法制导翻译与属性文法 语法制导翻译 为文法的每一个产生式配一个相应的语义子程序（或语义规则描述的语义动作），并在语法分析的同时调用它。 Ch6 语义分析与中间代码生成 6.2 语法制导翻译与属性文法 属性翻译文法 把语义引入文法，给产生式中的文法符号附加“属性”，构成涉及语义的翻译文法。 形式定义 A = （ G , V , F ） 其中： G： 一般为二型文法； V： 属性的有穷集； F： 关于属性的断言或谓词的有穷集。文法符号的语义性质(语义属性) Ch

4、6 语义分析与中间代码生成 6.2 语法制导翻译与属性文法 属性表示 N . t ( N是G符号，t是N的属性) （终结符的属性均为lexval）产 生 式语 义 规 则L EE E + TE TT T * FT FF (E)F digitprint( E .val )E .val = E1 .val + T .valE .val = T .valT .val = T1 .val F .valT .val = F .valF .val = E .valF .val = digit .lexval数、符号串、类型、存储空间 Ch6 语义分析与中间代码生成 6.2 语法制导翻译与属性文法 综合属性

5、 分析树中,如果一个结点的属性值是通过子结点的属性值计算得到,则称为综合属性。 Ch6 语义分析与中间代码生成 6.2 语法制导翻译与属性文法例如， 3 * 5 + 4 ; LE; print( E .val )EE+T E.val = E1.val + T.valET E .val = T .valTT*F T.val = T1.valF.valTF T.val = F.valF(E) F.val = E.valFdigit F.val = digit.lexvalL;EE+TT*FFTdigitdigitFdigit.lexval=3.lexval=5.lexval=4.val=3.val

6、=3.val=5.val=15.val=15.val=4.val=4.val=19 Ch6 语义分析与中间代码生成 6.2 语法制导翻译与属性文法 继承属性 分析树中,如果一个结点的属性值是由该结点的父结点和(或)兄弟结点的属性定义的称为继承属性。 综合属性 分析树中,如果一个结点的属性值是通过子结点的属性值计算得到则称为综合属性。 Ch6 语义分析与中间代码生成 6.2 语法制导翻译与属性文法例如，float id1，id2 ， id3 DTL L .in = T .typeTint T .type = integerTfloat T .type = float LL,id L1 .in =

7、 L .in addtype(id.entry, L.in)Lid addtype(id.entry, L.in) DTLfloatL,id3L,id2id1.type=float.in=float.in=float.type=float.in=float.type=float.type=float第 6 章 语义分析与中间代码生成 6.1 语义分析综述 6.2 语法制导翻译与属性文法 6.3 中间语言 6.4 符号表 6.5 类型检查（自学） 6.6 语句翻译与中间代码生成 Ch6 语义分析与中间代码生成 6.3 中间语言中间语言( 中间代码)是语义程序的输出。 中间语言的设计与应用既要考虑

8、从源语言到目标语言的翻译跨度又要考虑目标机的指令集特点。中间语言N元式(三元式、间接三元式四元式)逆波兰式图 Ch6 语义分析与中间代码生成 6.3 中间语言 一. 逆波兰式(后缀式 )形式定义：e1e2 en ( n 1)运算对象运算符 a * b - aa+b*(c+d)*(e+f)例如， ab*a (表示单目)a b c d + * e f + * + IFthenelse(1) BZ (2)(3) BR(4)(5)引入两个操作符：BZ、BR。BZ是二目操作符，如果第一运算对象数的值为假，则产生一个到第二运算对象的转移。 BR则是一个单目操作符，它产生一个到运算对象的转移。 Ch6 语义

9、分析与中间代码生成 6.3 中间语言Label2Label1JFJ例6.1 设有如下C程序片段 int k； i=j=0；h： k=100； if (ki+j) k-；i+; else k=i*2-j*2； goto h； Ch6 语义分析与中间代码生成 6.3 中间语言逆波兰式代码：(1) i j 0 = =(2) k 100 =(3) k i j + ( ) BZ(4) k k 1 = (5) i i 1 + =(6) ( ) BR(7) k i 2*j2* =(8) (2) BR编号 78 二. N元式N个域的记录结构 （ D1， D2，D3， ，Dn） OP域 操作对象域三元式、间接三

10、元式双地址机指令形式 四元式三地址机指令形式 Ch6 语义分析与中间代码生成 6.3 中间语言 常见N元式 其中： NO.:为产生的三元式的顺序编号； OP : 是操作符； ARG1和ARG2为第一操作数和第二操作数。(也可以是前面某一个三元式的编号， 代表该三元式的计算结果被作为操作数 ) Ch6 语义分析与中间代码生成 6.3 中间语言三元式形式定义： NO. ( OP , ARG1 , ARG2 ) 间接三元式形式定义： 间接码表 + 三元式表 例如，语句 X=A+B*C 的三元式表示为 NO. OP ARG1 ARG2(1)(2)(3)* B C+ A (1)= (2) X Ch6 语

11、义分析与中间代码生成 6.3 中间语言 NO. OP ARG1 ARG2(1)(2)(3)(4)(5)(6)(7) X Y BZ (1) (5)= X ZBR (7) + Y 1 = (5) Z if XY then Z = X else Z = Y+1的三元式可以表示为 Ch6 语义分析与中间代码生成 6.3 中间语言 (a+b)2 + (a+b)3 Ch6 语义分析与中间代码生成 6.3 中间语言 其中：“” 表示幂运算。 + 3 + a b 2 + a b OP ARG1 ARG2NO (a+b)2 + (a+b)3 的间接三元式 间接码表 +, , , , 3 , , 2 + , a,

12、 b 三元式表 Ch6 语义分析与中间代码生成 6.3 中间语言控制三元式代码执行顺序 四元式形式定义： NO. ( OP , ARG1 , ARG2 ，Result) Ch6 语义分析与中间代码生成 6.3 中间语言(a+b)2 + (a+b)3的四元式：* 注：Ti是临时变量。(4) +， T2， T4 ，T5(3) , T3, 3， T4(1) , T1, 2， T2(0) + , a, b， T1(2) + , a, b， T3 NO. OP ARG1 ARG2 Result (1)(2)(3)(4)(5)(6)(7) X Y t1BZ t1 (5) = X ZBR (7) + Y 1

13、 t2 = t2 Z if XY then Z = X else Z = Y+1的四元式可以表示为 Ch6 语义分析与中间代码生成 6.3 中间语言 三. 图（树） 一个三元式一棵子树 OP子树根 ARG1子树左叶节点 ARG2子树右叶节点 Ch6 语义分析与中间代码生成 6.3 中间语言 (a+b)2 + (a+b)3三元式ab+ab+23 Ch6 语义分析与中间代码生成 6.3 中间语言 +, , , , 3 + , a, b , , 2 + , a, b if XY then Z = X else Z = Y+1的树可以表示为 Ch6 语义分析与中间代码生成 6.3 中间语言zBRYYX

14、BZ(4)xz=(5)1(4)=+(5)(1)(2)(3)树编号树编号 ab+ab+23树线性化：后序遍历 逆波兰式几种表示间关系 Ch6 语义分析与中间代码生成 6.3 中间语言“单步”表示 三元式 Ch6 语义分析与中间代码生成 6.3 中间语言语法分析的结果为树；逆波兰式适于栈式存储的计算机（堆栈机）；四元式便于优化；间接三元式优化时的时空效率类似于四元式。综述：第 6 章 语义分析与中间代码生成 6.1 语义分析综述 6.2 语法制导翻译与属性文法 6.3 中间语言 6.4 符号表 6.5 类型检查（自学） 6.6 语句翻译与中间代码生成 Ch6 语义分析与中间代码生成 6.4 符号表

15、 源程序流基本组成单位特点 关键字：表示语句性质，反映语句结构； 标识符：表示程序中各种实体； 如，变量名；常量名；标号名；过程名；函数名；文件名，数组名 V: name , type , addr , level array: name , type , addr , dim , level , size Ch6 语义分析与中间代码生成 6.4 符号表语句标号: name , addr , 定义否 过程、函数: name , addr , 形参 反映了标识符的语义特征属性，是翻译的依据。 记录于符号表中（namelist） 整个编译过程中动态地采集、记录、变更、引用 Ch6 语义分析与中间代

16、码生成 6.4 符号表例如，设有C程序片段 : int i , a4 ; i=a2 ; 词法语法语义分析i, a 符号表i.type 符号表a.type 符号表a.维数 符号表a.每维大小 符号表 类型检查； 数组越界检查； 回填addr; Ch6 语义分析与中间代码生成 6.4 符号表 符号表 存放源程序中有关标识符的属性信息的数据结构。 符号表作用语义检查依据；代码生成时地址分配依据。收集标识符属性信息； 符号表结构 属性信息域 名字域 Ch6 语义分析与中间代码生成 6.4 符号表 常见标识符类的主要属性与作用1. 标识符名。作用：查重(考虑作用域和可视性前提)2. 类型。作用：存储空间

17、分配；可施加运算的检查等3. 存储类别。作用：提供语义处理、检查、存储 分配的依据。4. 作用域、可视性。作用：动态活动环境支持，提 供量所在层次；第 6 章 语义分析与中间代码生成 6.1 语义分析综述 6.2 语法制导翻译与属性文法 6.3 中间语言 6.4 符号表 6.5 类型检查（自学） 6.6 语句翻译与中间代码生成 Ch6 语义分析与中间代码生成 6.6 语句翻译与中间代码生成 语句翻译设计要点 1. 根据语义确定语句的目标结构 ；源语句中间及目标代码的布局If E then S1 测E S1.codeE.f:Goto E.f E.code Ch6 语义分析与中间代码生成 6.6

18、语句翻译与中间代码生成2. 确定中间代码 ； 3. 根据目标结构和语义规则，构造语义 子程序（转换翻译程序） ；4. 涉及的实现技术 语句翻译设计要点 1. 根据语义确定语句的目标结构 ；6.6 语句翻译与中间代码生成 6.6.1 说明类语句的翻译 6.6.2 赋值语句与表达式翻译 6.6.3 控制流类语句翻译 6.6.4 数组说明与数组元素引用的翻译 6.6.5 过程、函数说明和调用的翻译 Ch6 语义分析与中间代码生成 6.6 语句翻译与中间代码生成 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.1 说明类 语句翻译 说明类语句 语言中定义性信息，一般不产生目标代码，其作用是辅

19、助完成编译。例如， 常量说明，变量说明，类型说明， 对象说明，标号说明 说明类语句的处理 相关说明的属性信息填入符号表，提供语义检查和存储分配的依据。 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.1 说明类 语句翻译 一. 常量定义语句的翻译 二. 简单说明类语句 三. 复合类型说明语句 6.6.1 说明类语句的翻译 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.1 说明类 语句翻译常量说明语句的文法CONST_DEF CONST ; ; id=num 常量说明语句的语义子程序 num.ord=look_con_table(num.lexval); id.ord=nu

20、m.ord; id.type= num.type; id.kind=constant; add(id.entry;id.ord; id.type; id.kind) 一. 常量定义语句的翻译 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.1 说明类 语句翻译 CONST 标识符常量； CONST pi=3.1416; true=1; true pi13.1416 addr type kind namenamelistvalueconslistRCONSBCONSCONST pi=3.1415926;3.1415926举例说明： Ch6 语义分析与中间代码生成 6.6 语句翻译 6.

21、6.1 说明类 语句翻译 一. 常量定义语句的翻译 二. 简单说明类语句 三. 复合类型说明语句 6.6.1 说明类语句的翻译 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.1 说明类 语句翻译 翻译方案和语义子程序Dint id fill(ENTRY(id)，int)；D.AT=int Dfloat id fill(ENTRY(id)，float)；D.AT=float DD，id; fill(ENTRY(id)，D1 .AT)； D.AT=D1 .AT * 其中：D.AT：非终结符D的属性。fill(P, A): 完成把性质A填入P所指的符号表入口的相应数据项中的函数。ENTR

22、Y(i)：给出i所代表的量在符号表中的入口的函数 二. 简单说明类语句 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.1 说明类 语句翻译int i , j ;float a ,b ;类型变量表 name kind type addr iVI0 jVI4 aVR8 bV R16 namelist举例说明： Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.1 说明类 语句翻译 一. 常量定义语句的翻译 二. 简单说明类语句 三. 复合类型说明语句 6.6.1 说明类语句的翻译 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.1 说明类 语句翻译 三. 复合类型说明

23、语句 T struct LD VL id | D D;F | FF type V;V V, id | 其中： L： 结构类型名； D：结构成员； V：变量表； F： 结构成员项； id: 标识符； Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.1 说明类 语句翻译 语义处理涉及 (1) 结构成员与该结构相关； (2) 结构的存储：一个结构的所有成员项 连续存放(简单方式)； (3) 结构的引用是结构成员的引用，不能 整体引用；（成员信息须单独记录） 例如， struct date int year, month, day; today, yesterday; Ch6 语义分析与中间

24、代码生成 6.6 语句翻译 6.6.1 说明类 语句翻译14084LEN 52CV d12Iarray c4RV b0IV a OFFSET type kind name 结构成员分表name kind addr k1struct namelist例如，struct k1 int a; float b; int c10; char d; 第 6 章 语义分析与中间代码生成 6.6.1 说明类语句的翻译 6.6.2 赋值语句与表达式翻译 6.6.3 控制流类语句翻译 6.6.4 数组说明与数组元素引用的翻译 6.6.5 过程、函数说明和调用的翻译 Ch6 语义分析与中间代码生成 6.6 语句翻译

25、与中间代码生成 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.2 赋值 语句与表达式翻译 赋值语句形式定义 A V = E 赋值语句目标结构* 赋值语句的处理集中在表达式的处理上 计算E.code E值 VCode区 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.2 赋值 语句与表达式翻译 A i=E GEN(=，E.PLACE， _，ENTRY(i) 赋值语句翻译语义子程序其中: GEN(OP，ARG1，ARG2，RESULT): 函数。 把四元式(OP，ARG1，ARG2，RESULT) 填入四元式表。 E.PLACE：表示存放E值的变量名在符号表的 入口地址。 E

26、NTRY(i)：给出i表示的单词在符号表中的入口。 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.2 赋值 语句与表达式翻译 (2) “=”的处理： “=”左右部类型相容性检查和转换 ； 赋值语句语义处理 (1) 表达式处理(产生表达式的中间代码)； Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.2 赋值 语句与表达式翻译 表达式形式定义 E E op E | op E | id 其中： OP: 为运算符； E, id: 运算对象。 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.2 赋值 语句与表达式翻译 (1) E E OP E E.PLACE=NEWTE

27、MP； GEN(OP, E1.PLACE, E2.PLACE, E.PLACE) (2) E OP E E.PLACE=NEWTEMP； GEN(OP, E1.PLACE，_, E.PLACE) (3) E id E.PLACE=ENTRY(id) 表达式翻译的语义子程序 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.2 赋值 语句与表达式翻译 写出语句a=b+c+d翻译后的四元式代码：赋值 语句与表达式翻译举例：(+ b c t1)(+ t1 d t2)(= t2 - a) +id=+idididAEEEEE第 6 章 语义分析与中间代码生成 6.6.1 说明类语句的翻译 6.6

28、.2 赋值语句与表达式翻译 6.6.3 控制流类语句翻译 6.6.4 数组说明与数组元素引用的翻译 6.6.5 过程、函数说明和调用的翻译 Ch6 语义分析与中间代码生成 6.6 语句翻译与中间代码生成 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.3 控制流类 语句翻译 控制流语句: 改变程序执行顺序，引起程序执行发生跳转的语句。 程序设计语言中出现频繁的语句； 为可执行语句，要产生相应的目标代码； 控制流程的变换，依靠代码中的跳转指 令与对应跳转的语句标号。 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.3 控制流类 语句翻译 控制流语句特点 改变程序执行顺序，引起

29、程序执行发生跳转（向前或向后）。 跳转目标与依据语句标号 显式：位于源语句之前； （如， L1： S;） 隐式：内含于源语句之中且在源 程序中未标识的； Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.3 控制流类 语句翻译If (er) S1; else S2for ( e1; e2; e3) S ; 跳出循环体继续 循环体 开 始 循环体终值判别 er=T跳转目标 er=F跳转目标跳出if 继续循环变量重赋值 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.3 控制流类 语句翻译一. 语句标号与拉链返填技术条件语句的翻译循环语句的翻译 四. 多分支语句的翻译6.6.3

30、控制流类语句翻译 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.3 控制流类 语句翻译 语句标号处理 控制流类语句处理面对的公共问题和实现技术 语句标号处理 先定义后引用 先引用后定义 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.3 控制流类 语句翻译语句标号 定义性出现 （如， L1: S ;） 使用性出现 （如， goto L1 ;） addr 定义否(flag)标号名语句标号表（LT）标号所标识的源语句的中间代码序列的第一条代码的存放地址1表示定义性出现0表示使用性出现 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.3 控制流类 语句翻译 对多遍扫描

31、的编译器 视为一种情况(先定义后引用) 处理。例如， 20: c=a*b ; goto 20; goto 20; Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.3 控制流类 语句翻译 *, a, b, c j, , , q j, , , q q-1 q k n Code区q120 LT20: c=a*b;goto 20;goto 20;20: c=a*b ; goto 20; goto 20; Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.3 控制流类 语句翻译 适用于一遍扫描的编译器；例如， goto 20; goto 20; 20: c=a*b ; 产生这2条语句的

32、代码时，还未扫描到20号语句，即没有生成该语句的代码，因此转向的目标地址未定。拉链-返填技术处理标号先引用后定义的情况： Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.3 控制流类 语句翻译 goto 20; goto 20; 20: c=a*b ; ( j , , , 0 ) p Code区p020 LT q200q ( j , , , p )链尾 r201r ( *, a, b, c)返填 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.3 控制流类 语句翻译 goto 20; goto 20; 20: c=a*b ; p ( j , , , 0 )Code区200p

33、 LT q200q ( j , , , p )拉链 r201r ( *, a, b, c)返填rr Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.3 控制流类 语句翻译 注意：链尾标志在代码区的四元式中，链头在标号表中，链在与同一语句标号相关的跳转代码中； 3. 返填次序: 2. 拉链次序： p q尾头q p ( 在代码区跳转指令中(addr=0) )尾头 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.3 控制流类 语句翻译一. 语句标号与拉链返填技术条件语句的翻译循环语句的翻译 四. 多分支语句的翻译 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.3 控制

34、流类 语句翻译二. 条件语句的翻译 条件语句文法: S if (E) then S1 | if (E) S1 else S2 | while (E) S1 其中： E：条件表达式 (有语义值 E.True和 E.False)； S1, S2: 语句； Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.3 控制流类 语句翻译计算EE?S1非0= 0 S if (E) then S1 E.trueE.false 测E S1.codeE.true:E.false:Goto E.trueGoto E.false E.codeE.true:E.false: Ch6 语义分析与中间代码生成 6.6

35、 语句翻译 6.6.3 控制流类 语句翻译 条件语句翻译的语义子程序 S if E then S1 E.true=newlabel； E.false=newlabel； S.code=E.code|GEN(jT ，_，_，E.true)| GEN(jF ，_，_，E.false)| GEN(E.true：) | S1.code| GEN(E.false：) Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.3 控制流类 语句翻译计算EE?S1= 0非0 S if (E) then S1E.false 测E S1.codeE.false:Goto E.false E.codeE.fals

36、e: Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.3 控制流类 语句翻译 条件语句翻译的语义子程序 S if E then S1 E.false=newlabel； S.code=E.code|GEN(jF ，_，_，E.false)| S1.code| GEN(E.false：) Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.3 控制流类 语句翻译if (E) S1 else S2计算EE?S1E.true:E.false:非0= 0S2Next:E.trueE.falseNext 测E S1.codeE.true:E.false:Goto E.false goto

37、 Next S2.code Next :Goto E.true E.code Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.3 控制流类 语句翻译S if E then S1 else S2 E.true=newlabel； E.false=newlabel； S.next=newlabel； S.code=E.code | GEN(jT ，_，_，E.true) | GEN (jF ，_，_，E.false) | GEN (E.true：| S1.code | GEN (j，_，_，S.next) | GEN (E.false：) | S2.code|GEN(S.next ： )

38、 条件语句翻译的语义子程序 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.3 控制流类 语句翻译if (E) S1 else S2计算EE?S1E.false:非0= 0S2Next:E.falseNext 测E S1.codeE.false:Goto E.false goto Next S2.code Next : E.code Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.3 控制流类 语句翻译S if E then S1 else S2 E.false=newlabel； S.next=newlabel； S.code=E.code | GEN (jF ，_，_，

39、E.false) | S1.code | GEN (j，_，_，S.next) | GEN (E.false：) | S2.code|GEN(S.next ： ) 条件语句翻译的语义子程序 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.3 控制流类 语句翻译 while (E) S1计算EE?E.true:E.false:=0非0S1E.begin:E.trueE.falsebegin 测E S1.codeE.true:E.false:Goto E.falsegoto begin begin :Goto E.true E.code Ch6 语义分析与中间代码生成 6.6 语句翻译

40、6.6.3 控制流类 语句翻译S while (E) S1 E.true=newlabel； E.false=newlabel； S.begin=newlabel； S.code=GEN(S.begin：) | E.code | GEN(jT ，_，_，E.true) | GEN(jF ，_，_，E.false) | GEN(E.true：) | S1.code | GEN(j，_，_，S.begin)| GEN(E.false：) 条件语句翻译的语义子程序 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.3 控制流类 语句翻译 while (E) S1计算EE?E.false:=0

41、非0S1E.begin:E.falsebegin 测E S1.codeE.false:Goto E.falsegoto begin begin : E.code Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.3 控制流类 语句翻译S while (E) S1 E.false=newlabel； S.begin=newlabel； S.code=GEN(S.begin：) | E.code | GEN(jF ，_，_，E.false) | S1.code | GEN(j，_，_，S.begin)| GEN(E.false：) 条件语句翻译的语义子程序 Ch6 语义分析与中间代码生成

42、6.6 语句翻译 6.6.3 控制流类 语句翻译例6.2 if (AB & BC ) S1 else S2用到的语法：Sif C S else SCC & T|TTididNDA Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.3 控制流类 语句翻译例6.2 if (AB & BC ) S1 else S2L1L2L3 ( A B T1) ( B C T2) (JT T3 _ 0 ) (JF T3 _ 0 ) S1.code 36 S2.code(J _ _ 0 )10:14:18:20:24:28:32:36:40:44:320L3240L2200L1128281140L1:L2:

43、L3:结果S1S20 非0计算AB & BC (& T1 T2 T3) 3640JT L1JF L2 S1.codeL2:goto L3 L1: AB & BC S2.codeL3: Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.3 控制流类 语句翻译一. 语句标号与拉链返填技术条件语句的翻译循环语句的翻译 四. 多分支语句的翻译6.6.3 控制流类语句翻译 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.3 控制流类 语句翻译计算e1计算e2S计算e3e2?L1:L2:L4:L3:= 0非0 ( jT, _, _, L2) ( jF, _, _, L3) e3.code

44、 ( j , _, _, L1) S.code ( j , _, _, L4)L4:L1:L2:L3:e1.codee2.code测e2三. 循环语句的翻译 A for ( e1 ; e2 ; e3 ) SL1L3L4L2 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.3 控制流类 语句翻译循环语句的翻译的语义子程序 A for ( e1 ; e2 ; e3 ) S L1=newlabel；L2=newlabel； L3=newlabel；L4=newlabel； A.code=e1.code |GEN(L1：) | e2.code | GEN(jT，_，_，L2) | GEN(j

45、F，_，_，L3) | GEN(L4：) | e3.code | GEN(j，_，_，L1) |GEN(L2：) | S.code |GEN(j ，_，_，L4) | GEN(L3：) ( jT, _, _, L2) ( jF, _, _, L3) e3.code ( j , _, _, L1) S.code ( j , _, _, L4)L4:L1:L2:L3:e1.codee2.code测e2给出如下C程序段的目标代码结构： for ( e1; e2; e3;) for ( t1; t2; t3;) if ( er ) S1; S2; L1L2L3L4L5L7L6L9L8 Ch6 语义分析

46、与中间代码生成 6.6 语句翻译 6.6.3 控制流类 语句翻译L1:L2:L4:L3:计算e1计算e2S1计算t3e2?= 0非0计算t1计算t2t2?非0计算erer?非0计算e3= 0S2L5L6L7L8L9e1.codee2.code测e2值( jT , , , L3 )( jF , , , L9 )e3.code( j , , , L1 )t1.codet2.codet3.code( j , , , L4 )er.code测t2值测er值( jF , , , L7 )S1.codeS2.code( j , , , L5 )L1:L2:L3:L4:L5:L6:L7:( jT , , ,

47、 L6 )( jF , , , L8 )L8:( j , , , L2 )L9: Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.3 控制流类 语句翻译设有下列C语言的语句（注： Li是设定的语句标号,在注释中标识出所在位置）i=j=0;for ( ; j=0, i=0, i=100; L2：i+,j-)if (E1) S1; / if L3: (E1) L4: S1;S2; / L5: S2;其中：S1和S2代表语句，对应的四元式分别为S1.code和S2.code；E1代表条件表达式，对应的四元式为E1.code。 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.3 控

48、制流类 语句翻译1给出该语句的四元式形式的目标代码结构，填入下表。说明：无条件转移操作符用“j”表示；条件成立转移的操作符用“jT”表示；条件不成立转移的操作符用“jF”表示。 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.3 控制流类 语句翻译Adresscode备注(可有可无)2. 给出中间代码生成后对应该段代码填写的下列语句标号表内容（按填写标号表的实际顺序）。 注：设编译器是一遍扫描的编译器。 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.3 控制流类 语句翻译语句标号(Li)定义与否标志(1表示已定义，0反之)Addr Ch6 语义分析与中间代码生成 6.6

49、语句翻译 6.6.3 控制流类 语句翻译一. 语句标号与拉链返填技术条件语句的翻译循环语句的翻译 四. 多分支语句的翻译6.6.3 控制流类语句翻译 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.3 控制流类 语句翻译四. 多分支语句的翻译 A switch (e ) case c1 : S1 break ; case c2 : S2 break ; case cn : Sn break ; default : Sn+1 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.3 控制流类 语句翻译计算e值e?S1S2SnSn+1L1:L3:L2n-1:L2:L2n-2:next

50、:L2n : Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.3 控制流类 语句翻译四. 多分支语句的翻译 A switch (e ) case c1 : S1 break ; case c2 : S2 break ; case cn : Sn break ; default : Sn+1 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.3 控制流类 语句翻译e.code测C1S1.code(j, _, _, next)测C2S2.code(j, _, _, next)测CnSn.code(j, _, _, next)Sn+1.code L1: L2: L3: L4: L2

51、n-2: L2n-1: L2n: next:jT L1jF L2jT L3jF L4 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.3 控制流类 语句翻译 A switch (e ) case c1 : S1 break ; case c2 : S2 break ; case cn : Sn break ; default : Sn+1 e.code(j, _, _, test)S1.code(j, _, _, next)S2.code(j, _, _, next)Sn.code(j, _, _, next)Sn+1.code(j, _, _, next)If e=c1 goto

52、L1If e=c2 goto L2If e=cn goto Lngoto Ln+1 L1: Ln+1: test: next: L2: Ln:测试表 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.3 控制流类语句翻译第 6 章 语义分析与中间代码生成 6.6.1 说明类语句的翻译 6.6.2 赋值语句与表达式翻译 6.6.3 控制流类语句翻译 6.6.4 数组说明与数组元素引用的翻译 6.6.5 过程、函数说明和调用的翻译 Ch6 语义分析与中间代码生成 6.6 语句翻译与中间代码生成 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.4 数组说明与引用翻译一. 数组说明t

53、ype A d1 d2 dn ；type A d1 . d1 d2 . d2 dn . dn ；数组类型数组名数组维数、每维大小、数组体积n: di个数 di的值d1*d2* *dn Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.4 数组说明与引用翻译数组说明的语义处理 填表，登记数组的属性信息。typenamedimdim_valuevol符号表公共、等长信息 （符号表）与计算数组元素地址有关、不等长信息 （信息向量表） Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.4 数组说明与引用翻译例6.3设有说明 int a22； float b4；abnamelist b

54、array R a array Iname kind type addr数组第一个元素地址a计算数元地址不变部分C体积 =d1*d2*dn维数第n维大小第二维大小第一维大小信息向量表 若为上下界需计算： a(2.10)10-2+1=9何时计算？动态数组如何处理？returnb0Cb14a0Ca2*2222信息向量表4*1 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.4 数组说明与引用翻译二. 数组元素引用type A d1 d2 dn ； 数组说明 A i1 i2 in 数组引用 * 不能整体引用，仅对单一数组元素引用。 数组元素引用的语义处理 语义检查： 类型匹配；下标越界检查

55、； 产生代码：数组元素地址计算的中间代码。 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.4 数组说明与引用翻译数组元素地址计算编译时能否完成？一般不能 A i1 i2 in 中 ik多为表达式 如， ai+j-1j+ 运行时得到下标值涉及数组元素地址计算的有关知识 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.4 数组说明与引用翻译 数组存储方式 (线性连续)按行存储按列存储 例如， int a22;a11a10a01a00 a0按行a11a01a10a00 a0按列a01add = a0+1*bytea01add = a0+2*byte Ch6 语义分析与中间代码生

56、成 6.6 语句翻译 6.6.4 数组说明与引用翻译 数组元素地址计算 据存储方式，通过下述规则计算数组元素位置 (顺序号) + a0 对一维数组 int an; / 默认下标下界=0 则 aiaddr = a0 +( i ) ( 若数组下标下限=1，则ai = a0 + ( i-1 ) ) Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.4 数组说明与引用翻译 对二维数组 int anm ; 则 aijaddr = a0 +( i *m + j) 若数组下标下限=1，则 aijadd = a0 +(i-1) *m + ( j-1) Ch6 语义分析与中间代码生成 6.6 语句翻译

57、6.6.4 数组说明与引用翻译 对n维数组 int ad1 d2 dn; 则 ai1 i2 in add = a0 +( i1 *d2*d3 * *dn + i2 *d3 *d4* *dn + + in-1 *dn + in)含ik,是可变部分，程序运行时方可知。进一步考虑更一般的情况：若数组下标下限0 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.4 数组说明与引用翻译 则 ai1 i2 in add = a0 +( (i1-1) *d2*d3 * *dn + (i2 -1) *d3 *d4* *dn + + (in-1 -1) *dn + ( in -1) ) = a0 + i

58、1d2d3 dn + i2d3d4 dn+in-1dn +in (d2d3 dn +d3d4 dn + +dn+1)V不变 C变换返回若数组下标下限=1 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.4 数组说明与引用翻译 ai1 i2 in add = a0 + i1d2d3 dn + i2d3d4 dn+in-1dn +in (d2d3 dn +d3d4 dn + +dn+1)V不变 C = a0 C + V = CUN + Vconspartvarpart编译时计算,填入内情向量表据数元引用情况，产生计算的中间代码，程序运行时算出。信息向量表 Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.4 数组说明与引用翻译 数组元素引用目标结构V.codeV值 VCUN = a0 CT = CUN + V计算V的中间代码计算 CUN数组元素地址 T Ch6 语义分析与中间代码生成 6.6 语句翻译 6.6.