《编译原理教程第二版胡元义课后答案第四章》由会员分享，可在线阅读，更多相关《编译原理教程第二版胡元义课后答案第四章（35页珍藏版）》请在金锄头文库上搜索。
1、第四章语义分析和中间代码生成4. 1完成下列选择题：(1) 四元式之间的联系是通过实现的。a. 指示器b.临时变量c.符号表d.程序变量(2) 间接三元式表示法的优点为_。a. 采用间接码表，便于优化处理b. 节省存储空间，不便于表的修改BRCKc. 便于优化处理，节省存储空间d. 节省存储空间，不便于优化处理(3) 表达式(-1 AVB) A(CVD)的逆波兰表示为oa. n ABVACDVb. An BVCDVAc. ABVn CDVAd. An BVACDV(4) 有一语法制导翻译如下所示：SbAbA- (Bprint1 print2 AaBAa)print3 print4 若输入序列为
2、b(aa)a)a)b,且采用自下而上的分析方法，则输出序列为o令 第四章 语义分析和中间代码生成a. 32224441b. 34242421c. 12424243d. 34442212【解答】(1) b (2) a (3) b (4) b4.2何谓“语法制导翻译” ？试给出用语法制导翻译 生成中间代码的要点，并用一简例予以说明。【解答】 语法制导翻译(SDTS)直观上说就是为每个产 生式配上一个翻译子程序(称语义动作或语义子程序)，并且 在语法分析的同时执行这些子程序。也即在语法分析过程中, 当一个产生式获得匹配(对于自上而下分析)或用于归约(对 于自下而上分析)时，此产生式相应的语义子程序进
3、入工作, 完成既定的翻译任务。用语法制导翻译(SDTS)生成中间代码的要点如下：(1) 按语法成分的实际处理顺序生成，即按语义 要求生成中间代码。(2) 注意地址返填问题。(3) 不要遗漏必要的处理，如无条件跳转等。 例如下面的程序段：if (i0) a=i+e-b*d; else a=0;令 第四章 语义分析和中间代码生成在生成中间代码时，条件“i0”为假的转移地址 无法确定，而要等到处理“else”时方可确定，这时就 存在一个地址返填问题。此外，按语义要求，当处理 完（i0）后的语句（即“i0”为真时执行的语句）时,则 应转出当前的if语句，也即此时应加入一条无条件跳 转指令，并且这个转移
4、地址也需要待处理完else之后 的语句后方可获得，就是说同样存在着地址返填问题。 对于赋值语句a二i+e-b*d,其处理顺序（也即生成中间 代码顺序）是先生成i+e的代码，再生成b*d的中间代码, 最后才产生运算的中间代码，这种顺序不能颠倒。4. 3令S. val为文法GS生成的二进制数的值，例如 对输入串101. 101,则S.val=5. 625。按照语法制导翻译方 法的思想，给出计算S. val的相应的语义规则，G(S)如下：GS : S-*L.L|LL-*LB|BB-0 1【解答】计算S. val的文法(/ S及语义动作如下：产生式语义动作Gz S: S -*S print (S. v
5、al)SfLfL?S. val :=Lr val +L2. val/2L2-lengthSL S. val :=L. valLfLBL val:=Lr va 1*2 + B. valL length:二L length +1L-BL. val:二B valL length:二2B-1B. val:=lB-0B. val:=O令 第四章 语义分析和中间代码生成4.4下面的文法生成变量的类型说明：D-id LL-, id L| :TT-* integer|real试构造一个翻译方案，仅使用综合属性，把每个 标识符的类型填入符号表中（对所用到的过程，仅说明 功能即可，不必具体写出）。令 第四章 语义
6、分析和中间代码生成【解答】 此题只需要对说明语句进行语义分析 而不需要产生代码，但要求把每个标识符的类型填入 符号表中。对D、L、T,为其设置综合属性type,而过 程enter (name, type)用来把名字name填入到符号表中, 并且给出此名字的类型typeo翻译方案如下：D-id Lenter (id name, L. type) ;L-*, id I/Denter (id name, L(D. type);L. type=L(1) type;WB心轸第呵章语义分析和中间代码生成L-:TL type=T type;TintegerT. type=integer;TtealT. ty
7、pe=real;4.5写出翻译过程调用语句的语义子程序。在所 生成的四元式序列中，要求在转子指令之前的参数四 元式pa讨安反序出现（与实现参数的顺序相反）o此时, 在翻译过程调用语句时，是否需要语义变量（队 列）queue ?令 第四章 语义分析和中间代码生成【解答】 为使过程调用语句的语义子程序产生 的参数四元式par按反序方式出现，过程调用语句的文 法为S-call i (arglist)arglistEarglistatglist，E按照该文法，语法制导翻译程序不需要语义变量 队列queue,但需要一个语义变量栈STACK,用来实现 按反序记录每个实在参数的地址。翻译过程调用语句 的产生
8、式及语义子程序如下：令 第四章 语义分析和中间代码生成(1) arglist-*E建立一个arglist. STACK栈，它仅包含一项E. place(2) arglist-*arglist(1) , E 将E. place压 入 arglist . STACK 栈 ， arglist. STACK二atglist.STACK(3) Scalli (arglist)whilearglist. STACK7null dobegin将arglist. STACK栈顶项弹出并送入p单元之中；emit (par, _ , _ , p);end;emit (call, _ , _ , entry (i)
9、;簣第呵章语义分析和中间代码生成4.6设某语言的while语句的语法形式为S-* wh订e E do S 其语义解释如图4-1所示。(1) 写出适合语法制导翻译的产生式；写出每个产生式对应的语义动作。假图4-1习题4. 6的语句结构图轸 第四章 语义分析和中间代码生成【解答】 本题的语义解释图已经给出了翻译后 的中间代码结构。在语法制导翻译过程中，当扫描到 wh订e时，应记住E的代码地址；当扫描到do时，应对E 的“真出口”进行回填，使之转到S代码的入口处； 当扫描到S时，除了应将E的入口地址传给S.chain 之外，还要形成一个转向E入口处的无条件转移的四元 式，并且将E. fc继续传下去。
10、因此，应把S-wh订e E do S改写为如下的三个产生式：Wwh 订 eA-W E doS-A S - 每个产生式对应的语义子程序如下:W-*wh ile W. quad二nxq;A-*W E do Backpatch (E tc, nxq);A. chain=E fc;A. quad二W quad; /S-A S Backpatch (S(1). chain, A. quad);emit (j,_，A. quad);S.chain=A chain;令 第四章 语义分析和中间代码生成4.7改写布尔表达式的语义子程序，使得irop i不按通常方式翻译为下面的相继两个四元式：（jrop, i,i
11、,0）（j, 0 ）而是翻译成如下的一个四元式：（jnrop, i，i，0）使得当irop i为假时发生转移，而为真时并 不发生转移（即顺序执行下一个四元式），从而产生效 率较高的四元式代码。-【解答】按要求改造描述布尔表达式的语义子程序如下：(1) E-iE. tc=null;E. fc=nxq;emit(jez, entry(i), _ , 0);/(2) E-*i rop i E. tc=null; E. fc=nxq; emit (jnrop, entry (i(1), entry (i(2);)/* ntop表示关系运算符与top相反*/(3) E- (E)E. tc二E(D.tc;
12、 E. fc二E.fc;(4) E-n E E. fc=nxq; emit (j, _ , _ , 0) ;Backpatch (E(1). fc, nx q) ；(5) EA-E A EA. fc=E fc;(6) E_EAE(2)E. tc二E.tc; E. fcornerg (EA. fc, E.fc) :(7) E-E(1)VE. tc=nxq; emit (j, _ , _ , 0) : Backpatch(E(1) fc, n xq) :(8) E-EE(2)E fc二E(2). fc;Backpatch(E tc, nxq) ;4. 8按照三种基本控制结构文法将下面的语句翻 译成
13、四元式序列：wh订e (ACABD)if (A21) C=C+1;else while (ACD)A=A+2;【解答】 该语句的四元式序列如下（其中E、E2 和E3分别对应ACAB AN1和AWD,并且关系运 算符优先级高）：100 (j, A, C, 102)101 (j,_,113)102 (j，B,D, 104)103 (j,_,113)/*E为 F*/*E为 T*/*E为 F*/*E 为 T*/(j=A, 1,106)轸第呵章语义分析和中间代码生成105106107108109110111112113(j,亠,108)(+, c, 1, O(j,亠,1 (jW,A, D, HO)(j,
14、亠,1(+, A, 2, A)(j,亠,108)(j,亠，100)/*E?为F*/*C:=C+1*/*跳过else后的语句*/*已3为T*/*Eg为F*/*A:二A+2*/*转回内层while语句开始处*/*转回外层while语句开始处*/4.9已知源程序如下：prod=0;i=l；while (iW20)prod=prod+ai*bi;i二i+1;试按语法制导翻译法将上述源程序翻译成四元式 序列(设A是数组a的起始地址，B是数组b的起始地址； 机器按字节编址，每个数组元素占四个字节)。【解答】 源程序翻译为下列四元式序列:100(=,0 ,_ ,prod)101(=,1 ,_ , i)102(jW,i,20, 104 )103（j,H4 )104(* ,4,i , A )105(-,A,4丄）106（二,丁2，）107 (
