中 国 科 学 技 术 大 学
2006－2007 学年第二学期考试试卷（A）
考试科目：编译原理和技术 得分：
学生所在系： 姓名： 学号：
1、（ 10 分）用子集构造法给出由下面的 NFA 得到的 DFA 的转换表
2、（ 20 分）（1）通过构造识别活前缀的 DFA 和构造分析表，来证明文法 E E + id | id
是 SLR(1)文法。
（2）下面左右两个文法都和（1）的文法等价
E E + M id | id E M E + id | id
M M
请指出其中有几个文法不是 LR(1)文法，并给出它们不是 LR(1)文法的理由。
3、（ 10 分）下面是 C 语言两个函数 f 和 g 的概略（它们不再有其它的局部变量）：
int f (int x) { int i; …return i +1; … }
int g (int y) {int j; … f (j +1); … }
请按照教材上例 6.5 中图 6.13 的形式，画出函数 g 调用 f，f 的函数体正在执行时，活动记
录栈的内容及相关信息，并按图 6.12 左侧箭头方式画出控制链。假定函数返回值是通过寄
存器传递的。
4、（ 10 分）C 语言函数 f 的定义如下：
int f (int x, int py, int ppz)
{
ppz +=1; py +=2; x +=3; return x + py + ppz;
}
变量 a 是指向 b 的指针，变量 b 是指向 c 的指针，c 是整型变量并且当前值是 4。那么执行 f
(c, b, a)的返回值是多少？
5、（ 10 分）Java 语言的实现通常把对象和数组都分配在堆上，把指向它们的指针分配在
栈上，依靠运行时的垃圾收集器来回收堆上那些从栈不可达的空间（垃圾）。这种方式提
高了语言的安全性，但是增加了运行开销。编译时能否采用一些技术，以降低垃圾收集所
占运行开销？概述你的方案。
0 1
start
3
2
a, b
a
a
a b
a, b
a, b
