4．（15分）就下面文法 S ? ( L) | a L ? L ? S | S
? 给出一个语法制导定义，它输出配对括号的个数。 ? 给出一个翻译方案，它输出每个a的嵌套深度。
如句子(a, (a, a) )，第一小题的输出是2，第二小题的输出是1 2 2。 5．（10分）Pascal语言for语句的含义见教材第222页习题7.13。请为该语句设计一种合理的中间代码结构。你可以按第215页图7.17的方式或者第219页图7.19的方式写出你的设计，不需要写产生中间代码的语法制导定义。 6．（5分）一个C语言程序如下：
func(i1,i2,i3) long i1,i2,i3; {
long j1,j2,j3;
printf(\ printf(\}
main() {
long i1,i2,i3; func(i1,i2,i3); }
该程序在某种机器的Linux上的运行结果如下：
Addresses of i1,i2,i3 = 27777775460,27777775464,27777775470 Addresses of j1,j2,j3 = 27777775444,27777775440,27777775434
从上面的结果可以看出，func 函数的3个形式参数的地址依次升高，而3个局部变量的地址依次降低。试说明为什么会有这个区别。 7．（15分）一个C语言程序及其在某种机器linux操作系统上的编译结果如下。根据所生成的汇编程序来解释程序中四个变量的作用域、生存期和置初值方式等方面的区别。
static long aa = 10; short bb = 20;
func() {
第45页共6页
static long cc = 30; short dd = 40; }
.file \ .version \gcc2_compiled.: .data
.align 4
.type aa,@object .size aa,4 aa:
.long 10 .globl bb .align 2
.type bb,@object .size bb,2 bb:
.value 20 .align 4
.type cc.2,@object .size cc.2,4 cc.2:
.long 30 .text
.align 4 .globl func
.type func,@function func:
pushl ?p
movl %esp,?p subl $4,%esp
movw $40,-2(?p) .L1:
leave ret .Lfe1:
.size func,.Lfe1-func .ident \(GNU) egcs-2.91.66 19990314/Linux (egcs-1.1.2 release)\ 8．（10分）C语言是一种类型语言，但它不是强类型语言，因为编译时的类型检查不能保证所接受的程序没有运行时的类型错误。例如，编译时的类型检查一般不能保证运行时没有数组越界。请你再举一个这样的例子说明C语言不是强类型
第46页共6页
语言。 9．（10分）如果在A机器上我们有C语言编译器CCA，也有它的源码SA（用C语言写成）。如何利用它通过尽量少的工作来得到B机器的C语言编译器CCB。 10．（5分）表达式(?x.(?yz.(x + y) + z) 3) 4 5和(?x.(?yz.(x + y) + z) 3 5) 4有同样的结果。在抽象机FAM上，哪一个表达式对应的目标代码的执行效率高？为什么？
参考答案 1．
others start 1 / 2 * 2 * others 4 *
/ 5
2．LR（1）文法 LR（1）文法 二义文法 S ? AB | aABb S ? AB S ? AASb | ? A ? aaAb | ? A ? aaAb | ab | ? A ? a | ?
B ? Bb | ? B ? Bb | ? 3． int real id , $ D D?TL D?TL T T?int T?real L L?id R R R ?, id R R ? ?
4． S? ? S print(S.num) S ? (L) S.num := L.num +1 S ? a S.num := 0 L ? L1,S L.num := L1.num + S.num L ? S L.num := S.num S? ? {S.depth := 0} S S ? {L.depth := S.depth +1} (L) S ? a {print(S.depth)} L ? {L1.depth := L.depth} L1, {S.depth := L.depth} S L ? { S.depth := L.depth} S 5． t1 := initial t2 := final if t1 > t2 goto L1 v := t1 L2: stmt
第47页共6页
if v = t2 goto L1 v := v + 1 goto L2 L1: 6．由于实参表达式是反序进入活动记录，而局部变量是顺序在活动记录中分配。 7．aa是静态外部变量，而bb是外部变量，它们都分配在静态数据区（由.data伪指令开始），但是bb由伪指令.globl指明为全局的，用来解决其它文件中对bb的外部引用，而aa只能由本文件引用。cc是静态局部变量，同aa和bb一样，它的生存期是整个程序并分配在静态数据区。由于cc在源程序中的作用域是函数func的体，而在目标文件中，它的作用域至少已是整个文件了，为避免同源文件中外部变量和其它函数的静态局部变量的名字冲突，所以要对它进行改名，成了cc.2。由于cc不是全局的，因此cc.2前面没有伪指令.globl。dd是自动变量，其作用域是函数func的体，其生存期是该函数激活期间，因此它分配在栈区，并且置初值是用运行时的赋值来实现。
8．例如联合体的类型检查一般也不可能在编译时完成，虽然下面例子是可静态判断类型错误的。 union U { int u1; int *u2;} u; int ?p; u.u1 = 10; p = u.u2; ?p = 0;
9． ? 修改源码SA 的代码生成部分，让它产生B机器的代码，称结果程序为SB。 ? 将SB提交给CCA进行编译，得到一个可执行程序。
? 将SB提交给上述可执行程序进行编译，得到所需的编译器CCB。
10．第一个表达式在执行?yz.(x + y) + z) 3时出现参数个数不足的情况，因此有FUNVAL的值进入栈顶，然后发现参数个数不足，又把它做成FANVAL的情况。而第二个表达式执行的是(?yz.(x + y) + z) 3 5，不会出现参数个数不足的情况。因此第二个表达式的执行效率比第一个表达式的高。
《编译原理》期末大题
1. 设有如下文法G（S），试消除其左递归。
G（S）：S—>Ac|c A—>Bb|b B—>Sa|a
解：
S→abcS′|bcS′|cS′, S′→abcS′|?
2. 试构造与下面G（S）等价的无左递归的文法。
G（S）：S—>Sa|Nb|c N—>Sd|Ne|f
解：S→fN′bS′|cS′, S′→aS′|dN′bS′|?, N′→eN′|? 3. 设有文法G（S）：
S—>aBc|bAB
第48页共6页