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

《编译原理》课后习题第 1 章引论第1 题解释下列术语：（1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。

（2）源程序：源语言编写的程序称为源程序。

（3）目标程序：目标语言书写的程序称为目标程序。

（4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。

通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符号表管理等工作。

（5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。

（6）遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。

第2 题一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。

答案：一个典型的编译程序通常包含 8 个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。

其各部分的主要功能简述如下。

词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。

语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。

语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。

中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代码，如三元式或四元式。

中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。

目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。

表格管理程序：负责建立、填写和查找等一系列表格工作。

表格的作用是记录源程序的各类信息和编译各阶段的进展情况，编译的每个阶段所需信息多数都从表格中读取，产生的中间结果都记录在相应的表格中。

编译原理第六章到第十一章课后习题答案p116/1.已知文法G[S]为：S→a|∧|(T)T→T,S|S(1) 计算FIRSTVT -- LASTVT表(2) 构造算符优先关系表（OPERATER PRIORITY RELATION TABLE），说明是否为算符优先文法。

=: #=#, (=)<: (< FIRSTVT(T) , ,<firstvt(s)<="" ,="" p="">>:LASTVT(S)># , LASTVT(T)>), LASTVT(T)> ,表中无多重人口所以是算符优先（OPG）文法。

（3）计算G[S]的优先函数。

收敛（4）对输入串（a,a）#的算符优先分析过程为Success!3.有文法G（S）：s->Vv->T/ViTT->F/T+FF->)V*|((1)(+(i(的规范推导S=>V=>ViT=>ViF=>Vi(=>Ti(=>T+Fi(=>T+(i(=>F+(i(=>(+(i((2)F+Fi（的短语、句柄、素短语。

短语S: F+Fi（T1:F+F （素短语）T2:F （句柄）F:( （素短语）(3) G(S)是否为OPG？若是，给出（1）中句子的分析过程！S’->#S# S->V V->T/ViT T->F/T+F F->)V*|(算符优先关系表（OPERATER PRIORITY RELATION TABLE）对输入串(+(I(的算符优先分析过程为:p152/2文法：S→L.L|LL→LB|BB→0|1拓广文法为G′，增加产生式S′→SI3若产生式排序为：0 S' →S1 S →L.L2 S →L3 L →LB4 L →B5 B →06 B →1由产生式知：First (S' ) = {0,1}First (S ) = {0,1}First (L ) = {0,1}First (B ) = {0,1}Follow(S' ) = {#}Follow(S ) = {#}Follow(L ) = {.,0,1,#}Follow(B ) = {.,0,1,#}G′的LR(0)项目集族及识别活前缀的DFA如下图所示：I5B →.0和B →.1为移进项目，S →L.为归约项目，存在移进-归约冲突，因此所给文法不是LR(0)文法。

第6章属性文法和语法制导翻译7. 下列文法由开始符号S产生一个二进制数，令综合属性val给出该数的值：试设计求的属性文法，其中，已知B的综合属性c, 给出由B产生的二进位的结果值。

例如，输入时，=，其中第一个二进位的值是4，最后一个二进位的值是。

【答案】11. 设下列文法生成变量的类型说明：(1)构造一下翻译模式，把每个标识符的类型存入符号表；参考例。

【答案】第7章语义分析和中间代码产生1. 给出下面表达式的逆波兰表示（后缀式）：【答案】3. 请将表达式－(a+b)*(c+d)-(a+b+c)分别表示成三元式、间接三元式和四元式序列。

【答案】间接码表：(1)→(2)→(3)→(4)→(1)→(5)→(6)4. 按节所说的办法，写出下面赋值句A:=B*(－C+D) 的自下而上语法制导翻译过程。

给出所产生的三地址代码。

【答案】5. 按照7.3.2节所给的翻译模式，把下列赋值句翻译为三地址代码：A[i, j]:=B[i, j] + C[A [k, l]] + d[ i+j]【答案】6. 按7.4.1和节的翻译办法，分别写出布尔式A or ( B and not (C or D) )的四元式序列。

【答案】用作数值计算时产生的四元式：用作条件控制时产生的四元式：其中：右图中(1)和(8)为真出口，(4)(5)(7)为假出口。

7. 用7.5.1节的办法，把下面的语句翻译成四元式序列： While A<C and B<D do if A=1 then C:=C+1 else while A ≦D do A:=A+2; 【答案】第9章 运行时存储空间组织4. 下面是一个Pascal 程序：当第二次( 递归地) 进入F 后，DISPLAY 的内容是什么当时整个运行栈的内容是什么 【答案】第1次进入F 后，运行栈的内容： 第2次进入F 后，运行栈的内容： 109 87 6 5 4 3 2 1 017 1615 14 13 12 11 10 9 8 7 6 5第2次进入F 后，Display 内容为：5. 对如下的Pascal 程序，画出程序执行到(1)和(2)点时的运行栈。

第6章习题6-1 将下列中缀式改写为逆波兰式。

(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/f6-2 将下列逆波兰式改写为中缀式。

(1) abc*+(2) abc-*cd+e/-(3) abc+≤a0>∧ab+0≠a0<∧∨6-3 将下列语句翻译成四元式序列。

(1) X:=A*(B+C)+D(2) if A∧(B∨(C∨D)) then S1 else S2(3) while A<C∧B>0 doif A=1 then C:=C+1 else A:=A+26-4 设有二维PASCAL数组A[1··10,1··20]和三维PASCAL数组B[1··10, 1··20,1··30]，给出赋值语句A[I,J]:=B[J,I+J,I+1]+X的四元式序列。

第5章习题答案6-1 解：(1) A-BC+*DE-/(2) ad*c+d/e+f*g+(3) ax+4≤cd3*>∨(4) abcde*f/<∧∨6-2 解：(1) a+b*c(2) a*(b-c)-(c+d)/e(3) a≤b+c∧a>0∨a+b≠0∧a<06-3 解：(1) (1) (+,B,C,T1)(2) (*,A,T1 ,T2)(3) (+,T2 ,D,T3)(4) (=,T3 ,0,X)(2) 如下所示：(1) (jnz,A,0,3);(2) (j,0,0,p+1);(3) (jnz,B,0,9);(4) (j,0,0,5);(5) (jnz,C,0,9);(6) (j,0,0,7);(7) (jnz,D,0,9);(8) (j,0,0,p+1);(9) 与S1相应的四元式序列(p) (j,0,0,q)(p+1) 与S2相应的四元式序列(q) …(3) 假设所产生的四元式序列编号从1开始(1) (j<A,C,3)(2) (j,0,0,13)(3) (j>,B,0,5)(4) (j,0,0,13)(5) (j=,A,1,7)(6) (j,0,0,10)(7) (+,C,1,T1)(8) (=,T1 , ,C)(9) (j,0,0,1)(10) (+,A,2,T2)(11) (=,T2 , ,A)(12) (j,0,0,1)(13) …6-4 解：(1) (*,I,20,T1)(2) (+,J,T1,T1)(3) (-,a A,C A ,T2)(4) (+,I,J,T3)(5) (*,J,20,T4)(6) (+,T3 ,T4 ,T4)(7) (+,I,1,T5)(8) (*,T4,30,T6)(9) (+,T5 ,T6 ,T6)(10) (-,a B,C B ,T7)(11) (=[],T7[T6],0,T8)(12) (+,T8 ,X,T9)(13) ([]=,T9 ,0,T2[T1])（注：(1)～(3)是计算下标变量A[I,J]XXX的四元式，T2中存放的是CONSTPART部分，而T1中存放的是VARPART部分，a A表示数组A的首XXX；(4)～(10) 是计算下标变量B[J,I+J,I+1]XXX的四元式，T7中存放的是CONSTPART 部分，而T6中存放的是VARPART部分，a B表示数组B的首XXX。

第一章编译程序概述1.1什么是编译程序编译程序是现代计算机系统的基本组成部分之一，而且多 数计算机系统都含有不止一个高级语言的编译程序。

对有些高 级语言甚至配置了几个不同性能的编译程序。

1.2编译过程概述和编译程序的结构编译程序完成从源程序到目标程序的翻译工作，是一个复 杂的整体的过程。

从概念上来讲，一个编译程序的整个工作过 程是划分成阶段进行的，每个阶段将源程序的一种表示形式转 换成另一种表示形式，各个阶段进行的操作在逻辑上是紧密连 接在一起的。

一般一个编译过程划分成词法分析、语法分析、 语义分析、中间代码生成，代码优化和目标代码生成六个阶段,这是一种典型的划分方法。

事实上，某些阶段可能组合在一起， 这些阶段间的源程序的中间表示形式就没必要构造岀来了。

我 们将分别介绍各阶段的任务。

另外两个重要的工作：表格管理 和岀错处理与上述六个阶段都有联系。

编译过程中源程序的各 种信息被保留在种种不同的表格里，编译各阶段的工作都涉及 到构造、查找或更新有关的表格，因此需要有表格管理的工作； 如果编译过程中发现源程序有错误，编译程序应报告错误的性 质和错误发生的地点，并且将错误所造成的影响限制在尽可能 小的范围内，使得源程序的其余部分能继续被编译下去，有些 编译程序还能自动校正错误， 这些工作称之为岀错处理。

图1.3表示了编译的各个阶段。

图1.3编译的各个阶段它不生成目标代码，它每遇到一个语句，就要对这个语句进行 分析以决定语句的含义，执行相应的动作。

右面的图示意了它 的工作机理第二章：PL/O 编译程序问答第1题 PL/0语言允许过程嵌套定义和递归调用，试问 它的编译程序如何解决运行时的存储管理。

答：PL/0语言允许过程嵌套定义和递归调用，它的编译程序在运行时采用了栈式动态存储管理。

(数组CODE 存放的只读目 标程序，它在运行时不改变。

)运行时的数据区S 是由解释程序 定义的一维整型数组，解释执行时对数据空间S 的管理遵循后进先岀规则，当每个过程(包括主程序)被调用时，才分配数据 空间，退出过程时，则所分配的数据空间被释放。

第6 章自底向上优先分析第1 题已知文法G[S]为：S→a|∧|(T)T→T,S|S(1) 计算G[S]的FIRSTVT 和LASTVT。

(2) 构造G[S]的算符优先关系表并说明G[S]是否为算符优先文法。

(3) 计算G[S]的优先函数。

(4) 给出输入串(a,a)#和(a,(a,a))#的算符优先分析过程。

答案：文法展开为：S→aS→∧S→(T)T→T,ST→S(1) FIRSTVT - LASTVT 表：表中无多重人口所以是算符优先（OPG）文法。

友情提示：记得增加拓广文法 S`→#S#，所以# FIRSTVT(S)，LASTVT(S) #。

(3)对应的算符优先函数为：Success!对输入串（a,(a,a)）# 的算符优先分析过程为：Success!第2 题已知文法G[S]为：S→a|∧|(T)T→T,S|S(1) 给出(a,(a,a))和(a,a)的最右推导，和规范归约过程。

(2) 将(1)和题1 中的(4)进行比较给出算符优先归约和规范归约的区别。

答案：(2)算符优先文法在归约过程中只考虑终结符之间的优先关系从而确定可归约串，而与非终结符无关，只需知道把当前可归约串归约为某一个非终结符，不必知道该非终结符的名字是什么，因此去掉了单非终结符的归约。

规范归约的可归约串是句柄，并且必须准确写出可归约串归约为哪个非终结符。

第３题：有文法G[S]：S VV T|ViTT F|T+FF )V*|((1) 给出(+(i(的规范推导。

(2) 指出句型F+Fi(的短语，句柄，素短语。

(3) G[S]是否为OPG若是，给出(1)中句子的分析过程。

因为该文法是OP，同时任意两个终结符的优先关系唯一，所以该文法为OPG。

(+(i(的分析过程第４题文法G［S］为：S→S;G｜GG→G(T)｜HH→a｜(S)T→T+S｜S（１）构造G［S］的算符优先关系表，并判断G［S］是否为算符优先文法。

（２）给出句型a(T+S);H;(S)的短语、句柄、素短语和最左素短语。

第六章习题解答6.1根据语法树，得到下述优先关系：E′*(E T′>+ F>* i>*+<T +<F +<i *<(6.2由文法各条产生式，有然后构造<：FIRST={(Z,b),(M,(),(M,a),(L,M)}FIRST+={(Z,b),(M,(),(M,a),(L,M),(L,(),(L,a)}FIRST*=FIRST+∪{(a,a),(b,b),((,(),( ),)),(Z,Z),(M,M),(L,L)}所以<={(b,(),(b,a),((,M),((,(),((,a))再构造>：LAST={(Z,b),(M,L),(M,a),(L,))}LAST+={(Z,b),(M,L),(M,a),(M,))(L,))}(LAST+)T={(b,Z),(L,M),(a,M),( ),M},( ),L}}(LAST+)T所以>={(L,b),(L,a),(a,b),(a,a),( ),b),(),a)}将这三种关系合并得到表6.1。

利用此算法分析符号串b((aa)a)b是否是文法G[Z]的句子，过程如表6.2所示。

分析成功，符号串b((aa)a)b是文法G[Z]的句子。

表6.1 G[Z]的简单优先关系矩阵表6.2 简单优先分析过程6.3由优先关系矩阵中所示的优先关系：a>c a<b b>b b以及优先函数的定义，应该有f(a)>g(c)，f(a)<g(b)，f(b)>g(b)，f(b)=g(c)则有f(a)>g(c)=f(b)>g(b)>f(a)矛盾。

所以该文法不存在优先函数。

6.4①定义集合∑=N，R={(x,y)∣x,y∈∑,x是y的因子}②定义集合∑=N,R={(x,y)|x,y∈∑,x和y均能被3整除}③定义集合∑=N-{1}，R={(x,y)|x,y∈∑,x和y有大于1的公约数}④定义集合∑=N,R为关系“=”6.5关系可以用集合定义，也可以用布尔矩阵表示。

第6章自底向上优先分析第1题已知文法G[S]为：S T a|A |(T)T,S|S(1)计算 G[S]的 FIRSTVT 和 LASTVT。

(2)构造G[S]的算符优先关系表并说明G[S]是否为算符优先文法。

⑶计算G[S]的优先函数。

(4)给出输入串(a,a)#和(a,(a,a))#的算符优先分析过程。

答案：文法展开为：S^aS T AS T (T)T T T,ST T S猱符优先关系表:友情提示：记得增加拓广文法S' T#S#，所以# FIRSTVT(S) , LASTVT(S) # 。

Success!对输入串(a,(a,a) ) #的算符优先分析过程为:栈〔STACK) 为询字符WH恋)剩余输入笊(INPUT_STRING)动作〔ACTION)岸n a.(a.a))# e ill * a 伽)># itove iiima{aa)> Reduce: S—q <a.a)># Move iii( a.a))# Move iiia 讪Move iiia))# Reduce: S—日#(N,(N i a))# \tove iii#(N.(N a Move m粼屈)Reduce: S—R粼N(N.N)Reduce； T—丁占)h【ovE iii)#Reduce: S—*(T) #(N,N )#Reduce: T—*T,S #(N )Move iiiKN) ##Reduce: S—"(T) Success!第2题已知文法G[S]为：S T a|A |(T)T,S|S(1)给出(a,(a,a))和(a,a)的最右推导，和规范归约过程。

⑵ 将⑴和题1中的⑷进行比较给出算符优先归约和规范归约的区另叽答案：(1 ) (n・a)的授右推导过程为: sn(T) =(T.S)=^(T.a)=>(S.a)=>(a.a)(a.(a.a))的最右推导过程为:S=>(T)O(T.S)=(T.(T))=>(r.(r.s))=>(T.(T.a))=>(T.(S.a))=>(T-(a.a))=>(S.(a.a))=>(a.(a.a))(a.(a.a))的规范归约过程:(冇)的规范！H约过阻(2)非终结符无关，只需知道把当前可归约串归约为某一个非终结符，不必知道该非终结符的名字是什么，因此去掉了单非终结符的归约。