《编译原理教程》习题解析与上机指导(第四版) 第十章

《编译原理》课后习题答案第一章
是哪种方式，其加工结果都是源程序的执行结果。目前很多解释程序采取上述两种方式的综 合实现方案，即先把源程序翻译成较容易解释执行的某种中间代码程序，然后集中解释执行 中间代码程序，最后得到运行结果。
广义上讲，编译程序和解释程序都属于翻译程序，但它们的翻译方式不同，解释程序是 边翻译（解释）边执行，不产生目标代码，输出源程序的运行结果。而编译程序只负责把源 程序翻译成目标程序，输出与源程序等价的目标程序，而目标程序的执行任务由操作系统来 完成，即只翻译不执行。
好似滚雪球一样，直到我们所要求的编译程序。 （4）移植：将 A 机器上的某高级语言的编译程序搬到 B 机器上运行。
《编译原理》课后习题答案第一章
第６题
计算机执行用高级语言编写的程序有哪些途径?它们之间的主要区别是什么?
答案： 计算机执行用高级语言编写的程序主要途径有两种，即解释与编译。 像 Basic 之类的语言，属于解释型的高级语言。它们的特点是计算机并不事先对高级语
第4题
对下列错误信息，请指出可能是编译的哪个阶段（词法分析、语法分析、语义分析、 代码生成）报告的。 （1） else 没有匹配的 if （2） 数组下标越界 （3） 使用的函数没有定义 （4） 在数中出现非数字字符
答案： （1） 语法分析 （2） 语义分析 （3） 语法分析 （4） 词法分析
第5题
b∶=10; end (q); procedure s; var c,d; procedure r;
var e,f; begin (r)
call q; end (r); begin (s) call r; end (s); begin (p) call s;
end (p); begin (main)

(1) 试应用DAG进行优化； (2) 假定只有R、H在基本块出口是活跃的，写出优化后 的四元式序列； (3) 假定只有两个寄存器AX、BX，试写出上述优化后 的四元式序列的目标代码。 【解答】 (1) 根据DAG的构造算法构造基本块P的DAG 步骤如图7-1的(a)到(h)所示。
MOV MUL
R1, A R1, R0 该结果
//取一个空闲寄存器 R1 //运算结束后 R1 中为 T2 结果，内存中无
MOV R0, D
ADD R0, ?1? 该结果
/*此时 R0 中结果 T1 已经没有引用点， 且临时单元 T1 是非活跃的，所以，寄存 器 R0 可作为空闲寄存器使用*/ //运算结束后 R0 中为 T3 结果，内存中无
本块时，所有的寄存器被当成空闲的寄 存器使用，从而造成计算结果的丢失。
考虑到寄存器 R0 中的 T5和寄存器 R1 中 的 W，临时单元 T5 是非活跃的，因此 只要将结果 W 存回对应单元即可*/
7.4 对基本块 P：
S0=2 S1=3/S0 S2=T-C S3=T+C R=S0/S3 H=R S4=3/S1 S5=T+C S6=S4/S5 H=S6*S2
我们以四元式T=a+b为例来说明其翻译过程。 汇编语言的加法指令代码形式为
ADD R, X
其中，ADD为加法指令；R为第一操作数，第一操作数必须 为寄存器类型；X为第二操作数，它可以是寄存器类型，也 可以是内存型的变量。ADD R,X指令的含义是：将第一操 作数R与第二操作数相加后，再将累加结果存放到第一操作 数所在的寄存器中。要完整地翻译出四元式T=a+b，则可能 需要下面三条汇编指令：
MOV T2, R1
MOV R1, E SUB R1, F MUL R0, R1

第7 题证明下述文法G[〈表达式〉]是二义的。

〈表达式〉∷=a|(〈表达式〉)|〈表达式〉〈运算符〉〈表达式〉〈运算符〉∷=+|-|*|/答案：可为句子a+a*a 构造两个不同的最右推导:最右推导1 〈表达式〉=>〈表达式〉〈运算符〉〈表达式〉=>〈表达式〉〈运算符〉a=>〈表达式〉* a=>〈表达式〉〈运算符〉〈表达式〉* a=>〈表达式〉〈运算符〉a * a=>〈表达式〉+ a * a=>a + a * a最右推导2 〈表达式〉=>〈表达式〉〈运算符〉〈表达式〉=>〈表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式〉=>〈表达式〉〈运算符〉〈表达式〉〈运算符〉a=>〈表达式〉〈运算符〉〈表达式〉* a=>〈表达式〉〈运算符〉a * a=>〈表达式〉+ a * a=>a + a * a第8 题文法G[S]为：S→Ac|aB A→ab B→bc该文法是否为二义的？为什么？答案：对于串abc(1)S=>Ac=>abc (2)S=>aB=>abc即存在两不同的最右推导。

所以，该文法是二义的。

或者：对输入字符串abc，能构造两棵不同的语法树，所以它是二义的。

第9 题考虑下面上下文无关文法：S→SS*|SS+|a(1)表明通过此文法如何生成串aa+a*，并为该串构造语法树。

(2)G[S]的语言是什么？答案：(1)此文法生成串aa+a*的最右推导如下S=>SS*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*(2)该文法生成的语言是：*和+的后缀表达式，即逆波兰式。

第10 题文法S→S(S)S|ε(1) 生成的语言是什么？(2) 该文法是二义的吗？说明理由。

答案：（１）嵌套的括号（２）是二义的，因为对于（）（）可以构造两棵不同的语法树。

第11 题令文法G[E]为：E→T|E+T|E-T T→F|T*F|T/F F→(E)|i证明E+T*F 是它的一个句型，指出这个句型的所有短语、直接短语和句柄。

试用图表示 ex 调用 PP(a)前后活动记录的过程。
第六章 运行时存储空间组织 【解答】 按照嵌套过程语言栈式实现方法，ex调用PP(a)
前后活动记录的过程如图6-2所示。
图6-2 ex调用PP(a)前后的活动记录
第六章 运行时存储空间组织
6.5 类 PASCAL 结构(嵌套过程)的程序如下，该语言的编 译器采用栈式动态存储分配策略管理目标程序数据空间：
第六章 运行时存储空间组织 第六章 运行时存储空间组织
第六章 运行时存储空间组织
6.1 完成下列选择题：
(1) 分配目标程序数据空间的基本策略分为
。
A．栈式分配和堆式分配

B．局部分配和整体分配
C．静态分配和动态分配
D．程序运行之前分配
(2) 过程的DISPLAY表中记录了
。
A．过程的连接数据
B．过程的嵌套层次
第六章 运行时存储空间组织 图6-1 递归过程的活动记录
第六章 运行时存储空间组织
过程进入指令为
SP=TOP+1 1[SP]=返回地址
TOP=TOP+L 建立 DISPLAY 表 P； 返回指令为 TOP=SP-1
/*执行 P 过程*/
SP=0[SP]
X=2[TOP]
UJ 0[X]
(2) 对于 return 后的直接递归情况，可简化为
后放”和“后请先放”的原则，即申请和释放的顺序是任意的。 故选D。
第六章 运行时存储空间组织
(5) 栈式动态分配与管理在过程返回时应做的工作有：① 恢复老TOP；② 恢复老SP；③ 根据返回地址无条件返回。故 选B。
(6) 如果活动记录中没有DISPLAY表，则说明程序中不允 许有嵌套定义的过程。故选B。