第八章第八章 语法制导翻译语法制导翻译和中间代码生成和中间代码生成教学目的教学目的：让学生了解语法制导翻译：让学生了解语法制导翻译的基本思想，掌握中间代码的几种常用的基本思想，掌握中间代码的几种常用形式及表达式与基本语句的翻译方法。形式及表达式与基本语句的翻译方法。教学重点教学重点：中间代码形式、布尔表达：中间代码形式、布尔表达式与赋值、控制语句的翻译。式与赋值、控制语句的翻译。课时分配课时分配：4 学时。学时。教学过程教学过程：7/29/202418.1 8.1 语法制导翻译概述语法制导翻译概述1 1、语法制导翻译的概念、语法制导翻译的概念 在语法分析过程中根据各个规则所相在语法分析过程中根据各个规则所相联的语义动作或所对应的语义子程序进行联的语义动作或所对应的语义子程序进行翻译的办法。翻译的办法。2 2、要求、要求 语法结构具有规定的语义。语法结构具有规定的语义。3 3、本质、本质 在进行语法分析的同时，完成相应的在进行语法分析的同时，完成相应的语义处理，关键是语义处理，关键是如何根据被识别出的语如何根据被识别出的语法成分进行语义处理。法成分进行语义处理。7/29/202424 4、语义分析的任务、语义分析的任务1 1）静态语义检查）静态语义检查例：类型、运算、维数、越界例：类型、运算、维数、越界例：类型、运算、维数、越界例：类型、运算、维数、越界a+b-1*truea+b-1*truea+b-1*truea+b-1*true2 2）动态语义处理（真正的翻译）动态语义处理（真正的翻译）例：变量的存储分配例：变量的存储分配例：变量的存储分配例：变量的存储分配例：表达式的求值例：表达式的求值例：表达式的求值例：表达式的求值例：语句的翻译（中间代码的生成）例：语句的翻译（中间代码的生成）例：语句的翻译（中间代码的生成）例：语句的翻译（中间代码的生成）总目标：总目标：生成等价的中间代码生成等价的中间代码/ /目标代码目标代码7/29/202435、处理方法、处理方法 1）对应每一个文法规则编制一个语义子对应每一个文法规则编制一个语义子程序，当一个规则获得匹配时，调用相程序，当一个规则获得匹配时，调用相应的语义子程序实现语义检查与翻译。应的语义子程序实现语义检查与翻译。2）在文法规则的右部适当位置，插入相应在文法规则的右部适当位置，插入相应的语义动作，按照分析的进程，执行遇的语义动作，按照分析的进程，执行遇到的语义动作。到的语义动作。注意注意：语义：语义可以看成是相应文法符号可以看成是相应文法符号的属性。的属性。7/29/202446、语法制导翻译的具体实现途径、语法制导翻译的具体实现途径 使用使用LR分析器实现：分析器实现：通过对符号栈通过对符号栈加上语义，扩充加上语义，扩充LR分析器的分析能力，使分析器的分析能力，使它在用某个文法规则进行归约的同时，调它在用某个文法规则进行归约的同时，调用相应的语义子程序或产生某种中间代码用相应的语义子程序或产生某种中间代码形式。形式。7/29/202458.2 8.2 属性文法属性文法1 1、现代编译系统多采用现代编译系统多采用语法制导翻译方法语法制导翻译方法，该，该方法使用属性文法为工具来说明程序设计语方法使用属性文法为工具来说明程序设计语言的语义。言的语义。2 2、属性文法是属性文法是KnuthKnuth在在19681968年提出的。年提出的。3 3、属性属性文法文法的特点的特点1 1）是）是一种接近形式化的语义描述方法；一种接近形式化的语义描述方法；2 2）每个语法符号有相应的）每个语法符号有相应的属性符号；属性符号；3 3）每个文法规则都有相应的计算属性的规）每个文法规则都有相应的计算属性的规则：则：属性变量属性变量= =属性表达式属性表达式7/29/20246一、属性文法举例一、属性文法举例规则规则 属性属性( (计算计算) )规则规则/ /语义规则语义规则E EE E1 1 + E + E2 2 E.val := E E.val := E1 1.val + E.val + E2 2.val.valE EE E1 1 * E * E2 2 E.val := E E.val := E1 1.val * E.val * E2 2.val.valE (EE (E1 1) ) E.val := E E.val := E1 1.val.valE idE id E.val := id E.val := id .val.val7/29/20247二、属性文法的定义二、属性文法的定义1 1、定义为三、定义为三元组元组（，（，）。）。 其中：是其中：是其中：是其中：是上下文无关上下文无关上下文无关上下文无关文法；是属性文法；是属性文法；是属性文法；是属性的有穷的有穷的有穷的有穷集；是关于集；是关于集；是关于集；是关于属性的属性的属性的属性的谓词谓词谓词谓词/ / / /断言，充当计算规断言，充当计算规断言，充当计算规断言，充当计算规则。则。则。则。说明：说明：说明：说明：任何布尔表达式都是谓词。任何布尔表达式都是谓词。任何布尔表达式都是谓词。任何布尔表达式都是谓词。2 2、属性、属性( (语义信息语义信息) )与终结符或非与终结符或非终结符终结符相相联；谓词与文法规则相联。联；谓词与文法规则相联。3 3、静态语义审查即、静态语义审查即验证关于所编译源程序验证关于所编译源程序的谓词是否全为真的谓词是否全为真。可用。可用带语义信息结点带语义信息结点的语法树的语法树来表示与输入串对应语法树的静来表示与输入串对应语法树的静态语义审查。态语义审查。7/29/20248三、用法三、用法1、根据文法符号的语义根据文法符号的语义，为文法符号设，为文法符号设置置属性。属性。2、为为每个每个文法规则设置文法规则设置语义语义规则（用于规则（用于描述描述各属性的各属性的关系关系计算规则）计算规则）3、两种使用形式：两种使用形式：用于语法用于语法制导制导定义定义：语义的抽象：语义的抽象说明。说明。用于翻译用于翻译模式的定义模式的定义：规定实现：规定实现方法方法(计算次序计算次序)。7/29/20249例例1 1：计算器的设计：计算器的设计对下列文法：对下列文法：L E L E E EE E1 1 + T | T + T | T T TT T1 1 * F | F * F | FF ( E ) | digitF ( E ) | digit用属性文法描述语法制导的翻译过用属性文法描述语法制导的翻译过程如下：程如下：7/29/202410L E print( E.val )L E print( E.val )（虚属性）虚属性）E EE E1 1 + T E.val := E + T E.val := E1 1.val + T.val.val + T.valE T E.val := T.valE T E.val := T.valT TT T1 1 * F T.val := T * F T.val := T1 1.val * F.val.val * F.valT F T.val := F.valT F T.val := F.valF ( E ) F.val := E.valF ( E ) F.val := E.valF digit F.val := F digit F.val := digit.lexvaldigit.lexval其中其中：lexvallexval 是单词是单词 digit digit 的属性的属性7/29/202411例例2 2：说明语句的设计说明语句的设计说明语句的文法说明语句的文法D T LD T LT intT intT real T real L LL L1 1,id,idL idL id1 1、要解决的问题：、要解决的问题：1 1）记录标识符的类型；）记录标识符的类型；2 2）类型信息的传递。）类型信息的传递。7/29/2024122 2、说明语句类型信息传递的实现、说明语句类型信息传递的实现1 1）方法）方法 编写说明语句的文法，将类型信息作编写说明语句的文法，将类型信息作为为类型描述类型描述 T T 的的属性属性 type type 和和变量表变量表 L L 的的属性属性 inin。2 2）目的目的 分析说明语句分析说明语句 D D，为变量指定类型。为变量指定类型。7/29/2024133 3、属性文法的属性文法的实现实现D T L L.in := T.typeD T L L.in := T.typeT int T.type := integerT int T.type := integerT real T.type := realT real T.type := realL LL L1 1,id L,id L1 1.in := L.in.in := L.in addtype( id.entry, L.in ) addtype( id.entry, L.in )L id addtype( id.entry, L.in )L id addtype( id.entry, L.in )其中：其中：entry entry 为为单词单词 id id 的的属性属性；addtypeaddtype 表示在符号表中为变量填加类型信息；表示在符号表中为变量填加类型信息；7/29/202414四、属性分类四、属性分类1 1、综合属性、综合属性 设设 AXAX1 1X X2 2XnXn 为为一个文法规则，则一个文法规则，则A.s=fA.s=f(c(c1 1,c,c2 2,c,ck k) )中，中，c c1 1,c,c2 2,c,ck k表示表示X X1 1，X X2 2，XnXn的属性。而的属性。而A.sA.s是从其右部符号是从其右部符号的属性值计算出来的，如：例中的的属性值计算出来的，如：例中的 E.valE.val、T.typeT.type。即即左部非终结符的属性值的计算左部非终结符的属性值的计算来自其规则右部非终结符来自其规则右部非终结符。 这种属性叫做综合属性这种属性叫做综合属性。 适应范围：适应范围：归约分析归约分析。7/29/2024152 2、继承属性、继承属性 设设AXAX1 1X X2 2XnXn为一个文法规则，则为一个文法规则，则B.in=f(cB.in=f(c1 1,c,c2 2,c,ck k) )中，中，B B即即X Xi i，而，而c c1 1,c,c2 2,c,ck k是是A, XA, X1 1，X X2 2，X Xi-1i-1的属的属性。如：例中性。如：例中 L.inL.in 这种属性叫做继承这种属性叫做继承(Inherited)(Inherited)属性。属性。7/29/2024163 3、固有属性、固有属性 语言中的单词，如标识符、常数语言中的单词，如标识符、常数（数值的、符号的）、常量，它们的（数值的、符号的）、常量，它们的属性是用户给定的、不变的。属性是用户给定的、不变的。 这种属性称为固有这种属性称为固有(Inherent)(Inherent)属性属性（单词属性）。（单词属性）。7/29/202417五、属性的计算五、属性的计算1、综合属性、综合属性 自底向上自底向上按照语义规则来计算各结按照语义规则来计算各结点的综合属性值。点的综合属性值。2 2、继承属性、继承属性 根据依赖关系决定计算顺序（根据依赖关系决定计算顺序（可以可以是依赖图的任意一个拓扑排序是依赖图的任意一个拓扑排序）。）。3 3、固有属性、固有属性 在词法分析时计算，此处不考虑。在词法分析时计算，此处不考虑。7/29/202418例：例：3*5+4 3*5+4 的分析的分析树与属性计算。树与属性计算。7/29/2024191 1、即、即S-attributed DefinitionS-attributed Definition（ S-attributed Grammar S-attributed Grammar ）。）。2 2、只包含综合属性的语法制导定只包含综合属性的语法制导定义。义。3 3、例如、例如：算术表达式求值的属性：算术表达式求值的属性文法。文法。六、六、- -属性定义属性定义(S-(S-属性文法属性文法) ) 7/29/2024201 1、即即L-attributed L-attributed DefinitionDefinition（L-attributed L-attributed GrammarGrammar）。）。2 2、包含综合属性和继承属性的语包含综合属性和继承属性的语法制导定义。法制导定义。3 3、例如：算术表达式求值的属性、例如：算术表达式求值的属性文法、说明语句的属性文法。文法、说明语句的属性文法。七、七、L-L-属性定义属性定义(L-(L-属性文法属性文法) ) 7/29/2024214 4、其、其属性可用属性可用深度优先的顺序深度优先的顺序从左至从左至右右计算。计算。5 5、对于、对于所有所有 1 1 2 2 n n，其其中中i i 属性计算属性计算仅使用仅使用1 1、2 2、i-1i-1 的的属性和的继承属性。属性和的继承属性。6 6、S-S-属性文法属于属性文法属于L-L-属性文法。属性文法。7/29/202422八、翻译模式八、翻译模式(Translation (Translation Scheme)Scheme)1 1、特征、特征1 1）规定在语法分析中使用语义规则进行计）规定在语法分析中使用语义规则进行计算的次序；算的次序；2 2）保证当动作使用某属性时，该属性必须）保证当动作使用某属性时，该属性必须是可用的；是可用的；2 2、实现方法、实现方法将语义动作插入到文法规则的某个位置。将语义动作插入到文法规则的某个位置。7/29/202423例：建立说明语句的翻译方案例：建立说明语句的翻译方案语法制导定义：语法制导定义：D T LD T LL.in := T.typeL.in := T.typeT intT intT.type := integerT.type := integerT realT realT.type := realT.type := realL LL L1 1 ,id,idL L1 1.in := L.in.in := L.inaddtype(id.entry, L.in)addtype(id.entry, L.in)L idL idaddtype(id.entry, L.in)addtype(id.entry, L.in)上述动作的执行时，按照自顶向下分析法上述动作的执行时，按照自顶向下分析法进行推导。进行推导。7/29/202424九、翻译模式的设计九、翻译模式的设计方法：方法：将将语义动作语义动作中继承属性的计算前中继承属性的计算前移，使移，使它出现它出现在其在其相应文法相应文法符号符号之前。之前。D T L.in := T.type LD T L.in := T.type LT int T.type := integer T int T.type := integer T real T.type := real T real T.type := real L LL L1 1.in := L.in .in := L.in L L1 1 , id addtype(id.entry, L.in) , id addtype(id.entry, L.in) L id addtype(id.entry, L.in) L id addtype(id.entry, L.in) 7/29/2024258.3 8.3 中间代码中间代码1 1、源程序、源程序经过语义分析被译成中间代码经过语义分析被译成中间代码序列（中间序列（中间语言的语句语言的语句）；）；2 2、用、用中间语言过渡的好处：中间语言过渡的好处：便于编译系统的实现、移植、代码便于编译系统的实现、移植、代码便于编译系统的实现、移植、代码便于编译系统的实现、移植、代码优化。优化。优化。优化。7/29/2024263、常用的中间代码、常用的中间代码(语言语言)1 1）三）三）三）三地址地址地址地址代码代码代码代码 四四四四元元元元式式式式( (编译系统中普遍采用编译系统中普遍采用编译系统中普遍采用编译系统中普遍采用) ) 用四元组（算符，操作数用四元组（算符，操作数用四元组（算符，操作数用四元组（算符，操作数1 1 ，操作数，操作数，操作数，操作数2 2，结果）或用，结果）或用，结果）或用，结果）或用简单赋值形式表示。对中间结果通过简单赋值形式表示。对中间结果通过简单赋值形式表示。对中间结果通过简单赋值形式表示。对中间结果通过给定的名字给定的名字给定的名字给定的名字显显显显式引用。式引用。式引用。式引用。2 2）语法）语法）语法）语法( (结构结构结构结构) )树树树树 三三三三元元元元式式式式 用三元组（算符，操作数用三元组（算符，操作数用三元组（算符，操作数用三元组（算符，操作数1 1 ，操作数，操作数，操作数，操作数2 2）表示，对中）表示，对中）表示，对中）表示，对中间结果可通过间结果可通过间结果可通过间结果可通过三元式编号三元式编号三元式编号三元式编号显式引用。显式引用。显式引用。显式引用。3 3） 后缀式后缀式后缀式后缀式逆波兰表示逆波兰表示逆波兰表示逆波兰表示( (用栈实现用栈实现用栈实现用栈实现) ) 注意：操作数注意：操作数注意：操作数注意：操作数2 2缺省时用缺省时用缺省时用缺省时用下划线下划线下划线下划线表示。表示。表示。表示。7/29/2024274 4、特点：、特点：形式简单、语义明确、便于翻译，形式简单、语义明确、便于翻译，独立于目标语言。独立于目标语言。例例 ：表达式：表达式 (A - 12) * B + 6 的语法结构树。的语法结构树。7/29/202428例：将赋值语句变换为例：将赋值语句变换为语法结构树语法结构树1 1）属性设置：）属性设置：E.p E.p E.p E.p 是语法结构树是语法结构树是语法结构树是语法结构树指针；指针；指针；指针；id.entry id.entry id.entry id.entry 是名字的表项是名字的表项是名字的表项是名字的表项入口；入口；入口；入口；num.val num.val num.val num.val 是是是是数值；数值；数值；数值；2）基本函数）基本函数结点构造结点构造mknode mknode 建中间建中间建中间建中间结点；结点；结点；结点；mkleaf mkleaf 建叶结点建叶结点建叶结点建叶结点；7/29/2024293 3）其语法制导定义）其语法制导定义( (属性文法属性文法) )7/29/202430例：例：a := b * (- c) + b * (- 34) a := b * (- c) + b * (- 34) 的语法结构树的语法结构树:=*-0+*-0idbnum 34idbidcidaroot7/29/202431例：表达式例：表达式 a:=b*(-c)+b/(-d) a:=b*(-c)+b/(-d) 的中间代码的中间代码表表示。示。2 2）三元式：）三元式： (- , c , _ )(- , c , _ ) (* , b , ) (* , b , ) (- , d , _ ) (- , d , _ ) (/ , b , ) (/ , b , ) (+ , , ) (+ , , ) (:= , ,a ) (:= , ,a )3 3）四元式）四元式: : (- , c , _ ,t1) (- , c , _ ,t1) (* , b ,t1 ,t2) (* , b ,t1 ,t2) (- , d , _ ,t3) (- , d , _ ,t3) (/ , b ,t3 ,t4) (/ , b ,t3 ,t4) (+ ,t2 ,t4 ,t5) (+ ,t2 ,t4 ,t5) (:= ,t5 ,_ , a) (:= ,t5 ,_ , a)1） 逆波兰式：逆波兰式： abcabc-*-*bdbd-/+:=-/+:=7/29/2024325 5、生成后缀式的属性文法、生成后缀式的属性文法注释：注释：注释：注释： | | | | 表示代码序列的连接表示代码序列的连接表示代码序列的连接表示代码序列的连接7/29/2024336 6、三地址代码、三地址代码 1 1）形式：）形式：一般一般/ /直观形式直观形式 x := y op zx := y op z 四元式形式四元式形式（op, y, z, xop, y, z, x） 其中其中 x, y, z x, y, z 为变量名、常数或编译产为变量名、常数或编译产生的临时生的临时变量。变量。2 2）种类：）种类：x := y op z x := y op z 双目运算双目运算 x := op y x := op y 单目运算单目运算 x := yx := y 复制语句复制语句if x if x reloprelop y y gotogoto l l 条件转移语句条件转移语句7/29/2024343 3）其它语句的三地址代码）其它语句的三地址代码 goto l goto l goto l goto l 无条件转移无条件转移无条件转移无条件转移 paramparamparamparam x x x x 实在参数实在参数实在参数实在参数 call p, n call p, n call p, n call p, n 过程调用过程调用过程调用过程调用 return x return x return x return x 过程返回过程返回过程返回过程返回 x := yix := yix := yix := yi 数组运算数组运算数组运算数组运算 xi := yxi := yxi := yxi := y x := &y x := &y x := &y x := &y 指针运算指针运算指针运算指针运算 x := *yx := *yx := *yx := *y *x = y *x = y *x = y *x = y 7/29/2024358.48.4 赋值语句的翻译赋值语句的翻译一、翻译的需求一、翻译的需求 1、充分了解各种语言现象的语义，包、充分了解各种语言现象的语义，包括：控制结构、数据结构、单词；括：控制结构、数据结构、单词；2、充分了解它们的实现方法；、充分了解它们的实现方法； 3、了解目标语言的语义；、了解目标语言的语义；4、了解中间代码的语义；、了解中间代码的语义；5、了解运行环境。、了解运行环境。7/29/202436二、实现赋值语句的翻译二、实现赋值语句的翻译1 1、基本子程序、基本子程序产生一条中间代码产生一条中间代码 gen(code)gen(code)产生新的临时变量产生新的临时变量 newtempnewtemp2 2、属性属性设置设置中间代码序列中间代码序列 codecode存储位置存储位置 placeplace7/29/202437三、赋值语句的四元式翻译三、赋值语句的四元式翻译S id := E S.code := E.code | gen( id.place:=E.place ) E E1 + E2 E.place := newtemp; E.code := E1.code | E2.code | gen(E.place:=E1.place+E2.place)E E1 * E2 E.place := newtemp; E.code := E1.code | E2.code | gen(E.place:=E1.place*E2.place) E - E1 E.place := newtemp; E.code := E1.code | gen(E.place:=0-E1.place) 7/29/202438注释注释注释注释：1 1 1 1）| | | | 表示代码序列的表示代码序列的表示代码序列的表示代码序列的连接；连接；连接；连接；2 2 2 2）语义过程）语义过程）语义过程）语义过程newtempnewtempnewtempnewtemp表示生成一个临时变量；表示生成一个临时变量；表示生成一个临时变量；表示生成一个临时变量；3 3 3 3）E.placeE.placeE.placeE.place表示存放表示存放表示存放表示存放E E E E值的变量名在符号表中的登录项值的变量名在符号表中的登录项值的变量名在符号表中的登录项值的变量名在符号表中的登录项或一个整数码；或一个整数码；或一个整数码；或一个整数码；4 4 4 4）语义过程）语义过程）语义过程）语义过程gengengengen表示生成四元式序列到输出文件（中表示生成四元式序列到输出文件（中表示生成四元式序列到输出文件（中表示生成四元式序列到输出文件（中间代码）。间代码）。间代码）。间代码）。E ( E1 ) E.place:= E1.place; E.code:= E1.code E id E.place:= id.place; E.code:= E num E.place:= num.val；E.code:= 7/29/202439例：例： 翻译翻译 a:= -c+b*34a:= -c+b*34 7/29/202440a:= -c+b*34a:= -c+b*34的中间代码的中间代码t2:=0 ct3:=b*34t1:=t2+t3a:=t17/29/202441四、表达式翻译中的其它问题四、表达式翻译中的其它问题1、运算、运算合法性检查合法性检查利用符号表保存的名字类型利用符号表保存的名字类型进行。进行。2、类型、类型自动转换自动转换 添加专用指令；通过加入添加专用指令；通过加入if语句进行类语句进行类型的判别和转换。参见教材型的判别和转换。参见教材p163的类型转的类型转换语义处理例子。换语义处理例子。3、临时、临时变量空间的统计变量空间的统计了解了解空间需求空间需求、及时、及时释放。释放。7/29/2024428.5 8.5 控制语句的翻译控制语句的翻译一、高级一、高级语言的控制结构语言的控制结构顺序顺序 begin begin 语句语句; ; 语句；语句； end end条件条件 if_then_elseif_then_else； if_thenif_then； switch switch case case循环循环 while_dowhile_do； do_whiledo_while； forfor；repeat_untilrepeat_until。二、三二、三地址代码的控制结构地址代码的控制结构goto label;goto label;if x if x reloprelop( (关系符）关系符） y goto label;y goto label;7/29/202443S while C do S1 的翻译的翻译属性设置（继承）属性设置（继承）布尔式布尔式 C（入口）入口）代码段代码段代码段代码段真出口真出口真出口真出口 true true 代码段假出口代码段假出口代码段假出口代码段假出口 falsefalse语句语句 S 、 S 1 1 代码段的入口代码段的入口代码段的入口代码段的入口 beginbegin后续段入口后续段入口后续段入口后续段入口 nextnextS.begin= S1.next S.begin= S1.next 7/29/202444三、循环语句的属性文法三、循环语句的属性文法 Swhile C do SSwhile C do S1 1 C.false := S.next; C.false := S.next; S.begin := S S.begin := S1 1.next := newlabel;.next := newlabel; C.true := S C.true := S1 1.begin := newlabel;.begin := newlabel; S.code := gen( S.begin: ) | C.code | S.code := gen( S.begin: ) | C.code | gengen( C.true: ) | S( C.true: ) | S1 1.code |.code | gengen( gotoS.begin )( gotoS.begin )语义过程：语义过程：语义过程：语义过程：新标号的产生新标号的产生 newlabel7/29/202445S if C then S1else S2 的翻译的翻译代码序列代码序列C CS1 S1 S2S2属性关系属性关系S1.begin = C.trueS1.begin = C.trueS2.begin = C.falseS2.begin = C.falseS1.next = S2.next = S.nextS1.next = S2.next = S.next7/29/202446四、条件语句的属性文法四、条件语句的属性文法S if C then SS if C then S1 1 C.true := newlabel; C.true := newlabel; else S else S2 2 C.false := newlabel;C.false := newlabel;S S1 1.next := S.next := S2 2.next := S.next;.next := S.next; S.code := C.code | gen( C.true: ) |S.code := C.code | gen( C.true: ) | S S1 1.code | gen( goto S.next ) |.code | gen( goto S.next ) | gen( C.false: ) | Sgen( C.false: ) | S2 2.code.code7/29/202447五、简单布尔表达式的翻译五、简单布尔表达式的翻译C EC E1 1 reloprelop E E2 2 C.code := EC.code := E1 1.code | E.code | E2. 2.code code | gen( if E | gen( if E1 1.place .place relop.oprelop.op E E2 2.place .place gotoC.true ) gotoC.true ) | gen( gotoC.false ) | gen( gotoC.false )7/29/202448例例1 1：翻译下列：翻译下列ifthenelseifthenelse语句语句if if abab or or cdcfef then s1 else s2 then s1 else s2上例生成的三地址代码上例生成的三地址代码/ /四元式序列如下：四元式序列如下：(1) if a b goto (7)(1) if a b goto (7)(2) (2) gotogoto (3) (3)(3) if c d goto (5)(3) if c f (5) if e f gotogoto (7) (7)(6) (6) gotogoto (p+1) (p+1)(7) s1(7) s1对应的四元式序列对应的四元式序列 (p) (p) gotogoto (q) (q)(p+1) s2(p+1) s2对应的四元式序列对应的四元式序列 (q)(q)四元式标号采用回填技术四元式标号采用回填技术7/29/202450例例2 2：翻译下列：翻译下列whilewhile语句语句while while a ba b do doC C if if c 5c y do z := x + 1; while x y do z := x + 1; else else S S1212 x := y x := yS17/29/202451上例生成的三地址代码上例生成的三地址代码/ /四元式序列四元式序列(1) if a b goto (2)(1) if a b goto (2)(1) if a b goto (2)(1) if a b goto (2) goto goto goto goto LnextLnextLnextLnext(2) if c 5 goto (3)(2) if c 5 goto (3)(2) if c 5 goto (3)(2) if c y goto (4)(3) if x y goto (4)(3) if x y goto (4)(3) if x y goto (4) goto (1) goto (1) goto (1) goto (1)(4) t1 := x + 1(4) t1 := x + 1(4) t1 := x + 1(4) t1 := x + 1z := t1z := t1z := t1z := t1 goto (3) goto (3) goto (3) goto (3)(5) x := y(5) x := y(5) x := y(5) x := y goto (1) goto (1) goto (1) goto (1)LnextLnextLnextLnext: : : :C.codeC1.codeS11.codeS12.codeS1.code标号采用回填技术标号采用回填技术7/29/202452六、开关语句、六、开关语句、forfor语句、出口语句过语句、出口语句过程调用语句的翻译程调用语句的翻译 其核心是其核心是控制转移控制转移的翻译，的翻译，结合循环和布尔表达式的翻译结合循环和布尔表达式的翻译的考虑，具体实现略。的考虑，具体实现略。参见教参见教材材P171-178。7/29/202453七、控制结构翻译中的其他问题七、控制结构翻译中的其他问题1 1、分层结构的记录、分层结构的记录涉及变量的作用域。涉及变量的作用域。2 2、转移目标的先引用后定义、转移目标的先引用后定义使用使用回填技术；回填技术；涉及循环语句、条件语句、转移标号；涉及循环语句、条件语句、转移标号；7/29/2024548.6 8.6 数组和结构的翻译数组和结构的翻译一、数组的翻译一、数组的翻译 例：例：A为为 10 *20 数组，令数组，令d1=10, d2=20, 将数将数组赋值语句组赋值语句 X=A I , J 翻译成四元式序列。翻译成四元式序列。(*,I,20,T1)(*,I,20,T1)(+,J,t1,T1)(+,J,t1,T1)(-,A,21,T2)(-,A,21,T2)(=,T2T1,_,T3)(=,T2T1,_,T3)/* /* /* /* T3:=T2T1 T3:=T2T1 T3:=T2T1 T3:=T2T1 */*/*/*/(:=,T3,_ ,X)(:=,T3,_ ,X)解解：1、先计算、先计算A I , J A I , J 地址：地址：A+(I-1)*20+(J-1)=(A-21)+(20*I+J)2、根据所求地址译成根据所求地址译成四元式序列如右：四元式序列如右：7/29/202455二、结构说明和引用翻译二、结构说明和引用翻译 1、同数组的翻译一样，关键是计算各分、同数组的翻译一样，关键是计算各分量的地址量的地址; 2、一般编译时，将几个分量的结构按以、一般编译时，将几个分量的结构按以下形式登记在一张独立的表中：下形式登记在一张独立的表中： 由于各分量信息，如名字、类型、长度在由于各分量信息，如名字、类型、长度在编译时已知，故易确定各分量地址编译时已知，故易确定各分量地址。分量分量1分量分量2分量分量n7/29/2024568.7 8.7 属性文法的实现属性文法的实现一、分析一、分析1 1、将属性看成文法符号；、将属性看成文法符号；、将属性看成文法符号；、将属性看成文法符号；2 2、实现内容局限于文法规则。、实现内容局限于文法规则。、实现内容局限于文法规则。、实现内容局限于文法规则。二、递归子程序的改进二、递归子程序的改进1 1、为每个文法符号设置结构或对象（类、为每个文法符号设置结构或对象（类、为每个文法符号设置结构或对象（类、为每个文法符号设置结构或对象（类以每个属性为分量）；以每个属性为分量）；以每个属性为分量）；以每个属性为分量）；2 2、每个函数设置一个结构（或对象类）指针。、每个函数设置一个结构（或对象类）指针。、每个函数设置一个结构（或对象类）指针。、每个函数设置一个结构（或对象类）指针。7/29/202457