编译原理语法制导翻译和中间代码生成

《编译原理语法制导翻译和中间代码生成》由会员分享，可在线阅读，更多相关《编译原理语法制导翻译和中间代码生成（16页珍藏版）》请在装配图网上搜索。

1、编译程序的任务是把源程序翻译成目标程序，这个目标程序必须和源程序的语义等同，也就是说， 尽管它们的语法结构完全不同，但它们所表达的结果应完全相同。通常，在词法分析程序和语法分 析程序对源程序的语法结构进行分析之后，要么由语法分析程序直接调用相应的语义子程序进行语 义处理，要么首先生成语法树或该结构的某种表示，再进行语义处理。编译中的语义处理是指两个功能：第一，审查每个语法结构的静态语义，即验证语法结构合法 的程序是否真正有意义。第二，如果静态语义正确，语义处理则要执行真正的翻译，即，要么生成 程序的一种中间表示形式（中间代码），要么生成实际的目标代码。为什么有的编译程序直接生成目标代码，有的编

2、译程序采用中间代码，所谓中间代码，也称中 间语言，是复杂性介于源程序语言和机器语言的一种表示形式。一般，快速编译程序直接生成目标 代码，没有将中间代码翻译成目标代码的额外开销。但是为了使编译程序结构在逻辑上更为简单明 确，常采用中间代码，这样可以将与机器相关的某些实现细节置于代码生成阶段仔细处理，并且可 以在中间代码一级进行优化工作使得代码优化比较容易实现。本章重点：属性文法、语法制导翻译方法的基本思想、几种典型的中间代码形式、一些语法成 分的翻译工作。E Ti.t = T2.t Ti.t=int第七章 语法制导翻译和中间代码生成第一节属性文法现在很多编译程序采用语法制导翻译方法。这仍不是一种

3、形式系统，但它是比较接近形式化的。 这种方法使用属性文法为工具来说明程序设计语言的语义。一个属性文法包含一个上下文无关文法 和一系列语义规则，这些语义规则附在文法的每个产生式上，在语法分析过程中，完成附加在所使 用的产生式上的语义规则描述的动作，从而实现语义处理。首先简单介绍属性文法。属性，常用以描述事物或人的特征、性质、品质等等。比如，谈到一个物体，可以用“颜色” 描述它，谈起某人，可以使用“有幽默感”来形容他。对编译程序使用的语法树的结点，可以用“类 型”、“值”或“存储位置”来描述它。形式上讲，一个属性文法是一个三元组，A=（G，V，F），一个上下文无关文法G； 一个属性 的有穷集V和关

4、于属性的断言或谓词的有穷集F。每个属性与文法的某个非终结符或终结符相联。 每个断言与文法的某产生式相联。如果对G中的某一输入串而言（句子），A中的所有断言对该输 入串的语法树结点的属性全为真，则该串也是A语言中的句子。编译程序的静态语义审查工作就是 验证关于所编译的程序的断言是否全部为真。比如，有文法G为：E 一 T1+T2|T1orT2T 一 num|true|false使用上角标将它们区分开。因为T在同一个产生式里出现了两次，对输入串3+4的语法树如图7-1-1（a）(a)T一trueT.t： =boolT一fhlseT.t： =bool(b)图7-1-1静态语义审查属性文法记号中常使用N

5、.t的形式表示与非终结符N相联的属性t。比如可把完成对上面表达式 的类型检查的属性文法写成图7-1-2的形式。与每个非终结符T相联的有属性t，t要么是int，要么 是bool。与非终结符E的产生式相联的断言指明：两个T的属性必须相同。图7-1-1（b）是图7-1-1（a） 语法树结点带有语义信息的表示。E一T1+T2 T1.t=int AND T2.t=int E一T1orT2 T1.t=bool AND T2.t=bool T一numT.t： =int图7-1-2类型检查的属性文法属性文法最早出自克努特笔下。他把属性分成两类：继承属性和综合属性，我们不对属性文法 进行理论上的研究而仅仅将它做

6、为工具描述语义分析。在编译的许多实际应用中，属性和断言以多 种形式出现，也就是说，与每个文法符号相联的可以是各种属性、断言、以及语义规则，或者某种 程序设计语言的程序段等等。下面再给出一些例子。例1 ：简单算术表达式求值的语义描述。产生式语义规则（0）L一 Eprint(E.val)（1）E一E1+TE.val： =E1.val+T.val（2）E一TE.val： =T.val（3）T一T1*FT.val： =T1.valX F.val（4）T一FT.val： =F.val（5）F一(E)F.val： =E.val（6）F一digitF.val： =digit.lexval在该描述中，每个非终

7、结符都有一个属性：一个整数值的称作val的属性。按照语义规则对每 个产生式来说，它的左部E，T，F的属性值的计算来自它右部的非终结符，这种属性称作综合属性。 单词digit仅有综合属性，它的值是由词法分析程序提供的。和产生式L-E相联的语义规则是一个 过程，打印由E产生的表达式的值。我们可以理解为L的属性是空的或是虚的。第二节语法制导翻译概论在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（或语义规则 描述的语义动作）进行翻译的办法称作语法制导翻译。假定我们现在要分析的语法成分是简单算术表达式，所完成的语义的处理不是将它翻译成中间 代码或目标代码，而是计算表达式的值。采用

8、的描述系统是上节的例1。假如语法分析方法是自下 而上的。在用某一产生式进行归约的同时就执行相应的语义动作，在分析出一个句子时，这个句子 的“值”也就同时产生了，例如输入串是2+3*5，其语法树如图7-2-1（a），在第一步归约用到了产生 式（6），执行的语义动作是置F.val的值为单词digit值，我们把语法树中每个结点的语义值括在该 结点处。那么第一步归约并完成语义动作后的情形在图7-2-1（b）中指出。继续进行分析，第七次归约后的情形在图7-2-1（c）中指出归约至E时，它的值17也计算出来了。LLLE zKE zKE zKE1+ TE1+ TE1+ T1T I/KT1 * FI I1/K

9、TT1 * FII I(2)(15)1F1211F513(a)111F(2)F513(b)(c)图7-2-1语法制导方法计算表达式语法制导翻译的具体实现途径不困难。假定有一个LR语法分析器，现在把它的分析栈扩充， 使得每个文法符号都跟有语义值，即把栈的结构看成图7-2-2所示那样。Smy.ValYSx.ValX!So#状态栈语义值符号栈图7-2-2扩充的分析栈状态ACTION(动作)GOTO (转换)d(+*)#ETF0s5s41231s6Acc2r2s7r2r23r4r4r4r44s5s48235r6r6r6r66s5s4937s5s4108s6s119r1s7r1r110r3r3r3r31

10、1r5r5r5r5图7-2-3 LR分析表同时把LR分析器的能力扩大，使它不仅执行语法分析任务，且能在用某个产生式进行归约的同时调用相应的语义子程序，完成在例1的属性文法中描述的语义动作。每步工作后的语义值保存 在扩充的分析栈里“语义值”栏中。采用的LR分析表见图7-2-3,其中使用d代替digit。分析和计值2+3*5的过程列在图7-2-4中。按照上述实现办法，若把语义子程序改为产生某种中间代码的动作，那么则可在语法分析的制导下，随着分析的进展逐步生成中间代码。步骤归约动作状态栈语义栈(值栈)符号栈留余输入串1)0一#2+3*5#2)05#2+3*5#3)r6032#F+3*5#4)r402

11、2#T+3*5#5)r2012#E+3*5#6)0162-#E+3*5#7)01652-#E+3*5#8)r6016323#E+F*5#9)r4016923#E+T*5#10)0169723#E+T*5#11)01697523#E+T*5#12)r601697(10)235#E+T*F#13)r301692(15)#E+T#14)r101-(17)#E#15)接受图 7-2-42+3*5的分析和计值过程第二节中间代码的形式编译程序所使用的中间代码有多种形式。常见的有逆波兰记号、三元式、四元式和树形表示。 下面分别介绍。一、 逆波兰记号逆波兰记号是最简单的一种中间代码表示形式，早在编译程序出现之

12、前，它就用于表示算术表 达式，是波兰逻辑学家卢卡西维奇发明的。这种表示法将运算对象写在前面，把运算符号写在后面，比如把a+b写成ab+，把a*b写成ab*， 用这种表示法表示的表达式也称做后缀式。图7-3-1给出了程序设计语言中的简单表达式和赋值语句相应的逆波兰表示形式：程序设计语言中的表示逆波兰表示a+bab+a+b*c(a+b)*ca： =b*c+b*dabc*+ab+c*abc*bd*+：=图7-3-1逆波兰表示后缀表示法表示表达式，其最大的优点是最易于计算机处理表达式。利用一个栈，自左至右扫 描算术表达式（后缀表示）。每碰到运算对象，就把它推进栈；碰到运算符，若该运算符是二目的， 则对

13、栈顶部的两个运算对象实施运算，并将运算结果代替这两个运算对象而进栈。若是一目运算符， 则对栈顶元素执行该运算，并以运算结果代替该元素进栈。最后的结果留在栈顶。例如BCD*+ （它的中缀表示为一B+C*D，使用表示一目减）的计值过程为：1、B进栈；2、对栈顶元素施行一目减运算，并将结果代替栈顶，即一B置于栈顶；3、C进栈；4、D进栈；5、栈顶两元素相乘，两元素退栈，相乘结果置栈顶；6、栈顶两元素相加，两元素退栈，相加结果进栈，现在栈顶存放的是整个表达式的值。由于后 缀式表示上的简洁和计值的方便，特别适用于解释执行的程序设计语言的中间表示，也方便具有堆 栈体系的计算机的目标代码生成。逆波兰表示很容

14、易扩充到表达式以外的范围。二、三元式和树形表示另一类中间代码形式是三元式。把表达式及各种语句表示成一组三元式。每个三元式三个组成部分是：算符op，第一运算对象ARG1，和第二运算对象ARG2。例如：a： =b*c+b*d的表示为：(1) (*b，c)(2) (*b，c)(3) ( +(1)，(2)(4)(:=(3)，a)与后缀式不同，二元式中含有对中间计算结果的显式引用，比如二元式1）表示的是b*c的结果。三元式（3）中的（1）和（2）分别表示第一个三元式和第二个三元式的结果。对于一目算符op，只需选用一个运算对象，不防规定只用ARG1。至于多目算符，可用若干个 相继的三元式表示。树形表示是三

15、元式表示翻版。上述三元式可表示成下面的树表示：表达式的树形表示很容易实现：简单变量或常数的树就是该变量或常数自身，如果表达式ej和 e2的树分别为T1和T2，那么e1+ e2，e1* e2，e1的树分别为：*AT1T2e1+ e2e1* e2一e1二目运算对应二叉子树，多目运算对应多叉子树，不过，为了便于安排存储空间，一棵多叉子 树可以通过引进新结而表示成一棵二叉子树。三、四元式四元式是一种比较普遍采用的中间代码形式。四元式的四个组成成分是：算符op，第一和第二 运算对象ARG1和ARG2及运算结果RESULT。运算对象和运算结果有时指用户自己定义的变量， 有时指编译程序引进的临时变量。例如a

16、:=b*c+b*d的四元式表示如下：(1) (*, b, c, t1)(2) (*, b, d, t2)(3) (*, tt2, t3)(4) (:=, t3, , a)四元式和三元式的主要不同在于，四元式对中间结果的引用必须通过给定的名字，而三元式是 通过产生中间结果的三元式编号。也就是说，四元式之间的联系是通过临时变量实现的。四元式表示很类似于三地址指令，有时把这类中间表示称为“三地址代码”因为这种表示可看 作一种虚拟三地址机的通用汇编码，即这种虚拟机的每条“指令”包含操作符和三个地址，两个是 为运算对象的，一个是为结果的。这种表示对于代码优化的目标代码生成都较有利。为了更直观，把四元式的

17、形式写成简单赋值形式。比如把上述四元式序列写成：(1) J： =b*c(2) t2： =b*d(3) t3： = t1+ t2(4) a： = t3把 (jump，一，1)写成 goto L把(jrop， B， C， L)写成 if B rop C goto L第四节 简单赋值语句的翻译为了叙述的方便，两种形式我们将同时使用。在第三节的四元式中，使用变量名字本身表示运算对象ARG1和ARG2，用ti表示RESULT。在实 际实现中，它们或者是一个指针，指向符号表的某一登录项，或者是一个临时变量的整数码。在对 赋值语句翻译为四元式的描述中，我们将表明怎样查找这样的符号表登录项。首先对id表示的单

18、词 定义一属性id.name，用做语义变量，用Lookup(id.name)表示审查id.name是否出现在符号表中，如 在，则返回一指向该登录项的指针，否则返回nil。语义过程emit表示输出四元式到输出文件上。语 义过程newtemp表示生成一临时变量，每调用一次，生成一新的临时变量。语义变量E.place，表示 存放E值的变量名在符号表的登录项或一整数码(若此变量是一个临时变量)下面，列出了翻译赋 值语句到四元式的语义描述。这里的语义工作包括对变量进行“先定义后使用”的检查。(1) Sid： =E(2) E一E1+E2(3) E一E1*E2(4) E一一E1(5) E一 (E1)(6)

19、Eid(p： =look up(id.name)；if p/nil thenemit(p： =E.place)else error(E.place： =new temp；emit(E.place ： =E 1 .place+E2.place)(E.place： =new temp；emit(E.place，： =，E1.place*E2.place)(E.place： =newtemp；emit(E.place： = uminusE1.place)(E.place： = E1.place (p: =look up(id.name)；if p/nil thenE.place： =ppIqp pr

20、rnr I第五节布尔表达式的翻译程序设计语言中的布尔表达式有两个作用。一是计算逻辑值，二是用做改变控制流语句中的条 件表达式，如if-then, if-then-else，或是while-do语句中那样。布尔表达式是由布尔算符(and, or和not)(或表示AV和豕)施于布尔变量或关系表达式而成。 即布尔表达式的形式为E1rop E2,其中E1和E2都是算术表达式，rop是关系符，如=，=，=， /等等。我们考虑如下文法生成的布尔表达式。EE and EIE or El not El id rop id Itruelfalse按通常习惯，约定布尔算符的优先顺序(从高到低) 为 豕、A、V，并

21、且A和V服从左结合。一、布达表达式的翻译方法计算布尔表达式的值有两种办法，第一种办法，如同计算算术表达式一样，步步计算出各部分 的真假值，最后计算出整个表达式的值。例如，用数1表示true，用0表示false。那么布尔表达式1 or(not 0 and 0)or 0的计算过程是：1 or(not 0 and 0)or 0=1 or(1 and 0)or 0=1 or 0 or 0=1 or 0=1另一种计算方法是采取某种优化措施，只计算部分表达式，例如要计算A or B，若计算出A的 值为1，那么B的值就无需再计算了，因为不管B的值为何结果，A or B的值都为1。上述两种方法对于不包含布尔函

22、数调用的表达式是没有什么差别的。但是，假若一个布尔式中 会有布尔函数调用，并且这种函数调用引起副作用(如有对全局量的赋值)时，这两种方法未必等 价。采用哪种方法取决于程序设计语言的语义，。若按第一种办法计算布尔表达式。布尔表达式a or b and not c翻译成四元式序列为：(1) t1： =not c(2) t1： = b and t1(3) J： =aort?对于像ab这样的关系表达式，可看成等价的条件语句if ab then 1 else 0，它翻译成的四元式 序列为：(1) if ab goto (4)(2) t : =0(3) goto(5)(4) t： =1(5) 其中用临时变

23、量t存放布尔表达式ab的值，(5)为后续的四元式序号。下面给出了按第一种办法计算布尔表达式的值，将布尔表达式翻译成四元式的描述，其中 nextstat给出的输出序列中下一四元式序号。emit过程每被调用一次，nextstat增加1。E一E1orE2E.place： =new temp；emit(E.place： =E1.place orE2.place)E一E1 and E2E.place： =new temp；emit(E.place) =，E1.place andE2.place)E一not E1E.place： =newtemp：；emit(E.place，： = notE1.place

24、)E一 (E1) E.place： = E1.place E 一id1 relop id2 E.place： =newtemp；emit(if idplace relop.opid2.place goto nextstat+3)；emit(E.place，： = 0)emit( goto nextstat+2)emit(E.place： = 1)E一tureE.place： =newtemp；emit(E.place： = 1)E一false(E.place： =newtemp；emit(E.place： = 0)二、控制语句中布尔表达式的翻译现在讨论出现在if-then； if-then-e

25、lse和while-do等语句中的布尔表达式E的翻译。这三种语句的语法为：Sif E then S1lif E then S1 else S2l while E do S1这些语句的代码结构示意分别在图7-5-1(a)(b)(c)中,其中使用和。两个出口分别用于表示E 为真和假时控制流向的转移。分别叫真出口和假出口。作为条件转移的E，仅把E翻译成代码是一串条件转和无条件转四元式。翻译的基本思路是， 对于E为a rop b的形式生成代码为：if a rop b goto E. true 和goto E.false其中，使用E. true和E.false分别表示E的“真”“假”出口转移目标。E的代

26、码二S1的代码(a) if E then Si代码结构(c) while E do Si代码结构(b) if E then Si else S2的代码结构图7-5-1控制语句的代码结构对于E为Ei or E2的形式，若E1是真，则可知道E为真即E1的真出口和E的真出口一样。如果 E1是假，那么必须计算E2, E1的假出口就是E2代码的第一个四元式标号，这时E2的真出口和假出 口分别与E的真出口和假出口一样。类似的考虑适于E1 and E2的情形。E1的翻译理解容易，只需调换E1的真假出口即可得到E 的真假出口。例如布尔表达式ab or cf翻译为如下四元式序列：(1) if a goto E.

27、 true(2) goto 3(3) if cf goto E. true(6) goto E.false当然生成的四元式显然不是最优的，如(2)是不需要的。这种问题可留待代码优化阶段解决。在上例中，我们使用E.ture和E.false分别表示整个表达式ab or cf的真、假出口， 而E.false的值并不能在产生四元式的同时就知道的。为了看清这一点，我们把该表达式放在条件语 句中考虑，如语句if ab or cf then S1 else S2 四元式序列为(1) if ab goto(7) /* (7)是整个布尔表达式的真出口*/(2) goto(3)(3) if cd goto(5)(

28、4) goto(p+1)/* (p+1)是整个布尔表达式的假出口*/(5) if ef goto(7)(6) goto(p+1)(7) (关于S1的四元式)(p) goto (q)(p+1)(关于S2的四元式)(q)上述四元式(1)和(5)，(4)和(6)的转移地址并不能产生这些四元式的同时得知。例如1) 和(5)的转移地址是在整个布尔表达式的四元式产生完毕之后才得知。因此要回填这个地址。为了 记录需回填地址的四元式，常采用一种“拉链”的办法。把需回填E.true的四元式拉成一链，把需 回填E.false的四元式拉成一链，分别称做“真”链和“假”链。拉链的方式是这样的，若有四元式 序列：(10

29、) goto E.true(20) goto E.true(30) goto E.true则链成(10)goto (0)(20)goto (10)（30）goto （20）把地址（30）称作链首，0为链尾标志，即地址（10）为链尾。第六节控制结构的翻译一、开关语句开关语句（case语句或swith语句）是很多程序设计语言中都有的，方式不尽相同。我们假定 要讨论的开关语句的形式为：switch E ofcase V1： Scase V2: S2:case Vn-1： Sn-1default: Snend这里的E是一个表达式。开关语句是分情形选择机制，在E被计算之后，测试它的值符合哪种 case中

30、的值，而执行和该值相关的语句，并做相应的转移。如果E的值不能与任何V】（1WiWn-1） 匹配，便执行“default”时的语句。直观上看，case语句可翻译成如下的一连串条件转移语句。t :=E;L1： if V1 goto L2;S1；goto next;L2: if t/V2 goto L3;S2goto next;Ln-1:if tVn-1 gto Ln;s -n-1goto next;Ln: Sn;next:还可以采用另外的实现办法，这种办法是建立一个n项的二元组表。第一元为V.的值，第二元 为V,对应的语句S,的标号（或序号）。编译程序构造一张这样的表，产生把选择子E的值传送到该

31、表末项第一元的指令。该项的另一元是缺省情况（default）的语句号。并构造一个对E值查该表的 程序，即该程序把E的值和二元组表项中的各个V值相比，若与某个V匹配，就去执行相应的S,， 如果找不到这样的V,，则末项自动匹配，便去执行S。11下面（图7-6-1）给出开关语句的一种翻译结果（中间代码），其中把所有的测试都放在最后， 以便目标代码生成阶段产生高质量的目标指令。计算E值、并把结果放到临时变量t的中间代码L1:goto testS1的中间代码L2:goto nextS2的中间代码goto nextLn-1：Si的中间代码goto nextLn：Sn的中间代码goto nexttest:i

32、f t=V goto Lif t=V2 goto L2:if 比Vn-1 goto Ln-1goto Lnnext:图7-6-1开关语句的翻译结果翻译为图7-6-1中的中间代码的过程大致如下：当看见关键字switch时，产生新的标号test、next 和一个临时变量t。然后在分析表达式E时，产生计算E值的代码，并把E的结果放到临时变量t 中，接着见到E后的of则产生四元式goto testo然后，每当看见关键字case时，则产生一个标号L填进符号表中，把它在符号表中的位置(不 妨假定为P.)连同case后的V,即(V, P.)对存放于某一存储区(用QUEUE或STACK均可)中； 接着，按通常

33、方式产生相应语句S,代码，紧跟在S,之后是goto next代码。当看见关键字end之后， 则能够产生形成n个分支的(对t的测试)代码了。一般在翻译开关语句的分支的代码时，常常将(if t=Vi goto L.)写成形如(case, V. L.,)四元式形 式。而将四元式(label, next,)加在该四元式序列最后，即形成如下序列：(case, V., L1,)(case, V2, I?,):(case, Vn-1，Ln-1,一)(case, t, Ln,)(Label, next,)用case做为四元式操作码的目的在于提示目标代码生成程序对它进行特别处理(优化)。这组 四元式可以看成是n

34、项二元组表的雏形，末端的四元式将告诉目标代码生成程序，它现在可以视不 同情况产生实现多个分支的目标指令组了。二、for循环语句除了 while-do语句外，很多程序设计语言具有下面形式的循环语句：for i :=E1 step E2 until E3 do S1我们按ALGOL的意义来翻译这种循环句。为了简单起见，假定E2总是正的。在这种假定下，上述 循环句的ALGOL意义等价于：i :=E1goto OVER;AGAIN: i :=i+E2；OVER: if iWE3thenbegin S1; goto AGAIN end;为了按上述顺序产生四元式，必须改写方法。为此，我们使用如下的产生式：

35、Ffor i :=E1F2F step E2F3F2 until E3S-F3 do S1例如，循环语句for I :=1 step 1 until N do M :=M+I将翻译成如下的四元式序列：100 I :=1101 goto 103102 I :=I+1103 if KN goto 105104 goto 108105 T :=M+1106 M :=T107 goto 102108三、goto语句多数程序语言中的转移是通过标号和goto语句实现的。带标号语句的形式是L： S； goto语句 的形式是goto L。当L : S;语句处理之后，标号L是“定义了 ”的。即在符号表中，将登记

36、L的项的“地址”栏 中登上语句S的第一个四元式的地址。如果gotoL是一个向上转移的语句，那么，当编译程序碰到这个语句时，L必是已定义了的。 通过对L查找符号表获得它的定义地址p，编译程序可立即产生出相应于这个goto L的四元式如（j, 一 , 一 , P）。如果goto L是一个向下转移的语句，也就是说，标号L尚未定义，那么，若L是第一次出现， 则把它填进符号表中并标志上“未定义”。由于L尚未定义，对goto L只能产生一个不完全的四元 式（goto 一），它的转移目标须待L定义时再回填进去。在这种情况下，必须把所有那些以L为转 移目标的四元式的地址全都记录下来，以便一旦L定义时就可对这些

37、四元式进行回填。我们将采用 如图7-6-2所示的拉链办法，把所有以L为转移目标的四元式串在一起。链的首地址放在符号表中L 的“地址”栏中。建链的方法是：若goto L中的标号L尚未在符号表中出现，则把L填入表中，置 L “定义否”标志为“未”，把nextstat填进L的地址栏中作为新链首，然后，产生四元式（goto 0）， 其中0为链尾标志。若L已在符号表中现出（但“定义否”标志为“未”），则把它的地址栏中的编 号（记为q）取出，把nextstat填进该栏作新链首，然后产生四元式（goto q）四元式名字类型定义否地址L标号未r 图 8.17未定三义标号的J引用链符号表(p) (goto 0)

38、(q) (goto p)图 7-6-2* (r) (goto q)一旦标号L定义时，我们将根据这条链回填那些待填转移目标的四元式。一般而言，假定用下 面的产生式来定义标号语句S 一 label Slabel 一 i:那么，当用label一i:进行归约时，应做如下的语义动作：1、若i所指的标识符（假定为L）不在符号表中，则把它填入，置“类型”为“标号”，“定义 否”为“已”，“地址”为nextstato2、若L已在符号表中但“类型”不为“标号”或“定义否”为“已”则报告出错。3、若L已在符号表中，则把标志“未”改为“已”然后，把地址栏中的链首（记为q）取出， 同时把nextstat填在其中，最后

39、，执行backpatch （q, nextstat）o翻译goto语句时，还有两点必须注意，第一：是相同名字的标号可以在不同名字作用域中定义。 如：（1）begin（2）L:begin（3）goto L;（4）(5) L:(6) end(7) end当在行(3)处理goto语句时，不知道L的作用域到底是哪个，(因为还没见到语句(5)，因 此一定要延迟解决这个标号的使用。另外有些转移标号是非法的，如下例：(1) for i :=1 to 10 do(2) begin goto L;(3) for j :=1 to 20 do(n)(4) begin goto L;L: end for j end

40、 for j第七节说明语句的翻译处理到第(n)行后，第(4)行的goto目标得以解决。而第(2)行的goto L是非法的，但只有当循环 关闭时才能确定。程序设计语言中的说明语句旨在定义各种形式的有名实体，如常量、变量、数组、记录(结构)、 过程、子程序等等，说明语句的种类也多，变量说明、类型说明、过程说明等等。编译程序把说明 语句中定义的名字和性质登记在符号表中，用以检查名字的引用和说明是否一致。许多说明语句的 翻译并不生成相应的目标代码。过程说明和动态数组的说明有相应的代码。一、简单说明句的翻译程序设计语言中最简单的说明句的语法描述为：Dinteger | realnamelist, id

41、|id即使用关键字integer和real定义一串名字的性质。对这种说明句的翻译是指在符号表中登录该名和 性质。用上述文法来制导翻译(自上而下)存在着这样一个问题，我们只能在把所有的名字都归约成 namelist后才能把它们的性质登记进符号表。这意味着namelist必须用一个队列(或栈)来保存所有 这些名字。但我们可以把上述的文法改写成：DD1，id|integer id|real id这样，就能把所说明的性质及时地告诉每个名字id，或者说，每当读进一个标识符时，就可以把它 的性质登记在符号表中，不用把它们集中起来最后再成批登记了。现在来定义这些产生式所对应的语义动作，给非终结符D 一个语义

42、变量D.ATT，用以记录说明 句所引入的名字的性质(int还是real)。使用过程enter(id, A)把名字id和性质A登录在名表中。enter(id, int);D. ATT : = intenter(id, real);D. ATT : = realenter(id, D1. ATT);D. ATT : = D1. ATT第八节(1)(2)(3)Dinteger idDreal idDD1, id习题一、单项选择题中间代码生成所依据的一。a.语法规则b.词法规则c.语义规则四元式之间的联系是通过实现的。a.指示器b.临时变量c.符号表后缀式ab+cd+/可用表达式来表示。a.a+b/c

43、+db.(a+b)/(c+d)c.a+b/(c+d)表达式(AVB)八(CVD)的逆波兰表示为。a. n ABVACDVb. Al BVCDVA1、2、3、4、b.词法规则d.等价变换规则d.程序变量d.a+b+c/dc. AB Vi CDVAd. Ai BVACDV5、 中间代码的树型表示A B C D 所对应的表达式为。a.A+B+C+D b.A+(B+C)+Dc.(A+B)+C+Dd.(A+B)+(C+D)6、四元式表示法的优点为。a.不便于优化处理，但便于表的更动b.不便于优化处理，但节省存储空间c.便于优化处理，也便于表的更动d.便于表的更动，也节省存储空间7、终结符具有属性。a.传

44、递b.继承c.抽象d.综合解答1、选 c。2、四元式之间的联系是通过临时变量实现的，故选b。3、选 b。4、选 b。5、选 d。6、四元式表示法的优点与间接三元式相同，故选c。7、选 d。二、多顶选择题1、 中间代码主要有。a.四元式b.二元式 c.三元式 d.后缀式 e.间接三元式2、下面中间代码形式中，能正确表示算术表达式a+b+c的有。a. ab+c+ b. abc+c.+Zcd.+e. a+b+c3、 在下面的语法制导翻译中，采用拉链-回填技术。赋值语句b. goto语句c.条件语句d.循环语句4、 下列 中间代码形式有益于优化处理。a.三元式 b.四元式 c.间接三元式 d.逆波兰表

45、示法5、 在编译程序中安排中间代码生成的目的 。便于进行存储空间的组织利于编译程序的移植利于提高目标代码的质量6、 下面的中间代码形式中，能正确表示算术表达式a+b*c。题)a.c.c.e.树形表示法a.c.e.b.利于目标代码的优化d.利于目标代码的移植e.*a. ab+c* b. abc*+c. a+b*c d. + lc/a b7、三地址代码语句具体实现通常有表示方法。a.逆波兰表示 b.三元式 c.间接三元式d.树形表示e.四元式解答1、选 a、c、d、e。2、b、d的中间代码不能正确表示a+b+c，而e不是中间代码：故选a、c。3、凡涉及到跳转的语句都需要采用拉链一一回填技术，故选b

46、、c、d。4、选 b、c。5、选 b、d。6、选 b、e。7、选 b、c、e。三、填空题1、中间代码有 等形式，生成中间代码主要是为了彳2、 语法制导翻译既可以用来产生代码，也可以用来产生指令，甚至可用来对输入串进彳亍。3、 当源程序中的标号出现“先引用后定义”时，中间代码的转移地址须才 时才能确定， 因而要进行。4、 文法符号的属性有两种，一种称为，另一种称为。5、 后缀式abc-/所代表的表达式是，表达式(a-b)*c可用后缀式表示。6、 用一张 辅以 的办法来表示中间代码，这种表示法称为间接三元式。解答1、 逆波兰记号、树形表示、三元式、四元式目标代码的优化容易实现2、中间 目标 解释执

47、行3、标号定义回填4、继承属性综合属性5、a/(b-c) ab-c*6、间接码表三元式表四、综合题1、给出下列表达式的逆波兰表示(后缀式)： a*(-b+c) (AVB)A(CVn DAE)2、写出算术表达式：A+B*(C-D)+E/(C-D) f N的四元式序列；三元式序列；间接三元式序列解答1、 abc+*; ABVCDn EAVA2、表达式的四元式序列：表达式的三元式序列间接三元式序列(1)(-,C,D,T1)(1) (-,C,D)(1) (-,C,D)(2) (*,B,T,T2)(2) (*,B,(1)(2) (*,B,(1)(3) (+,A,T2,T3)(3) (+,A,(2)(3) (+,A,(2)(4) (-,C,D,T4)(4) (-,C,D)(f ,(1),N)(5) ( f ,T4,N,T5)(5) ( f ,(4),N)(/,E,(4)(/,E,T5,T6)(+,T3,T6,T7)(/,E,(5)(+,(3),(6)(+,(3),(5)