编译原理教程课后习题答案——

1、第四章 语义分析和中间代码生成4.1完成下列选择题：(1) 四元式之间的联系是通过 _实现的。a. 指示器b临时变量c.符号表d.程序变量(2) 间接三元式表示法的优点为 。a. 采用间接码表，便于优化处理b. 节省存储空间，不便于表的修改c. 便于优化处理，节省存储空间d. 节省存储空间，不便于优化处理(3) 表达式(n A V B) A (C V D)的逆波兰表示为 。a. n AB VA CD Vb. An B V CD VAc. AB Vn CD VAd. A n B VA CDV(4) 有一语法制导翻译如下所示：St bAbprintTAt (Bprint2A t aprint3Bt

2、 Aa)print4若输入序列为b(aa)a)a)b，且采用自下而上的分析方法，则输出序列为 。a.32224441b.34242421c.12424243 d.34442212【解答】(1) b a b b4.2何谓语法制导翻译”？试给出用语法制导翻译生成中间代码的要点，并用一 简例予以说明。【解答】语法制导翻译(SDTS)直观上说就是为每个产生式配上一个翻译子程序(称语义动作或语义子程序)，并且在语法分析的同时执行这些子程序。也即在语法分析过程 中，当一个产生式获得匹配(对于自上而下分析)或用于归约(对于自下而上分析)时，此产生式相应的语义子程序进入工作，完成既定的翻译任务。用语法制导翻译

3、(SDTS)生成中间代码的要点如下：(1) 按语法成分的实际处理顺序生成，即按语义要求生成中间代码。(2) 注意地址返填问题。(3) 不要遗漏必要的处理，如无条件跳转等。例如下面的程序段：if (i>0) a=i+e-b*d; else a=0;在生成中间代码时，条件卜0”为假的转移地址无法确定，而要等到处理else”时方可确定，这时就存在一个地址返填问题。此外，按语义要求，当处理完(i>0)后的语句(即i>0”为真时执行的语句)时，则应转出当前的if语句，也即此时应加入一条无条件跳转指令，并且 这个转移地址也需要待处理完else之后的语句后方可获得，就是说同样存在着地址返填

4、问题。对于赋值语句 a=i+e-b*d，其处理顺序(也即生成中间代码顺序)是先生成i+e的代码，再 生成b*d的中间代码，最后才产生丁运算的中间代码，这种顺序不能颠倒。4.3 令S.val为文法GS生成的二进制数的值，例如对输入串101.101，贝U S.val=5.625。按照语法制导翻译方法的思想，给出计算S.val的相应的语义规则，G(S)如下：GS: St l.L|LL t LB|BB t 0|1【解答】产生式计算S.val的文法G' S及语义动作如下： 语义动作G ' S: S't S print(S.val)St L1 L2S.val:=L1.val + L

5、2.val/2L2e ngthStL S.val:=L.val LtL1BL.val:=L1.val*2 + B.valL.length:=L1.length +1LtBL.val:=B.valL.length:=2Bt1B.val:=1Bt0B.val:=04.4 下面的文法生成变量的类型说明:Dtid LLt,id L|:TTt integer|real试构造一个翻译方案，仅使用综合属性，把每个标识符的类型填入符号表中(对所用到的过程，仅说明功能即可，不必具体写出)。【解答】 此题只需要对说明语句进行语义分析而不需要产生代码， 但要求把每个标识符的 类型填入符号表中。对D、L、T,为其设置

6、综合属性type，而过程enter(name,type)用来把名字name填入到符号表中，并且给出此名字的类型type。翻译方案如下：Dtid Lenter (, L.type);Lt,id L(1)enter (, L(1).type);L.type=L(1).type;Lt:TL.type=T.type;Tt integerT.type=integer;Tt realT.type=real;4.5 写出翻译过程调用语句的语义子程序。在所生成的四元式序列中,要求在转子指令之前的参数四元式par按反序出现(与实现参数的顺序相反)。此时，在翻译过程调用语句时,是否需要

7、语义变量(队列 )queue？【解答】为使过程调用语句的语义子程序产生的参数四元式par按反序方式出现，过程调用语句的文法为St call i(arglist) arglisttE arglisttarglist(1),E按照该文法，语法制导翻译程序不需要语义变量队列queue,但需要一个语义变量栈STACK，用来实现按反序记录每个实在参数的地址。翻译过程调用语句的产生式及语义 子程序如下：(1) arglisttE建立一个 arglist.STACK 栈，它仅包含一项 E.place(2) arglist t arglist(1) , E 将 E.place 压入 arglist(1). S

8、TACK 栈，arglist. STACK=arglist.STACK(3) St call i (arglist)while arglist.STACK 丰 null dobegin将arglist.STACK栈顶项弹出并送入 p单元之中；emit (par,_ ,_ ,p); en d;emit (call,_ ,_ , entry (i);4.6设某语言的while语句的语法形式为St while E do S(1)其语义解释如图4-1所示。(1) 写出适合语法制导翻译的产生式；(2) 写出每个产生式对应的语义动作。图4-1习题4.6的语句结构图【解答】本题的语义解释图已经给出了翻译后的

9、中间代码结构。在语法制导翻译过程中，当扫描到while时，应记住E的代码地址；当扫描到 do时，应对E的 真出口 ”进行回填， 使之转到S(1)代码的入口处；当扫描到S(1)时，除了应将E的入口地址传给 S(1).chain之外， 还要形成一个转向E入口处的无条件转移的四元式，并且将E.fc继续传下去。因此，应把Stwhile E do S(1)改写为如下的三个产生式：W t whileA t w E doSt a S(1)每个产生式对应的语义子程序如下：W t while W.quad=nxq;A t w E do Backpatch(E.tc, nxq);A.cha in=E.fc;A.q

10、uad=W.quad;St a S(1) Backpatch(S(1).chai n, A.quad);emit(j,_,_,A.quad);S.chain=A.chain;4.7 改写布尔表达式的语义子程序，使得 i(1) rop i(2) 不按通常方式翻译为下面的相继 两个四元式：(jrop, i(1), i(2), 0)(j ,_ ,_ , 0 ) 而是翻译成如下的一个四元式：(jnrop, i(1), i(2), 0)使得当 i(1) rop i(2) 为假时发生转移，而为真时并不发生转移(即顺序执行下一个四元式 )，从而产生效率较高的四元式代码。【解答】 按要求改造描述布尔表达式的语

11、义子程序如下：(1) E t iE.tc=null;E.fc=nxq;emit(jez,entry(i),_ ,0); E t i(i)rop i(2)E.tc=null;E.fc= nxq;emit(j nrop,e ntry(i(1),e ntry(i(2);)/* nrop 表示关系运算符与 rop 相反 */(3) Et(E(1)E.tc=E(1).tc; E.fc=E(1).fc; Et E(1)E.fc=nxq;emit(j,_ ,_ ,0);Backpatch(E(1).fc,nxq); EA t E(1) A EA.fc=E(1).fc;(6) EtEAE(2)E.tc=E(2

12、).tc;E.fc=merg(EA.fc,E(2).fc);(7) E0t E(1) VE0.tc=nxq;emit(j,_ ,_ ,0);Backpatch(E(1).fc,nxq);(8) EtE0E(2) E.fc=E(2).fc;Backpatch(E0.tc,nxq);4.8 按照三种基本控制结构文法将下面的语句翻译成四元式序列：while (A<C A B<D)if (A > 1) C=C+1;else while (A w D)A=A+2;【解答】 该语句的四元式序列如下 w D ，并且关系运算符优先级高(其中E1、E2和E3分别对应 A v C A B v D

13、、A > 1和A105 (j,_,_106 (+, C, 1, C)107 (j,_,_,112)108 (j w ,A,D,110)109 (j,_,_,112)110 (+, A, 2, A)111 (j,_,_,108)112 (j,_,_,100)100 (j<,A,C,102)101 (j,_,_,113)/*E1为F*/102 (j<,B,D,104)/*E1为T*/103 (j,_,_,113)/*E1为F*/104 (j=,A,1,106)/*E2为T*/,108)/*E2为 F*/)：/*C:=C+1*/*跳过else后的语句*/*E3 为 T*/*E3 为

14、 F*/*A:=A+2*/* 转回内层 while 语句开始处 */ /*转回外层 while 语句开始处 */1134.9 已知源程序如下：prod=0;i=1;while (i w 20)prod=prod+ai*bi;i=i+1;试按语法制导翻译法将上述源程序翻译成四元式序列(设A是数组a的起始地址，B是数组b的起始地址；机器按字节编址，每个数组元素占四个字节)。【解答】源程序翻译为下列四元式序列：100 (= ,0 ,_ ,prod)101 (= ,1 ,_ , i )102 (j w ,i ,20,104 )103 ( j 一114 )104 ( * ,4 ,i ,T1 )105 (

15、 - ,A ,4 ,T2 )106 (= ,T2 ,T1 ,T3 )107 ( * ,4 ,i ,T4 )108 ( - ,B ,4 ,T5 )109 (= ,T5 ,T4 ,T6 )110 ( * ,T3 ,T6 ,T7 )111 ( +,prod,T7,prod)112 ( +, i, 1, i )113 (j,_ ,_ ,102 )1144.10 给出文法 GS: S tSaA | AA t AbB | BBtcSd | e(1) 请证实 AacAbcBaAdbed是文法 GS的一个句型；(2) 请写出该句型的所有短语、素短语以及句柄；(3) 为文法GS的每个产生式写出相应的翻译子程序，

16、使句型 AacAbcBaAdbed经该翻译方案后，输出为131042521430。【解答】(1)根据文法GS画出AacAbcBaAdbed对应的语法树如图 4-2所示。由图4-2可知AacAbcBaAdbed是文法GS的一个句型。A图4-2 AacAbcBaAdbed对应的语法树（2）由图 4-2 可知，句型 AacAbcBaAdbed 中的短语为B, BaA, cBaAd, AbcBaAd, e, cBaAdbe, cAbcBaAdbed, A, AacAbcBaAdbed从图 4-2 可看出， 句型 AacAbcBaAdbed 中相邻终结符对应的优先关系如下 （层次靠下的 优先级高 ）：#?a?c?b?c?a?d?b?e?d?#素短语为 BaA 和 e。 句柄 （最左直接短语 ）为 A 。（3）采用修剪语法树的办法，按句柄方式自下而上归约，每当一个产生式得到匹配 时，则按