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