中国科技大学编译原理课程测试八套卷合集(附解析)

编译原理课程测试第一套卷（附解析）1．（20分）写出字母表={a,b}上语言L={w|w中a的个数是偶数}的正规式，并画出接受该语言的最简DFA。2．（15分）考虑下面的表达式文法，它包括数组访问、加和赋值：EE[E]|E+E|E=E|(E)|id该文法是二义的。请写一个接受同样语言的LR(1)文法，其优先级从高到低依次是数组访问、加和赋值，并且加运算是左结合，赋值是右结合。3．（10分）下面是产生字母表={0,1,2}上数字串的一个文法：SDSD|2D0|1写一个语法制导定义，它打印一个句子是否为回文数（一个数字串，从左向右读和从右向左读都一样时，称它为回文数）。4．（10分）教材上7.2.1节的翻译方案P{offset:=0}DDD;DDid:T{enter(id.name,T.type,offset);offset:=offset+T.width}Tinteger{T.type:=integer;T.width:=4}Treal{T.type:=real;T.width:=8}使用了变量offset。请重写该翻译方案，它完成同样的事情，但只使用文法符号的属性，而不使用变量。5．（5分）一个C语言程序如下：voidfun(struct{intx;doubler;}val){}main(){struct{intx;doubler;}val;fun(val);}该程序在X86/Linux机器上的用cc命令编译时，报告的错误信息如下：1:warning:structuredefinedinsideparms1:warning:anonymousstructdeclaredinsideparameterlist1:warning:itsscopeisonlythisdefinitionordeclaration,1:warning:whichisprobablynotwhatyouwant.7:incompatibletypeforargument1of‘fun’请问，报告最后一行的错误的原因是什么？如何修改程序，使得编译时不再出现这个错误信息。6．（10分）一个C语言程序如下：typedefstruct_a{shorti;shortj;shortk;}a;typedefstruct_b{longi;shortk;}b;main(){printf(Sizeofshort,long,aandb=%d,%d,%d,%d\n,sizeof(short),sizeof(long),sizeof(a),sizeof(b));}该程序在X86/Linux机器上的运行结果如下：Sizeofshort,long,aandb=2,4,6,8已知short类型和long类型分别对齐到2的倍数和4的倍数。试问，为什么类型b的size会等于8？7．（15分）一个C语言程序如下：intfact(i)inti;{if(i==0)return1;elsereturni*fact(i-1);}main(){printf(%d\n,fact(5));printf(%d\n,fact(5,10,15));printf(%d\n,fact(5.0));printf(%d\n,fact());}该程序在X86/Linux机器上的运行结果如下：1201201Segmentationfault(coredumped)请解释下面问题：第二个fact调用：结果为什么没有受参数过多的影响？第三个fact调用：为什么用浮点数5.0作为参数时结果变成1?第四个fact调用：为什么没有提供参数时会出现Segmentationfault？8．（5分）C语言的赋值操作并非仅对简单类型而言，例如若有类型声明longa[100],b[100];，则赋值a=b是允许的。同样，若a和b是同一类型的两个结构，则赋值a=b也是允许的。用教材上第七章所给出的三地址语句，我们能否为这种赋值产生中间代码？若你持肯定态度，请你给出对应这种赋值的中间代码序列；否则请你为这种赋值设计一种三地址语句。你所选用或设计的三地址语句要便于目标代码的生成。9．（5分）一个C程序的三个文件的内容如下：head.h:shortinta=10;file1.c:#includehead.hmain(){}file2.c:#includehead.h在X86/Linux机器上的编译命令如下：ccfile1.cfile2.c编译结果报错的主要信息如下：multipledefinitionof‘a’试分析为什么会报这样的错误。10．（5分）按照教材上介绍的方法，把下面C++语言的函数翻译成C的函数。voidzoom(GraphicalObj&obj,doublezoom_factor,Point¢er){obj.translate(center.x,center.y);//将中心点移至原点(0,0)obj.scale(zoom_factor);//缩放}编译原理课程测试第一套卷参考答案1．语言L的正规式是：(ab*a|b)*或b*(ab*ab*)*接受该语言的最简DFA是：2start1abba2．ET=E|TTT+F|FFF[E]|(E)|id3．SSprint(S.val)SD1S1D2S.val=(D1.val=D2.val)andS1.valS2S.val=trueD0D.val=0D1D.val=14．文法符号D的属性offset1是继承属性，代表在分析D前原来使用的变量offset的大小；属性offset2是综合属性，代表在分析D后原来使用的变量offset的大小。P的属性offset是综合属性，记录该过程所分配的空间。P{D.offset1:=0}D{P.offset:=D.offset2}D{D1.offset1:=D.offset1}D1;{D2.offset1:=D1.offset2}D2{D.offset2:=D2.offset2}Did:T{enter(id.name,T.type,D.offset1);D.offset2:=D.offset1+T.width}Tinteger{T.type:=integer;T.width:=4}Treal{T.type:=real;T.width:=8}5．C语言对所有的类型都采用结构等价，唯有结构类型例外，采用名字等价。这里的类型不相容是因为两个val不是名字等价的。要消除这个错误，包括所有的警告，程序修改如下：structs{intx;doubler;};voidfun(structsval){}main(){structsval;fun(val);}6．一个数组的size等于数组元素的size乘以数组元素的个数，这是一个原则。对于结构类型b来说，它的一个变量只需6个字节就够了。如果声明结构类型b的一个数组，有两种可能：（a）结构类型b的size是6，数组元素之间空两个字节，以保证每个数组元素的地址都是4的倍数（因为第一个域i的类型是long，要求对齐到4的倍数）。（b）结构类型b的size是8，以保证它作为数组元素的类型时，数组元素之间不用再考虑对齐问题。方法（a）违反了我们一开始提到的原则，因此只能取方法（b）。7．（1）参数表达式逆序计算并进栈，fact能够取到第一个参数。（2）参数5.0转换成双精度数进栈，占8个字节。它低地址的4个字节看成整数时正好是0。（3）由于没有提供参数，fact把老ebp（控制链）（main的活动记录中保存的ebp）当成参数，它一定是一个很大的整数，使得活动记录栈溢出。8．教材上的中间代码有形如x:=y的复写语句，用它就可以了。但是生成目标代码时，必须考虑x和y的类型。若x和y不是简单类型，则应该根据它们类型的size，产生一连串的值传送指令。9．由于file1.c和file2.c两个文件都包含文件head.h，而head.h中有shortinta=10，因此该程序有两个a的强符号定义。10．按照教材上介绍的方法，函数的翻译结果如下：voidzoom(GraphicalObj&obj,doublezoom_factor,Point¢er){obj.vptr[0](obj,center.x,center.y);//将中心点移至原点(0,0)obj.vptr[1](obj,zoom_factor);//缩放}编译原理课程测试第二套卷（附解析）1．（20分）写出字母表={a,b}上语言L={w|w的最后两个字母是aa或bb}的正规式，并画出接受该语言的最简DFA。2．（15分）说明下面的文法不是SLR(1)文法，并重写一个等价的SLR(1)文法。SMa|bMc|dc|bdaMd3．（10分）为下面的语言写一个无二义的文法：ML语言中用分号分隔语句的语句块，例如：((s;s);(s;s;s);s);(s;s)4．（20分）考虑一个类Pascal的语言，其中所有的变量都是整型（不需要显式声明），并且仅包含赋值语句、读语句、写语句，条件语句和循环语句。下面的产生式定义了该语言的语法（其中lit表示整型常量；OP的产生式没有给出，因为它和下面讨论的问题无关）。定义Stmt的两个属性：MayDef表示它可能定值的变量集合，MayUse表示它可能引用的变量集合。（1）写一个语法制导定义或翻译方案，它计算Stmt的MayDef和MayUse属性。（2）基于MayDef和MayUse属性，说明Stmt1;Stmt2和Stmt2;Stmt1在什么情况下有同样的语义。ProgramStmtStmtid:=ExpStmtread(id)Stmtwrite(Exp)StmtStmt;StmtStmtif(Exp)thenbeginStmtendelsebeginStmtendStmtwhile(Exp)dobeginStmtendExpidExplitExpExpOPExp5．（10分）下面是一个C语言程序：main(){longi;longa[0][4];longj;i=4;j=8;printf(“%d,%d\n”,sizeof(a),a[0][0]);}虽然出现longa[0][4]这样的声明，在X86/Linux机器上该程序还是能通过编译并生成目标代码。请回答下面两个问题：（1）sizeof(a)的值是多少，请说明理由。（2）a[0][0]的值是多少，请说明理由。6．（15分）考虑下面的三地址语句序列：b:=1b:=2ifw=xgotoL2e:=bgotoL2L1:gotoL3L2:c:=3b:=4c:=6L3:ify=zgotoL4gotoL5L4:g:=g+1h:=8gotoL1L5:h:=9（1）在该代码中用水平的横线将代码分成基本块，并给每个基本块一个序号。（2）画出该代码的控制流图，每个基本块就用（1）的序号表示。（3）若有循环的话，列出构成每个循环的结点。7．（5分）如果（1）用编译命令cctest.c会报告有未定义的符号；（2）用编译命令cctest.c–lusr.a会得到可执行程序（–lusr.a表示连接库libusr.a）。那么，用编译命令cctest.c–lusr.a–lusr.a是否会报告有多重定义的符号？请说明理由。8．（5分）C++中的对象声明语句应如何翻译成C语句？如书上图11.11程序中的Point_center;应翻译成什么？编译原理课程测试第二套卷参考答案1．语言L的正规式是：(a|b)*(aa|bb)接受该语言的最简DFA是：2．S’SSMa|bMc|dc|bdaMd因为a是M的后继符号之一，因此在上面最右边一个项目集中有移进归约冲突。等价的SLR(1)文法是Sda|bdc|dc|bda3．SLS|SL;SSs|(SL)4．（1）ProgramStmtStmtid:=Exp{Stmt.MayDef:={id.name};Stmt.MayUse:=Exp.MayUse}Stmtread