编译原理期末考试卷

12001年编译原理试题1．（10分）处于/*和*/之间的串构成注解，注解中间没有*/。画出接受这种注解的DFA的状态转换图。2．（10分）为语言L＝{ambn|0m2n}（即a的个数不超过b的个数的两倍）写一个LR（1）文法，不准超过6个产生式。（若超过6个产生式，不给分。若所写文法不是LR（1）文法，最多给5分。）3．（10分）构造下面文法的LL（1）分析表。DTLTint|realLidRR,idR|4．（15分）就下面文法S(L)|aLLS|S给出一个语法制导定义，它输出配对括号的个数。给出一个翻译方案，它输出每个a的嵌套深度。如句子(a,(a,a))，第一小题的输出是2，第二小题的输出是122。5．（10分）Pascal语言for语句的含义见教材第222页习题7.13。请为该语句设计一种合理的中间代码结构。你可以按第215页图7.17的方式或者第219页图7.19的方式写出你的设计，不需要写产生中间代码的语法制导定义。6．（5分）一个C语言程序如下：func(i1,i2,i3)longi1,i2,i3;{longj1,j2,j3;printf(Addressesofi1,i2,i3=%o,%o,%o\n,&i1,&i2,&i3);printf(Addressesofj1,j2,j3=%o,%o,%o\n,&j1,&j2,&j3);}main(){longi1,i2,i3;2func(i1,i2,i3);}该程序在某种机器的Linux上的运行结果如下：Addressesofi1,i2,i3=27777775460,27777775464,27777775470Addressesofj1,j2,j3=27777775444,27777775440,27777775434从上面的结果可以看出，func函数的3个形式参数的地址依次升高，而3个局部变量的地址依次降低。试说明为什么会有这个区别。7．（15分）一个C语言程序及其在某种机器linux操作系统上的编译结果如下。根据所生成的汇编程序来解释程序中四个变量的作用域、生存期和置初值方式等方面的区别。staticlongaa=10;shortbb=20;func(){staticlongcc=30;shortdd=40;}.filestatic.c.version01.01gcc2_compiled.:.data.align4.typeaa,@object.sizeaa,4aa:.long10.globlbb.align2.typebb,@object.sizebb,2bb:.value20.align4.typecc.2,@object.sizecc.2,4cc.2:3.long30.text.align4.globlfunc.typefunc,@functionfunc:pushl%ebpmovl%esp,%ebpsubl$4,%espmovw$40,-2(%ebp).L1:leaveret.Lfe1:.sizefunc,.Lfe1-func.identGCC:(GNU)egcs-2.91.6619990314/Linux(egcs-1.1.2release)8．（10分）C语言是一种类型语言，但它不是强类型语言，因为编译时的类型检查不能保证所接受的程序没有运行时的类型错误。例如，编译时的类型检查一般不能保证运行时没有数组越界。请你再举一个这样的例子说明C语言不是强类型语言。9．（10分）如果在A机器上我们有C语言编译器CCA，也有它的源码SA（用C语言写成）。如何利用它通过尽量少的工作来得到B机器的C语言编译器CCB。10．（5分）表达式(x.(yz.(x+y)+z)3)45和(x.(yz.(x+y)+z)35)4有同样的结果。在抽象机FAM上，哪一个表达式对应的目标代码的执行效率高？为什么？2003年编译原理试题41．（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;5}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？68．（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);//缩放}2004年编译原理试题71．（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机器上该程序还是能通过编译并8生成目标代码。请回答下面两个问题：（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;应翻译成什么？中国科学技术大学92004－2005学年第二学期考试试卷考试科目：编译原理和技术得分：1．（15分）(a)字母