资源描述
编译原理试卷八1、(10分)描述由正规式b*(abb*)*(a| e)定义的语言,并画出接受该语言的最简DFA。2、(10分)证明文法E E + id | id是SLR(1)文法。3、(10分)下面是表达式和赋值语句的文法,其中and的类型是bool bool bool,+的类型是int int int,=的类型是int int bool,:= 要求id 和E的类型都是int或者都是bool。为该文法写一个语法制导定义或翻译方案,它完成类型检查。S id := EE E and E | E + E | E = E |id4、(10分)对于下面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、(10分)下面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=%dn, s=pi*r*r, &r);6、(10分)描述由正规式b*a(bb*a) *b*定义的语言,并画出接受该语言的最简DFA。7、(20分)下面的文法产生代表正二进制数的0和1的串集:B B 0 | B 1 | 1下面的翻译方案计算这种正二进制数的十进制值:B B1 0B.val := B1.val 2 | B1 1B.val := B1.val 2 +1| 1 B.val := 1 请消除该基础文法的左递归,再重写一个翻译方案,它仍然计算这种正二进制数的十进制值。8、(10分)在C语言中,如果变量i和j都是long类型,请写出表达式&i和表达式&i-&j的类型表达式。为帮助你回答问题,下面给出一个程序作为提示,它运行时输出1。main() long i, j;printf(“%dn”, &i-&j);9、(10分)一个C语言的函数如下:func(i) long i; long j;j = i 1;func(j);下面左右两边的汇编代码是两个不同版本GCC编译器为该函数产生的代码。左边的代码在调用func之前将参数压栈,调用结束后将参数退栈。右边代码对参数传递的处理方式没有实质区别。请叙述右边代码对参数传递的处理方式并推测它带来的优点。func:|func:pushl%ebp|pushl%ebpmovl%esp, %ebp|movl%esp, %ebpsubl$4, %esp|subl$8, %espmovl8(%ebp), %edx|movl8(%ebp), %eaxdecl%edx|decl%eaxmovl%edx, -4(%ebp)|movl%eax, -4(%ebp)movl-4(%ebp), %eax|movl-4(%ebp), %eaxpushl%eax|movl%eax, (%esp)callfunc|callfuncaddl$4, %esp|leaveleave|retret|编译原理试卷八答案1、(10分)start1abb2由正规式b*(abb*)*(a| e)定义的语言是字母表a, b上不含子串aa的所有串的集合。最简DFA如下:2、(10分)先给出接受该文法活前缀的DFA如下:E EE E + idE idI0E EE E+ idI1E idI2Eid+E E +idI3E E + idI4idI0和I3都只有移进项目,肯定不会引起冲突;I2和I4都无移进项目并仅含一个归约项目,也肯定不会引起冲突;在I1中,E的后继符号只有$,同第2个项目的展望符号“+”不一样,因此I1也肯定不会引起冲突。由此可以断定该文法是SLR(1)的。3、(10分)语法制导定义如下。S id := E S.type := if (id.type = bool and E.type = bool) or (id.type = int and E.type = int)then type_ok else type_error E E1 and E2 E.type := if E1.type = bool and E2.type = bool then bool else type_error E E1 + E2 E.type := if E1.type = int and E2.type = int then int else type_error E E1 = E2 E.type := if E1.type = int and E2.type = int then bool else type_error E id E.type := lookup(id.entry) 4、(10分)对于函数f1,局部变量x声明的作用域是整个函数体,导致在函数体中不可能访问形式参数x。由于这是一个合法的C语言函数,因此编译器给出警告错误。对于函数f2,由于局部变量x的作用域只是函数体的一部分,不会出现上述问题,因而编译器不报错。5、(10分)使用非优化编译时,变量s, pi, r在局部数据区都分配4个字节的空间。使用优化编译时,由于复写传播,pi*r*r 变成3.14159*r*r,pi=3.14159成为无用赋值而删去,函数中不再有pi的引用,因此不必为pi分配空间。类似地,s=3.14159*r*r也是一个无用赋值(表达式要计算,但赋值是无用的),也不必为s分配空间。这样,和非优化情况相比,局部数据区少了8个字节, 因此r的地址向高地址方向移动了8个字节。start2abb10ab6、正规式b*a(bb*a) *b*体现的特点是,每个a的左边都有若干b,除非a是第一个字母。该正规式定义的语言是:至少含一个a,但不含子串aa的所有a和b的串集。最简DFA如下:7、消除左递归后的文法如下:B 1 BB 0 B | 1 B | e相应的翻译方案如下:B 1 B.i := 1 BB.val := B.valB 0 B1.i := B.i 2 B1 B.val := B1.val| 1 B1.i := B.i 2 +1 B1 B.val := B1.val| e B.val := B.i8、表达式&i的类型表达式是pointer(long),表达式&i-&j的类型表达式是long。按照C语言的规定,指向同一个类型的两个指针可以相加减,它们值的差是它们之间的元素个数。9、左边的编译器版本:一般只为局部变量分配空间。调用函数前,用若干次pushl指令将参数压栈,返回后用addl $n, %esp一次将所有参数退栈(常数n根据调用前做了多少次pushl来决定)。右边的编译器版本:除了为局部变量分配空间外,同时还为本函数中出现的函数调用的参数分配空间,并且参数所用空间靠近栈顶。调用函数前,用movl指令将参数移入栈顶,调用结束后无需参数退栈指令。优点是每次函数调用结束后不需要执行addl $n, %esp指令,另外增加优化的可能性。4
展开阅读全文