编译原理第5章(语法制导翻译技术)-1

1、语义分析的任务： 静态语义审查静态语义审查 审查每个语法结构的静态语义审查每个语法结构的静态语义, 即验证语法结构合法的程序即验证语法结构合法的程序,是否是否 真正有意义真正有意义。 第5章 语法制导翻译技术和中间代 码生成 5.1 概述 例如: 表达式 A+B*C 对运算对象进行类型检查, 对变 量进行先定义后使用检查 如果静态语义正确, 语义处理则要执 行真正的翻译, 即生成程序的某种中间 代码的形式或直接生成目标代码。 执行真正的翻译执行真正的翻译 第5章 语法制导翻译技术和中间代 码生成 目前多数编译程序进行语义分析的方 法是采用语法制导翻译法采用语法制导翻译法 。它不是一种 形式系统

2、, 但它比较接近形式化。 语法制导翻译法使用属性文法为工具 来描述程序设计语言的语义。 第5章 语法制导翻译技术和中间代 码生成 (1) 属性 对文法的每一个符号, 引进一些属 性, 这些属性代表与文法符号相关的信 息, 如类型、值、存储位置等。与属性 相关的信息, 即属性值,可以在语法分析 过程中计算和传递。 5.2 属性文法 第5章 语法制导翻译技术和中间代 码生成 属性分为两类: 综合属性其计算规则按“自下而上”方 式进行, 即规则左部符号的某些属性根 据其右部符号的属性和(或)自己的其他 属性计算而得。 属性加工的过程即是语义的处理过程。属性加工的过程即是语义的处理过程。 综合属性和继

3、承属性。 第5章 语法制导翻译技术和中间代 码生成 继承属性其计算规则按“自上而下”方 式进行, 即规则右部符号的某些属性根 据其左部符号的属性和(或)右部其他符 号的某些属性计算而得。 第5章 语法制导翻译技术和中间代 码生成 (2) 属性文法 为文法的每一个规则配备的计算属性 的计算规则, 称为语义规则(描述语义处 理的加工动作) 。 属性文法包含一个上下文无关文法和 一系列语义规则。 语义规则: 第5章 语法制导翻译技术和中间代 码生成 这些语义规则附在文法的每个产生 式上,在语法分析过程中, 执行语义规则 描述的动作, 从而实现语义处理。也就 是说, 附在文法的每个产生式上语义规 则描

4、述了语义处理的加工动作。 目前流行的语义描述和语义处理的 方法主要是属性文法和语法制导翻译方 法。 第5章 语法制导翻译技术和中间代 码生成 G： EE+T |T TT*F |F F(E)|i G： DTL Tinteger |real LL,id|id 5.3 语法制导翻译概述语法制导翻译概述 为文法的每个产生式都配备一个语义 动作或语义子程序。 在语法分析的过程中，每当使用一条 产生式进行推导或归约时，就执行相应 产生式的语义动作, 从而实现语义处理。 第5章 语法制导翻译技术和中间代 码生成 (1) 语法制导翻译法 的基本思想 S Axy a1 a2 a3 ai ai+1 an 语义处理

5、的 加工动作 语法制导翻译法使用属性文法为工具 来说明程序设计语言的语义。 第5章 语法制导翻译技术和中间代 码生成 (2) 语法制导翻译法语法制导翻译法 在语法分析过程中，依随分析的过程， 根据每个产生式所对应的语义子程序(或 语义规则描述的语义处理的加工动作)进 行翻译的方法。 第5章 语法制导翻译技术和中间代 码生成 为文法每一产生式设计相应的求值的语义 描述(语义动作)： 例如，设有简单算术表达式的文法： 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

6、(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章 语法制导翻译技术和中间代 码生成 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.val = 47 E.val = 8 E.val = 40 E.val = 7 E.val = 5 + 5 * 8 7 E E E E

7、E 5.4 编译中常用的中间代码: 逆波兰式四元式 三元式树形表示 第5章 语法制导翻译技术和中间代 码生成 逆波兰式逆波兰式 逆波兰式除去了原表达式中的括号， 并将运算对象写在前面，运算符写在后 面，因而又称为后缀式后缀式。 例如：逆波兰式 a*bab* (a+b)*(c+d)ab+cd+* 中缀表达式 第5章 语法制导翻译技术和中间代 码生成 逆波兰式表示法同中缀表示法相比其 优点是: 不再有括号,且运算符出现的顺序体 现了中缀表达式 的运算顺序 2. 易于计算机处理 第5章 语法制导翻译技术和中间代 码生成 一般表达式计值时，要处理两类符 号，一类是运算对象，另一类是运算符， 通常用两个

8、工作栈分别处理。但处理用 逆波兰式表示的表达式却只用一个工作 栈。 第5章 语法制导翻译技术和中间代 码生成 当计算机自左到右顺序扫描逆兰波 式时，若当前符号是运算对象则进栈， 若当前符号是运算符，设为K元运算符， 则将栈顶的K个元素依次取出，同时进 行K元运算，并将运算结果置于栈顶， 表达式处理完毕时，其计算结果自然呈 现在栈顶。 第5章 语法制导翻译技术和中间代 码生成 逆波兰式ab+c*的处理过程如下图： b aT1 c T1T2 第5章 语法制导翻译技术和中间代 码生成 逆波兰形式可以推广到其他语法结构： 赋值语句 V=E 逆波兰式 VE= 条件语句逆波兰式 if E S1 ; els

9、e S2ES1S2￥ 第5章 语法制导翻译技术和中间代 码生成 三元式和树形表示 三元式三元式主要由三部分组成： （OP，arg1, arg2） 其中OP是运算符， arg1,arg2分别是第一和第二两个运算对象。 当OP是一目运算时，常常将运算对象定 义为arg1。 第5章 语法制导翻译技术和中间代 码生成 例如 a+b*c 的 三元式序列： (1) ( * , b , c ) (2) ( + , a , (1) ) 运算对象是指向符号表的某一项或指向 三元式表的某一项。 第5章 语法制导翻译技术和中间代 码生成 1. 三元式出现的顺序和语法成份的 计值顺序相一致。 三元式的特点： 2. 三

10、元式之间的联系是通过指示器 实现的。 第5章 语法制导翻译技术和中间代 码生成 间接三元式 (1) 间接三元式表: 用来存放各三元式本身。 (2) 间接码表: 按执行各三元式的顺序,依次 列出各三元式在三元式表中的位置。 注意注意 : 间接三元式表中不存放重复的间接三元式表中不存放重复的 三元式。三元式。 第5章 语法制导翻译技术和中间代 码生成 例如 语句 X= (A+B)*C Y= D(A+B) 三元式序列 (1) ( + , A , B ) (2) ( * , (1) , C ) (3) ( = , X , (2) ) (5) ( , D , (4) ) (4) ( + , A , B

11、) (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章 语法制导翻译技术和中间代 码生成 树形表示 A * B + C*D + C * A * BD 末端结点表示一个运算对象, 每一个内 结点表示一个一元或二元运算符。 树形表示是三元式的翻版 (3)+ (1)*(2)* CABD 第5章 语法制导翻译技术和中间代 码生成 四元式四元式主

12、要由四部分组成： （OP，arg1, arg2, result） 其中OP是运算符， arg1,arg2分别是第一和第二两个运算对象。 当OP是一目运算时，常常将运算对象定义 为arg1。 第5章 语法制导翻译技术和中间代 码生成 四元式的第四个分量result是编译程序 为存放中间运算结果而临时引进的变量， 常称为临时变量，如Ti，也可以是用户 自定义变量，如X。 例如 X a*bc/d 的 四元式序列： (1) ( *, a, b, T1 ) (2) ( /, c, d, T2 ) (3) ( +, T1, T2, T3 ) (4) ( =, T3, - -, X ) 第5章 语法制导翻译

13、技术和中间代码生成 2. 四元式之间的联系是通过临时变量实 现的，这样易于调整和变动四元式。 1. 四元式出现的顺序和语法成份的计值 顺序相一致。 四元式的特点： 3. 便于优化处理。 第5章 语法制导翻译技术和中间代 码生成 四元式还可以表示条件的转移 (if ab goto 0) (goto 0) 编译系统中，有时将四元式表示成另一 种更直观，更易理解的形式三地址代 码或三地址语句。 result : arg1 OP arg2 三地址语句三地址语句:语句中是三个量的赋值语句, 每个量占一个地址。 三地址代码形式定义为： 第5章 语法制导翻译技术和中间代 码生成 例如 X a*bc/d 的

14、四元式序列： (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 第5章 语法制导翻译技术和中间代 码生成 例1. a + b * ( c + d )的逆波兰式 a bc d + * + 第5章 语法制导翻译技术和中间代 码生成 t1= a t2= c t3= t2 + d t5= t1+ t4 a + b * ( c + d )的四元式表示 t4= b* t3 第5章 语法制导翻译技

15、术和中间代 码生成 i( i /( i i ) )的逆波兰式 i( i /( i i ) )的四元式 t1= i i t2= i / t1 t3= i t2 i i i i / 例2. 第5章 语法制导翻译技术和中间代 码生成 语义函数 emit（Targ1 OP arg2） 功能是生成一个三地址语句，并送 到输出文件中。 语义函数 newtemp( ) 功能是产生一个新的临时变量名字， 并回送新的临时变量名的整数码。 如T1，T2等。 5.5.1 简单算术表达式和赋值语句的翻译 (2) 不进符号表，临时变量单词值部 分用整数码表示。 (1) 送到符号表。 对临时变量有两种不同的处理方法: 第

16、5章 语法制导翻译技术和中间代 码生成 语义过程 Lookup（） 功能是审查是否出现在符号表中， 在则返回其指针，否则返回NULL。 语义变量 E.place 表示存放非终结符E值的变量名在符号 表中的入口地址或临时变量名的整数码。 第5章 语法制导翻译技术和中间代 码生成 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 ) 第5章 语法

17、制导翻译技术和中间代 码生成 3. E （E(1)） E.place E(1).place； 4. E i p Lookup (); if (p != NULL) E.place p; else error( ); 第5章 语法制导翻译技术和中间代 码生成 5. Ai=E p Lookup (); if (p != NULL) emit(pE.place; ) else error( ); 5.5.2布尔表达式到四元式的翻译 一.布尔表达式的文法 计算逻辑值 程序设计语言中布尔表达式有两个作用: 用作控制语句中的条件式 布尔表达式是由布尔算符(、和) 施于布尔变量或关系

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

19、ue 三. 布尔表达式的翻译方法 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( )； emit (if i (1).place ro

20、p.op i (2).place goto nextq+3); emit ( E.place 0 ); emit ( goto nextq+2); emit ( E.place 1 ); E.place i . place； 5. E i 布尔表达式到四元式的翻译 例如布尔表达式 a = bc d 对应如 下四元式序列: 101 if a = b goto 104 102 t1= 0 103 goto 105 104 t1= 1 105 t2= c d 106 t3 = t1 t2 布尔表达式到四元式的翻译 2. 控制语句中布尔表达式的翻译 条件语句的语法为: 根据条件语句的语义,条件语句的代

21、码结构为: 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为真时控制 流向的转移目标 假出口表示布尔表达式E为假时控制 流向的转移目标 布尔表达式到四元式的翻译 (2) 作为条件转移的E,把E翻译成的代码 是一串条件转或无条件转的四元式 对于E为 a

22、 rop b 的形式生成代码为: if a rop b goto 真出口 goto 假出口 布尔表达式到四元式的翻译 布尔表达式到四元式的翻译 布尔表达式的真、假出口不能在产生其 四元式的同时得知 E.true: 记录表达式 E 所对应的四元式需 回填真出口的四元式的地址所构成的链 E.false: 记录表达式 E 所对应的四元式 需回 填假出口的四元式的地址所构成的链 (3) 设置两个语义变量: 布尔表达式到四元式的翻译 把以 p1, p2为链首的两条链合并为一, 返回合并后的链首 (4) 链结函数和回填函数: merge (p1, p2) : backpatch ( int p, int

23、t ) : 将 p 所链结的每个四元式的第四 区分量都回填 t ; 布尔表达式到四元式的翻译 为及时回填转移地址, 使用语义变量 E. bcode 记录表达式E的第一个四元式 语句序号。 (6) 定义语义变量 nextq 为四元式表指针。 布尔表达式到四元式的翻译 布尔表达式语义动作的设计 1. E E (1) E (2) backpatch( E(1).false, E(2). bcode) ； E. bcode= E(1).bcode ; E.true=merge ( E(1).true, E(2).true ) ; E.false= E(2).false ; 布尔表达式到四元式的翻译 布尔表达式语义动作的设计 2. E E (1) E (2) backpatch( E(1).true, E(2).bcode) ； E.bcode= E(1).bcode ; E.true= E(2).true ; E.false=merge( E(1).false, E(2).false ) ; 布尔表达式语义动作的设计 3. E E (1) E.bcode= E(1).bcode ; E.true=E(1). false ; E.false= E(1). true ; 布尔表达式到四元式的翻译 4. E ( E (1)