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) call p;
end (main). 答案：
程序执行到赋值语句 b∶=10 时运行栈的布局示意图为： 第 3 题
写出题 2 中当程序编译到r 的过程体时的名字表table 的内容。 name kind level/val adr size 答案：
题 2 中当程序编译到r 的过程体时的名字表table 的内容为： name kind level/val adr size x variable 0 dx y variable 0 dx+1
p procedure 0 过程p 的入口（待填） 5 《编译原理》课后习题答案第二章 a variable 1 dx
q procedure 1 过程q 的入口4
s procedure 1 过程s 的入口（待填） 5 c variable 2 dx d variable 2 dx
r procedure 2 过程r 的入口5 e variable 3 dx f variable 3 dx+1
注意：q 和s 是并列的过程，所以q 定义的变量b 被覆盖。
第 4 题
指出栈顶指针t，最新活动记录基地址指针b，动态链指针dl，静态链指针sl 与返 回地址ra 的用途。 答案：
栈顶指针 t，最新活动记录基地址指针b，动态链指针dl，静态链指针sl 与返回地址
ra 的用途说明如下：
t： 栈顶寄存器t 指出了当前栈中最新分配的单元(t 也是数组s 的下标)。
b：基址寄存器，指向每个过程被调用时，在数据区s 中给它分配的数据段起始 地址， 也称基地址。
sl： 静态链，指向定义该过程的直接外过程（或主程序）运行时最新数据段的基地址， 用以引用非局部（包围它的过程）变量时，寻找该变量的地址。
dl： 动态链，指向调用该过程前正在运行过程的数据段基地址，用以过程执行结束释 放数据空间时，恢复调用该过程前运行栈的状态。 ra： 返回地址，记录调用该过程时目标程序的断点，即调用过程指令的下一条指令的 地址，用以过程执行结束后返回调用过程时的下一条指令继续执行。
在每个过程被调用时在栈顶分配3 个联系单元，用以存放sl，dl， ra。
第 5 题
pl/0 编译程序所产生的目标代码是一种假想栈式计算机的汇编语言，请说明该汇编语 言中下列指令各自的功能和所完成的操作。 （１） int 0 a （２） opr 0 0 （３） cal l a 答案：
pl/0 编译程序所产生的目标代码中有3 条非常重要的特殊指令，这3 条__________指令在code 中
的位置和功能以及所完成的操作说明如下： 《编译原理》课后习题答案第二章 int 0 a
在过程目标程序的入口处，开辟a 个单元的数据段。a 为局部变量的个数+3。 opr 0 0
在过程目标程序的出口处，释放数据段（退栈），恢复调用该过程前正在运行的过程的 数据段基址寄存器b 和栈顶寄存器t 的值，并将返回地址送到指令地址寄存器p 中，以使 调用前的程序从断点开始继续执行。 cal l a
调用过程，完成填写静态链、动态链、返回地址，给出被调用过程的基地址值，送入基 址寄存器b 中，目标程序的入口地址a 的值送指令地址寄存器p 中，使指令从a 开始执行。 第 6 题
给出对 pl/0 语言作如下功能扩充时的语法图和ebnf 的语法描述。 (1) 扩充条件语句的功能使其为：
if〈条件〉then〈语句〉[else〈语句〉] (2) 扩充repeat 语句为：
repeat〈语句〉{；〈语句〉}until〈条件〉 答案：
对 pl/0 语言作如下功能扩充时的语法图和ebnf 的语法描述如下： (1) 扩充条件语句的语法图为：
ebnf 的语法描述为： 〈条件语句〉::= if〈条件〉then〈语句〉[else〈语句〉]
(2) 扩充repeat 语句的语法图为：
ebnf 的语法描述为： 〈 重复语句〉::= repeat〈语句〉{；〈语句〉}until〈条件〉
【篇二：编译原理复习题2(第二版张素琴吕映芝蒋维杜
戴桂兰编著)】
|e+t|e-t
t?f|t*f|t/ff?（e）|i 1） 2）
给出i+i*i的最左推导和最右推导； 给出i-i-i的语法树。
∵e=e+t=e+t*f ∴e+t*f是文法g[e]的一个句型 ∴此句型相对于e
的短语有:e+t*f；相对于t的短语有t*f, 直接短语为：t*f；。 句柄为：t*f
2、设有文法g[s]:（12分）
1）请给出句子(a,(a,a))的最左,最右推导 2）给出(a,(a,a))的语法树 3、下面的文法生成的是以x和y为操作数、二元运算符+、*和-为运算符的前缀表达式： e?+ee|*ee|-ee|x|y
1） 给出串+*-xyxy的最左推导和最右推导； 2） 给出+*-xyxy的语法树。
4、将下图中的自动机确定化并最小化。 5、将下图中的自动机确定化并最小化。 6、设有dfa m=(k,∑,f,s,z) 其中：
k={0，1，2，3} ∑={a,b}s=0 z={3} f为： f(0,a)=1 f(1,b)=1 f(0,b)=2
f(2,a)=1 f(1,a)=3 f(2,b)=3 试画出其状态转换矩阵和状态转换图。 7、将下图中的自动机确定化。 8、考虑下面文法g1：（18分） s?a|?|(t) t?t，s|s
1） 消去g1的左递归；
2） 经改写后的文法是否是ll(1)的？给出它的预测分析表(要求写出详细过程，应先
求出每个非终结符的first和follow集合)。 9、构造正规式1(0|1)101相应的自动机 *
10、考虑下面文法g1： e?e+t|t t?t*f|f f?i|(e)
3） 消去g1的左递归；
4） 经改写后的文法是否是ll(1)的？ (要求写出详细过程，应先求出改写后的每个非
终结符的first和follow集合)。
11、对于文法g（s）： s?(l)|as|a l?l,s|s 1）画出句型(s,(a))的语法树。
2）写出上述句型的所有短语、直接短语、句柄和素短语。 12、对于文法g（s）： s?(l)|as|a l?l,s|s
1）画出句型(s,(a))的语法树。
2）写出上述句型的所有短语、直接短语、句柄和素短语。 13、对于文法g（e）： e?t|e+t t?f|t*f f?(e)|i|j|k
1）画出句型i*j+k的语法树。
2）写出上述句型的所有短语、直接短语、句柄和素短语。 14、设文法g（s）：
相关推荐：
loading