编译原理第五章答案精选.

第一章1．典型的编译程序在逻辑功能上由哪几部分组成？答：编译程序主要由以下几个部分组成：词法分析、语法分析、语义分析、中间代码生成、中间代码优化、目标代码生成、错误处理、表格管理。

2. 实现编译程序的主要方法有哪些？答：主要有：转换法、移植法、自展法、自动生成法。

3. 将用户使用高级语言编写的程序翻译为可直接执行的机器语言程序有哪几种主要的方式？答：编译法、解释法。

4. 编译方式和解释方式的根本区别是什么？答：编译方式：是将源程序经编译得到可执行文件后，就可脱离源程序和编译程序单独执行，所以编译方式的效率高，执行速度快；解释方式：在执行时，必须源程序和解释程序同时参与才能运行，其不产生可执行程序文件，效率低，执行速度慢。

第二章1.乔姆斯基文法体系中将文法分为哪几类？文法的分类同程序设计语言的设计与实现关系如何？答：1）0型文法、1型文法、2型文法、3型文法。

2）2. 写一个文法，使其语言是偶整数的集合，每个偶整数不以0为前导。

答：Z→SME | BS→1|2|3|4|5|6|7|8|9M→ε | D | MDD→0|SB→2|4|6|8E→0|B3. 设文法G为：N→ D|NDD→ 0|1|2|3|4|5|6|7|8|9请给出句子123、301和75431的最右推导和最左推导。

答：N⇒ND⇒N3⇒ND3⇒N23⇒D23⇒123N⇒ND⇒NDD⇒DDD⇒1DD⇒12D⇒123N⇒ND⇒N1⇒ND1⇒N01⇒D01⇒301N⇒ND⇒NDD⇒DDD⇒3DD⇒30D⇒301N⇒ND⇒N1⇒ND1⇒N31⇒ND31⇒N431⇒ND431⇒N5431⇒D5431⇒75431N⇒ND⇒NDD⇒NDDD⇒NDDDD⇒DDDDD⇒7DDDD⇒75DDD⇒754DD⇒7543D⇒75431 4. 证明文法S→iSeS|iS| i是二义性文法。

答：对于句型iiSeS存在两个不同的最左推导：S⇒iSeS⇒iiSesS⇒iS⇒iiSeS所以该文法是二义性文法。

编译原理-第5章-习题与答案2第五章习题5-1 设有文法G[S]：S→A/ A→aA∣AS∣/(1) 找出部分符号序偶间的简单优先关系。

(2) 验证G[S]不是简单优先文法。

5-2 对于算符文法G[S]：S→E E→E-T∣T T→T*F∣F F→-P∣P P→(E)∣i(1) 找出部分终结符号序偶间的算符优先关系。

(2) 验证G[S]不是算符优先文法。

5-3 设有文法G′[E]：E→E1 E1→E1+T1|T1 T1→T T→T*F|F F→(E)|i其相应的简单优先矩阵如题图5-3所示，试给出对符号串（i+i）进行简单优先分析的过程。

题图5-3 文法G′[E]的简单优先矩阵5-4 设有文法G[E]：E→E+T|TT→T*F|FF→(E)|i其相应的算符优先矩阵如题图5-4所示。

试给出对符号串（i+i）进行算符优先分析的过程。

题图5-4 文法G[E]的算符优先矩阵5-5 对于下列的文法，试分别构造识别其全部可归前缀的DFA和LR(0)分析表，并判断哪些是LR(0)文法。

(1) S→aSb∣aSc∣ab(2) S→aSSb∣aSSS∣c(3) S→A A→Ab∣a5-6 下列文法是否是SLR(1)文法？若是，构造相应的SLR(1)分析表，若不是，则阐明其理由。

(1) S→Sab∣bR R→S∣a(2) S→aSAB∣BA A→aA∣B B→b(3) S→aA∣bB A→cAd∣ε B→cBdd∣ε5-7 对如下的文法分别构造LR(0)及SLR(1)分析表，并比较两者的异同。

S→cAd∣b A→ASc∣a5-8 对于文法G[S]:S→A A→BA∣ε B→aB∣b(1) 构造LR(1)分析表；(2) 给出用LR(1)分析表对输入符号串abab的分析过程。

5-9 对于如下的文法，构造LR(1)项目集族，并判断它们是否为LR(1)文法。

(1) S→A A→AB∣ε B→aB∣b(2) S→aSa∣a第5章习题答案25-1 解：(1) 由文法的产生式和如答案图5-1(a)所示的句型A／／a／的语法树，可得G中的部分优先关系如答案图5-1(b)所示。

第五章2．对下面的文法G：E→TE/E/→+E|εT→FT/T/→T|εF→PF/F/→*F/|εP→(E)|a|b|^(1)计算这个文法的每个非终结符的FIRST集和FOLLOW集。

(2)证明这个方法是LL(1)的。

(3)构造它的预测分析表。

(4)构造它的递归下降分析程序。

解：（1）计算这个文法的每个非终结符的FIRST集和FOLLOW集。

FIRST集合有：FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^};FIRST(E/)={+,ε}FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^};FIRST(T/)=FIRST(T)∪{ε}={(,a,b,^,ε};FIRST(F)=FIRST(P)={(,a,b,^};FIRST(F/)=FIRST(P)={*,ε};FIRST(P)={(,a,b,^};FOLLOW集合有：FOLLOW(E)={),#};FOLLOW(E/)=FOLLOW(E)={),#};FOLLOW(T)=FIRST(E/)∪FOLLOW(E)={+,),#};//不包含εFOLLOW(T/)=FOLLOW(T)=FIRST(E/)∪FOLLOW(E)={+,),#};FOLLOW(F)=FIRST(T/)∪FOLLOW(T)={(,a,b,^,+,),#};//不包含εFOLLOW(F/)=FOLLOW(F)=FIRST(T/)∪FOLLOW(T)={(,a,b,^,+,),#};FOLLOW(P)=FIRST(F/)∪FOLLOW(F)={*,(,a,b,^,+,),#};//不包含ε(2)证明这个方法是LL(1)的。

各产生式的SELECT集合有：SELECT(E→TE/)=FIRST(T)={(,a,b,^};SELECT(E/→+E)={+};SELECT(E/→ε)=FOLLOW(E/)={),#}SELECT(T→FT/)=FIRST(F)={(,a,b,^};SELECT(T/→T)=FIRST(T)={(,a,b,^};SELECT(T/→ε)=FOLLOW(T/)={+,),#};SELECT(F→PF/)=FIRST(P)={(,a,b,^};SELECT(F/→*F/)={*};SELECT(F/→ε)=FOLLOW(F/)={(,a,b,^,+,),#};SELECT(P→(E))={(}SELECT(P→a)={a}SELECT(P→b)={b}SELECT(P→^)={^}可见，相同左部产生式的SELECT集的交集均为空，所以文法G[E]是LL(1)文法。

第五章习题解答5.1 设一NDPDA识别由下述CFG定义的语言，试给出这个NDPDA的完整形式描述。

S→SASCS→εA→AaA→bC→DcDD→d5.2 消除下列文法的左递归：① G[A]:A→BX∣CZ∣WB→Ab∣BcC→Ax∣By∣Cp② G[E]:E→ET+∣ET–∣TT→TF*∣TF/FF→(E)∣i③ G[X]:X→Ya∣Zb∣cY→ Zd∣Xe∣fZ→X e∣Yf∣a④ G[A]:A→Ba|Aa|cB→Bb|Ab|d5.3 设文法G[<语句>]：<语句>→<变量>: = <表达式>|if<表达式>then<语句>|if<表达式>then<语句>else<语句> <变量>→i<表达式>→<项>|<表达式>+<项><项>→<因子>|<项>*<因子><因子>→<变量>|′(′<表达式>′)′试构造该文法的递归下降子程序。

5.4 设文法G[E]：E→ TE'E'→ + E∣εT→ FT'T'→ T∣εF→ PF'F'→ *F∣εP→ (E)∣ a∣^①构造该文法的递归下降分析程序；②求该文法的每一个非终结符的FIRST集合和FOLLOW集合；③构造该文法的LL（1）分析表，并判断此文法是否为LL（1）文法。

5.5 设文法G[S]：S→ SbA∣aAB→ SbA→ Bc①将此文法改写为LL（1）文法；②求文法的每一个非终结符的FIRST集合和FOLLOW集合；③构造相应的LL（1）分析表。

5.6 设文法G[S]：S→ aABbcd∣εA→ ASd∣εB→ SAh∣eC∣εC→ Sf∣Cg∣εD→ aBD∣ε①求每一个非终结符的FOLLOW集合；②对每一个非终结符的产生式选择，构造FIRST集合；③该文法是LL（1）文法。

第四章4.1文法G1为：N→ND | D D→0 | 1（1）L(G1)如何表示？（2）给出句子011100的最左推导和最右推导。

解答：(1) L(G1)为无符号二进制数。

(2)最左推导：N⇒ND⇒NDD⇒ NDDD⇒ NDDDD⇒ NDDDD⇒ NDDDDD⇒ DDDDDD ⇒ 0DDDDD⇒ 01DDDD⇒ 011DDD⇒ 0111DD⇒ 01110D⇒ 011100最右推导：N⇒ND⇒N0⇒ ND0⇒ N00⇒ ND00⇒ N100⇒ ND100⇒ N1100 ⇒ ND1100 ⇒ N11100⇒ D11100 ⇒ 0111004.2 写一文法G2，使其L(G2)是正奇数集合，且每个数不以0打头。

解答：令G2={ V N,V T,P, <正奇数>}，其中，V T ={0,1,2,3,4,5,6,7,8,9}，V N ={<正奇数>, <一位奇数>, <一位偶数>, <数字串>, <数字1>, <数字>}，P：<正奇数>→<一位奇数>│<数字串> <一位奇数><数字串>→<数字串><数字>│<数字1><数字>→<一位奇数>│<一位偶数>数字1→1│2│3│4│5│6│7│8│9<一位奇数>→1│3│5│7│9<一位偶数>→0│2│4│6│84.3 设文法G3为：E→E+T | TT→T*F | FF→(E) | i试证明符号串T*F+ i是G3的句型，并给出此句型的所有短语以及句柄。

解答：由于有推导E⇒E+T⇒T+T⇒T*F+T⇒ T*F+F⇒T*F+i所以T*F+i是的G3的句型。

此句型T*F+i的语法树如图4-5：EE + TT Fi图4-5 句型T*F+i的语法树根据语法树此句型的短语有：T*F, i, T*F+i.句柄为T*F。

第一章1.2 计算机执行用高级语言编写的程序有哪些途径？它们之间的主要区别是什么？ 【解答】计算机执行用高级语言编写的程序主要有两种途径：解释和编译。

这两种途径的主要区别在于：解释方式下不生成目标代码程序，而编译方式下生成目标代码程序。

从执行速度上看，编译型的高级语言比解释型的高级语言要快，但解释方式下的人机界面比编译型好，便于程序调试。

（在解释方式下，翻译程序事先并不采用将高级语言程序全部翻译成机器代码程序，然后执行这个机器代码程序的方法，而是每读入一条源程序的语句，就将其解释(翻译)成对应其功能的机器代码语句串并执行，而所翻译的机器代码语句串在该语句执行后并不保留，最后再读入下一条源程序语句，并解释执行。

这种方法是按源程序中语句的动态执行顺序逐句解释(翻译)执行的，如果一语句处于一循环体中，则每次循环执行到该语句时，都要将其翻译成机器代码后再执行。

在编译方式下，高级语言程序的执行是分两步进行的：第一步首先将高级语言程序全部翻译成机器代码程序，第二步才是执行这个机器代码程序。

因此，编译对源程序的处理是先翻译，后执行。

）1.3 请画出编译程序的总框图。

如果你是一个编译程序的总设计师，设计编译程序时应当考虑哪些问题？ 【解答】编译程序总框图如图1-1所示。

作为一个编译程序的总设计师，首先要深刻理解被编译的源语言其语法及语义；其次，要充分掌握目标指令的功能及特点，如果目标语言是机器指令，还要搞清楚机器的硬件结构以及操作系统的功能；第三，对编译的方法及使用的软件工具也必须准确化。

总之，总设计师在设计编译程序时必须估量系统功能要求、硬件设备及软件工具等诸因素对编译程序构造的影响等。

第二章2.1 正规式M1和M2等价是指：M1和M2所识别的语言集相等。

2.2 什么是扫描器？扫描器的功能是什么？【解答】扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。

第五章语法制导翻译及中间代码生成5.1说明属性文法与属性翻译文法有何异同?5.2考虑下面的属性文法：Z →sXattribution:Z.a=X.c;X.b=X.a；Z.p=X.b；Z →t Xattribution：X.b=X.d;Z.a=X.b;X →uattribution:X.d=1;X.c=X.d;X →Vattribuion:X.c=2;X.d=X.c;(1) 上述文法中的属性哪些是继承的?哪些是综合的?(2) 上述文法中的属性依赖是否出现了循环?5.3为什么说S属性文法一定是L属性文法?反之结论亦正确吗?5.4将下列中缀式改写为逆波兰式。

(1) -A*(B+C)↑(D-E)(2) ((a*d+c)/d+e)*f+g(3) a+x≤4∨(C∧d*3)(4) a∨b∧c+d*e↑f(5) s=0; i=1;while (i＜=100) {s+=i*i; i++;}5.5将下列后缀式改写为中缀式。

(1) abc*+(2) abc-*cd+e/-(3) abc+≤a0＞∧ab+0≠a0∧∨(4) ab＜p1 BZ xab-c↑= p2 BR gh=↑↑p1p25.6设已给文法G［E］：E →E+T | -T | TT →T*F | FF →P ↑F | PP →(E) | i试设计一个递归下降分析器，要求此分析器在语法分析过程中，将所分析的符号串翻译成后缀式。

5.7设已给布尔表达式文法G［Z］：Z →EE →T{∨T}T →F{∧F}F → F | (E) | b试设计一个递归下降分析器，它把由G［Z］所描述的布尔表达式翻译为四元式序列。

5.8(1) 利用54节所给的属性翻译文法将赋值语句：X=A*(B+C)+D翻译成四元式序列，给出语法制导的翻译过程。

(2) 利用55节所给的属性翻译文法将布尔表达式：A∧(B∨(C∨D F))翻译成四元式序列，给出语法制导的翻译过程。

(3) 利用56节所给的属性翻译文法将语句：while A＜C∧B＞0 doif A=1 then C∶=C+1else while A＜=D do A∶=A+2翻译成四元式序列，给出语法制导的翻译过程。

第五章代码优化5.1 完成以下选择题：(1) 优化可生成的目标代码。

a. 运行时间较短b. 占用存储空间较小c. 运行时间短但占用内存空间大d. 运行时间短且占用存储空间小(2) 下列优化方法不是针对循环优化进行的。

a. 强度削弱b. 删除归纳变量c. 删除多余运算d. 代码外提(3) 基本块内的优化为。

a. 代码外提，删除归纳变量b. 删除多余运算，删除无用赋值c. 强度削弱，代码外提d. 循环展开，循环合并(4) 在程序流图中，我们称具有下述性质的结点序列为一个循环。

a. 它们是非连通的且只有一个入口结点b. 它们是强连通的但有多个入口结点c. 它们是非连通的但有多个入口结点d. 它们是强连通的且只有一个入口结点(5) 关于必经结点的二元关系，下列叙述中不正确的是。

a. 满足自反性b. 满足传递性c. 满足反对称性d. 满足对称性【解答】(1) d (2) c (3) b (4) d (5) d5.2 何谓局部优化、循环优化和全局优化？优化工作在编译的哪个阶段进行？【解答】优化根据涉及的程序范围可分为三种。

(1) 局部优化是指局限于基本块范围内的一种优化。

一个基本块是指程序中一组顺序执行的语句序列(或四元式序列)，其中只有一个入口(第一个语句)和一个出口(最后一个语句)。

对于一个给定的程序，我们可以把它划分为一系列的基本块，然后在各个基本块范围内分别进行优化。

通常应用DAG方法进行局部优化。

(2) 循环优化是指对循环中的代码进行优化。

例如，如果在循环语句中某些运算结果不随循环的重复执行而改变，那么该运算可以提到循环外，其运算结果仍保持不变，但程序运行的效率却提高了。

循环优化包括代码外提、强度削弱、删除归纳变量、循环合并和循环展开。

5.3 将下面程序划分为基本块并作出其程序流图。

read(A,B)F=1C=A*AD=B*Bif C<D goto L1E=A*AF=F+1E=E+Fwrite(E)haltL1: E=B*BF=F+2E=E+Fwrite(E)if E >100 goto L2haltL2: F=F-1goto L1【解答】先求出四元式程序中各基本块的入口语句，即程序的第一个语句，或者能由条件语句或无条件转移语句转移到的语句，或者条件转移语句的后继语句。