《语法制导翻译生成中间代码》由会员分享,可在线阅读,更多相关《语法制导翻译生成中间代码(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.三地址码的种类