《编译原理-语法制导翻译生成中间代码》由会员分享，可在线阅读，更多相关《编译原理-语法制导翻译生成中间代码（59页珍藏版）》请在金锄头文库上搜索。
1、第四章 语法制导翻译生成中间代码语法制导翻译是处理语义的基本方法，它以语法分析为 基础，在语法分析得到语言结构的结果时，处理附着于此结 构上的语义，如计算表达式的值、生成中间代码等。与语法分析部分的讨论不同，本章的内容更注重于实际 方法的讨论。 主要内容包括：语法制导翻译的基本概念中间代码简介符号表简介典型声明语句与可执行语句的翻译上机作业第三部分（略）14.1 语法制导翻译简介 4.1.1 语法与语义语法与语义的关系语法是指语言的结构、即语言的“样子”；语义是指 附着于语言结构上的实际含意 ，即语言的“意义”。对于语法和语义： 语义不能离开语法独立存在； 语义远比语法复杂； 同一语言结构可包
2、含多种含意，不同语言结构可表 示相同含意； 语法与语义之间没有明确的界线。 24.1.1 语法与语义（续1）例1：猫吃老鼠与老鼠吃猫 例2：程序设计语言中的分情况结构：1case condition iscase1: stat1;case2: stat2;.end case; 2switch (condition) case c1:stat1; case c2:stat2; . break; break;34.1.1 语法与语义（续2）检查是否结构正确的句子所表示的意思也合法；执行规定的语义动作，如： 表达式求值 符号表填写 中间代码生成等语义分析的方法语法制导翻译语义分析的两个作用44.1.
3、2 属性与语义规则 语法制导翻译的基本思想 通俗地讲：以语法分析为基础，伴随语法分析的各个步骤， 执行相应的语义动作。 具体方法： 1.将文法符号所代表的语言结构的意思，用附着于该文法符 号的属性表示； 用语义规则规定产生式所代表的语言结构之间的关系（即 属性之间的关系），即用语义规则实现属性计算。 1.语义规则的执行：在语法分析的适当时刻（如推导或归约）执行附着在对 应产生式上的语义规则，以实现 对语言结构语义的处理，如 计算表达式的值、查填符号表、生成中间代码、发布出错信 息等。54.1.2 属性与语义规则（续1）属性的抽象表示：.attr 例如：E.val（值） E.type（类型） E
4、.code（代码序列） E.place（存储空间）对文法的约定 本章关注的是语法分析基础上的语义处理，忽略语 法分析。 为了简单，本章的文法一般为二义文法。默认解决 二义的方法是规定常规意义下的优先级和结合性。64.1.2 属性与语义规则（续2）定义4.1 对于产生式A，其中是由文法符号X1X2.Xn组成 的序列，它的语义规则可以表示为(4.1)所示关于属性的函数：b := f(c1, c2, ., ck) (4.1) 语义规则中的属性存在下述性质与关系。(1) 若b是A的属性，c1, c2, ., ck是中文法符号的属性， 或者A的其它属性，则称b是A的综合属性。(2) 若b是中某文法符号X
5、i的属性，c1, c2, ., ck是A的 属性，或是中非Xi的文法符号的属性，则称b是Xi的继承属性。(3) 称(4.1)中属性b依赖于属性c1, c2, ., ck。(4) 若语义规则的形式如下述(4.2)，则可将其想像为产生式左 部文法符号A的一个虚拟属性。属性之间的依赖关系，在虚拟属性 上依然存在。f(c1, c2, ., ck) (4.2) 属性的定义*74.1.2 属性与语义规则（续2）EE1+E2 E.val:=E1.val+E2.valE的属性.val由E1和E2的相应属性计算而来，因此我们说E 的属性依赖于E1和E2的属性。简单讲，属性之间的计算构成了语义规则，计算的先后 次
6、序被称为属性的依赖关系。例如：84.1.3 语义规则的两种形式 语法制导定义用抽象的属性和运算表示的语义规则；(公式，做什么)翻译方案用具体的属性和运算表示的语义规则。(程序段，如何做) 语义规则也被习惯上称为语义动作。 忽略实现细节，二者作用等价。（设计与实现）94.1.3 语义规则的两种形式（续1）例4.1 将中缀形式的算术表达式转换为后缀表示的语法制 导定义和翻译方案。产生式 LE EE1+E2Enum 语法制导定义 print(E.post) E.post:=E1.post|E2.post|+; E.post:=num.lexval; 翻译方案1 print_post(post); p
7、ost(k):=+; k:=k+1;post(k):=lexval; k:=k+1; 产生式 翻译方案2 LE EE1+E2 print(+); Enum print(lexval); 虚拟属性：print(E.post) 可想象为：L.p:=print(E.post)104.1.3 语义规则的两种形式（续2）翻译方案1，自下而上计算，LR分析。 （以3+5+8为例，归约时翻译）post:(3 5 + 8 +)翻译方案中需要考虑的问题： 1采用什么样的语法分析方法； 2为属性分配存储空间； 3考虑计算次序。 语法制导定义算法 翻译方案程序实现，方法不唯一产生式翻译方案1 LE print_po
8、st(post); EE1+E2 post(k):=+; k:=k+1; Enum post(k):=lexval; k:=k+1; 产生式 翻译方案2 LE EE1+E2 print(+); Enum print(lexval); 114.1.3 语义规则的两种形式（续3）属性作为分析树的注释将属性附着在分析树对应文法符号上，形成注释分析树。 产生式 语法制导定义 翻译方案LE print(E.post); EE1+E2 E.post:=E1.post|E2.post|+; print(+); Enum E.post:=num.lexval; print(lexval); 例4.2 3+5+
9、8的分析树和注释分析树： .post=3.post=5.post=8.post=35+.post=35+8+(print(35+8+)124.1.3 语义规则的两种形式（续4）继承属性是自上而下计算的综合属性是自下而上计算的 提醒：除非特别提醒，本章讨论的语法制导翻译是综合属性。注释分析树上看继承属性与综合属性 134.1.4 LR分析翻译方案的设计LR分析中的语法制导翻译实质上是对LR语法分析的扩充： 1.扩充LR分析器的功能：当执行归约产生式的动作时， 也执行产生式对应的语义动作。由于是归约时执行语 义动作，因此限制语义动作仅能放在产生式右部的最 右边； 2. 扩充分析栈：增加一个与分析栈
10、并列的语义栈，用于 存放分析栈中文法符号所对应的属性值。 144.1.4 LR分析翻译方案的设计（续1）例如： EE1+E2 valtop:=valtop+valtop+2; 对于表达式： 5+3当归约为左部E时， 同时也得到了值8。154.1.4 LR分析翻译方案的设计（续2） 例4.3 3+5*8的语法制导翻译。 翻译方案 print(valtop); valtop:=valtop+valtop+2; valtop:=valtop*valtop+2; valtop:=lexval; 产生式 LE EE1+E2 EE1*E2 En语法制导定义 print(E.val) E.val:=E1.v
11、al+E2.val; E.val:=E1.val*E2.val; E.val:=n.lexval;164.1.4 LR分析翻译方案的设计（续3）（格局的变化） 分析栈 语义栈输入 语义动作 # # 3+5*8#shift #n # +5*8#En， valtop:=lexval #E #3 +5*8#shift #E+ #3? 5*8#shift #E+n #3? *8#En， valtop:=lexval #E+E #3?5 *8#shift #E+E* #3?5? 8# shift #E+E*n #3?5? # En， valtop:=lexval #E+E*E #3?5?8 # EE1*
12、E2; valtop:=valtop*valtop+2; #E+E #3?40 # EE1+E2，valtop:=valtop+valtop+2; #E #43 #acc 174.1.5 递归下降分析翻译方案的设计递归下降方法是用程序实现对非终结符的展开和对终 结符的匹配。翻译方案的设计需要解决两个问题： 1如何在递归下降子程序中嵌入语义动作：产生式右部的任何位置； 2如何为文法符号的属性设计存储空间：函数返回值、参数、变量等。 例如函数绘图语言解释器语法制导翻译设计(E表达式) ： 1.递归子程序可以设计为函数，用于返回必要的属性值； 2. 适当设计子程序中的临时变量，用于保存属性值； 将语
13、义动作嵌入在子程序的适位置，正确计算属性值。 阅读： 教材的例4.4184.2. 中间代码简介 1.编译器各阶段的完整输出，均可以被认为是源程序的 某种中间表示。 2. 本章讨论的是中间代码生成器输出的中间表示，称之 为中间代码。 3. 中间代码实际上应起一个编译器前端与后端分水岭的 作用。 4. 要求中间代码具有如下特性，以便于编译器的开发移 植和代码的优化： 便于语法制导翻译； 既与机器指令的结构相近，又与具体机器无关。 5. 中间代码的主要形式：树、后缀式、三地址码等。 194.2.1 后缀式 后缀式的特征操作数在前，操作符紧随其后，无需用括号限制运算的 优先级和结合性。例如：中缀式3+
14、5*2/7 (3+5)*(2/7)后缀式352*7/+ 35+27/*20计算后缀式的虚拟机 算法4.1 后缀式计算 输入 后缀式 输出 计算结果 方法 采用下述过程进行计算，最终结果留在栈中。 x := first_token; while not end_of_exp loop next(x); end loop; if x in operands then push x; - 操作数进栈 else pop(operands); - 算符，弹出操作数push(evaluate); - 计算，并将结果进栈 end if;214.2.1 后缀式（续1）算术表达式3+5+8的后缀式为35+8+。
15、 （#35+8+#pushu(3)） （#3 5+8+#pushu(5) ） （#35 +8+#pop(3和5)，push(3+5)） （#8 8+#pushu(8) ） （#88 +#pop(8和8)，push(8+8)） （#16 # ）x := first_token; while not end_of_exp loop if x in operandsthen push x; - 操作数进栈else pop(operands); - 算符，弹出操作数push(evaluate); - 计算，并将结果进栈end if;next(x); end loop; 后缀式计算224.2.1 后缀式（续2）对语句： if e then x else y后缀式可以写为：e x y if-then-else(1) 上述表示中，e、x和y均需计算。 而实际上，根据条件e的取值，x和y不能都计算： e p1 jez x p2 jump p1: y p2:
