编译原理：第6章 语义分析与中间代码生成.ppt
130页
课课 程程 内内 容容第第 1 章章 编编 译译 引引 论论第第 2 章章 形式语言与自动机基础形式语言与自动机基础第第 3 章章 词法分析词法分析 (Lexical Analysis)第第 4 章章 语法分析语法分析(Syntax Analysis) —— 自上而下分析法自上而下分析法第第 5 章章 语法分析语法分析(Syntax Analysis) —— 自下而上分析法自下而上分析法第第 6 章章 语义分析与中间代码生成语义分析与中间代码生成第第 7 章章 运运 行行 环环 境境第第 8 章章 代码优化（代码优化（optimization）） 第第 2 页页第第 6 章章 语义分析与中间代码生成语义分析与中间代码生成 6.1 语义分析综述语义分析综述 6.2 语法制导翻译与属性文法语法制导翻译与属性文法 6.3 中间语言中间语言 6.4 符号表符号表 6.5 类型检查（自学）类型检查（自学） 6.6 语句翻译与中间代码生成语句翻译与中间代码生成 第第 3 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.1 语义分析综述语义分析综述§ 语义分析的地位语义分析的地位Front end ( 分析分析 )Back end ( 综合综合 )语语义义处处理理Ø 编译程序最实质性的工作；编译程序最实质性的工作；Ø 第一次对源程序的语义作出解释，引第一次对源程序的语义作出解释，引 起源程序质的变化。
起源程序质的变化 第第 4 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.1 语义分析综述语义分析综述§ 语义分析的任务语义分析的任务 按照语法分析器识别的语法范畴进行语按照语法分析器识别的语法范畴进行语义检查和处理，产生相应的中间代码或目标义检查和处理，产生相应的中间代码或目标代码§ 中间代码中间代码 介于源语言和目标代码之间的一种代码介于源语言和目标代码之间的一种代码 第第 5 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.1 语义分析综述语义分析综述§ 引入中间代码的目的引入中间代码的目的 1. 方便生成目标代码；方便生成目标代码； 2. 便于优化；便于优化； 3. 便于移植便于移植 第第 6 页页第第 6 章章 语义分析与中间代码生成语义分析与中间代码生成 6.1 语义分析综述语义分析综述 6.2 语法制导翻译与属性文法语法制导翻译与属性文法 6.3 中间语言中间语言 6.4 符号表符号表 6.5 类型检查（自学）类型检查（自学） 6.6 语句翻译与中间代码生成语句翻译与中间代码生成 第第 7 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.2 语法制导翻译与属性文法语法制导翻译与属性文法§ 语法制导翻译语法制导翻译 为文法的每一个产生式配一个相应的语义为文法的每一个产生式配一个相应的语义子程序（或语义规则描述的语义动作），并在子程序（或语义规则描述的语义动作），并在语法分析的同时调用它。
语法分析的同时调用它 第第 8 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.2 语法制导翻译与属性文法语法制导翻译与属性文法§ 属性翻译文法属性翻译文法 把语义引入文法，给产生式中的文法符把语义引入文法，给产生式中的文法符号附加号附加“属性属性”，构成涉及语义的翻译文法构成涉及语义的翻译文法§ 形式定义形式定义 A = （（ G , V , F ）） 其中：其中： G：： 一般为二型文法；一般为二型文法； V：： 属性的有穷集；属性的有穷集； F：： 关于属性的断言或谓词的有穷集关于属性的断言或谓词的有穷集文法符号的语义性质文法符号的语义性质(语义属性语义属性) 第第 9 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 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数、符号串、类型、存储空间数、符号串、类型、存储空间… 第第 10 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.2 语法制导翻译与属性文法语法制导翻译与属性文法§ 综合属性综合属性 分析树中分析树中, ,如果一个结点的属性值是通过如果一个结点的属性值是通过子结点的属性值计算得到子结点的属性值计算得到, ,则称为综合属性。
则称为综合属性 第第 11 页页 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.val×F.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=3.val=5.val=15.val=15.val=4.val=4.val=19 第第 12 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.2 语法制导翻译与属性文法语法制导翻译与属性文法§ 继承属性继承属性 分析树中分析树中, ,如果一个结点的属性值是由该如果一个结点的属性值是由该结点的父结点和结点的父结点和( (或或) )兄弟结点的属性定义的兄弟结点的属性定义的称为继承属性。
称为继承属性§ 综合属性综合属性 分析树中分析树中, ,如果一个结点的属性值是通过如果一个结点的属性值是通过子结点的属性值计算得到则称为综合属性子结点的属性值计算得到则称为综合属性 第第 13 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.2 语法制导翻译与属性文法语法制导翻译与属性文法例如，例如，float id1，，id2 ，， id3 DTL L .in = T .typeTint T .type = integerTfloat T .type = float LL,id L1 .in = 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 第第 14 页页第第 6 章章 语义分析与中间代码生成语义分析与中间代码生成 6.1 语义分析综述语义分析综述 6.2 语法制导翻译与属性文法语法制导翻译与属性文法 6.3 中间语言中间语言 6.4 符号表符号表 6.5 类型检查（自学）类型检查（自学） 6.6 语句翻译与中间代码生成语句翻译与中间代码生成 第第 15 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.3 中间语言中间语言中间语言中间语言( 中间代码中间代码)是语义程序的输出。
是语义程序的输出 中间语言的设计与应用既要考虑从源中间语言的设计与应用既要考虑从源语言到目标语言的翻译跨度又要考虑目标语言到目标语言的翻译跨度又要考虑目标机的指令集特点机的指令集特点中间语言中间语言N元式元式(三元式、间接三元式四元式三元式、间接三元式四元式)逆波兰式逆波兰式图图 第第 16 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.3 中间语言中间语言 一一. 逆波兰式逆波兰式(后缀式后缀式 )形式定义：形式定义：e1e2 … en ( n ≥1)运算对象运算对象运算符运算符 a * b - aa+b*(c+d)*(e+f)例如，例如， ab*a＠＠ (＠＠表示单目表示单目――)a b c d + * e f + * + 第第 17 页页 IF
BZ是二目操作符，如果是二目操作符，如果第一运算对象数第一运算对象数的值为假，的值为假，则产生一个到则产生一个到第二运算对象第二运算对象的转移 BR则是一个单目操作符，它产生一个到则是一个单目操作符，它产生一个到运算对象运算对象的的转移 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.3 中间语言中间语言Label2Label1JFJ 第第 18 页页例例6.1 设有如下设有如下C程序片程序片段段{ int k；； i=j=0；；h：： k=100；； if (k>i+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 第第 19 页页 二二. N元式元式N个域的记录结构个域的记录结构 （（ D1，， D2，，D3，，… ，，Dn）） OP域域 操作对象域操作对象域三元式、间接三元式三元式、间接三元式双地址机指令形式双地址机指令形式 四元式四元式三地址机指令形式三地址机指令形式 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.3 中间语言中间语言§ 常见常见N元式元式 第第 20 页页 其中：其中： NO.:.:为产生的三元式的顺序编号；为产生的三元式的顺序编号； OP : 是操作符；是操作符； ARG1和和ARG2为第一操作数和第二操作数。
为第一操作数和第二操作数 (也可以是前面某一个三元式的编号，也可以是前面某一个三元式的编号， 代表该三元代表该三元式的计算结果被作为操作数式的计算结果被作为操作数 ) Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.3 中间语言中间语言三元式形式定义：三元式形式定义： NO. ( OP , ARG1 , ARG2 ) 间接三元式形式定义：间接三元式形式定义： 间接码表间接码表 + 三元式表三元式表 第第 21 页页 例如，语句例如，语句 X=A+B*C 的三元式表示为的三元式表示为 NO. . OP ARG1 ARG2(1)(2)(3)* B C+ A (1)= (2) X Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.3 中间语言中间语言 第第 22 页页 NO. OP ARG1 ARG2(1)(2)(3)(4)(5)(6)(7) > X Y BZ (1) (5)= X ZBR (7) + Y 1 = (5) Z if X>Y then Z = X else Z = Y+1的三元式可以表示为的三元式可以表示为 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.3 中间语言中间语言 第第 23 页页 (a+b)2 + (a+b)3 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.3 中间语言中间语言 其中：其中：“ ” 表示幂运算。
表示幂运算 + ②② ④④ ⑤⑤ ③③ 3 ④④ + a b ③③ ①① 2 ②② + a b ①①OP ARG1 ARG2NO 第第 24 页页 (a+b)2 + (a+b)3 的间接三元式的间接三元式 ④④ ③③ ①① ②② ①①间接码表间接码表 +, ②② , ③③ ④④ , ①① , 3 ③③ , ①① , 2 ②② + , a, b ①①三元式表三元式表 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.3 中间语言中间语言控控制制三三元元式式代代码码执执行行顺顺序序 第第 25 页页 四元式形式定义：四元式形式定义： 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 第第 26 页页 NO. OP ARG1 ARG2 Result (1)(2)(3)(4)(5)(6)(7) > X Y t1BZ t1 (5) = X ZBR (7) + Y 1 t2 = t2 Z if X>Y then Z = X else Z = Y+1的四元式可以表示为的四元式可以表示为 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.3 中间语言中间语言 第第 27 页页 三三. 图（树）图（树） 一个三元式一个三元式一棵子树一棵子树 OP子树根子树根 ARG1子树左叶节点子树左叶节点 ARG2子树右叶节点子树右叶节点 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.3 中间语言中间语言 第第 28 页页 (a+b)2 + (a+b)3三元式三元式ab+ab+ +23 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.3 中间语言中间语言 +, ②② , ④④ ⑤⑤ , ③③ , 3 ④④ + , a, b ③③ , ①① , 2 ②② + , a, b ①① 第第 29 页页 if X>Y then Z = X else Z = Y+1的树可以表示为的树可以表示为 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.3 中间语言中间语言zBRYYXBZ>(4)xz=(5)1(4)=+(5)(1)(2)(3)树编号树编号树编号树编号 第第 30 页页 ab+ab+ +23树树线性化：后线性化：后序遍历序遍历 逆波兰式逆波兰式几种表示间关系几种表示间关系 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.3 中间语言中间语言“单步单步”表表示示 三元式三元式 第第 31 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.3 中间语言中间语言&语法分析的结果为树；语法分析的结果为树；&逆波兰式适于栈式存储的计算机（堆栈机）；逆波兰式适于栈式存储的计算机（堆栈机）；&四元式便于优化；四元式便于优化；&间接三元式优化时的时空效率类似于四元式。
间接三元式优化时的时空效率类似于四元式综述：综述： 第第 32 页页第第 6 章章 语义分析与中间代码生成语义分析与中间代码生成 6.1 语义分析综述语义分析综述 6.2 语法制导翻译与属性文法语法制导翻译与属性文法 6.3 中间语言中间语言 6.4 符号表符号表 6.5 类型检查（自学）类型检查（自学） 6.6 语句翻译与中间代码生成语句翻译与中间代码生成 第第 33 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.4 符号表符号表§ 源程序流基本组成单位特点源程序流基本组成单位特点 关键字：关键字：表示语句性质，反映语句结构；表示语句性质，反映语句结构； 标识符：标识符：表示程序中各种实体；表示程序中各种实体； 如，变量名；常量名；标号名；过程名；如，变量名；常量名；标号名；过程名；函数名；文件名，数组名函数名；文件名，数组名 … V: name , type , addr , level … array: name , type , addr , dim , level , size … 第第 34 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.4 符号表符号表语句标号语句标号: name , addr , 定义否定义否 …过程、函数过程、函数: name , addr , 形参形参 …反映了标识符的语义特征属性，是翻译的依据。
反映了标识符的语义特征属性，是翻译的依据 记录于符号表中（记录于符号表中（namelist）） 整个编译过程中动态地采集、记录、变更、引用整个编译过程中动态地采集、记录、变更、引用 第第 35 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.4 符号表符号表例如，设有例如，设有C程序片段程序片段 : int i , a[4] ; { … i=a[2] ; … }词法语法语义词法语法语义分析分析i, a ⇒ ⇒ 符号表符号表i.type ⇒⇒符号表符号表a.type ⇒⇒符号表符号表a.维数维数 ⇒ ⇒ 符号表符号表a.每维大小每维大小 ⇒ ⇒ 符号表符号表 …… 类型检查；类型检查； 数组越界检查；数组越界检查； 回填回填addr; … 第第 36 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.4 符号表符号表§ 符号表符号表 存放源程序中有关标识符的属性信息的存放源程序中有关标识符的属性信息的数据结构。
数据结构§ 符号表作用符号表作用语义检查依据；语义检查依据；代码生成时地址分配依据代码生成时地址分配依据收集标识符属性信息；收集标识符属性信息；§ 符号表结构符号表结构 属性信息域属性信息域 名字域名字域 第第 37 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.4 符号表符号表§ 常见标识符类的主要属性与作用常见标识符类的主要属性与作用1. 标识符名标识符名作用：作用：查重查重(考虑作用域和可视性前提考虑作用域和可视性前提)2. 类型作用：作用：存储空间分配；可施加运算的检查等存储空间分配；可施加运算的检查等3. 存储类别存储类别作用：作用：提供语义处理、检查、存储提供语义处理、检查、存储 分配的依据分配的依据4. 作用域、可视性作用域、可视性作用：作用：动态活动环境支持，提动态活动环境支持，提 供量所在层次；供量所在层次； 第第 38 页页第第 6 章章 语义分析与中间代码生成语义分析与中间代码生成 6.1 语义分析综述语义分析综述 6.2 语法制导翻译与属性文法语法制导翻译与属性文法 6.3 中间语言中间语言 6.4 符号表符号表 6.5 类型检查（自学）类型检查（自学） 6.6 语句翻译与中间代码生成语句翻译与中间代码生成 第第 39 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译与中间代码生成语句翻译与中间代码生成§ 语句翻译设计要点语句翻译设计要点 1. 根据语义确定语句的目标结构根据语义确定语句的目标结构 ；；源语句源语句中间及目标代码的布局中间及目标代码的布局If E then S1 测测E S1.codeE.f:Goto E.f E.code 第第 40 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译与中间代码生成语句翻译与中间代码生成2. 确定中间代码确定中间代码 ；； 3. 根据目标结构和语义规则，构造语义根据目标结构和语义规则，构造语义 子程序（转换翻译程序）子程序（转换翻译程序） ；；4. 涉及的实现技术涉及的实现技术 § 语句翻译设计要点语句翻译设计要点 1. 根据语义确定语句的目标结构根据语义确定语句的目标结构 ；； 第第 41 页页6.6 语句翻译与中间代码生成语句翻译与中间代码生成 6.6.1 说明类语句的翻译说明类语句的翻译 6.6.2 赋值语句与表达式翻译赋值语句与表达式翻译 6.6.3 控制流类语句翻译控制流类语句翻译 6.6.4 数组说明与数组元素引用的翻译数组说明与数组元素引用的翻译 6.6.5 过过程、函数程、函数说说明和明和调调用的翻用的翻译译 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译与中间代码生成语句翻译与中间代码生成 第第 42 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.1 说明类说明类 语句翻译语句翻译§ 说明类语句说明类语句 语言中定义性信息，一般不产生目标代码，语言中定义性信息，一般不产生目标代码，其作用是辅助完成编译。
其作用是辅助完成编译例如，例如， 常量说明，变量说明，类型说明，常量说明，变量说明，类型说明， 对象说明，标号说明对象说明，标号说明 ……§ 说明类语句的处理说明类语句的处理 相关说明的属性信息填入符号表，提供语相关说明的属性信息填入符号表，提供语义检查和存储分配的依据义检查和存储分配的依据 第第 43 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.1 说明类说明类 语句翻译语句翻译 一一. 常量定义语句的翻译常量定义语句的翻译 二二. 简单说明类语句简单说明类语句 三三. 复合类型说明语句复合类型说明语句 6.6.1 说明类语句的翻译说明类语句的翻译 第第 44 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.1 说明类说明类 语句翻译语句翻译常量说明语句的文法常量说明语句的文法CONST_DEF → CONST
的属性fill(P, A): 完成把性质完成把性质A填入填入P所指的符号表入口的相应所指的符号表入口的相应数据项中的函数数据项中的函数ENTRY(i)：：给出给出i所代表的量在符号表中的入口的函数所代表的量在符号表中的入口的函数 二二. 简单说明类语句简单说明类语句 第第 48 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.1 说明类说明类 语句翻译语句翻译int i , j ;float a ,b ;类型类型变量表变量表 name kind type addr … iVI0 jVI4 aVR8 bV R16 …namelist举例说明：举例说明： 第第 49 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.1 说明类说明类 语句翻译语句翻译 一一. 常量定义语句的翻译常量定义语句的翻译 二二. 简单说明类语句简单说明类语句 三三. 复合类型说明语句复合类型说明语句 6.6.1 说明类语句的翻译说明类语句的翻译 第第 50 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.1 说明类说明类 语句翻译语句翻译 三三. 复合类型说明语句复合类型说明语句 T struct L{D} VL id | D D;F | FF type V;V V, id | 其中：其中： L：： 结构类型名；结构类型名； D：：结构成员；结构成员； V：：变量表；变量表； F：： 结构成员项；结构成员项； id: 标识符；标识符； 第第 51 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.1 说明类说明类 语句翻译语句翻译§ 语义处理涉及语义处理涉及 (1) 结构成员与该结构相关；结构成员与该结构相关； (2) 结构的存储：一个结构的所有成员项结构的存储：一个结构的所有成员项 连续存放连续存放(简单方式简单方式)；； (3) 结构的引用是结构成员的引用，不能结构的引用是结构成员的引用，不能 整体引用；（成员信息须单独记录）整体引用；（成员信息须单独记录） 例如，例如， struct date { int year, month, day;} today, yesterday; 第第 52 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 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 c[10]; char d; } 第第 53 页页第第 6 章章 语义分析与中间代码生成语义分析与中间代码生成 6.6.1 说明类语句的翻译说明类语句的翻译 6.6.2 赋值语句与表达式翻译赋值语句与表达式翻译 6.6.3 控制流类语句翻译控制流类语句翻译 6.6.4 数组说明与数组元素引用的翻译数组说明与数组元素引用的翻译 6.6.5 过过程、函数程、函数说说明和明和调调用的翻用的翻译译 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译与中间代码生成语句翻译与中间代码生成 第第 54 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.2 赋值赋值 语句与表达式翻译语句与表达式翻译§ 赋值语句形式定义赋值语句形式定义 A V = E § 赋值语句目标结构赋值语句目标结构** 赋值语句的处理集中在表达式的处理上赋值语句的处理集中在表达式的处理上 计算计算E.code E值值 VCode区区 第第 55 页页 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值的变量名在符号表的值的变量名在符号表的 入口地址入口地址 ENTRY(i)：：给出给出i表示的单词在符号表中的入口表示的单词在符号表中的入口 第第 56 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.2 赋值赋值 语句与表达式翻译语句与表达式翻译 (2) “=”的处理：的处理： “=”左右部类型相容性左右部类型相容性检查和转换检查和转换 ；；§ 赋值语句语义处理赋值语句语义处理 (1) 表达式处理表达式处理(产生表达式的中间代码产生表达式的中间代码)；； 第第 57 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.2 赋值赋值 语句与表达式翻译语句与表达式翻译§ 表达式形式定义表达式形式定义 E E op E | op E | id 其中：其中： OP: 为运算符；为运算符； E, id: 运算对象。
运算对象 第第 58 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.2 赋值赋值 语句与表达式翻译语句与表达式翻译 (1) E →E OP E { { E. .PLACE=NEWTEMP；； 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) } }§ 表达式翻译的语义子程序表达式翻译的语义子程序 第第 59 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.2 赋值赋值 语句与表达式翻译语句与表达式翻译 写出语句写出语句a=b+c+d翻译后的四元式代码：翻译后的四元式代码：§赋值赋值 语句与表达式翻译举例：语句与表达式翻译举例：(+ b c t1)(+ t1 d t2)(= t2 -- a) +id=+idididAEEEEE 第第 60 页页第第 6 章章 语义分析与中间代码生成语义分析与中间代码生成 6.6.1 说明类语句的翻译说明类语句的翻译 6.6.2 赋值语句与表达式翻译赋值语句与表达式翻译 6.6.3 控制流类语句翻译控制流类语句翻译 6.6.4 数组说明与数组元素引用的翻译数组说明与数组元素引用的翻译 6.6.5 过过程、函数程、函数说说明和明和调调用的翻用的翻译译 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译与中间代码生成语句翻译与中间代码生成 第第 61 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.3 控制流类控制流类 语句翻译语句翻译§ 控制流语句控制流语句: 改变程序执行顺序，引起程改变程序执行顺序，引起程序执行发生跳转的语句。
序执行发生跳转的语句Ø 程序设计语言中出现频繁的语句；程序设计语言中出现频繁的语句；Ø 为可执行语句，要产生相应的目标代码；为可执行语句，要产生相应的目标代码；Ø 控制流程的变换，依靠代码中的跳转指控制流程的变换，依靠代码中的跳转指 令与对应跳转的语句标号令与对应跳转的语句标号 第第 62 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.3 控制流类控制流类 语句翻译语句翻译§ 控制流语句特点控制流语句特点 改变程序执行顺序，引起程序执行发生跳改变程序执行顺序，引起程序执行发生跳转（向前或向后）转（向前或向后）§ 跳转目标与依据跳转目标与依据语句标号语句标号 显式：显式：位于源语句之前；位于源语句之前； （（如，如， L1：： S;）） 隐式：隐式：内含于源语句之中且在源内含于源语句之中且在源 程序中未标识的；程序中未标识的； 第第 63 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.3 控制流类控制流类 语句翻译语句翻译If (er) S1; else S2for ( e1; e2; e3) S ; 跳出循跳出循环体继续环体继续 循环体循环体 开开 始始 循环体循环体终值判别终值判别 er=T跳转目标跳转目标 er=F跳转目标跳转目标跳出跳出if 继续继续循环变量循环变量重赋值重赋值 第第 64 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.3 控制流类控制流类 语句翻译语句翻译一一. 语句标号与拉链返填技术语句标号与拉链返填技术二二.条件语句的翻译条件语句的翻译三三.循环语句的翻译循环语句的翻译 四四. 多分支语句的翻译多分支语句的翻译6.6.3 控制流类语句翻译控制流类语句翻译 第第 65 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.3 控制流类控制流类 语句翻译语句翻译§ 语句标号处理语句标号处理 控制流类语句处理面对的公共问题和实现控制流类语句处理面对的公共问题和实现技术技术 § 语句标号处理语句标号处理 先定义后引用先定义后引用 先引用后定义先引用后定义 第第 66 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.3 控制流类控制流类 语句翻译语句翻译语句标号语句标号 定义性出现定义性出现 （（如，如， L1: S ;）） 使用性出现使用性出现 （（如，如， goto L1 ;）） addr 定义否定义否(flag)标号名标号名语句标号表（语句标号表（LT））标号所标识的源语句的中间代码序列的标号所标识的源语句的中间代码序列的第一条代码的存放地址第一条代码的存放地址1表示定义性出现表示定义性出现0表示使用性出现表示使用性出现 第第 67 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.3 控制流类控制流类 语句翻译语句翻译§ 对多遍扫描的编译器对多遍扫描的编译器 视为一种情况视为一种情况(先定义后引用先定义后引用) 处理。
处理例如，例如，… 20: c=a*b ; … goto 20; … goto 20; … 第第 68 页页 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; … 第第 69 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.3 控制流类控制流类 语句翻译语句翻译 适用于一遍扫描的编译器；适用于一遍扫描的编译器；例如，例如， …goto 20; … goto 20; … 20: c=a*b ; …产生这产生这2条语句条语句的代码时，还未的代码时，还未扫描到扫描到20号语号语句，即没有生成句，即没有生成该语句的代码，该语句的代码，因此转向的目标因此转向的目标地址未定。
地址未定§拉链拉链-返填技术处理返填技术处理标号标号先引用后定义的情况：先引用后定义的情况： 第第 70 页页 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)返填返填 第第 71 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.3 控制流类控制流类 语句翻译语句翻译 … goto 20; … goto 20; … 20: c=a*b ; … … p ( j , , , 0 )Code区区200p LT… q200q ( j , , , p )拉链拉链… r201r ( *, a, b, c)返填返填rr 第第 72 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.3 控制流类控制流类 语句翻译语句翻译 注意：注意：1.链尾标志在代码区的四元式中，链头在标号链尾标志在代码区的四元式中，链头在标号表中，链在与同一语句标号相关的跳转代码中；表中，链在与同一语句标号相关的跳转代码中； 3. 返填次序返填次序: 2. 拉链次序：拉链次序： p q尾尾头头q p ( 在代码区跳转指令中在代码区跳转指令中(addr=0) )尾尾头头 第第 73 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.3 控制流类控制流类 语句翻译语句翻译一一. 语句标号与拉链返填技术语句标号与拉链返填技术二二.条件语句的翻译条件语句的翻译三三.循环语句的翻译循环语句的翻译 四四. 多分支语句的翻译多分支语句的翻译 第第 74 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.3 控制流类控制流类 语句翻译语句翻译二二. 条件语句的翻译条件语句的翻译 条件语句文法条件语句文法: S if (E) then S1 ①① | if (E) S1 else S2 ② ② | while (E) S1 ③③ 其中：其中： E：：条件表达式条件表达式 (有语义值有语义值 E.True和和 E.False)；； S1, S2: 语句；语句； 第第 75 页页 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: 第第 76 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 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'：：') } 第第 77 页页 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.false: 第第 78 页页 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'：：') } 第第 79 页页 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 Next S2.code Next :Goto E.true E.code 第第 80 页页 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 '：：' ) } § 条件语句条件语句②②翻译的语义子程序翻译的语义子程序 第第 81 页页 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 第第 82 页页 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 ，，_，，_，，E.false) | S1.code | GEN (j，，_，，_，，S.next) | GEN (E.false'：：') | S2.code|GEN(S.next '：：' ) } § 条件语句条件语句②②翻译的语义子程序翻译的语义子程序 第第 83 页页 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 第第 84 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 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'：：') }§ 条件语句条件语句③③翻译的语义子程序翻译的语义子程序 第第 85 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.3 控制流类控制流类 语句翻译语句翻译 while (E) S1计算计算EE?E.false:=0非非0S1E.begin:E.falsebegin 测E S1.codeE.false:Goto E.falsegoto begin begin : E.code 第第 86 页页 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'：：') }§ 条件语句条件语句③③翻译的语义子程序翻译的语义子程序 第第 87 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.3 控制流类控制流类 语句翻译语句翻译例例6.2 if (A>B && B>C ) S1 else S2用到的语法：用到的语法：Sif C S else SCC && T|TTid>id 第第 88 页页ND A Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.3 控制流类控制流类 语句翻译语句翻译例例6.2 if (A>B && B>C ) 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:320L3240L2200L11 28281140L1:L2:L3:结果S1S20 非非0计算计算A>B && B>C (&& T1 T2 T3) 3640JT L1JF L2 S1.codeL2:goto L3 L1: A>B && B>C S2.codeL3: 第第 89 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.3 控制流类控制流类 语句翻译语句翻译一一. 语句标号与拉链返填技术语句标号与拉链返填技术二二.条件语句的翻译条件语句的翻译三三.循环语句的翻译循环语句的翻译 四四. 多分支语句的翻译多分支语句的翻译6.6.3 控制流类语句翻译控制流类语句翻译 第第 90 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.3 控制流类控制流类 语句翻译语句翻译计算计算e1计算计算e2S计算计算e3e2?L1:L2:L4:L3:= 0非非0 ( jT, _, _, L2) ( jF, _, _, L3) e3.code ( j , _, _, L1) S.code ( j , _, _, L4)…L4:L1:L2:L3:e1.codee2.code测测e2三三. 循环语句的翻译循环语句的翻译 A for ( e1 ; e2 ; e3 ) SL1L3L4L2 第第 91 页页 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(jF，，_，，_，，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 第第 92 页页给出如下给出如下C程序段的目标代码结构：程序段的目标代码结构： … for ( e1; e2; e3;) for ( t1; t2; t3;) if ( er ) S1; S2; …L1L2L3L4L5L7L6L9L8 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.3 控制流类控制流类 语句翻译语句翻译L1:L2:L4:L3:计算计算e1计算计算e2S1计算计算t3e2?= 0非非0计算计算t1计算计算t2t2?非非0计算计算erer?非非0计算计算e3= 0S2L5L6L7L8L9 第第 93 页页e1.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 , , , L6 )( jF , , , L8 )L8:( j , , , L2 )L9: Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.3 控制流类控制流类 语句翻译语句翻译 第第 94 页页设有下列设有下列C语言的语句（注：语言的语句（注： Li是设定的语句标是设定的语句标号号,在注释中标识出所在位置）在注释中标识出所在位置） i=j=0;for ( ; j>=0, i<=100; i++,j--) //for (;L1: j>=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 控制流类控制流类 语句翻译语句翻译 第第 95 页页1．给出该语句的四元式形式的目标代码结构，．给出该语句的四元式形式的目标代码结构，填入下表填入下表说明：说明：无条件转移操作符用无条件转移操作符用“j”表示；条件成立转表示；条件成立转移的操作符用移的操作符用“jT”表示；条件不成立转移的操作表示；条件不成立转移的操作符用符用“jF”表示 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.3 控制流类控制流类 语句翻译语句翻译Adresscode备注(可有可无) 第第 96 页页2. 给出中间代码生成后对应该段代码填写的下列给出中间代码生成后对应该段代码填写的下列语句标号表内容（按填写标号表的实际语句标号表内容（按填写标号表的实际顺序） 注：设编译器是一遍扫描的编译器注：设编译器是一遍扫描的编译器 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.3 控制流类控制流类 语句翻译语句翻译语句标号语句标号(Li)定义与否标志定义与否标志(1表示已定义，表示已定义，0反之反之)Addr 第第 97 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.3 控制流类控制流类 语句翻译语句翻译一一. 语句标号与拉链返填技术语句标号与拉链返填技术二二.条件语句的翻译条件语句的翻译三三.循环语句的翻译循环语句的翻译 四四. 多分支语句的翻译多分支语句的翻译6.6.3 控制流类语句翻译控制流类语句翻译 第第 98 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.3 控制流类控制流类 语句翻译语句翻译四四. 多分支语句的翻译多分支语句的翻译 A switch (e ) { case c1 : S1 break ; case c2 : S2 break ; …… case cn : Sn break ; default : Sn+1 } 第第 99 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.3 控制流类控制流类 语句翻译语句翻译计算计算e值值e?S1S2Sn……Sn+1L1:L3:L2n-1:L2:L2n-2:next:L2n : 第第 100 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.3 控制流类控制流类 语句翻译语句翻译四四. 多分支语句的翻译多分支语句的翻译 A switch (e ) { case c1 : S1 break ; case c2 : S2 break ; …… case cn : Sn break ; default : Sn+1 } 第第 101 页页 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: L2n-2: …… L2n-1: L2n: next:jT L1jF L2jT L3jF L4…… 第第 102 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.3 控制流类控制流类 语句翻译语句翻译 A switch (e ) { case c1 : S1 break ; case c2 : S2 break ; …… case cn : Sn break ; default : Sn+1 } 第第 103 页页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 L1If e=c2 goto L2If e=cn goto Lngoto Ln+1………… L1: Ln+1: test: next: L2: Ln:测测试试表表 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.3 控制流类语句翻译控制流类语句翻译 第第 104 页页第第 6 章章 语义分析与中间代码生成语义分析与中间代码生成 6.6.1 说明类语句的翻译说明类语句的翻译 6.6.2 赋值语句与表达式翻译赋值语句与表达式翻译 6.6.3 控制流类语句翻译控制流类语句翻译 6.6.4 数组说明与数组元素引用的翻译数组说明与数组元素引用的翻译 6.6.5 过过程、函数程、函数说说明和明和调调用的翻用的翻译译 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译与中间代码生成语句翻译与中间代码生成 第第 105 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.4 数组说明与引用翻译数组说明与引用翻译一一. 数组说明数组说明type A [d1] [d2]… [dn] ；；type A [d1 .. d1'] [d2 .. d2']… [dn .. dn'] ；；数组类型数组类型数组名数组名数组维数、每维大小、数组体积数组维数、每维大小、数组体积n: di个数个数 di的值的值d1*d2*… *dn 第第 106 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.4 数组说明与引用翻译数组说明与引用翻译数组说明的语义处理数组说明的语义处理 填表，登记数组的属性信息。
填表，登记数组的属性信息typenamedimdim_valuevol符号表符号表公共、等长信息公共、等长信息 （符号表）（符号表）与计算数组元素地址与计算数组元素地址有关、不等长信息有关、不等长信息 （信息向量表）（信息向量表） 第第 107 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.4 数组说明与引用翻译数组说明与引用翻译例例6.3设有说明设有说明 int a[2][2]；； float b[4]；；abnamelist b 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 第第 108 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.4 数组说明与引用翻译数组说明与引用翻译二二. 数组元素引用数组元素引用type A [d1] [d2]… [dn] ；； 数组说明数组说明 A [i1] [i2]… [in] 数组引用数组引用 ** 不能整体引用，仅对单一数组元素引用。
不能整体引用，仅对单一数组元素引用Ø 数组元素引用的语义处理数组元素引用的语义处理 语义检查：语义检查： 类型匹配；下标越界检查；类型匹配；下标越界检查； 产生代码：数组元素地址计算的中间代码产生代码：数组元素地址计算的中间代码 第第 109 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.4 数组说明与引用翻译数组说明与引用翻译数组元素地址计算编译时能否完成数组元素地址计算编译时能否完成？？一般不能一般不能 ∵∵ A [i1] [i2]… [in] 中中 ik多为表达式多为表达式 如，如， a[i+j-1][j++] 运行时得到下标值运行时得到下标值涉及数组元素地址计算的有关知识涉及数组元素地址计算的有关知识 第第 110 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.4 数组说明与引用翻译数组说明与引用翻译§ 数组存储方式数组存储方式 (线性连续线性连续)按行存储按行存储按列存储按列存储 例如，例如， int a[2][2];a[1][1]a[1][0]a[0][1]a[0][0] a0按行按行a[1][1]a[0][1]a[1][0]a[0][0] a0按列按列a[0][1]add = a0+1*bytea[0][1]add = a0+2*byte 第第 111 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.4 数组说明与引用翻译数组说明与引用翻译§ 数组元素地址计算数组元素地址计算 据存储方式，通过下述规则计算数组元素位置据存储方式，通过下述规则计算数组元素位置 (顺序号顺序号) + a0§ 对一维数组对一维数组 int a[n]; // 默认下标下界默认下标下界=0 则则 a[i]addr = a0 +( i ) ( 若数组下标下限若数组下标下限=1，则，则a[i] = a0 + ( i-1 ) ) 第第 112 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.4 数组说明与引用翻译数组说明与引用翻译§ 对二维数组对二维数组 int a[n][m] ; 则则 a[i][j]addr = a0 +( i *m + j) 若数组下标下限若数组下标下限=1，则，则 a[i][j]add = a0 +((i-1) *m + ( j-1)) 第第 113 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.4 数组说明与引用翻译数组说明与引用翻译§ 对对n维数组维数组 int a[d1] [d2]… [dn]; 则则 a[i1] [i2] … [in] add = a0 +( i1 *d2*d3 * … *dn + i2 *d3 *d4*… *dn + … + in-1 *dn + in)含含ik,是可变部是可变部分，程序运行分，程序运行时方可知。
时方可知进一步考虑更一般的情况：进一步考虑更一般的情况：若数组下标下限若数组下标下限≠0 第第 114 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.4 数组说明与引用翻译数组说明与引用翻译 则则 a[i1] [i2] … [in] add = a0 +( (i1-1) *d2*d3 * … *dn + (i2 -1) *d3 *d4*… *dn + … + (in-1 -1) *dn + ( in -1) ) = a0 + i1d2d3 … dn + i2d3d4 … dn+…+in-1dn +in – (d2d3 … dn +d3d4 … dn + … +dn+1)V不变不变 C变变换换返回返回若数组下标下限若数组下标下限=1 第第 115 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.4 数组说明与引用翻译数组说明与引用翻译 a[i1] [i2] … [in] add = a0 + i1d2d3 … dn + i2d3d4 … dn+…+in-1dn +in – (d2d3 … dn +d3d4 … dn + … +dn+1)V不变不变 C = a0 – C + V = CUN + Vconspartvarpart编译时计算编译时计算,填填入内情向量表入内情向量表据数元引用情况，产生计算的据数元引用情况，产生计算的中间代码，程序运行时算出。
中间代码，程序运行时算出信息向量表信息向量表 第第 116 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.4 数组说明与引用翻译数组说明与引用翻译§ 数组元素引用目标结构数组元素引用目标结构V.codeV值值 VCUN = a0 – CT = CUN + V计算计算V的中间代码的中间代码计算计算 CUN数组元素地址数组元素地址 T 第第 117 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.4 数组说明与引用翻译数组说明与引用翻译例例6.4 设有说明设有说明 … int a[10][20] … s= a[x][y]；； … …Iarray aaddrtypekindnamenamelist …a0C=(20+1)*4=8410*20=20022010内内情情向向量量表表C的计算的计算V.codeV值值 VCUN = a0 – CT = CUN + V①① t1 = x * 20②② t1 = t1 + y③③ t2 = 4 * t1④④ t3 = a0 – 84 ⑤⑤ t4 = t3[t2] ⑥⑥ s = t4a[x][y]addr•code 第第 118 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.4 数组说明与引用翻译数组说明与引用翻译§ 动态数组？动态数组？ type A [d1] [d2]… [dn] ；； ( di是变量是变量 ) ( 每维大小、体积等信息程序运行时确定每维大小、体积等信息程序运行时确定)§ 动态数组处理动态数组处理 内情向量表在程序运行时建立，编译时仅内情向量表在程序运行时建立，编译时仅分配内情向量表所占存储空间分配内情向量表所占存储空间(据维数据维数)。
在运在运行时，行时， di确定后，确定后，计算体积、计算计算体积、计算C、、为数组为数组分配存储空间分配存储空间且将这些信息登录内情向量表且将这些信息登录内情向量表∴∴ 动态数组动态数组: 产生此部分代码产生此部分代码 + 静态数组元素引用静态数组元素引用 第第 119 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.4 数组说明与引用翻译数组说明与引用翻译§ 动态数组处理目标结构动态数组处理目标结构 取取di 内情向量表内情向量表code 计算体积、计算体积、C的的code 为数组分配存储的为数组分配存储的codeV.codeV值值 VCUN = a0 – CT = CUN + V计算计算V的中间代码的中间代码计算不变部分计算不变部分 CUN数组元素地址数组元素地址 T动态数组说明动态数组说明 第第 120 页页第第 6 章章 语义分析与中间代码生成语义分析与中间代码生成 6.6.1 说明类语句的翻译说明类语句的翻译 6.6.2 赋值语句与表达式翻译赋值语句与表达式翻译 6.6.3 控制流类语句翻译控制流类语句翻译 6.6.4 数组说明与数组元素引用的翻译数组说明与数组元素引用的翻译 6.6.5 过过程、函数程、函数说说明和明和调调用的翻用的翻译译 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译与中间代码生成语句翻译与中间代码生成 第第 121 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.5 函数说明与调用翻译函数说明与调用翻译 函数翻译函数翻译处理说明（定义）处理说明（定义）处理调用处理调用一一. 函数说明的翻译函数说明的翻译1）） 函数及局部量信息登录符号表；函数及局部量信息登录符号表；2）） 记录函数中局部量的作用域记录函数中局部量的作用域(Level)；； 第第 122 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.5 函数说明与调用翻译函数说明与调用翻译例例6.5 设有设有C函数函数 fun1( int a,b) { int c; c=a+b ; return ( c ) }84IVc44I形参形参b04I形参形参aI函数函数fun1addroffsetlentypekindname namelistcode 第第 123 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.5 函数说明与调用翻译函数说明与调用翻译二二. 函数调用的翻译函数调用的翻译G：： S → call id (Elist) Elist → Elist，，E ┃┃ E其中：其中： id: 函数名；函数名； E：： 表达式。
表达式 Elist：：实参表；实参表； 第第 124 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.5 函数说明与调用翻译函数说明与调用翻译§ 函数调用的语义处理：函数调用的语义处理： ① ① 检查所调用的过程或函数是否定义；与检查所调用的过程或函数是否定义；与 所定义的过程或函数的类型、实参与形所定义的过程或函数的类型、实参与形 参的数量、顺序及类型是否一致；参的数量、顺序及类型是否一致； ②② 给被调过程或函数分配活动记录所需给被调过程或函数分配活动记录所需 的存储空间；的存储空间； ③ ③ 传送实参并计算；传送实参并计算； ④④ 加载调用结果和返回地址，恢复主调加载调用结果和返回地址，恢复主调 用过程或函数的继续执行；用过程或函数的继续执行； ⑤ ⑤ 转向相应的过程或函数转向相应的过程或函数。
第第 125 页页 Ch6 语义分析与中间代码生成语义分析与中间代码生成 6.6 语句翻译语句翻译 6.6.5 函数说明与调用翻译函数说明与调用翻译§ 函数调用返回的语义处理函数调用返回的语义处理 ① ① 返回一个或多个结果值存于指定位置；返回一个或多个结果值存于指定位置； ②② 恢复调用过程的活动记录；恢复调用过程的活动记录； ③③ 生成一条转移指令（返回）；生成一条转移指令（返回）； 第第 126 页页语义分析与中间代码生成总结语义分析与中间代码生成总结 语语 义义分分 析析L2L2中间代码中间代码根据语义进行语义检查和代码生成根据语义进行语义检查和代码生成对对L2扫描的顺序性；产生的代码执行的线性性；扫描的顺序性；产生的代码执行的线性性；语义映射的准确性；语义映射的准确性； 第第 127 页页 说明性语句说明性语句登录编译信息、为可执登录编译信息、为可执行语句提供语义检查和行语句提供语义检查和语句翻译的信息依据。
语句翻译的信息依据可执行语句可执行语句 目标代目标代 码结构码结构 中间代码中间代码语义动作语义动作动态语义动态语义设计设计映射映射语义分析与中间代码生成语义分析与中间代码生成 第第 128 页页第第 六六 章章 结结 束束 第第 129 页页(1)给定文法给定文法G：：E→E+T|T T→T*F|F F→i|(E)则则L(G)中的一个句子中的一个句子i+i+(i*i)*i的逆波兰表示为的逆波兰表示为_____ A) iii*i++ B) ii+iii**+ C) ii+ii*i*+ D) A、、B、、C都不正确都不正确(2) 中间代码生成时所依据的是中间代码生成时所依据的是____________ A）语法规则）语法规则 B）词法规则）词法规则 C）语义规则）语义规则 D）等价变换规则）等价变换规则(3)在编译程序中与生成中间代码的目的无关的是在编译程序中与生成中间代码的目的无关的是___。
A)便于代码优化便于代码优化 B)便于存储空间的组织便于存储空间的组织 C)便于移植便于移植 D)便于生成目标代码便于生成目标代码 第第 130 页页(4)在语法制导翻译中不采用拉链在语法制导翻译中不采用拉链-返填技术的返填技术的 语句是语句是_________ A）转向语句）转向语句 B）赋值语句）赋值语句 C）条件语句）条件语句 D）循环语句）循环语句判断正误判断正误(1)使用语法制导翻译方法的编译程序能同时进行语法使用语法制导翻译方法的编译程序能同时进行语法 分析和语义分析分析和语义分析2)返填就是稍后填写转移指令的地址返填就是稍后填写转移指令的地址3)对任何一个编译程序对任何一个编译程序,产生中间代码是不可缺少的产生中间代码是不可缺少的4)三元式同间接三元式是等价的三元式同间接三元式是等价的5)语法制导翻译方法可用来产生各种中间代码，又可语法制导翻译方法可用来产生各种中间代码，又可 用来产生目标代码。
