编译原理试卷八1、（10分）描述由正规式b*(abb*)*(a|)定义的语言，并画出接受该语言的最简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EandE|E+E|E=E|id4、（10分）对于下面C语言文件s.cf1(intx){longx;x=1;}f2(intx){{longx;x=1;}}某编译器编译时报错如下：s.c:Infunction‘f1’:s.c:3:warning:declarationof‘x’shadowsaparameter请回答，对函数f2为什么没有类似的警告错误。5、（10分）下面C语言程序经非优化编译后，若运行时输入2，则结果是area=12.566360,addr=-1073743076经优化编译后，若运行时输入2，则结果是area=12.566360,addr=-1073743068请解释为什么输出结果有区别。main(){floats,pi,r;pi=3.14159;scanf("%f",&r);printf("area=%f,addr=%d\n",s=pi*r*r,&r);}6、（10分）描述由正规式ba(bba)b定义的语言，并画出接受该语言的最简DFA。7、（20分）下面的文法产生代表正二进制数的0和1的串集：BB0|B1|1下面的翻译方案计算这种正二进制数的十进制值：BB10{B.val:=B1.val2}|B11{B.val:=B1.val2+1}|1{B.val:=1}请消除该基础文法的左递归，再重写一个翻译方案，它仍然计算这种正二进制数的十进制值。8、（10分）在C语言中，如果变量i和j都是long类型，请写出表达式&i和表达式&i&j的类型表达式。为帮助你回答问题，下面给出一个程序作为提示，它运行时输出1。main(){longi,j;printf(“%d\n”,&i&j);}9、（10分）一个C语言的函数如下：func(i)longi;{longj;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|)定义的语言是字母表{a,b}上不含子串aa的所有串的集合。最简DFA如下：2、（10分）先给出接受该文法活前缀的DFA如下：E·EE·E+idE·idI0EE·EE·+idI1Eid·I2Eid+EE+·idI3EE+id·I4idI0和I3都只有移进项目，肯定不会引起冲突；I2和I4都无移进项目并仅含一个归约项目，也肯定不会引起冲突；在I1中，E的后继符号只有$，同第2个项目的展望符号“+”不一样，因此I1也肯定不会引起冲突。由此