语法制导翻译生成中间代码培训

《语法制导翻译生成中间代码培训》由会员分享，可在线阅读，更多相关《语法制导翻译生成中间代码培训（41页珍藏版）》请在金锄头文库上搜索。

1、第四章 语法制导翻译生成中间代码语法制导翻译是处理语义的基本方法，它以语法分析为 基础，在语法分析得到语言结构的结果时，对附着于此结构 的语义进行处理，如计算表达式的值、生成中间代码等。与语法分析部分的讨论不同，本章的内容更注重于实际 方法的讨论。主要内容包括：语法制导翻译的基本概念中间代码简介符号表简介典型声明语句与可执行语句的翻译上机作业第三部分：语法制导翻译绘制函数图形14.1 语法制导翻译简介 4.1.1 语法与语义语法与语义的关系语法是指语言的结构、即语言的“样子”；语义是指附着于 语言结构上的实际含意 ，即语言的“意义”。 对于语法和语义： 语义不能离开语法独立存在； 语义远比语法

2、复杂； 同一语言结构可包含多种含意，不同语言结构表示相同含意； 语法与语义之间没有明确的界线。 例1：猫吃老鼠与老鼠吃猫 例2：程序设计语言中的分情况结构： 1case condition iscase1: stat1;case2: stat2;.end case; 2switch (condition) case condition1:stat1; case condition2:stat2; . break; break;24.1.1 语法与语义（续1）语义分析的两个作用检查是否结构正确的句子所表示的意思也合法；执行规定的语义动作，如： 表达式求值 符号表填写 中间代码生成等语义分析的方法

3、语法制导翻译34.1.2 属性与语义规则 语法制导翻译的基本思想 通俗地讲：以语法分析为基础，伴随语法分析的各个步骤， 执行相应的语义动作。 具体方法： 1.将文法符号所代表的语言结构的意思，用附着于该文法符 号的属性表示； 用语义规则规定产生式所代表的语言结构之间的关系（即 属性之间的关系），即用语义规则实现属性计算。语义规则的执行：在语法分析推导或归约的每一步骤中，执行 附着在对应产生式上的语义规则，实现对语义的处理，如查添 符号表、生成中间代码、发布错误信息等。44.1.2 属性与语义规则（续1）属性的抽象表示 .attr 例如：E.val（值） E.type（类型） E.code（代码

4、序列） E.place（存储空间）对文法的约定本章关注的是语法分析的基础上的语义处理，忽略语法 分析。为了简单，本章的文法一般为二义文法。默认解决二义 的方法是规定常规意义下的优先级和结合性。54.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是中某文法符号Xi的属性，c1,

5、c2, ., ck是A的 属性，或者是中其它文法符号的属性，则称b是Xi的继承属性。(3) 称(4.1)中属性b依赖于属性c1, c2, ., ck。(4) 若语义规则的形式如下述(4.2)，则可将其想像为产生式左 部文法符号A的一个虚拟属性。属性之间的依赖关系，在虚拟属性 上依然存在。f(c1, c2, ., ck) (4.2) (4.1)中属性之间的依赖关系，实质上反映了属性计算的先后 次序，即所有属性ci被计算之后才能计算属性b。 EE1+E2 E.val:=E1.val+E2.valEE1+E2 print(E.val)属性的定义*64.1.3 语义规则的两种形式 语法制导定义用抽象的

6、属性和运算符号表示的语义规则；(公式，做什么)翻译方案用具体属性和运算表示的语义规则。（程序段，如何做） 语义规则也被习惯上称为语义动作。 忽略实现细节，二者作用等价。（设计与实现）74.1.3 语义规则的两种形式（续1）例4.1 将中缀形式的算术表达式转换为后缀表示的语法制导定义和翻 译方案。虚拟属性print(E.post)可想象为L.p:=print(E.post)。 产生式 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; 翻译方案中需要考虑的问题： 1采用什么样的语法分析方法； 2为属性分配存储空间； 3考虑计算次序。 产生式 翻译方案2 LE EE1+E2 print(+); Enum print(lexval); 语法制导定义算法 翻译方案程序实现，多种方法翻译方案1，自下而上计算，LR分析。 （以3+5+8为例，归约时翻译）post:(3 5 + 8 +)84.1.3 语义规则的两种形式（续2）属性作为分析树的注释 将属性附着在分析树对应文法符号上，形成注释分析树。 产生式 语法制导定义 翻译方案 LE print(E.

8、post); EE1+E2 E.post:=E1.post print(+);|E2.post|+; Enum E.post:=num.lexval; print(lexval); 例4.2 3+5+8的分析树和注释分析树： .post=3.post=5.post=8.post=35+.post=35+8+(print(35+8+)94.1.3 语义规则的两种形式（续3）继承属性是自上而下计算的综合属性是自下而上计算的 提醒：除非特别提醒，本章讨论的语法制导翻译是综合属性。注释分析树上看继承属性与综合属性 104.1.4 LR分析翻译方案的设计 LR分析中的语法制导翻译实质上是对LR语法分析的

9、扩充：扩充LR分析器的功能：当执行归约产生式的动作时，也执 行产生式对应的语义动作。由于是归约时执行语义动作，因此 限制语义动作仅能放在产生式右部的最右边；扩充分析栈：增加一个与分析栈并列的语义栈，用于存放 分析栈中文法符号所对应的属性值。 例如： EE1+E2 valtop:=valtop+valtop+2; 对于表达式： 5+3当归约为左部E时， 同时也得到了值8。114.1.4 LR分析翻译方案的设计（续1）例4.3 3+5*8的语法制导翻译。 语法制导定义 print(E.val) E.val:=E1.val+E2.val; E.val:=E1.val*E2.val; E.val:=n

10、.lexval;翻译方案 print(valtop); valtop:=valtop+valtop+2; valtop:=valtop*valtop+2; valtop:=lexval; 产生式 LE EE1+E2 EE1*E2 En分析栈 语义栈输入 语义动作 # # 3+5*8#shift #n #3 +5*8#En，valtop:=lexval #E #3 +5*8#shift #E+ #3? 5*8#shift #E+n #3?5 *8#En，valtop:=lexval #E+E #3?5 *8#shift #E+E* #3?5? 8# shift #E+E*n #3?5?8 # E

11、n，valtop:=lexval #E+E*E #3?5?8 # EE1*E2; valtop:=valtop*valtop+2; #E+E #3?40 # EE1+E2，valtop:=valtop+valtop+2; #E #43 #acc 124.1.5 递归下降分析翻译方案的设计 递归下降方法是用程序实现对非终结符的展开和对终结符 的匹配。翻译方案的设计需要解决两个问题： 1如何在递归下降子程序中嵌入语义动作：产生式右部的任何位置； 2如何为文法符号的属性设计存储空间：函数返回值、参数、变量等。 例 函数绘图语言的解释器中语法制导翻译的设计： 1.递归子程序可以设计为函数，用于返回必要

12、的属性值； 2. 适当设计子程序中的临时变量，用于保存属性值； 3. 将语义动作嵌入在子程序的合适位置，正确计算属性值。 （第三次上机课介绍）阅读： 95页的例4.4134.2. 中间代码简介 1.编译器各阶段的完整输出，均可以被认为是源程序的某 种中间表示。 2. 本章讨论的是中间代码生成器输出的中间表示，称之为 中间代码。 3. 中间代码实际上应起一个编译器前端与后端分水岭的作 用。 4. 要求中间代码具有如下特性，以便于编译器的开发移植 和代码的优化： 便于语法制导翻译； 既与机器指令的结构相近，又与具体机器无关。 5. 中间代码的主要形式：树、后缀式、三地址码等。 144.2.1 后缀

13、式 后缀式的特征操作数在前，操作符紧随其后，无需用括号限制运算的 优先级和结合性。计算后缀式的虚拟机 算法4.1 后缀式计算 输入 后缀式 输出 计算结果 方法 采用下述过程进行计算，最终结果留在栈中。 x := first_token; while not end_of_exp loop next(x); end loop; if x in operators then push x; - 操作数进栈 else pop(operators); - 算符，弹出操作数push(evaluate); - 计算，并将结果进栈 end if;154.2.1 后缀式（续1）算术表达式3+5+8的后缀式为

14、35+8+。 算法4.1的计算： （#35+8+#进栈） （#3 5+8+#进栈） （#35 +8+#pop(3和5)，push(3+5)） （#8 8+#进栈） （#88 +#pop(8和8)，push(8+8)） （#16 # ）x := first_token; while not end_of_exp loop if x in operatorsthen push x; - 操作数进栈else pop(operators); - 算符，弹出操作数push(evaluate); - 计算，并将结果进栈end if;next(x); end loop; 后缀式计算164.2.1 后缀式（续

15、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:(2) 其中： p1和p2分别是标号； p1 jez表示e的结果为0（假）则转向p1； p2 jump表示无条件转向p2。 与 (1)比较，(2)中的if-then-else被分解，首先计算e，根 据e的结果是否为真，决定计算x还是计算y。 将后缀式推广到其他语句174.2.2 三地址码 三地址码的直观表示 语法： 语义：例如： 赋值句x := a + b * c的三地址码序列： T1 := b * c T2 := a + T1 x := T2 注意：直观表示与源程序中赋值句的区别。result := arg1 op arg2 或 result := op ar