编译原理第5章

《编译原理第5章》由会员分享，可在线阅读，更多相关《编译原理第5章（122页珍藏版）》请在金锄头文库上搜索。

1、第第5 5章章 语法制导翻译技术和中间代语法制导翻译技术和中间代码生成码生成 编译程序将高级语言所写的源程序翻译成等价的机器语言或汇编语言的目标程序,首先进行词法分析，得到单词符号序列，再进行语法分析，得到各类语法成份（或语法单位），接着，将进行语义分析。 第第5 5章章 语法制导翻译技术和中间代语法制导翻译技术和中间代码生成码生成本章主要介绍：语法制导翻译法的基本思想 常见的几种中间代码的形式 各种不同语法结构的语法制 导翻译技术 5.1 概述语义分析的任务：静态语义审查静态语义审查 审查每个语法结构的静态语义审查每个语法结构的静态语义,即验证语法结构合法的程序即验证语法结构合法的程序,是否

2、是否真正有意义真正有意义。5.1 概述例如:表达式 A+B*C对运算对象进行类型检查, 对变量进行先定义后使用检查 如果静态语义正确, 语义处理则要执行真正的翻译, 即生成程序的某种中间代码的形式或直接生成目标代码。执行真正的翻译执行真正的翻译5.1 概述 目前多数编译程序进行语义分析的方法是采用语法制导翻译法采用语法制导翻译法 。它不是一种形式系统, 但它比较接近形式化。 语法制导翻译法使用属性文法为工具来描述程序设计语言的语义。5.2 属性文法(1) 属性 对文法的每一个符号, 引进一些属性, 这些属性代表与文法符号相关的信息, 如类型、值、存储位置等。与属性相关的信息, 即属性值,可以在

3、语法分析过程中计算和传递。1. 属性文法5.2 属性文法属性分为两类:综合属性其计算规则按“自下而上”方式进行, 即规则左部符号的某些属性根据其右部符号的属性和(或)自己的其他属性计算而得。属性加工的过程即是语义的处理过程。属性加工的过程即是语义的处理过程。综合属性和继承属性。5.2 属性文法继承属性其计算规则按“自上而下”方式进行, 即规则右部符号的某些属性根据其左部符号的属性和(或)右部其他符号的某些属性计算而得。5.2 属性文法(2) 属性文法 为文法的每一个规则配备的计算属性的计算规则, 称为语义规则(描述语义处理的加工动作) 。 属性文法包含一个上下文无关文法和一系列语义规则。语义规

4、则:5.2 属性文法 这些语义规则附在文法的每个产生式上,在语法分析过程中, 执行语义规则描述的动作, 从而实现语义处理。也就是说, 附在文法的每个产生式上语义规则描述了语义处理的加工动作。 目前流行的语义描述和语义处理的方法主要是属性文法和语法制导翻译方法。5.3 语法制导翻译概述语法制导翻译法的基本思想语法制导翻译法的基本思想 为文法的每个产生式都配备一个语义动作或语义子程序。 在语法分析的过程中，每当使用一条产生式进行推导或归约时，就执行相应产生式的语义动作, 从而实现语义处理。5.3 语法制导翻译概述S Axy a1 a2 a3 ai ai+1 an语义处理的加工动作 语法制导翻译法使

5、用属性文法为工具来说明程序设计语言的语义。5.3 语法制导翻译概述(语义子程序语义子程序) 描述了一个产生式所对应的翻译工作描述了一个产生式所对应的翻译工作。 产生式只能产生符号串,并没有指明所产生符号串的意义,仅仅是一些符号串的集合。语义动作语义动作5.3 语法制导翻译概述 语义动作不仅指明了该产生式所产生符号串的意义，而且还根据这种意义规定了对应的加工动作（如查填各类表格、改变编译程序的某些变量的值、打印各种错误信息及生成中间代码等），从而完成预定的翻译工作。 5.3 语法制导翻译概述语法制导翻译法语法制导翻译法 在语法分析过程中，依随分析的过程，根据每个产生式所对应的语义子程序(或语义规

6、则描述的语义处理的加工动作)进行翻译的方法。 为文法每一产生式设计相应的求值的语义描述(语义动作)： 5.3 语法制导翻译概述例如，设有简单算术表达式的文法： EEE | E*E | (E) | digit1.E E(1)E(2) E.val E(1).val E(2).val 2.E E(1)*E(2) E.val E(1).val*E(2).val 3.E (E(1) E.val E(1).val 4.E digit E.val Lex.digit 7+8*5,3+8,6*5,5.3 语法制导翻译概述E.val = 47E.val = 8E.val = 40E.val = 7E.val =

7、 5+5*871.E E(1)E(2) E.val E(1).val E(2).val 2.E E(1)*E(2) E.val E(1).val*E(2).val 3.E (E(1) E.val E(1).val 4.E digit E.val Lex.digit 句子 7+8*5 EEEEE5.3 语法制导翻译概述语法制导翻译技术分为： 自底向上语法制导翻译 自顶向下语法制导翻译 我们重点介绍自底向上语法制导翻译。 5.3 语法制导翻译概述LR分析制导的具体实现方法: 为文法的每一个产生式设计相应的 语义动作为文法构造LR分析表 5.3 语法制导翻译概述扩充LR分析栈，以便存放文法符号 对应

8、的语义值 语义值栈状态栈文法符号栈 S0 $ S1 X1 X1.val Sk Xk Xk.val . . . . . . .5.3 语法制导翻译概述修改总控程序 :查分析表, 当用某产 生式归约时,调用相应的语义动作5.3 语法制导翻译概述例如，设有简单算术表达式的文法： EEE | E*E | (E) | digit1.E E(1)E(2) E.val E(1).val E(2).val 2.E E(1)*E(2) E.val E(1).val*E(2).val 3.E (E(1) E.val E(1).val 4.E digit E.val Lex.digit 1.为文法每一产生式设计相应

9、的语义动作 (求值的语义描述) ： 5.3 语法制导翻译概述2. 为上述文法构造LR分析表如下图： 90状态ACTIONGOTO+digit*()$ES3S9S5S4S2S3S2S3S5S4S2S5S2S3r4r4r4r4r1r1r1r2r3r2r3r3r2r2r3123456781678acc5.3 语法制导翻译概述 根据前表，用LR语法制导翻译法得到表达式7+8*5的计值过程，如下图 ：步骤状态栈 语义栈 符号栈输入符号栈 主要动作1_2030$_$7301_7$E4014_7_$E+50143_7_$E+87+8*5$S3+8*5$+8*5$8*5$*5$r4S4S3r44. E dig

10、itE.val Lex.digit 5.3 语法制导翻译概述步骤状态栈语义栈符号栈输入符号栈 主要动作6_7_87014750147$E+E_7_8$E+E*8014753_7_8_$E+E*59014758 _7_8_5$E+E*E100147_7_40$E+E*5$S55$S3r4r2r11101_47$E$acc2. E E*E E.val E(1).val*E(2).val 1. E E+E E.val E(1).val+E(2).val 5.3 语法制导翻译概述自下而上语法制导翻译法的特点: 语义分析栈与语法分析栈同步操作 当栈顶形成句柄执行规约时，调用相应的语义动作若将其翻译成某种

11、中间代码, 如何给出相应的语义描述 ?5.4 中间语言编译中常见的中间语言 :逆波兰式（后缀式） 三元式 树形表示 四元式5.4.1 逆波兰式逆波兰式逆波兰式 逆波兰式除去了原表达式中的括号，并将运算对象写在前面，运算符写在后面，因而又称为后缀式后缀式。 例如：逆波兰式a*bab*(a+b)*(c+d)ab+cd+*中缀表达式5.4.1 逆波兰式 逆波兰式表示法同中缀表示法相比其优点是:1.不再有括号,且运算符出现的顺序体 现了中缀表达式 的运算顺序2. 易于计算机处理5.4.1 逆波兰式 一般表达式计值时，要处理两类符号，一类是运算对象，另一类是运算符，通常用两个工作栈分别处理。但处理用逆波

12、兰式表示的表达式却只用一个工作栈。 5.4.1 逆波兰式 当计算机自左到右顺序扫描逆兰波式时，若当前符号是运算对象则进栈，若当前符号是运算符，设为K元运算符，则将栈顶的K个元素依次取出，同时进行K元运算，并将运算结果置于栈顶，表达式处理完毕时，其计算结果自然呈现在栈顶。 5.4.1 逆波兰式逆波兰式ab+c*的处理过程如下图： baT1cT1T25.4.1 逆波兰式：逆波兰形式可以推广到其他语法结构： 赋值语句V=E逆波兰式VE=条件语句逆波兰式if E S1 ; else S2ES1S2￥5.4.1 逆波兰式LR分析制导生成逆波兰式：分析制导生成逆波兰式： 1.给出算术表达式翻译到逆波兰式的

13、语义 描述(1)首先搞清楚生成什么样的中间代码 或计值(2)根据各种语法成份的语义, 搞清楚它们应翻译成什么形式的代 码结构LR分析制导生成逆波兰式：例如: 赋值语句 V=E 计算E值的代码 将E值存放到V中的代码 其代码结构:LR分析制导生成逆波兰式：例如: 条件语句 if E S1 ; else S2 其代码结构:计算E值的代码S2的代码S1的代码FTLR分析制导生成逆波兰式：(3) 给出从源结构到目标结构的变换方法例如，简单算术表达的文法： 给出算术表达式翻译到逆波兰式的语义描述EEE | E*E | (E) | i 源结构 a+b*c目标结构 abc*+LR分析制导生成逆波兰式：EEE

14、 | E*E | (E) | i1.E E(1)E(2) print + 2.E E(1)*E(2) print * 3.E (E(1) 空 4.E i print i 0.E E 空 E(1).code | E(2).code| + E(1).code | E(2).code| *LR分析制导生成逆波兰式：0状态ACTIONGOTO+ i*()$ES3S9S5S4S2S3S2S3S5S4S2S5S2S3r4r4r4r4r1r1r1r2r3r2r3r3r2r2r31234567891678acc2.为上述文法构造LR分析表如下图： LR分析制导生成逆波兰式：3. 算术表达式a+b*c翻译到逆波

15、兰式的过程： 状态栈符号栈输入串输出区030$a01$E014$E+0143$E+ba+b*c$+b*c$+b*c$b*c$*c$aaa4.Eiprint iLR分析制导生成逆波兰式：014750147$E+E$E+E*014753$E+E*c014758$E+E*E0147$E+E*c$abc$abababcabc*01$E$abc*+状态栈符号栈输入串输出区acc2. EE(1)*E(2)print *1. EE(1)+E(2)print +5.4.2 三元式和树形表示三元式三元式主要由三部分组成： （OP，arg1, arg2） 其中OP是运算符， arg1,arg2分别是第一和第二两个

16、运算对象。 当OP是一目运算时，常常将运算对象定义为arg1。 5.4.2 三元式和树形表示例如 a+b*c 的 三元式序列： (1) ( * b c ) (2) ( + a (1) )运算对象是指向符号表的某一项或指向三元式表的某一项。 5.4.2 三元式和树形表示 1. 三元式出现的顺序和语法成份的 计值顺序相一致。 三元式的特点：2. 三元式之间的联系是通过指示器 实现的。 5.4.2 三元式和树形表示间接三元式(1) 间接三元式表: 用来存放各三元式本身。(2) 间接码表: 按执行各三元式的顺序,依次 列出各三元式在三元式表中的位置。注意注意 : 间接三元式表中不存放重复的间接三元式表

17、中不存放重复的 三元式。三元式。5.4.2 三元式和树形表示 例如 语句 X= (A+B)*C Y= D(A+B)三元式序列(1) ( + , A , B )(2) ( * , (1) , C )(3) ( = , X , (2) )(5) ( , D , (4) )(4) ( + , A , B )(6) ( = , Y, (5) )间接三元式间接码表三元式表(1)(2)(3)(1)(4)(5)(1) ( + , A , B )(2) ( * , (1) , C )(3) ( = , X , (2) )(4) ( , D , (1) )(5) ( = , Y, (4) )5.4.2 三元式和

18、树形表示 树形表示 A * B + C*D +C*A*BD 末端结点表示一个运算对象, 每一个内结点表示一个一元或二元运算符。树形表示是三元式的翻版(3)+(1)*(2)*CABD5.4.3 四元式四元式四元式主要由四部分组成： （OP，arg1, arg2, result） 其中OP是运算符， arg1,arg2分别是第一和第二两个运算对象。 当OP是一目运算时，常常将运算对象定义为arg1。 四元式的第四个分量result是编译程序为存放中间运算结果而临时引进的变量，常称为临时变量，如Ti，也可以是用户自定义变量，如X。 5.4.3 四元式例如 X a*bc/d 的 四元式序列：(1) (

19、 *, a, b, T1 )(2) ( /, c, d, T2 )(3) ( +, T1, T2, T3 )(4) ( =, T3, - -, X )5.4.4 四元式2. 四元式之间的联系是通过临时变量实 现的，这样易于调整和变动四元式。 1. 四元式出现的顺序和语法成份的计值 顺序相一致。 四元式的特点：3. 便于优化处理。 5.4.4 四元式 编译系统中，有时将四元式表示成另一种更直观，更易理解的形式三地址代码或三地址语句。result : arg1 OP arg2 三地址语句三地址语句:语句中是三个量的赋值语句, 每个量占一个地址。 三地址代码形式定义为：5.4.4 四元式的翻译：例如

20、 X a*bc/d 的 四元式序列：(1) ( *, a, b, T1 )(2) ( /, c, d, T2 )(3) ( +, T1, T2, T3 )(4) ( =, T3, - -, X )相应的三地址语句序列为： （1）T1a*b （2）T2c/d （3）T3T1T2 （4）XT3 简单算术表达式和赋值语句到四元式的翻译：LR分析制导生成四元式分析制导生成四元式例如 A i E E EEE*E(E) | i 1. 给出算术表达式和赋值语句翻译到 四元式的语义描述简单算术表达式和赋值语句到四元式的翻译：A i E E EEE*E(E) | i 源结构目标结构（1）T1a*b （2）T2c

21、*d （3）T3T1T2 （4）X T3 X a*bc*d 简单算术表达式和赋值语句到四元式的翻译：语义函数 emit（Targ1 OP arg2） 功能是生成一个三地址语句，并送到输出文件中。 语义函数 newtemp( ) 功能是产生一个新的临时变量名字，并回送新的临时变量名的整数码。如T1，T2等。 简单算术表达式和赋值语句到四元式的翻译： (2) 不进符号表，临时变量单词值部 分用整数码表示。 (1) 送到符号表。 对临时变量有两种不同的处理方法: 简单算术表达式和赋值语句到四元式的翻译：语义过程 Lookup（i.name） 功能是审查i.name是否出现在符号表中，在则返回其指针，

22、否则返回NULL。 语义变量 E.place 表示存放非终结符E值的变量名在符号表中的入口地址或临时变量名的整数码。 简单算术表达式和赋值语句到四元式的翻译： 利用以上定义的语义变量和函数等，写出每一个规则式的语义动作如下：1. Ai E p = Lookup (i.name); if ( P != NULL ) emit ( pE.place ) ; else error( ) 简单算术表达式和赋值语句到四元式的翻译： 2. E E(1) E(2) 3. E E(1) * E(2) E.place newtemp( ); emit(E.placeE(1).placeE(2).place )

23、E.place newtemp( ); emit(E.placeE(1).place*E(2).place ) 简单算术表达式和赋值语句到四元式的翻译：4. E （E(1)） E.place E(1).place； 5. E i p Lookup (i.name); if (p != NULL) E.place p; else error( ); 简单算术表达式和赋值语句到四元式的翻译：90状态ACTIONGOTO+ i*()$ES3S9S5S4S2S3S2S3S5S4S2S5S2S3r4r4r4r4r1r1r1r2r3r2r3r3r2r2r3123456781678acc2.为文法构造LR分

24、析表如下图： 简单算术表达式和赋值语句到四元式的翻译：3. 算术表达式a+b*c翻译到三地址语句的过程： 030$a01$E014$E+0143$E+baaa状态栈符号栈语义栈输入串a+b*c$+b*c$+b*c$b*c$*c$ 变量在符号表的入口用变量本身表示简单算术表达式和赋值语句到四元式的翻译：*c$c$t1=b*c t2=a+t1 状态栈符号栈语义栈输入串014750147$E+E$E+E*014753$E+E*c014758$E+E*E0147$E+E01$Eab abcat1ababt2acc简单算术表达式和赋值语句到四元式的翻译： 2. E E(1) E(2) 3. E E(1)

25、 * * E(2) E.place newtemp( ); emit(E.placeE(1).placeE(2).place ) E.place newtemp( ); emit(E.placeE(1).place*E(2).place )布尔表达式到四元式的翻译一.布尔表达式的文法 计算逻辑值程序设计语言中布尔表达式有两个作用: 用作控制语句中的条件式布尔表达式是由布尔算符(、和)施于布尔变量或关系表达式而成。 布尔表达式到四元式的翻译 对某些语言,如 PL / 1,允许更通用的表达式,其中,布尔算符、算术算符和关系算符可施于任何类型的表达式,并不区别布尔值和算术值。 为简单起见,只考虑如下

26、文法生成的布尔表达式:布尔表达式到四元式的翻译 E E (1) E (2) E E (1) E (2) E E (1) E ( E (1) ) E i (1) rop i (2) E true E false E i布尔表达式到四元式的翻译 二. 布尔表达式的计值方法 1. 如同计算算术表达式一样,步步计算出各部分真、假值,最后计算出整个表达式的值。 2. 根据布尔运算的特殊性,采取某种优化措施,可避免计算整个表达式的值。布尔表达式到四元式的翻译 AB 解释成 AB 解释成 A 解释成if A then true else Bif A then B else falseif A then fa

27、lse else true 三. 布尔表达式的翻译方法 1. 同翻译算术表达式一样,翻译布尔表达式。布尔表达式到四元式的翻译 1. E E (1) E (2) E.place newtemp( )； emit ( E.placeE(1).placeE(2).place ) 2. E E (1) E (2) E.place newtemp( )； emit ( E.placeE(1).placeE(2).place ) 布尔表达式到四元式的翻译3. E ( E (1) ) E.place E(1).place； 4. E i (1) rop i (2) E.place newtemp( )； e

28、mit (if i (1).place rop.op i (2).place goto next+3); emit ( E.place 0 ); emit ( goto next+2); emit ( E.place 1 ); 布尔表达式到四元式的翻译5. E true E.place newtemp( )； emit ( E.place 1) E.place newtemp( )； emit ( E.place 0) 6. E false 或 E.place i . place； 6. E i 布尔表达式到四元式的翻译例如布尔表达式 a = bc d 对应如下四元式序列:101 if a =

29、 b goto 104102 t1= 0103 goto 105104 t1= 1105 t2= c d106 t3 = t1 t2 布尔表达式到四元式的翻译2. 控制语句中布尔表达式的翻译条件语句的语法为:根据条件语句的语义,条件语句的代码结构为:if E then S(1) else S(2)E的代码S(1)的代码S(2)的代码Jump out out: 真 假布尔表达式到四元式的翻译 E是布尔表达式,根据布尔运算的特殊性,布尔表达式的目标结构为:假E(1)的代码E(2)的代码真S(1)S(2)真假真E(1)的代码E(2)的代码假S(2)S(1)假真 (1) 真出口和假出口:真出口表示布尔

30、表达式E为真时控制流向的转移目标假出口表示布尔表达式E为假时控制流向的转移目标布尔表达式到四元式的翻译(2) 作为条件转移的E,把E翻译成的代码 是一串条件转或无条件转的四元式对于E为 a rop b 的形式生成代码为: if a rop b goto 真出口 goto 假出口布尔表达式到四元式的翻译(q)例如语句 if a bc d then S(1) else S(2) 的四元式为:100 if a b goto 104101 goto 102102 if c d goto 104 103 goto ( p+1) 104 ( 关于 S(1) 的四元式)(p) goto (q)(p+1) (

31、 关于 S(2) 的四元式)E(1)的真出口为104, E(1)的假出口为102E(2)的真出口为104, E(2)的假出口为(p+1)E的真出口为104, E的假出口为(p+1)布尔表达式到四元式的翻译布尔表达式到四元式的翻译布尔表达式的真、假出口不能在产生其四元式的同时得知例如 E(1)的真出口为104需分析到S(1)时才能得知,因此E.tr: 记录表达式 E 所对应的四元式需回填真出口的四元式的地址所构成的链E.fa: 记录表达式 E 所对应的四元式需回填假出口的四元式的地址所构成的链(3) 设置两个语义变量:(q)例如语句 if a bc d then S(1) else S(2) 的

32、四元式为:100 if a b goto 104101 goto 102102 if c d goto 104 103 goto ( p+1) 104 ( 关于 S(1) 的四元式)(p) goto (q)(p+1) ( 关于 S(2) 的四元式)布尔表达式到四元式的翻译E(1).tr=100, E(1).fa=101E(2).tr=102, E(2).fa=103布尔表达式到四元式的翻译E.fa=103; E.tr=100和102所构成的链 E(1) E(2)归约E时, 布尔表达式到四元式的翻译把以 p1, p2为链首的两条链合并为一, 返回合并后的链首(4) 链结函数和回填函数: merg

33、 (p1, p2) :布尔表达式到四元式的翻译 merg (int p1, int p2) if p2=0 return( p1 ) ;else p= p2 ; while ( 四元式p的第四分量内容不为0) p=四元式p的第四分量内容; 把p1填进四元式p的第四分量; return( p2 ) ;布尔表达式到四元式的翻译r1 ( 0 )q1 ( r1 )q2 ( r2 )p1 ( q1 )r2 ( 0 )p2 ( q2 )p1布尔表达式到四元式的翻译 merg (int p1, int p2) if p2=0 return( p1 ) ;else p= p2 ; while ( 四元式p的第

34、四分量内容不为0) p=四元式p的第四分量内容; 把p1填进四元式p的第四分量; return( p2 ) ;100102102(q)例如语句 if a bc d then S(1) else S(2) 的四元式为:100 if a b goto 0101 goto 102102 if c d goto 100 103 goto ( p+1) 104 ( 关于 S(1) 的四元式)(p) goto (q)(p+1) ( 关于 S(2) 的四元式)布尔表达式到四元式的翻译布尔表达式到四元式的翻译 bp ( int p, int t ) : 将 p 所链结的每个四元式的第四区分量都回填 t ;布尔

35、表达式到四元式的翻译 bp ( int p, int t )q=p;while (q != 0 ) r = 四元式 q 的第四分量内容; 把 t 填进四元式 q 的第四分量; q=r ;1021041000 102100(q)例如语句 if a bc d then S(1) else S(2) 的四元式为:100 if a b goto 104101 goto 102102 if c d goto 104 103 goto ( p+1) 104 ( 关于 S(1) 的四元式)(p) goto (q)(p+1) ( 关于 S(2) 的四元式)布尔表达式到四元式的翻译布尔表达式到四元式的翻译(5)

36、 为及时回填转移地址, 使用语义变量 E.code 记录表达式E的第一个四元式语句序号。(6) 定义语义变量 next 为四元式表指针。E (1).code=100E (2).code=102E .code=100布尔表达式到四元式的翻译布尔表达式语义动作的设计 1. E E (1) E (2) bp( E(1).fa, E(2).code) ； E.code= E(1).code ; E.tr=merg( E(1).tr, E(2).tr ) ; E.fa= E(2).fa ;布尔表达式到四元式的翻译布尔表达式语义动作的设计 2. E E (1) E (2) bp( E(1).tr, E(2

37、).code) ； E.code= E(1).code ; E.tr= E(2).tr ; E.fa=merg( E(1).fa, E(2).fa ) ;布尔表达式语义动作的设计 3. E ( E (1) ) E.code= E(1).code ; E.tr=E(1).tr ; E.fa= E(1).fa ;布尔表达式到四元式的翻译布尔表达式语义动作的设计 4. E i (1) rop i (2) E.tr= next ; E.code= next ; E.fa= next+1; emit ( if i (1).place rop.op i (2).place goto _ ) ; emit(

38、 goto _ ) ;布尔表达式到四元式的翻译布尔表达式语义动作的设计 5. E true E.tr= next ; E.code= next ; emit( goto _ ) ;布尔表达式到四元式的翻译布尔表达式到四元式的翻译布尔表达式语义动作的设计 6. E false E.fa= next ; E.code= next ; emit( goto _ ) ;布尔表达式到四元式的翻译布尔表达式语义动作的设计 5. E i E.tr= next ; E.fa= next +1; E.code= next ; emit(if i.place goto -); emit( goto _ ) ;5.

39、 E true 6. E false布尔表达式到四元式的翻译例如布尔表达式 a bc d 的翻译过程如下:布尔表达式到四元式的翻译a bc d E (1)c d 100 if a b goto 0101 goto 0 E(1).tr=100 ; E(1).fa=101 ; E(1).code=100 ; E (1) E (2) 102 if c d goto 0103 goto 0 E(2).tr=102 ; E(2).fa=103 ; E(2).code=102 ; 布尔表达式到四元式的翻译 E bp( E(1).fa, E(2).code) =bp( 101,102); E.fa=E(2)

40、.fa=103 ; E.tr=merg(E(1).tr, E(2).tr) = merg( 100,102)=102 ; E.code= E(1).code=100100 if a b goto 0101 goto 0102 if c d goto 100103 goto 0102E (1)E (2) 归约为E布尔表达式到四元式的翻译102 if c d goto 100103 goto 0100 if a b goto 0101 goto 102布尔表达式 a bc d E.tr=102E.fa=103简单说明语句的翻译 程序设计语言中，程序中的每个名字（变量名）都必须在使用前进行说明。说明

41、语句的功能就是告知编译程序每一个变量的类型信息。 翻译说明语句时,设计的语义动作应将变量的类型信息填入符号表中。简单说明语句的翻译简单说明语句文法 , id | idD integer real 简单说明语句的翻译 用上述文法的规则式进行归约时，按照自下而上制导翻译，首先将所有名字id归约为一个名字表namelist后，才能将namelist中所有名字的性质登录在符号表里。这样必须用一个队列（或栈）来保存namelist中的所有名字。简单说明语句的翻译 我们希望在扫描过程中，每遇到一个名字，就把它及其性质及时登录在符号表中。归约过程中涉及到这些名字及其性质时，就可以直接到符号表中进行查找，而无

42、需占用额外空间保存namelist 中名字的信息简单说明语句的翻译文法改写：DD(1)，idinteger id real id（1） 函数FILL(id，A)的功能是把名字 id和性质A登录在符号表中。对文法设计语义动作如下：（2）设置非终结符D的语义变量D.ATT, 记录说明语句所规定的相关名字性质。简单说明语句的翻译（1）Dinteger id（2）Dreal id（3）DD(1), id FILL(id, int) ; D.ATTint FILL(id, real) ; D.ATT=real FILL(id, D(1).ATT) ; D.ATT=D(1).ATT 过程或函数调用语句的翻

43、译过程或函数调用语句的翻译一种描述过程或函数调用语句的文法一种描述过程或函数调用语句的文法如下：如下：GS: Scall i() ,E E 过程或函数调用语句的翻译过程或函数调用语句的翻译Scall i() for(队列队列queue中的每一项中的每一项P) emit(par,_,_,P); emit(call,_,_,i.place);,E 将将E.place加入加入queue的队尾的队尾E 初始化初始化queue队列，仅包含队列，仅包含E.place本本 章章 小小 结结1. 简单算术表达式的逆波兰式和四元 式的表示例如 a + b * ( c + d )的逆波兰式 a bc d + *

44、+本本 章章 小小 结结t1= a t2= c t3= t2 + dt5= t1+ t4例 a + b * ( c + d )的四元式 t4= b* t3 本本 章章 小小 结结i( i /( i i ) )的逆波兰式 i( i /( i i ) )的四元式 t1= i i t2= i / t1t3= i t2i i i i /例如 ：本本 章章 小小 结结2. 编译中常用的中间代码:逆波兰式四元式三元式树形表示3. 什么是语法制导翻译法 在语法分析过程中，依随分析的过程，根据每个产生式所对应的语义子程序(语义规则描述的语义处理的加工动作)进行翻译的方法。 本本 章章 小小 结结4. 采用自下

45、而上的语法制导翻译法语义 动作的设计（1）搞清楚源结构和目标结构（2）自下而上的语法制导翻译特点： 栈顶形成句柄，归约时执行相应语义 动作（3）给出从源结构到目标结构的变换 方法本本 章章 小小 结结例1. 设文法及其相应的语义动作如下: SbTc print “1” Sa print “2” TR print “3” RR/S print “4” RS print “5” 采用自下而上语法制导翻译,给出输入串bR / bTc / bSc / ac的翻译结果 本本 章章 小小 结结分析: 首先对输入串 bR / bTc / bSc /ac画出语法树:ScTbRS/R/RS/RcTbaScTbR

46、S再考虑归约时执行相应语义动作本本 章章 小小 结结ScTbRS/R/RS/RcTbaScTbRS SbTc print “1” Sa print “2” TR print “3” RR/S print “4” RS print “5” 14翻译结果为:53142431本本 章章 小小 结结ScTbRS/R/RS/RcTbaScTbRS RR/S SbTc Sa TR RS 输出为:1453142431输入是bR / bTc / bSc /ac给出相应语义动作(翻译方案) print “1” print “2” print “3” print “4” print “5”本本 章章 小小 结结例

47、2 简单算术表达式求值的语义描述例如，设有简单算术表达式的文法： EEE | E*E | (E) | digit1.E E(1)E(2) E.val E(1).val E(2).val 2.E E(1)*E(2) E.val E(1).val*E(2).val 3.E (E(1) E.val E(1).val 4.E digit E.val Lex.digit 本本 章章 小小 结结例3 简单算术表达式翻译到四元式的 语义描述例如，设有简单算术表达式的文法： EEE | E*E | (E) | i 1. E E(1) E(2) 2. E E(1) * E(2) E.place newtemp( ); emit(E.placeE(1).placeE(2).place ) E.place newtemp( ); emit(E.placeE(1).place*E(2).place ) 本本 章章 小小 结结3. E （E(1)） E.place E(1).place； 4. E i p Lookup (i.name); if (p != NULL) E.place p; else error( ); 本本 章章 小小 结结