编译原理期末试题(三)附答案-.docVIP

《编译原理》期末试题（三） 1、描述由正规式b*(abb*)*(a| ?)定义的语言，并画出接受该语言的最简DFA。 2、证明文法E ? E + id | id是SLR(1)文法。 3、下面是表达式和赋值语句的文法，其中and的类型是bool ? bool ? bool，+的类型是int ? int ? int，=的类型是int ? int ? bool，:= 要求id 和E的类型都是int或者都是bool。为该文法写一个语法制导定义或翻译方案，它完成类型检查。 S ? id := E E ? E and E | E + E | E = E |id 4、对于下面C语言文件s.c f1(int x) { long x; x = 1; } f2(int x) { { long x; x = 1; } } 某编译器编译时报错如下： s.c: In function ‘f1’: s.c:3: warning: declaration of ‘x’ shadows a parameter 请回答，对函数f2为什么没有类似的警告错误。 5、下面C语言程序经非优化编译后，若运行时输入2，则结果是 area=12.566360, addr=-1073743076 经优化编译后，若运行时输入2，则结果是 area=12.566360, addr=-1073743068 请解释为什么输出结果有区别。 main() { float s, pi, r; pi=3.14159; scanf(%f, r); printf(area=%f, addr=%d\n, s=pi*r*r, r); } 6、描述由正规式b?a(bb?a) ?b?定义的语言，并画出接受该语言的最简DFA。 7、下面的文法产生代表正二进制数的0和1的串集： B ? B 0 | B 1 | 1 下面的翻译方案计算这种正二进制数的十进制值： B ? B1 0 {B.val := B1.val ? 2 } | B1 1 {B.val := B1.val ? 2 +1} | 1 {B.val := 1 } 请消除该基础文法的左递归，再重写一个翻译方案，它仍然计算这种正二进制数的十进制值。 8、 在C语言中，如果变量i和j都是long类型，请写出表达式i和表达式i?j的类型表达式。为帮助你回答问题，下面给出一个程序作为提示，它运行时输出1。 main() { long i, j; printf(“%d\n”, i?j); } 9、一个C语言的函数如下： func(i) long i; { long j; j = i – 1; func(j); } 下面左右两边的汇编代码是两个不同版本GCC编译器为该函数产生的代码。左边的代码在调用func之前将参数压栈，调用结束后将参数退栈。右边代码对参数传递的处理方式没有实质区别。请叙述右边代码对参数传递的处理方式并推测它带来的优点。 func: | func: pushl %ebp | pushl %ebp movl %esp, %ebp | movl %esp, %ebp subl $4, %esp | subl $8, %esp movl 8(%ebp), %edx | movl 8(%ebp), %eax decl %edx | decl %eax movl %edx, -4(%ebp) | movl %eax, -4(%ebp) movl -4(%ebp), %eax | movl -4(%ebp), %eax pushl %eax | movl %eax, (%esp) call func | call func addl $4, %esp | leave leave | ret ret | 编译原理试卷三答案 start start 1 a b b 2 1、由正规式b*(abb*)*(a| ?)定义的语言是字母表{a, b}上不含子串aa的所有串的集合。最简DFA如下： 2、先给出接受该文法活前缀的DFA如下： E E? ?·E E ?·E + id E ?·id I0 E? ? E· E ? E·+ id I1 E ? id· I2 E id + E ? E +·id I3 E ? E + id· I4 id I0和I3都只有移进项目，肯定不会引