华东师范大学计算机科学技术系

《华东师范大学计算机科学技术系》由会员分享，可在线阅读，更多相关《华东师范大学计算机科学技术系（119页珍藏版）》请在金锄头文库上搜索。

1、第五章 语法制导翻译和中间代码 生成 5.1 概述 语义分析包含静态语义检查和语义识别，并在此 基础上对源程序（单词串形式）进行等价转换， 转换为中间代码（目标代码）。 在后面的讨论中总是认为词法、语法分析已经完 成，读入的是（语法正确）句子！而不关心用什 么方法进行语法分析的（以后主要讨论自底向上 的句法分析方法），关心的是如何在语法分析的 同时正确地插入语义子程序进行翻译（语法制导 翻译） 。Date1华东师范大学计算机科学技术系一、静态语义检查 称在编译时刻进行的语义检查为静态语义检查， 通常可包含如下内容： 类型检查。 检查运算的合法性和参与运算的运算分量类型的 一致性（相容性）。必要

2、时进行相应的类型转换 。 (2) 控制流检查。 以保证控制语句有合法的转向点，如C语言中的 break语句，需寻找包含它的最小的switch、while 或for语句，方可找到转向点，否则出错。不允许 循环外控制转入循环内。Date2华东师范大学计算机科学技术系(3) 有关名字的匹配检查。 可以对某些程序段命名，该名字出现在程序段的 开始和结束处，如同语句括号一般，应检查它们 的配对。 (4) 一致性检查。 如在相同作用域中标识符只能说明一次（重复定 义），case语句的标号不能相同，枚举类型的元 素不能重复，没有定义数据类型等。Date3华东师范大学计算机科学技术系二、语法制导翻译 例1：对

3、算术表达式文法G的一个翻译方案 +print “1” print “2” * print “3” print “4” ()print “5” iprint “6” 其中 括起的称为该产生式的语义子程序。 对输入串W=(i+i)*i则W是G的一个句子。Date4华东师范大学计算机科学技术系 若采用自底向上的句法分析， 规定当用产生式归约时 ，调用相应的语义子程序，则 翻译结束后输出 64264154632。 若采用自顶向下的句法分析， 规定当用产生式推导时 ，调用相应的语义子程序，则 翻译结束后输出 23451246466。 应根据输出（翻译）目标，配 备适当的语义子程序，这就是 所要做的工作。

4、*)(+iiiDate5华东师范大学计算机科学技术系三、翻译要解决的问题 翻译成什么样的目标语言的代码？ 将源语言程序翻译成中间语言的程序。中间语言 与机器无关，而语句颗粒度又与机器语言相当， 于是带来了诸多好处： 编译逻辑结构简单明确，与机器相关的工作集 中到目标代码生成阶段，难度和工作量下降； 便于移植和维护。 利于优化，代码优化将分成与机器无关的中间 代码优化及与机器相关的目标代码优化两个阶段 ，使优化更有效。Date6华东师范大学计算机科学技术系2. 何时进行这种翻译？ 如例1所示，如果作为句柄所对应的产生式，都配 有一个相应的翻译子程序，则每当按句柄归约时 ，就调用相应的翻译子程序（

5、语义子程序）完成 局部的翻译，则一个句子，一段代码，按它们的 归约次序，将所有翻译子程序依次执行，就完成 了这个句子、这段代码的翻译。这种翻译与语法 分析紧密相关，称之为语法制导翻译：每当归约 时，调用相应的语义子程序，这就是翻译的时机 。Date7华东师范大学计算机科学技术系3. 如何实现这种翻译？ 语法制导翻译的关键，是为每个产生式编写翻译 子程序。例1中产生式所带有的这种语义子程序只 能输出这类数字串。现在，要对一个有穷表示的 文法的无穷多个语句，按所给出的语义子程序要 完成不同语句的翻译任务，输出各自的目标代码 。难点自然就集中在如何写这些语义子程序了。 采用属性翻译文法（属性文法），

6、这是一种形式 化的语义分析方法。Date8华东师范大学计算机科学技术系结论 语法制导的翻译方法就是在语法分析的同时（制 导下）插入一系列的语义动作（由语义子程序提 供），将源程序（单词形式）翻译成等价的中间 代码。 主要考虑自底向上句法分析的方法（在归约时调 用语义子程序），设计翻译方案（形成属性文法 ）。Date9华东师范大学计算机科学技术系5.2 中间语言 常见的中间语言有很多种，一般可单独或混合使用。 一、后缀表示（逆波兰表示） 是由波兰数学家卢卡西维奇(Lukasiewicz)提出的。它 是将a op b中运算量a、b依次写在算符op之前，即a b op，可以形式地给出表达式E的后缀表

7、示的递归定义 ： (1) 如果E是变量或常数，则E的后缀表示即E本身。 (2) 如果E为E1 op E2形式，则它的后缀表示为E1 E2 op ， 其中op是二元算符，E1，E2分别是E的后缀表示 (op为一元运算时E2为空)。 (3) 如果E为(E1)形式，则E1后缀表示即为E的后缀表示。Date10华东师范大学计算机科学技术系 后缀表示可以机械地计算。 中缀表示可以机械地转换为后缀表示。（ E.W.Dijkstra) 例2： (-a*b+c)-d的后缀表示为：a b* uminus c+d- 其中uminus表示一元运算-。 后缀表示的推广： O1，O2，On，其中是n元的运算符， Oi为

8、运算对象 i=1,2n。 假定：后缀表示存放在一维数组S中，Si是一个 单词Date11华东师范大学计算机科学技术系 例3：赋值语句 := 若V，E分别为 、的后缀表示，赋值语句的后缀表示为： V E:= 如：A:=B*C+D则为 ABC*D+:= 例4：条件语句 ifthenelse的后缀表 示为：E i1 BZ S1 i2 BR S2 其中： E, S1, S2分别是，的后 缀表示。i1是S2的首符号在S数组中的下标i2是S2的尾符号在S数组中的下标加1BZ是运算符表示“零转”BR是运算符表示“无条件转”Date12华东师范大学计算机科学技术系 试将语句if 5 then :=a;else

9、 :=b;表示成逆波兰表 示 引入二元运算符BZ、一元运算符BR。逆波兰表示 T,i,BZ的含义为若T的值为零，则转到位置为i处执行 。i,BR的含义为无条件转移到位置i处执行。假定上述语句的逆波兰表示存放在一维数组S中，用 数组的下标表示转向的位置。S数组可描述为： 511 BZa:= 14 BR b:=1 234567891011 121314Date13华东师范大学计算机科学技术系二、图(树、抽象句法树）表示 通过对分析树的简化得到 例5：对算术表达式文法G，输入串W=(i+i)*i 的分析树见前。而树表示为：反映了一种运算顺序 内结点表示运算及运算结果 见P82。亦可以使用无环路有向图

10、dag(directed acyclic graph)。*+iiiDate14华东师范大学计算机科学技术系三、三地址代码 三地址代码语句的一般形式为：:=y op z其中、y和z为名字、常量或编译时产生的临时变 量，op为运算符如定点运算符、浮点运算符、逻 辑运算符等。由于三地址语句只含一个运算符， 故多个算符组成的表达式必须用三地址语句序列 表示。 例如表达式+y*z的三地址代码为：t1:=y*zt2:=+t1其中t1和t2是编译时需要的临时变量。 Date15华东师范大学计算机科学技术系 三地址语句通常包含三个地址，两个用来存放运 算对象，一个用来存放运算结果。在实现时，用 户定义的名字将

11、由指向符号表中该名字项的指针 所代替。Date16华东师范大学计算机科学技术系四、三地址语句的种类 三地址语句有多种表示形式，常见的有： :=y op z赋值语句，其中op为二目的算术运算符或逻辑运 算符。(2) :=op y赋值语句，其中op为一目运算符，如一目减 uminus，逻辑否定not，移位算符及将定点数转换 成浮点数的类型转换符。(3) :=y复写语句，将y的值赋给。Date17华东师范大学计算机科学技术系(4) goto L 无条件转移语句，下一个将被执行的语句是标号 为L的语句。(5) if relop y goto L 或 if goto L 条件转移语句, relop为关系

12、运算符如、 =等，若和y满足关系relop就转而执行标号为L 的语句，否则顺序执行本语句的下一语句。Date18华东师范大学计算机科学技术系(6) param 和 call P，n过程调用语句，源程序中的过程调用语句call P(1, 2, , n)可以用下列三地址代码表示：param 1param 2param ncall P, n其中整数n为实参个数。过程返回语句为return y，其中y为返回值。Date19华东师范大学计算机科学技术系(7) 变址赋值：:=yi，表示将从地址y开始的第i个地址单元的值 赋给。i:=y，表示将y的值赋给从地址开始的第i个地 址单元。(8) 地址和指针赋值：

13、:= 1id, 2 2.dtype:=1.dtype; set_type(id.p, 1.dtype); id set_type(id.p, .dtype); 属性.dtype是继承属性 。Date41华东师范大学计算机科学技术系例2. S-属性翻译文法的例子 将中缀表达式翻译为抽象语法树的翻译文法。 简单算术表达式文法G ： 1+ .ptr:=Node(+,1.ptr,.ptr .ptr:= .ptr 1* .ptr:=Node(*,1.ptr,.ptr .ptr:= .ptr ().ptr:= .ptr c .ptr:=Node(/,c.class,c.value 其中属性.ptr的值是树

14、结点的地址，函数Node(,y,z) 的功能是：申请一块空间，将、y、z写入，并返回 该空间的首地址。 Date42华东师范大学计算机科学技术系 对单词串（c.3+c.9)*(c.2+c.15)经过分析与翻译后 转换为：*+c.3c.9c.2c.15Date43华东师范大学计算机科学技术系说明 在本章的讨论中，总使用S-属性翻译文法，采用 自底向上的句法分析（不关心用哪种方法）。主要的工作是：设计文法符号带有的综合属性；编制语义子程序 。翻译的目标是：三地址代码。 2. 为了实现这种翻译方法，要求： 词法分析程序在返回所识别的单词时，总带有 一个值（该值是数值或符号表中该单词（标识 符）所在的

15、地址或该单词的内部码）。Date44华东师范大学计算机科学技术系 句法分析时遵循： i)将非终结符移入栈时，将其所带的属性一起 入栈。 ii)使用产生式归约后，调用与该产生式相关的语 义子程序。3. 注意：“当非终结符出现在栈顶，那么与该非结 符有关的中间代码已经生成” 。为什么？Date45华东师范大学计算机科学技术系习题 P129，习题5 5.1 5.2Date46华东师范大学计算机科学技术系5.4 说明语句一、增加存储地址分配的说明语句的翻译方案 对说明语句a,b,c:real 语义为：设编译程序用于存储地址分配的变量是offset，将 标识符id的数据类型及由offset指出的存储地址送 入符号表相应的登记项中。 考虑文法G: ;|i:|i, int|real|arraynumof|Date47华东师范大学计算机科学技术系 令属性.type、.width分别表示数据类型和 该类型所需的存储字节数，i.name表示变量名（ 地址），num.val表示数值。 设过程enter(,y,z)的功能为：将y,z送入所指出的 地址中。 属性翻译文法为： - offset:=0 ; - i:enter(i.name,.type,offset);offset:=offset+.width