2023编译原理试卷.docx

《2023编译原理试卷.docx》由会员分享，可在线阅读，更多相关《2023编译原理试卷.docx（35页珍藏版）》请在课桌文档上搜索。

1、2023年编译原理试题1 .(10分)处于/*和*/之间的串构成注解，注解中间没有*/。画出接受这种注解的DFA的状态转换图。.(10分)为语言1.=ambn0 a LL,S LSprint(S.num)S.num := L.num +1S.num := 0L.num := L.num + S.numL.num := S.numS, S.depth := 0 SS L.depth := S.depth +1 (L)S a print(S.depth)L L.depth := L.depth Li, S.depth := L.depth SL S.depth := L.depth S5. t :

2、= initialt2 := finalif t t2 goto Ll v := tL2: stmtif v = t2 goto Ll v := v + 1goto L2LI:6 .由于实参表达式是反序进入活动记录，而局部变量是依次在活动记录中安排。7 .aa是静态外部变量，而bb是外部变量，它们都安排在静态数据区（由.data伪指令起先），但是bb由伪指令.globl指明为全局的，用来解决其它文件中对bb的外部引用，而aa只能由本文件引用。CC是静态局部变量，同aa和bb一样，它的生存期是整个程序并安排在静态数据区。由于CC在源程序中的作用域是函数fmc的体，而在目标文件中，它的作用域至少已

3、是整个文件了，为避开同源文件中外部变量和其它函数的静态局部变量的名字冲突，所以要对它进行改名，成了cc.2o由于CC不是全局的，因此cc.2前面没有伪指令.gkbldd是自动变量,其作用域是函数func的体，其生存期是该函数激活期间，因此它安排在栈区，并且置初值是用运行时的赋值来实现。8 .例如联合体的类型检查一般也不行能在编译时完成，虽然下面例子是可静态推断类型错误的。unionUintu1;int*u2;u;int*p;u.u1=10;p=u.u2;*p=0;9.修改源码SA的代码生成部分，让它产生B机器的代码，称结果程序为SBQ将以提交给Ca进行编译，得到一个可执行程序。将S提交给上述可

4、执行程序进行编译，得到所需的编译器CC5。10.第一个表达式在执行外2.。+历+2）3时出现参数个数不足的状况，因此有FUNVAL的值进入栈顶，然后发觉参数个数不足，又把它做成FANVAL的状况。而其次个表达式执行的是QyzG+y）+z）35,不会出现参数个数不足的状况。因此其次个表达式的执行效率比第一个表达式的高。2023年编译原理试题1 .（20分）写出字母表=a,b上语言L=卬IW中a的个数是偶数的正规式,并画出接受该语言的最简DFAo2 .（15分）考虑下面的表达式文法，它包括数组访问、加和赋值：EEEIEEIE=EI（E）Iid该文法是二义的。请写一个接受同样语言的LR（I）文法，其

5、优先级从高到低依次是数组访问、加和赋值，并且加运算是左结合，赋值是右结合。3 .（10分）下面是产生字母表=0,1,2上数字串的一个文法：SDSD2D01写一个语法制导定义，它打印一个句子是否为回文数（一个数字串，从左向右读和从右向左读都一样时，称它为回文数）。4 .（10分）教材上7.2.1节的翻译方案PToffset:=0)DDD;DDid:Tenter(id.name,T.type,ojfset)offset:二offset+T.widthTintegerT.type:=integer;T.width:=47realT.type:=real;T.width:=8运用了变量offset.请

6、重写该翻译方案，它完成同样的事情，但只运用文法符号的属性，而不运用变量。5. (5分)一个C语言程序如下：voidfun(structinix;doubler;val)main()(structintx;doubler;val;fun(val);)该程序在X86Linux机器上的用cc吩咐编译时，报告的错误信息如下：1: warning:structuredefinedinsideparms2: warning:anonymousstructdeclaredinsideparameterlist3: warning:itsscopeisonlythisdefinitionordeclarati

7、on,4: warning:whichisprobablynotwhatyouwant.7: incompatibletypeforargument1offun,请问，报告最终一行的错误的缘由是什么？如何修改程序，使得编译时不再出现这个错误信息。6. (10分)一个C语言程序如下：typedefstruct_ashorti;shortj;shortk;a；typedefstruct_blongi;shortk;b；main()printf(,Sizeofshort,long,aandb=%d,%d,%d,%dn,sizeof(short),sizeof(long),sizeof(a),size

8、of(b);)该程序在X86Linux机器上的运行结果如下：Sizeofshort,long,aandb=2,4,6,8已知Short类型和IOng类型分别对齐到2的倍数和4的倍数。试问，为什么类型b的size会等于8?7. (15分)一个C语言程序如下：intfact(i)inti;(if(i=0)return1;elsereturni*fact(i-l);main()(printf(%dn,fact(5);printf(,%dn,fact(5,10,15);printf(,%dnfact(5.0);printf(%dn,fact();)该程序在X86Linux机器上的运行结果如下：1201

9、201Segmentationfault(coredumped)请说明下面问题： 其次个fact调用：结果为什么没有受参数过多的影响？ 第三个fact调用：为什么用浮点数5.0作为参数时结果变成1? 第四个fact调用：为什么没有供应参数时会出现Segmentationfault?8. (5分)C语言的赋值操作并非仅对简洁类型而言，例如若有类型声明longa100,b100;,则赋值a=b是允许的。同样，若a和b是同一类型的两个结构，则赋值a=b也是允许的。用教材上第七章所给出的三地址语句，我们能否为这种赋值产生中间代码？若你持确定看法，请你给出对应这种赋值的中间代码序列；否则请你为这种赋值设

10、计一种三地址语句。你所选用或设计的三地址语句要便于目标代码的生成。9. (5分)一个C程序的三个文件的内容如下:head.h:shortinta=10;filel.c:#includehead.hmain()file2.c:includehead.h在X86Linux机器上的编译吩咐如下：ccflel.cfile2.c编译结果报错的主要信息如下：multipledefinitionofta,试分析为什么会报这样的错误。10. (5分)依据教材上介绍的方法，把下面C+语言的函数翻译成C的函数。voidzoom(GraphicalObj&obj,doublezoom_faclor,Point Di

11、 Si D2S2D0D 1print(S.val)S.val=(D.val=D2.val)andS.valS.val=trueD.val=0D.val=14 .文法符号D的属性offset是继承属性,代表在分析D前原来运用的变量offset的大小；属性offset!是综合属性,代表在分析D后原来运用的变量offset的大小。P的属性offset是综合属性，记录该过程所安排的空间。PD.ojfset:=0DP,offset:=D.offset!DfD.ojfset:=D.offset1D;D2.0jfset:=D.offset!D2D.offset!:=Di.offset!)id:Tenter(

12、id.name,T.type,Doffseil);D.offset2:=D.offseti+T.widthTintegerT.type:=integer,T.width:=4J7realT.type:=real,T.width:=85 .C语言对全部的类型都采纳结构等价，唯有结构类型例外，采纳名字等价。这里的类型不相容是因为两个val不是名字等价的。要消退这个错误，包括全部的警告，程序修改如下：structsintx;doubler;）；voidfun(structsval)main()structsval;fun(val);6 .一个数组的SiZe等于数组元素的SiZe乘以数组元素的个数，这

13、是一个原则。对于结构类型b来说，它的一个变量只需6个字节就够了。假如声明结构类型b的一个数组，有两种可能：(a)结构类型b的SiZe是6,数组元素之间空两个字节，以保证每个数组元素的地址都是4的倍数(因为第一个域i的类型是Iong,要求对齐到4的倍数)。(b)结构类型b的SiZe是8,以保证它作为数组元素的类型时，数组元素之间不用再考虑对齐问题。方法(a)违反了我们一起先提到的原则，因此只能取方法(b)o7 .(1)参数表达式逆序计算并进栈，fact能够取到第一个参数。(2)参数5.0转换成双精度数进栈，占8个字节。它低地址的4个字节看成整数时正好是0。(3)由于没有供应参数，fact把老eb

14、p(限制链)(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-faclor,Point¢er)obj

15、.vptr01(obj,-center.x,-center.y);/将中心点移至原点(0,0)obj.vptrl(obj,zoom_factor);/缩放I2023年编译原理试题1. (20分)写出字母表=a,b上语言L=w卬的最终两个字母是44或协的正规式，并画出接受该语言的最简DFA。2. (15分)说明下面的文法不是SLR(I)文法，并重写一个等价的SLR(I)文法。SMabMcdcbdaMd3. (10分)为下面的语言写一个无二义的文法：ML语言中用分号分隔语句的语句块，例如：(s;s);(s;s;s);s);(s;s)4. (20分)考虑一个类PaSCal的语言，其中全部的变量都是整

16、型(不须要显式声明)，并且仅包含赋值语句、读语句、写语句，条件语句和循环语句。下面的产生式定义了该语言的语法(其中Iit表示整型常量；OP的产生式没有给出，因为它和下面探讨的问题无关)。定义Stmt的两个属性：Ma)Qef表示它可能定值的变量集合，MayUse表示它可能引用的变量集合。(1)写一个语法制导定义或翻译方案，它计算Stmt的MayDefMayUse属性。(2)基于MoyEW和MayUse属性，说明Stmt;Stmt2和Stmt2;Stmtl在什么状况下有同样的语义。ProgramStmtStmtid:=ExpStmtread(id)Stmtwrite(Exp)StmtStmt;St

17、mtStmtif(Exp)thenbeginStmtendelsebeginStmtendStmtwhile(Exp)dobeginStmtendExpidExplitExpExpOPExp5. (10分)下面是一个C语言程序：main()(longi；longa04;IOngj;1 =4;j=8;Printfr%d,%dn,SiZeof(a),a00);)虽然出现IOnga04这样的声明，在X86Linux机器上该程序还是能通过编译并生成目标代码。请回答下面两个问题：(I)SiZeof(a)的值是多少，请说明理由。2 2)a0110的值是多少，请说明理由。6. (15分)考虑下面的三地址语句

18、序列：b:=1b:=2ifw=XgotoL2e:=bgotoL21.I:gotoL31.2:c:=3b:=4c:=61.3:ify=zgotoL4gotoL51.4:g:=g+1h:=8gotoLl1.5:h:=9(1)在该代码中用水平的横线将代码分成基本块，并给每个基本块一个序号。(2)画出该代码的限制流图，每个基本块就用(1)的序号表示。(3)若有循环的话，列出构成每个循环的结点。7. (5分)假如(1)用编译吩咐CCteSLC会报告有未定义的符号；(2)用编译吩咐cctest.c-lusr.a会得到可执行程序(-lusr.a表示连接库libusr.a)0那么，用编译吩咐cctest.c-

19、lusr.a-Iusna是否会报告有多重定义的符号？请说明理由。8. (5分)C+中的对象声明语句应如何翻译成C语句？如书上图11.11程序中的Point_center;应翻译成什么？2023年编译原理试题参考答案1.语言L的正规式是：(abY(aabb)接受该语言的最简DFA是:2.S,SSMabMcdcbdaMd因为a是M的后继符号之一，因此在上面最右边一个项目集中有移进-归约冲突。等价的SLR(I)文法是Sdabdcdcbda3. SLSSL;SSsI(SL)4. (1)ProgramStmtStmtid:=ExpStmLMayDef:=id.name;Stmt.MayUse:=ExpM

20、ayUseStmtread(id)Slml.MayUse:=;Stmt.MayDef:=id.nameStmtwrite(Exp) StvatMayDef=;Stmt.MayUse:=Ep.MayUseStmtStmti;Stmt2 Stml.MayUse:=Stmt.MayUseuStmt2.MayUse;Stmt.AZtzyDef:=StmtMayDefjStmt2.MayDefStmtif(Exp)thenbeginStmtiendelsebeginStmt2end Stml.MayUse:=Stmt.MayUseuStmt2.MayUseuExp.MayUse;SlmLMayDef:=

21、Stmt.MayDefuStmti.MayDef)Stmtwhile(Exp)dobeginStmtiend Stml.MayUse:=Stmt.MayUseuExp.MayUse;Stmt.MayDef:=StmtMayDefExpidExp.MayUse:=id.nameExplitExpMayUse:=)ExpExpiOPExpa Exp.MayUse:=Exp.MayUseuExp2.MayUse 2)StmtiMayDefnStmt2.MayUse=andStmt2.MayDefnStmt.MayUse=andStmthAYayDefnStmt2.MayDef=5. (1)依据数组S

22、iZe的计算公式，sizeof(a)的值确定是0。(2) a00的值是4o虽然a的size是0,但它仍旧有起始地址，并且a00的地址等于a的起始地址。由于X86Linux机器上，活动记录栈向低地址方向增长，另外由于低地址放低位字节，因此a0的地址和i的地址一样，其值和i的值一样，等于4。6. (1)(2)b := 1b := 2if w = X soto L2(1)e := bROto L2(2)U: ROtO L3(3)L2:c := 3b := 4c := 6(4)L3:if v = z goto L4(5)goto L5(6)L4:g ：=g+ 1 h:=8 goto L1(7)L5:h

23、 := 9(8)(3)结点5、7和3构成一个循环，其中5是入口结点。7. 不会。连接时，第一次遇到库IibUSr.a便能解决全部的外部引用。这样在其次次遇到库libusr.a时什么东西也不会加入目标程序。8. C+语言中类的对象声明不加翻译就成了C语言中相应结构类型的变量声明，不管对象声明出现在程序中的什么地方。中国科学技术大学2023-2023学年其次学期考试试卷1. (15分)(a)字母表=(,)上的语言(),()(),(),()()()()()是不是正规语言?为什么？(b)正规式(OH)*和(10)1*)*是否等价，说明理由。2. (15分)接受文法SAabAcdcbdaAd活前缀的DF

24、A见下图。请依据这个DFA来构造该文法的SLR(I)分析表，并说明该文法为什么不是SLR(I)文法。3. (10分)现有字母表=a,写一个和正规式a*等价的上下文无关文法，要求所写的文法既不是LR文法，也不是二义文法。4. (20分)(a)下面的文法定义语言L=(anbknm,n1。写一个语法制导定义，其语义规则的作用是：对不属于语言L的子集L产(anbncnnl的句子，打印出错信息。SDCDaDbabCCcc(b)语句的文法如下：Sid:=EIifEthenSwhileEdoSbeginS;Sendbreak写一个翻译方案，其语义动作的作用是：若发觉break不是出现在循环语句中，刚好报告错

25、误。5. (5分)C程序设计的教材上说，可以用两种形式表示字符串：其一是用字符数组存放一个字符串，另一种是用字符指针指向一个字符串。教材上同时介绍了这两种形式的许多共同点和不同点，但是有一种可能的区分没有介绍。下面是一个包含这两种形式的C程序：CharCW=good!”；char*c2=good!”;main()(cl0=tG*;printf(tc1=%sn,c1);c20=G,;Prinlf(c2=%sn”,c2);)该程序在X86Linux机器上运行时的信息如下：cl=Good!Segmentationfault(coredumped)请问，出现Segmentalionfault的缘由是什

26、么？6. (15分)下面是一个C语言程序：longfl(i)longi;(relum(i*10);longf2(longi)retum(i*10);main()(PrimfCfl=%d,f2=%dn”,fl(IO.O),f2(10.0);)其中函数fl和f2仅形式参数的描述方式不一样。该程序在X86Linux机器上的运行结果如下：f1=0,f2=100请说明为什么用同样的实在参数调用这两个函数的结果不一样。7. (10分)下面是一个C语言程序和在X86Linux机器上编译(未运用优化)该程序得到的汇编代码(为便于理解，略去了和探讨本问题无关的部分，并改动了一个地方)。(a)为什么会出现一条指令

27、前有多个标号的状况，如.L2和.L4,还有.L5、.L3和.Ll?从限制流语句的中间代码结构加以说明。(b)每个函数都有这样的标号.Ll,它的作用是什么，为什么本函数没有引用该标号的地方？main()(longij;if(j)i+；elsewhile(i)j+;1一一将老的基地址指针压栈一将当前栈顶指针作为基地址指针 一一为局部变量安排空间main:pushl%ebpmovl%esp,%ebpsubl$8,%espcmpl$0,-8(%ebp)jeL2incl-4(%ebp)jmp.L3.L2:.L4:cmpl$0,-4(%ebp)jne.L6jmp.L5.L6:incl-8(%ebp)jmp

28、.L4.L5:.L3:.L1:leave一一和下一条指令一起完成复原老的基地址指针，将栈顶ret一一指针复原到调用前参数压栈后的位置，并返回调用者8. (5分)cc是UNIX系统上C语言编译吩咐，-1是连接库函数的选择项。两个程序员分别编写了函数库IibuserLa和IibUSer2.a。当用吩咐cctest.c-IuserLa-Iuser2.a编译时，报告有重复定义的符号。(备注：库名中的Iib在吩咐中省略。该吩咐和吩咐CCIeSI.cIibuserLalibuser2.a的效果是一样的)。而改用吩咐cctest.c-Iuser2.a-IuserLa时，能得到可执行程序。试分析缘由。9. (

29、5分)依据教材上所介绍的方法，C+中的对象声明语句应如何翻译成C语句？如教材图11.11(旧教材的图10.11)程序中的Point_center;应怎样翻译？2023年编译原理和技术试题参考答案1.(a)语言(),()(),(),()()()()0是正规语言，因为该语言只包括有限个句子，它可以用正规式定义如下：OI()0)I()IOOO0()(b)我们分析正规式(|0)*表示的语言。可以看出正规式(|0)1*描述的语言是集合,1,11,111,.,0,01,011,0111,.),它含长度为1的两个串0和1。那么，(0|1)*所描述的语言是(|0)1*)*所描述的语言的子集，因为(Ol1)*表

30、示字母表0,I上全部串的集合，因此(10)1*)*所描述的语言不行能再有更多的句子，因而也是表示字母表0,1上全部串的集合。2.分析表如下。因为有两处有移进一归约冲突，所以该文法不是SLR(I)文法。注：Fallow（八）=(a,c)状态动作转移abed$SA0s3s4121acc2s53s764r558,r55r7510,r58r39r210r43 .满意条件的一个文法如下：SaSaIaI4 .(a)语法制导的定义如下：SDCifD.lengthC.lengththenprint(4lerrof,)DabD.length:=1DaDibD.length:=D.length+1CcC.leng

31、th:=1CCicC.length:=C.length+1(b)翻译方案如下：SS.loop:=false)SSid:=ESifEthenSi.loop:=S.loop)SSwhileEdoS!.loop:=true)SiSbeginS.loop:=S.loop)S;S2.l00p:=S.l00p)S2endSbreakifnotS.loopthenPrint(error)5 .cl是字符数组，cl=good!”看成是对这个数组的元素逐个地赋值。c2是字符指针，它所指向的“good!”看成是一个字符串常量，常量的值不允许修改，因此编译器把这个字符串常量安排在只读数据区。当执行赋值c20=，G，

32、时，试图对只读数据区赋值，因此报告错误。6 .历史上，C语言中有参函数定义的一般形式是：类型标识符函数名(形式参数列表)形式参数声明对于这种形式的声明，C语言编译器是不做实在参数和形式参数的个数和类型是否一样的检查的。如本题中函数fl的声明是这种形式。现在，ANSl新标准允许运用另一种方法声明形式参数，即在函数名后的括号中列出形式参数的同时，声明形式参数的类型。本题中函数&的声明是这种形式。C语言编译器对于这种形式的函数声明是要进行实在参数和形式参数的个数和类型是否一样的检查的。因此，在编译函数调用f2(10.0)时，会把浮点数10.0转换成整数10,并产生将整数10压栈的指令。因此函数调用f

33、2(10.0)的结果是100。而在编译函数调用fl(100)时，会把浮点数10.0转换成双精度型(参见编译原理习题精选第5.8题)，并产生将该双精度型数压栈的指令。双精度型数占8个字节。它低地址的4个字节看成整数时正好是0。因此函数调用fl(10.0)的结果是0(参见：staff.ustc.eduyiyun上2023年编译原理试题第7题)。7.(a)条件语句和循环语句的中间代码结构如下:if(E)thenSielseS?while(E)doSE的代码L4:E的代码假转L2真转L6S1的代码转L5转L3L6:S的代码L2:S2的代码转L4L3:L5:用这种代码结构，当WhiIe语句作为条件语句的

34、S2时，就会出现题目所给的这种状况。(b).Ll标号定义的入口是返回调用者时该执行的指令，在函数内部有return语句时就会跳转到.LL8.这是基于下面几点缘由。1 .两个函数库IibUSerl.a和IibUSer2.a都定义了某个函数或某个置初值的外部变量，把它简称为a。2 .est.c引用a。3 .lest.c还引用IibUSer2.a的其它某个函数或外部变量，把它简称为b。在IibUSer2.a中，a和b在同一个目标文件中。4 .在IibUSerLa中，含a的那个目标文件不含b。进一步的说明如下。由于test.c引用a和b,用其次种次序连接时，a和b的定义在Ii序ser2a都能找到,所以

35、不会再把IibuserLa中含a定义的目标文件连接进来。而用第一种次序连接时，先把Iibuserl.a中含a定义的目标文件连接进来，然后还须要把IibUSer2.a中含b定义的目标文件连接进来，引起把a的定义也要带进来，因为在IibUSer2.a中a和b的定义在同一个目标文件中。由此造成要连接a的两个定义。9.C+语言中类的对象声明不加翻译就成了C语言中相应结构类型的变量声明，不管对象声明出现在程序中的什么地方。备注：由于C+语言中一个类的全部非静态属性构成一个C语言的结构类型，并且类的名字就作为结构类型的名字，因此上面的语句不做任何修改，_cenler自然就成了Poim结构类型的变量。所要留

36、意的是，还应当依据Point类中构造函数的参数置初值的状况，来给.center适当地静态置初值。中国科学技术大学2023-2023学年其次学期考试试卷1、(15分)(a)用正规式表示字母表a,b上，a不会相邻的全部串。(b)画出一个最简的确定有限自动机，它接受全部大于IOl的二进制整数。2、(10分)构造下面文法的LL(I)分析表。SaBSbASAbAAIaBaBBb3、(10分)下面的文法是二义文法SEEwhileEdoEid:=EE+Eid(E)请你为该语言重写一个规范的LR(I)文法，它为该语言中的各种运算体现通常的优先级和结合规则。不须要证明你的文法是规范LR(I)的。4、(10分)为

37、下面文法写一个语法制导的定义，它完成一个句子的WhiICdo最大嵌套层次的计算并输出这个计算结果。SEEwhileEdoEid:=EE+Eid(E)5、(15分)考虑一个类似PaSCal的语言，其中全部的变量都是整型(不须要显式声明)，并且仅包含赋值语句、读语句、写语句、条件语句和循环语句。下面的产生式定义了该语言的语法(其中Iit表示整型常量；OP的产生式没有给出，因为它和下面探讨的问题无关)。定义Stmt的两个属性：Oe/表示在Stmt中确定会定值且在该定值前没有引用的变量集合，M-Use表示在SIml中有引用且在该引用前可能没有定值的变量集合。(a)写一个语法制导定义或翻译方案，它计算Slmt的Dd和MayUse属性。(b)基于上面的计算，程序可能未赋初值的变量集合从哪儿可以得到？可能未赋初值的变量是这样定义的：若存在从程序起先点到达变量a某引用点的一条路径，在这条路径上没有对变量a赋值，则变量a属于程序可能未赋初值的变量集合。ProgramStmtStmtid:=ExpStmtread(id)Stmtwrite(Exp)StmtStmt;StmtStmtif(Exp)thenbeginStmtendelsebeginStmtendStmtwhi