《编译原理第5章(语法制导翻译技术)-1.》由会员分享，可在线阅读，更多相关《编译原理第5章(语法制导翻译技术)-1.（65页珍藏版）》请在金锄头文库上搜索。
1、语义分析的任务： 静态语义审查 审查每个语法结构的静态语义,即 验证语法结构合法的程序,是否真正 有意义。 第5章 语法制导翻译技术和中间代 码生成 5.1 概述 例如: 表达式 A+B*C 对运算对象进行类型检查, 对变 量进行先定义后使用检查 如果静态语义正确, 语义处理则要执 行真正的翻译, 即生成程序的某种中间 代码的形式或直接生成目标代码。 执行真正的翻译 第5章 语法制导翻译技术和中间代 码生成 目前多数编译程序进行语义分析的方 法是采用语法制导翻译法 。它不是一种 形式系统, 但它比较接近形式化。 语法制导翻译法使用属性文法为工具 来描述程序设计语言的语义。 第5章 语法制导翻译
2、技术和中间代 码生成 (1) 属性 对文法的每一个符号, 引进一些属 性, 这些属性代表与文法符号相关的信 息, 如类型、值、存储位置等。与属性 相关的信息, 即属性值,可以在语法分析 过程中计算和传递。 5.2 属性文法 第5章 语法制导翻译技术和中间代 码生成 属性分为两类: 综合属性其计算规则按“自下而上”方式 进行, 即规则左部符号的某些属性根据 其右部符号的属性和(或)自己的其他属 性计算而得。 属性加工的过程即是语义的处理过程。 综合属性和继承属性。 第5章 语法制导翻译技术和中间代 码生成 继承属性其计算规则按“自上而下”方式 进行, 即规则右部符号的某些属性根据 其左部符号的属
3、性和(或)右部其他符号 的某些属性计算而得。 第5章 语法制导翻译技术和中间代 码生成 (2) 属性文法 为文法的每一个规则配备的计算属性 的计算规则, 称为语义规则(描述语义处 理的加工动作) 。 属性文法包含一个上下文无关文法和 一系列语义规则。 语义规则: 第5章 语法制导翻译技术和中间代 码生成 这些语义规则附在文法的每个产生 式上,在语法分析过程中, 执行语义规则 描述的动作, 从而实现语义处理。也就 是说, 附在文法的每个产生式上语义规 则描述了语义处理的加工动作。 目前流行的语义描述和语义处理的 方法主要是属性文法和语法制导翻译方 法。 第5章 语法制导翻译技术和中间代 码生成
4、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章 语法制导翻译技术和中间代 码生成 (2) 语法制导翻译法 在语法分析过程中
5、，依随分析的过程， 根据每个产生式所对应的语义子程序(或 语义规则描述的语义处理的加工动作)进 行翻译的方法。 第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(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章 语法制导翻译技
6、术和中间代 码生成 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 E 5.4 编译中常用的中间代码 : 逆波兰式四元式 三元式树形表示 第5章 语法制导翻译技术和中间代 码生成 逆波兰式 逆波兰式除去了原表达式中的括号， 并将运算对象写
7、在前面，运算符写在后 面，因而又称为后缀式。 例如：逆波兰式 a*bab* (a+b)*(c+d)ab+cd+* 中缀表达式 第5章 语法制导翻译技术和中间代 码生成 逆波兰式表示法同中缀表示法相比其 优点是: 1. 不再有括号,且运算符出现的顺序体 现了中缀表达式 的运算顺序 2. 易于计算机处理 第5章 语法制导翻译技术和中间代 码生成 一般表达式计值时，要处理两类符 号，一类是运算对象，另一类是运算符 ，通常用两个工作栈分别处理。但处理 用逆波兰式表示的表达式却只用一个工 作栈。 第5章 语法制导翻译技术和中间代 码生成 当计算机自左到右顺序扫描逆兰波 式时，若当前符号是运算对象则进栈，
8、 若当前符号是运算符，设为K元运算符 ，则将栈顶的K个元素依次取出，同时 进行K元运算，并将运算结果置于栈顶 ，表达式处理完毕时，其计算结果自然 呈现在栈顶。 第5章 语法制导翻译技术和中间代 码生成 逆波兰式ab+c*的处理过程如下图 ： b aT1 c T1T2 第5章 语法制导翻译技术和中间代 码生成 逆波兰形式可以推广到其他语法结构： 赋值语句 V=E 逆波兰式 VE= 条件语句逆波兰式 if E S1 ; else S2ES1S2￥ 第5章 语法制导翻译技术和中间代 码生成 三元式和树形表示 三元式主要由三部分组成： （OP，arg1, arg2） 其中OP是运算符， arg1,ar
9、g2分别是第一和第二两个运算对象。 当OP是一目运算时，常常将运算对象定 义为arg1。 第5章 语法制导翻译技术和中间代 码生成 例如 a+b*c 的 三元式序列： (1) ( * , b , c ) (2) ( + , a , (1) ) 运算对象是指向符号表的某一项或指向 三元式表的某一项。 第5章 语法制导翻译技术和中间代 码生成 1. 三元式出现的顺序和语法成份的 计值顺序相一致。 三元式的特点： 2. 三元式之间的联系是通过指示器 实现的。 第5章 语法制导翻译技术和中间代 码生成 间接三元式 (1) 间接三元式表: 用来存放各三元式本身。 (2) 间接码表: 按执行各三元式的顺序
10、,依次 列出各三元式在三元式表中的位置。 注意 : 间接三元式表中不存放重复的 三元式。 第5章 语法制导翻译技术和中间代 码生成 例如 语句 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
11、 , (2) ) (4) ( , D , (1) ) (5) ( = , Y, (4) ) 第5章 语法制导翻译技术和中间代 码生成 树形表示 A * B + C*D + C * A * BD 末端结点表示一个运算对象, 每一个内 结点表示一个一元或二元运算符。 树形表示是三元式的翻版 (3)+ (1)*(2)* CABD 第5章 语法制导翻译技术和中间代 码生成 四元式主要由四部分组成： （OP，arg1, arg2, result） 其中OP是运算符， arg1,arg2分别是第一和第二两个运算对象。 当OP是一目运算时，常常将运算对象定义 为arg1。 第5章 语法制导翻译技术和中间代
12、码生成 四元式的第四个分量result是编译程序 为存放中间运算结果而临时引进的变量 ，常称为临时变量，如Ti，也可以是用 户自定义变量，如X。 例如 X a*bc/d 的 四元式序列 ：(1) ( *, a, b, T1 ) (2) ( /, c, d, T2 ) (3) ( +, T1, T2, T3 ) (4) ( =, T3, -, X ) 第5章 语法制导翻译技术和中间代码生成 2. 四元式之间的联系是通过临时变量实 现的，这样易于调整和变动四元式。 1. 四元式出现的顺序和语法成份的计值 顺序相一致。 四元式的特点： 3. 便于优化处理。 第5章 语法制导翻译技术和中间代 码生成
13、四元式还可以表示条件的转移 (if ab goto 0) (goto 0) 编译系统中，有时将四元式表示成另一 种更直观，更易理解的形式三地址代 码或三地址语句。 result : arg1 OP arg2 三地址语句:语句中是三个量的赋值语句, 每个量占一个地址。 三地址代码形式定义为： 第5章 语法制导翻译技术和中间代 码生成 例如 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
14、 （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章 语法制导翻译技术和中间代 码生成 i( i /( i i ) )的逆波兰式 i( i /( i i ) )的四元式 t1= i i t2= i / t1 t3= i t2 i i i i / 例2. 第5章 语法制导翻译技术和中间代 码生成 语义函数 em
15、it（Targ1 OP arg2） 功能是生成一个三地址语句，并送 到输出文件中。 语义函数 newtemp( ) 功能是产生一个新的临时变量名字 ，并回送新的临时变量名的整数码 。如T1，T2等。 5.5.1 简单算术表达式和赋值语句的翻译 (2) 不进符号表，临时变量单词值部 分用整数码表示。 (1) 送到符号表。 对临时变量有两种不同的处理方法: 第5章 语法制导翻译技术和中间代 码生成 语义过程 Lookup（i.name） 功能是审查i.name是否出现在符号表中， 在则返回其指针，否则返回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章 语法制导翻译技术和中间代 码生成 3. E （E(1)）
