《语法制导翻译生成中间代码》由会员分享，可在线阅读，更多相关《语法制导翻译生成中间代码（117页珍藏版）》请在金锄头文库上搜索。
1、1第四章 语法制导翻译生成中间代码语法制导翻译是处理语义的基本方法，它以语法分析为基础， 在语法分析得到语言结构的结果时，对附着于此结构的语 义进行处理，如计算表达式的值、生成中间代码等。 与语法分析部分的讨论不同，本章的内容更注重于实际方法的 讨论。 主要内容包括：1.语法制导翻译的基本概念2.中间代码简介3.符号表简介4.典型声明语句与可执行语句的翻译5.上机： DBMS的设计与实现SQL的执行24.1 语法制导翻译简介F语法与语义1.语法与语义的关系 语法是指语言的结构、即语言的“样子”；语义是指附着于语言 结构上的实际含意 ，即语言的“意义”。语义不能离开语法独立存在；语义远比语法复杂
2、；同一语言结构可包含多种含意，不同语言结构可表示相 同含意；语法与语义之间没有明确的界线。例1 猫吃老鼠与老鼠吃猫，晒被子与晒太阳例2 程序设计语言中的分情况结构34.1 语法制导翻译简介case condition iscase1: stat1;case2: stat2;.end case; 2.语义分析的两个作用检查是否结构正确的句子所表示的意思也合法；执行规定的语义动作，如：表达式求值符号表填写中间代码生成等3.语义分析的方法 语法制导翻译switch (condition) case condition1:stat1; case condition2:stat2; . break; b
3、reak;44.1 语法制导翻译简介F属性与语义规则 1.语法制导翻译的基本思想 通俗地讲，以语法分析为基础，伴随语法分析的各个步骤，执 行相应的语义动作。 具体方法：将文法符号所代表的语言结构的意思，用附着于该文法符 号的属性表示；用语义规则规定产生式所代表的语言结构之间的关系（即 属性之间的关系），即用语义规则实现属性计算。 语义规则的执行：在语法分析的适当时刻（如推导或归约）执 行附着在对应产生式上的语义规则，以实现对语言结构语 义的处理，如计算、查填符号表、生成中间代码、发布出 错信息等。54.1 语法制导翻译简介2.属性的抽象表示 .attr 如：E.val（值），E.type（类型
4、），E.code（代码序列） ， E.place（存储空间）3.对文法的约定 只关注语法分析基础上的语义处理，忽略语法分析。为了 简单，讨论的文法一般为二义文法。默认解决二义的方法 是规定常规意义下的优先级和结合性。4.属性的定义 定义4.1 对于产生式A，其中是由文法符号X1X2.Xn 组成的序列，它的语义规则可以表示为(4.1)所示关于属性 的函数： b := f(c1, c2, ., ck)(4.1)64.1 语法制导翻译简介b := f(c1, c2, ., ck)(4.1) 语义规则中的属性存在下述性质与关系。若b是A的属性，c1, c2, ., ck是中文法符号的属性，或者 A的其
5、它属性，则称b是A的综合属性。若b是中某文法符号Xi的属性，c1, c2, ., ck是A的属性， 或者是中其它文法符号的属性，则称b是Xi的继承属性。称(4.1)中属性b依赖于属性c1, c2, ., ck。若语义规则的形式如下述(4.2)，则可将其想像为产生式左 部文法符号A的一个虚拟属性。属性之间的依赖关系，在 虚拟属性上依然存在。 f(c1, c2, ., ck)(4.2) (4.1)中属性之间的依赖关系，实质上反映了属性计算的先后次 序，即所有属性ci被计算之后才能计算属性b。74.1 语法制导翻译简介F语义规则的两种形式1.语法制导定义 用抽象属性和运算符号表示的语义规则(公式，做
6、什么)2.翻译方案 用具体属性和运算表示的语义规则（程序段，如何做） 语义规则也被习惯上称为语义动作。忽略实现细节，二者作用 等价。语法制导定义适用于设计阶段，翻译方案适用于实 现阶段。84.1 语法制导翻译简介例4.1 将中缀形式的算术表达式转换为后缀表示。其语法制 导定义和翻译方案可分别表示如下。其中print(E.post)是L的 虚拟属性，可以想象为L.p := print(E.post)。翻译方案中的 .lexval表示词法分析返回的记号num的值。产生式语法制导定义翻译方案1翻译方案2L Eprint(E.post)print_post(post);E E1 + E2E.post
7、:= E1.post |E2.post | +;post(k) := +; k := k+1;print(+);E numE.post := num.lexval;post(k) := lexval; k := k+1;print(lexval) ; 语法制导定义：算法 翻译方案：程序实现，方法不唯一94.1 语法制导翻译简介翻译方案中需要考虑的问题：采用什么样的语法分析方法，不同的分析方法对语义处理 的次序不同；为属性分配存储空间；考虑计算次序。 翻译方案1，自下而上计算，LR分析。以3+5+8为例，归约时 翻译。产生式翻译方案1L Eprint_post(post);E E1 + E2 p
8、ost(k) := +; k := k+1;E numpost(k) := lexval; k := k+1;post:(3 5 + 8 +)104.1 语法制导翻译简介3.属性作为分析树的注释 将属性附着在分析树对应文法符号上，形成注释分析树。 例4.2 3+5+8的分析树和注释分析树：产生式语法制导定义翻译方案2L Eprint(E.post)E E1 + E2E.post := E1.post | E2.post | +;print(+);E numE.post := num.lexval;print(lexval);.post=3.post=5.post=8.post=35+.post
9、=35+8+(print(35+8+)114.1 语法制导翻译简介4.注释分析树上看继承属性与综合属性 继承属性是自上而下计算的综合属性是自下而上计算的 提醒：除非特别提醒，本章讨论的语法制导翻译是综合属性。.post=3.post=5.post=8.post=35+.post=35+8+(print(35+8+)12上次课总结F语法制导翻译的基本概念属性与语义规则语义规则的两种形式134.1 语法制导翻译简介FLR分析翻译方案的设计 LR分析中的语法制导翻译实质上是对LR语法分析的扩充：扩充LR分析器的功能：当执行归约产生式的动作时， 也执行产生式对应的语义动作。由于是归约时执行语义 动作，
10、限制语义动作仅能放在产生式右部的最右边；扩充分析栈：增加一个与分析栈并列的语义栈，用于存 放分析栈中文法符号所对应的属性值。例如： EE1+E2 valtop:=valtop+valtop+2; 对于表达式5+3 当归约为左部E时 同时也得到了值814例4.3 3+5*8的语法制导翻译。 产生式 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 #
11、3?5*8#shift #E+E* #3?5?8#shift #E+E*n #3?5?8#En, 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翻译方案 print(valtop); valtop:=valtop+valtop+2; valtop:=valtop*valtop+2; valtop:=lexval; 语法制导定义 print(E.val) E.val:=E1.val+E2.val; E.val:=E1
12、.val*E2.val; E.val:=n.lexval;154.1 语法制导翻译简介F递归下降分析翻译方案的设计 递归下降方法是用程序实现对非终结符的展开和对终结符的匹 配。翻译方案的设计需要解决两个问题：1.如何在递归下降子程序中嵌入语义动作？ 产生式右部的任何位置；2.如何为文法符号的属性设计存储空间？ 函数返回值、参数、变量等。 例如在上机作业中，函数绘图语言解释器语法制导翻译设计：1.递归子程序可以设计为函数，用于返回必要的属性值；2.适当设计子程序中的临时变量，用于保存属性值；3.将语义动作嵌入在子程序的适当位置，正确计算属性值。164.2 中间代码简介1.编译器各阶段的完整输出，
13、均可以被认为是源程序的某 种中间表示。2.本章讨论的是中间代码生成器输出的中间表示，称之为中 间代码。3.中间代码实际上应起一个编译器前端与后端分水岭的作用 。4.要求中间代码具有如下特性，以便于编译器的开发移植 和代码的优化：便于语法制导翻译；既与机器指令的结构相近，又与具体机器无关。5.中间代码的主要形式：树、后缀式、三地址码等。174.2 中间代码简介F后缀式 操作数在前，操作符紧随其后，无需用括号限制运算的优先级 和结合性。 算法4.1 后缀式计算 采用下述过程进行计算，最终结果留在栈中。 x := first_token; while not end_of_exp loopif x
14、in operators thenpush x;- 操作数进栈 elsepop(operators); - 算符，弹出操作数 push(evaluate); - 计算，将结果进栈 end if; next(x); end loop;184.2 中间代码简介loopif x in operators thenpush x;- 操作数进栈 elsepop(operators); - 算符，弹出操作数 push(evaluate); - 计算，将结果进栈 end if; next(x); end loop;算术表达式3+5+8的后缀式为35+8+。 #35+8+#push(3) #35+8+#pus
15、h(3) #35+8+#pop(3和5)，push(3+5) #88+#push(8) #88+#pop(8和8)，push(8+8) #16#194.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 jum
16、p表示无条件转向p2。 与 (1)比较，(2)中的if-then-else被分解，首先计算e，根据e的结 果是否为真，决定计算x还是计算y。204.2 中间代码简介F三地址码1.三地址码的直观表示 语法：result := arg1 op arg2 或 result := op arg1 或 op arg1 语义：结果存放在result中的二元运算arg1 op arg2 结果存放在result中一元运算op arg1 一元运算op arg1 赋值句x := a + b * c的三地址码序列： T1 := b * c T2 := a + T1 x := T2214.2 中间代码简介2.三地址码的种类
