编译原理第5章

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、实现语义处理。 5.3 语法制导翻译概述 s axy a1 a2 a3 ai ai+1 an 语义处理的 加工动作 语法制导翻译法使用属性文法为工具 来说明程序设计语言的语义。 5.3 语法制导翻译概述 (语义子程序语义子程序) 描述了一个产生式所对应的翻译工作描述了一个产生式所对应的翻译工作。 产生式只能产生符号串,并没有指明所 产生符号串的意义,仅仅是一些符号串的 集合。 语义动作语义动作 5.3 语法制导翻译概述 语义动作不仅指明了该产生式所产生符 号串的意义，而且还根据这种意义规定了 对应的加工动作（如查填各类表格、改变 编译程序的某些变量的值、打印各种错误 信息及生成中间代码等），从

6、而完成预定 的翻译工作。 5.3 语法制导翻译概述 语法制导翻译法语法制导翻译法 在语法分析过程中，依随分析的过程， 根据每个产生式所对应的语义子程序(或 语义规则描述的语义处理的加工动作)进 行翻译的方法。 为文法每一产生式设计相应的求值的语义 描述(语义动作)： 5.3 语法制导翻译概述 例如，设有简单算术表达式的文法： eee | e*e | (e) | digit 1.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.

7、val lex.digit 7+8*5,3+8,6*5, 5.3 语法制导翻译概述 e.val = 47 e.val = 8 e.val = 40 e.val = 7 e.val = 5 + 5 * 8 7 1.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 e e e e e 5.3 语法制导翻译概述 语法制导翻译技术分为： 自底向上语法制导翻译 自顶向下语法制导翻译 我们重点

8、介绍自底向上语法制导翻译。 5.3 语法制导翻译概述 lr分析制导的具体实现方法: 为文法的每一个产生式设计相应的 语义动作 为文法构造lr分析表 5.3 语法制导翻译概述 扩充lr分析栈，以便存放文法符号 对应的语义值 语义值栈状态栈文法符号栈 s0 $ s1 x1 x1.val sk xk xk.val . . . . . . . . . 5.3 语法制导翻译概述 修改总控程序 :查分析表, 当用某产 生式归约时,调用相应的语义动作 5.3 语法制导翻译概述 例如，设有简单算术表达式的文法： eee | e*e | (e) | digit 1.e e(1)e(2) e.val e(1).v

9、al 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. 为文法每一产生式设计相应的语义动作 (求值的语义描述) ： 5.3 语法制导翻译概述 2. 为上述文法构造lr分析表如下图： 9 0 状 态 actiongoto + digit * ()$e s3 s9s5s4 s2s3 s2s3 s5s4 s2 s5 s2s3 r4r4r4r4 r1r1r1 r2 r3 r2 r3r3 r2r2 r3 1 2 3 4 5 6 7 8 1 6 7 8 a

10、cc 5.3 语法制导翻译概述 根据前表，用lr语法制导翻译法得到 表达式7+8*5的计值过程，如下图 ： 步骤状态栈 语义栈 符号栈输入符号栈 主要动作 1 _ 203 0$ _ $7 301 _7$e 4014 _7_$e+ 50143 _7_ $e+8 7+8*5$s3 +8*5$ +8*5$ 8*5$ *5$ r4 s4 s3 r4 4. e digit e.val lex.digit 5.3 语法制导翻译概述 步骤状态栈语义栈符号栈输入符号栈 主要动作 6 _7_8 701475 0147$e+e _7_8 $e+e* 8014753 _7_8_$e+e*5 9014758 _7_8

11、_5$e+e*e 10 0147 _7_40$e+e *5$s5 5$ $ $ $ s3 r4 r2 r1 1101 _47$e$acc 2. 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 语法制导翻译概述 自下而上语法制导翻译法的特点: 语义分析栈与语法分析栈同步操作 当栈顶形成句柄执行规约时，调用相 应的语义动作 若将其翻译成某种中间代码, 如何给出 相应的语义描述 ? 5.4 中间语言 编译中常见的中间语言 : 逆波兰式（后缀式） 三元式 树形表示 四元式 5.4.1 逆波兰式 逆波兰式逆波兰式 逆波

12、兰式除去了原表达式中的括号， 并将运算对象写在前面，运算符写在后 面，因而又称为后缀式后缀式。 例如：逆波兰式 a*bab* (a+b)*(c+d)ab+cd+* 中缀表达式 5.4.1 逆波兰式 逆波兰式表示法同中缀表示法相比其 优点是: 1. 不再有括号,且运算符出现的顺序体 现了中缀表达式 的运算顺序 2. 易于计算机处理 5.4.1 逆波兰式 一般表达式计值时，要处理两类符 号，一类是运算对象，另一类是运算符， 通常用两个工作栈分别处理。但处理用 逆波兰式表示的表达式却只用一个工作 栈。 5.4.1 逆波兰式 当计算机自左到右顺序扫描逆兰波 式时，若当前符号是运算对象则进栈， 若当前符

13、号是运算符，设为k元运算符， 则将栈顶的k个元素依次取出，同时进 行k元运算，并将运算结果置于栈顶， 表达式处理完毕时，其计算结果自然呈 现在栈顶。 5.4.1 逆波兰式 逆波兰式ab+c*的处理过程如下图： b at1 c t1t2 5.4.1 逆波兰式： 逆波兰形式可以推广到其他语法结构： 赋值语句 v=e 逆波兰式 ve= 条件语句逆波兰式 if e s1 ; else s2es1s2￥ 5.4.1 逆波兰式 lr分析制导生成逆波兰式：分析制导生成逆波兰式： 1. 给出算术表达式翻译到逆波兰式的语义 描述 (1)首先搞清楚生成什么样的中间代码 或计值 (2)根据各种语法成份的语义, 搞清

14、楚它 们应翻译成什么形式的代 码结构 lr分析制导生成逆波兰式： 例如: 赋值语句 v=e 计算e值的代码 将e值存放到v中的代码 其代码结构: lr分析制导生成逆波兰式： 例如: 条件语句 if e s1 ; else s2 其代码结构: 计算e值的代码 s2的代码 s1的代码 ft lr分析制导生成逆波兰式： (3) 给出从源结构到目标结构的变换方法 例如，简单算术表达的文法： 给出算术表达式翻译到逆波兰式的语义 描述 eee | e*e | (e) | i 源结构 a+b*c 目标结构 abc*+ lr分析制导生成逆波兰式： eee | e*e | (e) | i 1.e e(1)e(2

15、) 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 * ()$e s3 s9s5s4 s2s3 s2s3 s5s4 s2 s5 s2s3 r4r4r4r4 r1r1r1 r2 r3 r2 r3r3 r2r2 r3 1 2 3 4 5 6 7 8 9 1 6 7 8 acc 2.为上述文法构造lr分析表如下图： lr分析制导生成逆波兰式： 3. 算术

16、表达式a+b*c翻译到逆波兰式的过程： 状态栈符号栈输入串输出区 03 0 $ $a 01$e 014$e+ 0143$e+b a+b*c$ +b*c$ +b*c$ b*c$ *c$ a a a 4.ei print i lr分析制导生成逆波兰式： 01475 0147$e+e $e+e* 014753$e+e*c 014758$e+e*e 0147$e+e *c$ ab c$ $ $ $ ab ab abc abc* 01$e$ abc*+ 状态栈符号栈输入串输出区 acc 2. ee(1)*e(2) print * 1. ee(1)+e(2) print + 5.4.2 三元式和树形表示

17、三元式三元式主要由三部分组成： （op，arg1, arg2） 其中op是运算符， arg1,arg2分别是第一和第二两个运算对象。 当op是一目运算时，常常将运算对象定 义为arg1。 5.4.2 三元式和树形表示 例如 a+b*c 的 三元式序列： (1) ( * b c ) (2) ( + a (1) ) 运算对象是指向符号表的某一项或指向 三元式表的某一项。 5.4.2 三元式和树形表示 1. 三元式出现的顺序和语法成份的 计值顺序相一致。 三元式的特点： 2. 三元式之间的联系是通过指示器 实现的。 5.4.2 三元式和树形表示 间接三元式 (1) 间接三元式表: 用来存放各三元式本

18、身。 (2) 间接码表: 按执行各三元式的顺序,依次 列出各三元式在三元式表中的位置。 注意注意 : 间接三元式表中不存放重复的间接三元式表中不存放重复的 三元式。三元式。 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 ,

19、 b ) (2) ( * , (1) , c ) (3) ( = , x , (2) ) (4) ( , d , (1) ) (5) ( = , y, (4) ) 5.4.2 三元式和树形表示 树形表示 a * b + c*d + c * a * bd 末端结点表示一个运算对象, 每一个内 结点表示一个一元或二元运算符。 树形表示是三元式的翻版 (3)+ (1)*(2)* cabd 5.4.3 四元式 四元式四元式主要由四部分组成： （op，arg1, arg2, result） 其中op是运算符， arg1,arg2分别是第一和第二两个运算对象。 当op是一目运算时，常常将运算对象定义 为a

20、rg1。 四元式的第四个分量result是编译程序 为存放中间运算结果而临时引进的变量， 常称为临时变量，如ti，也可以是用户 自定义变量，如x。 5.4.3 四元式 例如 x a*bc/d 的 四元式序列： (1) ( *, a, b, t1 ) (2) ( /, c, d, t2 ) (3) ( +, t1, t2, t3 ) (4) ( =, t3, - -, x ) 5.4.4 四元式 2. 四元式之间的联系是通过临时变量实 现的，这样易于调整和变动四元式。 1. 四元式出现的顺序和语法成份的计值 顺序相一致。 四元式的特点： 3. 便于优化处理。 5.4.4 四元式 编译系统中，有时

21、将四元式表示成另一 种更直观，更易理解的形式三地址代 码或三地址语句。 result : arg1 op arg2 三地址语句三地址语句:语句中是三个量的赋值语句, 每个量占一个地址。 三地址代码形式定义为： 5.4.4 四元式的翻译： 例如 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分析制导

22、生成四元式分析制导生成四元式 例如 a i e e ee e*e (e) | i 1. 给出算术表达式和赋值语句翻译到 四元式的语义描述 简单算术表达式和赋值语句到四元 式的翻译： a i e e ee e*e (e) | i 源结构目标结构 （1）t1a*b （2）t2c*d （3）t3t1t2 （4）x t3 x a*bc*d 简单算术表达式和赋值语句到四元 式的翻译： 语义函数 emit（targ1 op arg2） 功能是生成一个三地址语句，并送 到输出文件中。 语义函数 newtemp( ) 功能是产生一个新的临时变量名字， 并回送新的临时变量名的整数码。 如t1，t2等。 简单算术

23、表达式和赋值语句到四元 式的翻译： (2) 不进符号表，临时变量单词值部 分用整数码表示。 (1) 送到符号表。 对临时变量有两种不同的处理方法: 简单算术表达式和赋值语句到四元 式的翻译： 语义过程 lookup（） 功能是审查是否出现在符号表中， 在则返回其指针，否则返回null。 语义变量 e.place 表示存放非终结符e值的变量名在符号 表中的入口地址或临时变量名的整数码。 简单算术表达式和赋值语句到四元 式的翻译： 利用以上定义的语义变量和函数等，写出 每一个规则式的语义动作如下： 1. ai e p = lookup (); if ( p !=

24、 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 ) 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 (); if (p != null

25、) e.place p; else error( ); 简单算术表达式和赋值语句到四元 式的翻译： 9 0 状 态 actiongoto + i * ()$e s3 s9s5s4 s2s3 s2s3 s5s4 s2 s5 s2s3 r4r4r4r4 r1r1r1 r2 r3 r2 r3r3 r2r2 r3 1 2 3 4 5 6 7 8 1 6 7 8 acc 2.为文法构造lr分析表如下图： 简单算术表达式和赋值语句到四元 式的翻译： 3. 算术表达式a+b*c翻译到三地址语句的过程： 03 0 $ $a 01$e 014$e+ 0143$e+b a a a 状态栈符号栈语义栈输入串 a+b

26、*c$ +b*c$ +b*c$ b*c$ *c$ 变量在符号表的 入口用变量本身 表示 简单算术表达式和赋值语句到四元 式的翻译： *c$ c$ $ $ $ $ t1=b*c t2=a+t1 状态栈符号栈语义栈输入串 01475 0147$e+e $e+e* 014753$e+e*c 014758$e+e*e 0147$e+e 01$e ab abc at1 ab ab t2 acc 简单算术表达式和赋值语句到四元 式的翻译： 2. e e(1) e(2) 3. e e(1) * * e(2) e.place newtemp( ); emit(e.placee(1).placee(2).pla

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

28、) 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 b if a then b else false if a then false else true 三. 布尔表达式的翻译方法 1. 同翻译算术表达式一样,

29、翻译布尔表达式。 布尔表达式到四元式的翻译 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( )； emit (if i (1).place rop.op i (2).place g

30、oto 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 = b goto 104 102 t1= 0 103 goto 105 1

31、04 t1= 1 105 t2= c d 106 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) 真出口和假出口: 真出口表示布尔表达式e为真时控

32、制 流向的转移目标 假出口表示布尔表达式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 104 101 goto 102 102 if c d goto 104 103 goto ( p+1) 104 ( 关于 s(1) 的四元式) (p) goto (q) (

33、p+1) ( 关于 s(2) 的四元式) e(1)的真出口 为104, e(1)的 假出口为102 e(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

34、 a bc d then s(1) else s(2) 的四元式为: 100 if a b goto 104 101 goto 102 102 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=101 e(2).tr=102, e(2).fa=103 布尔表达式到四元式的翻译 e.fa=103; e.tr=100和102所构成的链 e(1) e(2)归约e时, 布尔表达式到四元式的翻译 把以 p1, p2

35、为链首的两条链合并为一, 返回合并后的链首 (4) 链结函数和回填函数: merg (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 p

36、2) if p2=0 return( p1 ) ; else p= p2 ; while ( 四元式p的第四分量内容不为0) p=四元式p的第四分量内容; 把p1填进四元式p的第四分量; return( p2 ) ; 100 102 102 (q) 例如语句 if a bc d then s(1) else s(2) 的四元式为: 100 if a b goto 0 101 goto 102 102 if c d goto 100 103 goto ( p+1) 104 ( 关于 s(1) 的四元式) (p) goto (q) (p+1) ( 关于 s(2) 的四元式) 布尔表达式到四元式的翻

37、译 布尔表达式到四元式的翻译 bp ( int p, int t ) : 将 p 所链结的每个四元式的第四 区分量都回填 t ; 布尔表达式到四元式的翻译 bp ( int p, int t ) q=p; while (q != 0 ) r = 四元式 q 的第四分量内容; 把 t 填进四元式 q 的第四分量; q=r ; 10 2 10 4 10 0 0 10 2 10 0 (q) 例如语句 if a bc d then s(1) else s(2) 的四元式为: 100 if a b goto 104 101 goto 102 102 if c d goto 104 103 goto (

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

39、( e(1).tr, e(2).tr ) ; e.fa= e(2).fa ; 布尔表达式到四元式的翻译 布尔表达式语义动作的设计 2. e e (1) e (2) bp( e(1).tr, e(2).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

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

41、译 布尔表达式语义动作的设计 5. e i e.tr= next ; e.fa= next +1; e.code= next ; emit(if i.place goto -); emit( goto _ ) ; 5. e true 6. e false 布尔表达式到四元式的翻译 例如布尔表达式 a bc d 的翻译过 程如下: 布尔表达式到四元式的翻译 a bc d e (1)c d 100 if a b goto 0 101 goto 0 e(1).tr=100 ; e(1).fa=101 ; e(1).code=100 ; e (1) e (2) 102 if c d goto 0 10

42、3 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).fa=103 ; e.tr=merg(e(1).tr, e(2).tr) = merg( 100,102)=102 ; e.code= e(1).code=100 100 if a b goto 0 101 goto 0 102 if c d goto 100 103 goto 0 10 2 e (1)e (2) 归约为e 布尔表达式到四元式的翻译 102 if

43、c d goto 100 103 goto 0 100 if a b goto 0 101 goto 102 布尔表达式 a bc d e.tr=102 e.fa=103 简单说明语句的翻译 程序设计语言中，程序中的每个名 字（变量名）都必须在使用前进行说明。 说明语句的功能就是告知编译程序每一 个变量的类型信息。 翻译说明语句时,设计的语义动作应 将变量的类型信息填入符号表中。 简单说明语句的翻译 简单说明语句文法 , id | id d integer real 简单说明语句的翻译 用上述文法的规则式进行归约时，按 照自下而上制导翻译，首先将所有名字 id归约为一个名字表namelist后

44、，才能将 namelist中所有名字的性质登录在符号表 里。这样必须用一个队列（或栈）来保 存namelist中的所有名字。 简单说明语句的翻译 我们希望在扫描过程中，每遇到一个 名字，就把它及其性质及时登录在符号 表中。归约过程中涉及到这些名字及其 性质时，就可以直接到符号表中进行查 找，而无需占用额外空间保存namelist 中名字的信息 简单说明语句的翻译 文法改写： dd(1)，idinteger id real id （1） 函数fill(id，a)的功能是把名字 id和性质a登录在符号表中。 对文法设计语义动作如下： （2）设置非终结符d的语义变量d.att, 记录说明语句所规定的

45、相关名字性质。 简单说明语句的翻译 （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 过程或函数调用语句的翻译过程或函数调用语句的翻译 一种描述过程或函数调用语句的文法一种描述过程或函数调用语句的文法 如下：如下： 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 )的逆