编译原理期末考试试卷以及答案.pdf-淘文阁

资源描述

《编译原理期末考试试卷以及答案.pdf》由会员分享，可在线阅读，更多相关《编译原理期末考试试卷以及答案.pdf（43页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、一.填空题（每空 2 分，共 20分）1.不同的编译程序关于数据空间的存储分配策略可能不同，但大部分编译中采用的方案有两种：静态存储分配方案和动态存储分配方案，而后者又分为（1）和（2）o2.规范规约是最（3）规约。3.编译程序的工作过程一般划分为 5 个阶段：词法分析、（4）、语义分析与中间代码生成，代码优化及（5）o 另外还有（6）和出错处理。4.表达式 x+y*z/（a+b）

2、的后缀式为（7）。5.文法符号的属性有综合属性和（8）o6.假设二位数组按行存放,而且每个元素占用一个存储单元，则数组 a1.15,1.20J某个元素 ai,j的地址计算公式为包。7.局部优化是局限于一个工皿范围内的一种优化。得分二.选择题（1-6为单选题，7-8为多选题，每问 2 分，共 20分）1.一个上下文无关文法 G 包括四个组成部分：一组终结符，一组非终结符，一个（），以及

3、一组（）。A.字符串 B.产生式 C.开始符号 D.文法 2.程序的基本块是指（)oA.一个子程序 B.一个仅有一个入口和一个出口的语句C.一个没有嵌套的程序段 D.一组顺序执行的程序段，仅有一个入口和一个出口 3.高级语言编译程序常用的语法分析方法中，递归下降分析法属于（）分析方法。A.自左向右 B.自顶向下 C.自底向上 D.自右向左 4.在通常的语法分析方法中，（

4、）特别适用于表达式的分析。A.算符优先分析法 B.LR分析法 C.递归下降分析法 D.L L（1）分析法 5.经过编译所得到的目标程序是（）。A.四元式序列 B.间接三元式序列 C.二元式序列 D.机器语言程序或汇编语言程序 6.一个文法所描述的语言是（）；描述一个语言的文法是（）（,A.唯一的 B.不唯一的 C.可能唯一，也可能不唯一 7.如果在文法 G 中存在一个句子，当其满

5、足下列条件（）之一时，则称该文法是二义文法。A.其最左推导和最右推导相同 B.该句子有两个不同的最左推导 C.该句子有两个不同的最右推导 D.该句子有两棵不同的语法树E.该句子对应的语法树唯一 8.下面()语法制导翻译中，采用拉链一回填技术。A.赋值语句 B.布尔表达式的计算 C.条件语句 D.循环语句得分三.解答题(共 60分)1.(共 15分)已知文法 GE:E-*ETE|

6、(E)|iT-*|+(1)将文法 G 改造成 LL(1)文法；(5分)(2)构造文法 G 中每个非终结符的 FIRST集合及 FOLLOW集合；(5分)(3)构造 LL(1)分析表。(5分)2.(共 12 分)给定文法 GS：S-S(S)|(1)给出句子()()()()的规范推导过程；(4分)(2)指出每步推导所得句型的句柄；(4分)(3)画出该句子的语法推导树。(4分)3.(共 8 分)在一个移入-规约分析过程中采用以下的语法制导翻译模式

7、，在按一个产生式规约时，立即执行括号中的动作。A-*aB print“0”；A*c print“1”；BAb print“2”；(1)当分析器的输入为 a a c b b时-，打印的字符串是什么？(3 分)(2)写出分析过程。(5 分)4.(10 分)翻译循环语句 while(ad)then x:=y+z。要求：给出加注释的分析树及四元式序列。参考以下部分翻译模式：(1)S f if E then M Si backpatch(E.truelist,M.quad

8、);S.nextlist:=merge(E.falselist,Si.nextlist)(2)S-*while M i E do M 2 sl backpatch(Si.nextlist,Mi,.quad);backpatch(E.truelist,M2,.quad);S.nextlist:=E.falselistemit(j,-,-,Mi.quad)(3)S f A S.nextlist:=makelist()(4)L-S L.nextlist:=S.nextlistemit(4jrelop.op,4,5id.place,id2.place,O);(5)M-*M.quad:=nextquad

9、(6)E-id i relop id2 E.truelist:=makelist(nextquad);e.falselistmakelist(nextquad+1);emitCj,-,-。)(7)S-L:二 E emit(:=,E.place,-,L-place)(8)E-E1+E2 E.place:=newtemp;emit(+,Ei.place,E2.place,E.place,)5.（共 15分）设有表格构造文法 GS：S-a|A|（T）T-*T,S|S（1）计算文法 GS的 FIRSTVT集和 LASTVT集。（5 分）构造 GS的优先关系表，并判

10、断 GS是否为算符优先文法。（5 分）计算 GS的优先函数。（5 分）得分二.单项选择题（每题 2 分，共 10分）1.设有文法 GI：I-Il|I0|Ia|Ic|a|b|c下列符号串中是该文法句子的有（)0 abO aOcOl aaa bclO可选项有:A.B.C.D.2.程序的基本块是指（）。A.一个子程序 B.一个仅有一个入口和一个出口的语句 C.一个没有嵌套的程序段 D.一组顺序执行的程序段，仅有一个入口和一

11、个出口 3.高级语言编译程序常用的语法分析方法中，递归下降分析法属于（）分析方法。A.自左向右 B.自顶向下 C.自底向上 D.自右向左 4.经过编译所得到的目标程序是（）oA.四元式序列 B.间接三元式序列 C.二元式序列 D.机器语言程序或汇编语言程序5.运行阶段的存储组织与管理的目的是（）0 提高编译程序的运行速度节省编译程序的存储空间提高目标程

13、法。(2)构造文法 G 的优先函数表。4.(8 分)在一个移入-规约分析过程中采用以下的语法制导翻译模式，在按一个产生式规约时，立即执行括号中的动作。S-bAb print T A-(B print“2”A-*a print 3”B-*Aa)print 4(3)当输入序列为 b(aa)a)a)b时，打印的字符串是什么？(4)写出移入-规约分析过程。5.(12 分)翻译循环语句 while(xy)do if(a=b)then x:=2*y+a。要

14、求：给出加注释的分析树、三地址码序列及相应的四元式序列。参考以下部分翻译模式：(1)S-*if E then M S)backpatch(E.truelist,M.quad);S.nextlist:=merge(E.falselist,Si.nextlist)(2)while M i E do M 2 Si backpatch(S 1.nextlist,Mi,.quad);backpatch(E.truelist,M2.quad);S.nextlist:=E.falselistemit Mi.quad)S f A S.nextlis

15、t:=makelist()(4)L f S L.nextlist:=S.nextlist)M f e M.quad:=nextquad)(6)E-*idi relop idi E.truelist:=makelist(nextquad);e.falselist:=makelist(nextquad+l);emitCj,relop.op,idi.place,id2.place,0);(7)S f L:=E emit(:=,E.place,-,L.place)(8)EEI+E2 E.place:=newtemp;emit(+,Ei.place,E2.place,E-place,)6.(8 分)Ge

16、nerate assembly code for the following sequence assuming that x,yand z are in m e m o r y locations(noticing only two registers RI and R2).S=01=0LI:if xy goto L2Z=s+aiI=i+1Goto LIL2:7.(6 分)Give out the all basic blocks of the following program fragment andconstruct the relevant flow graph(DAG).read

17、CA=0B=1L4:A=A+BifBC goto L2B=B+1goto L4L2:write A8.（8 分）Translate the assignment statement bi=b*c-b*d into（1）A syntax tree.（2）Three address instructions.答案：栈式动态存储分配堆式动态存储分配(3)左(4)语法分析目标代码生成(6)表格管理 xyz*ab+/+(8)继承属性(9)a+(i-l)*20+j-l(10)基本块一、选择题(每问 2 分，共 2 0分)l.C B

18、2.D 3.B 4.A 5.D 6.A,C7.BCD,选对一个得 1分且不超过满分，选错一个扣一分，扣完为止。8.B C D,选对一个得 1分且不超过满分，选错一个扣一分，扣完为止。二、解答题 1.(1)文法存在左递归，消除左递归后的文法为：E f(E)E E(2 分)E TEE|(2 分)T-*|+(1 分)(2)(5分)没考虑#扣 0.5分，其它错或少写一个扣 0.5分 FIRST(E)=(,i FIRST(E,)=*,+,FIRST(T)=*,+FOLLOW(

19、E)=),*,+,#FOWLLOW(E,尸),*,+,#FOLLOW(T)=(,i(3)每错一个扣 0.5分，全错或不写不得分，扣完为止，共 5 分 2.(1)规范推导过程如下。写错推导符号扣 0.5分，错写或少写一步推导扣 0.5分，扣完为止，最左推导扣 2分，共 4 分。S n 咨 n S()n S(S)()n S(g)()=S(S)()()=S(S(S)()()n S(S()()()n S(S 0)()()=S(S()()()()n S(3)()()()=()()()()()i*+#E E 一(E)EE

20、-iE，E，E fE T E E E，-eE 一 TEEE,一 E ET*T-+(2)(1)中加下划线的部分是句柄，标识如(D o 每少写一个句柄扣 0.5分,扣完为止，共 4 分。(3)每少写步扣 0.5分，扣完为止，共 4 分。d Iq r q、/I3.(1)打印的字符串是：12020(错一个扣 0.5分，共 3分)(2)归约过程中错一步扣 0.5分，扣完为止。(共 5分)4.(1)每少写一步扣 0.5分，扣完为止，共 5分。(2)少写一个四元式扣 0.5分，全

21、错或不写不得分，回填错误扣 0.5分，共 5分。四元式序列为:100(j,c,J,104)103(；,1 0 6)104(+,y,z,n)1O5(：=,T1,_,X)106(j,_,100)5.(1)少写一个扣 1分，全错或不写不得分，共 5分。FIRSTVT(S)=a,八,(FIRSTVT(T)=,a,A,(LASTVT(S)=a,A,)LASTVT(T)=a,A,),)优先表如下。每错一个扣 0.5分，全错或不写不得分，扣完为止，共 3分文法 GS没有两个非终结符相邻的情况，

22、且其优先表中任一对终结符之间最多满足、三种关系中的一种，因此是 GS算符优先文法。(2 分)可以不考虑终结符或者 a A()#A A(z#z(3)优先函数。可以不考虑终结符每错一个扣 0.5分，全错或不写不得分，扣完为止，共 5 分。a A()#f 6 6 2 6 6 2manager)2 继承属性(inherited attribute)3 局部优化(local optimization)4 四元式(quatriple)5E+*()id四、单项

23、选择题(每题 2分，共 10分)l.B 2.D 3.B 4.D 5.C五、解答题(共 70分)1.(1)L(G)=0mlm|M l 共 2 分，2 写成扣 1 分(2)S=0Sl=00Sll=000111,共 3 分，=写成-扣 1 分(3)共 3分，错处扣 0.5分，扣完为止 2.(1)空白表格也可以填写“错误”字样，共 4 分，错一个扣 0.5分，扣完为止(2)共 6分，其中判断“baabbb是该文法句子”为 2 分，其他错一个扣 0.5a b c$(#)S S-aB c S-bA BA A f aAb A

24、-*bB B-b B f E B f 分，扣完为止符号栈输入串规则$s baabbb$BAb baabbb$SbAB$BA aabbb$A f aAb$BbAa aabbb$BbA abbb$A f aAb$BbbAa abbb$BbbA bbb$Ab$Bbbb bbb$Bbb bb$B-E$Bb b$b$success$3.(1)共 6 分，其中判断“该文法为算符优先文法”为 2 分，其他错一个扣 0.5分，扣完为止+*i+(2)共 4 分，错一个扣 0.5分，扣完为止+*if 2 4 4g1 3 54.(1)3424

25、2421,共 4 分，错一个扣 0.5 分(2)共 4 分，错一个扣 0.5分，扣完为止stack Input string action$b(aa)a)a)b$b(aa)a)a)b$shift$b(aa)a)a)b$abbb$shift$b(aa)a)a)b$bbb$shift$b(aa)a)a)b$bb$shift$b(a a)a)a)b$shift$b(A a)a)a)b$reduce,A a$b(Aa)a)a)b$shift$b(Aa)a)a)b$shift$b(B a)a)b$reduce,B-*Aa)$b(A a)a)b$reduce,A-*(B$b(Aa)a)b

26、$shift$b(Aa)a)b$shift$b(B a)b$reduce,B f Aa)$b(A a)b$reduce,(B$b(Aa)b$shift$b(Aa)b$shift$b(B b$reduce,B-*Aa)$bA b$reduce,A f(B$bAb$shift$S$reduce,S b A b$s$accept5.共 1 2分，其中带注释的分析树、三地址码序列和四元式序列分别为 4 分,错一个序列扣 0.5分，而错某点（某项）少于或等于 5 个扣 0.5分带注释语法树（略）三地址码序列 M

27、 l:if(xy)goto M2四元式序列 100(j,x,y,102)goto M4 101(j-J 0 8)M2:if(a=b)goto M3 102(j=,a,b,104)goto M l 103 0,-,-,100)M3:tl=2*y 104(*,2,y,tl)t2=tl+a 105(+,tl,a,t2)x=t2 106(=,t2,-,x)goto M l 107(j,-,-,100)M4:1086.共 8分，错一个扣 0.5分，扣完为止 LDR1,OSTS,RIST I,RILI:LDR1,XSUB R1,R1,Y(OR SUB R 1,Y)BGTZR1,L2LD

28、 R2,a(Rl)ADD R2,R2,S(OR ADD R2,S)ST Z,R2LDR1,I(从这开始，下面的语句中的 R I也可以全部变成 R2)ADDR1,R1,1(OR INC RI)ST I,RIBRL1L2:7.共 6分，基本块划分和流图各为 3分，错一处扣 1分，扣完为止 8.(1)共 4 分，错一项扣 1分，扣完为止(2)共 4 分，错一项扣 1分，扣完为止 tl=b*ct2=b*dt3=tl-t2t4=i+l(or t4=i)bt4=t3一、判断题：1.一个上下文无关文法的

29、开始符，可以是终结符或非终结符。()2.一个句型的直接短语是唯一的。()3.已经证明文法的二义性是可判定的。()4.每个基本块可用个 DAG 表示 0()5.每个过程的活动记录的体积在编译时可静态确定。()6.2 型文法一定是()7.一个句型一 3 型文法定句子)8.算符优先分析法每次都是对句柄进行归约。()9.采用三元式实现三地址代码时,不利于对中间代码进行

30、优化。()10.编译过程中，语法分析器的任务是分析单词是怎样构成的。()11.一个优先表一定存在相应的优先函数。()12.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。()13.递归下降分析法是一种自下而上分析法。()14.并不()15.每个是每个基本块文法都能改写成 LL 文法只有一个入口和一个出口 O()16.个 LL 文法一定是无二义的。()17.逆波

31、兰法表示的表达试亦称前缀式 O18.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。()19.正规文法产生的语言都可以用上下文无关文法来描述。()20.一个优先表一定存在相应的优先函数。()21.3 型文法一定是 2 型文法。()22.如果一个文法存在某个句子对应两棵不同的语法树，则文法是二义性的。()二、填空题：1.()称为规范推导。2.编译过程可

32、分为()，(),(),()和()五个阶段。3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是()o4.从功能上说，程序语言的语句大体可分为()语句和()语句两大类。5.语法分析器的输入是(),其输出是()。6.扫描器的任务是从()中识别出一个个()。7.符号表中的信息栏中登记了每个名字的有关的性质，如()等等。8.一个过程相应的 DISPLAY 表的内容为)o9.一

33、个句型的最左直接短语称为句型的()10.常用的两种动态存贮分配办法是（）动态分配和）动态分配。11.一个名字的属性包括（）和（）o12.常用的参数传递方式有（），（）和（）o13.根据优化所涉及的程序范围，可将优化分成为（）三个级别。14.语法分析的方法大致可分为两类，一类是（）,（）和）分析法，另一类是（）分析法。15.预测分析程序是使用一张（的。16.常用的参数传递方式

34、有（）和一个（）进行联合控制),()和()o17.一张转换图只包含有限个状态,其中有一个被认为是（）态;而且实际上至少要有一个（）态。18.根据优化所涉及的程序范围，可将优化分成为（），（）和（）三个级别。19.语法分析是依据语言的（）规则进行。中间代码产生是依据语言的（）规则进行的。20.一个句型的最左直接短语称为句型的（）。21.一个文法 G,若它的预测分析表 M 不含

35、多重定义，则该文法是（）文法。22.对于数据空间的存贮分配，FORTRAN采用（）策略，PASCAL采用（）策略。23.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（）。24.最右推导亦称为（），由此得到的句型称为（）句型。25.语法分析的方法大致可分为两类，一类是（）分析法，另一类是（）分析法。26.对于文法 G,仅含终结符号的句型称为（)27.所谓自上（28.语法分析

36、器的输入是（29.局限于基本块范围的优化称 30.预测分析程序是使用一张（的。31.2型文法又称为（32.每条指令的执行代价定义为 33.算符优先分析法每次都是对而下分析以）o）,其输出是（）。（）。）和一个（）文法；3 型文法又称为（）进行归约。;是指进行联合控制）文法。）。三、名词解释题:1.局部优化 2.二义性文法 3.DISPLAY 表 4.词法分析器 5.最左推导 6.语法 7.文法 8

37、.基本块 9.语法制导翻译 10.短语 11.待用信息 12.规范句型 13.扫描器 14.超前搜索 15.句柄16.语法制导翻译 17.规范句型 18.素短语 19.语法 2 C L待用信息 21.语义四、简答题：1.写一个文法 G,使其语言为不以。开头的偶数集。2.已知文法 G(S)及相应翻译方案 S-aA b print“1”S-a print“2”A-A S print“3”A-c print“4”输入 acab,输出是什么？3.已知文法 G(S)

38、S-bA aA f(B|aB f Aa)写出句子 b(aa)b的规范归约过程。4.考虑下面的程序：procedure p(x,y,z)；beginy:=x+y;z:=z*z;endbeginA-2;B:=A*2;P(A,A,B);Print A,Bend.试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出 A,B的值是什么？5.文法 G(S)S-dA BA f aA|aB fB b|描述的语言是什么？6.证明文法 G(S)S-*SaS|是二义性的。7.已知文法

40、的程序范围可分为哪几级优化？11.目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？12.一字母表 2=a,b,试写出 2 上所有以 a 为首的字组成的正规集相对应的正规式。13.基本的优化方法有哪几种？14.写一个文法 G,使其语言为 L(G)=abncn|n 0 15.考虑下面的程序：procedure p(x,y,z);beginy:=y+z;z:=y*z+xend;begina:=2;b:=3;p(a+b,b

41、,a);print aend.试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出 a 的值是什么？16.写出表达式 a+b*(c-d)/e的逆波兰式和三元序列。17.证明文法 G(A)A-*AA|(A)|E是二义性的。18.令 2=a,b,则正规式 a*b|b*a表示的正规集是什么？19.何谓 DISPLAY表？其作用是什么？20.考虑下面的程序：procedure p(x,y,z)；beginy:=y+2;z:=z+x;endbegina:

42、=5;b:=2;p(a+b,a-b,a);print aend.试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出 a 的值是什么？21.写一个文法 G,使其语言为 L(G尸值叼的 n0为奇数，m0为偶数 22.写出表达式 a:=(b+c)*e+(b+c)/f的逆波兰式和三元序列。23.一个文法 G 别是 LL(1)文法的充要条件是什么？24.已知文法 GSS f S*aF|aF|*aFFf+aF|+a消除文法左递归和提公

43、共左因子。25.符号表的作用是什么？符号表查找和整理技术有哪几种？五、计算题：1.设文法 G(S):S一人 I a|T-*T,S|S 消除左递归；(2)构造相应的 FIRST和 F O L L O W 集合；构造预测分析表 2.语句 if E then S(1)改写文法，使之适合语法制导翻译；(2)写出改写后产生式的语义动作。3.设文法 G(S)：S-(T)|aT f T+S|S(1)计算 FIRSTVT 和 LASTVT；(2)构造优先关

44、系表。4.设某语言的 for语句的形式为for i:=E()to E do S其语义解释为 i:=E(1)LIMIT:=E(2)again:if i=LIMIT thenBeginS;i:=i+1goto againEnd;(1)写出适合语法制导翻译的产生式;(2)写出每个产生式对应的语义动作。5.把语句 while a0 then a:=a+lelse a:=a*3-l;翻译成四元式序列。6.设有基本块 D:=A-CE:=A*CF:=D*ES:=2T:=A-CQ:=A*CG:=2*SJ

45、:=T*QK:=G*5L:=K+JM:=L假设基本块出口时只有 M 还被引用，请写出优化后的四元序列。7.已知文法 G(S)S f a|八|T f T,S|S(1)给出句子(a,(a,a)的最左推导；给出句型(T,S),a)的短语，直接短语，句柄。8.对于 C 语言 do S while E 语句(1)改写文法，使之适合语法制导翻译；(2)写出改写后产生式的语义动作。9.已知文法 G(S)S-*aAcBeA-Ab|bBd(1)给出句子 abbcde

47、句型(E+T)*i+F的短语，素短语和最左素短语。13.设文法 G(S)：S-*T|SV TT f U|TAUU f i|-U(1)计算 FIRSTVT 和 LASTVT；(2)构造优先关系表。参考答案一、是非题：l.X 2.x 3.X 4.V 5.V 6.x 7.X 8.X 9.V 10.X 11.X12.V 13.X 14.V 15.V 16.V 17.X 18.V 19.V 20.X 21.J 22.V二、填空题：1.（最右推导）2.（词法分析），（语法分析），（中间代码生成），（代码优化），（目

48、标代码生成）3.（二义性的）4.（执行性），（说明性）5.（单词符号），（语法单位）。6.（源程序），（单词符号）7.（类型、种属、所占单元大小、地址）8.（现行活动记录地址和所有外层最新活动记录的地址）9.（句柄）10.（栈式），（堆式）11.（类型），（作用域）12.（传地址），（传值），（传名）13.（局部优化），（循环优化），（全局优化）14.（自上而下），（自下而上）15.（分析表），（符号栈）16.（传地址），（传值

49、），（传名）17.（初），（终）18.（局部优化），（循环优化），（全局优化）19.（语法），（语义）20.（句柄）第。页共 4 3 页21.（LL（1）文法）22.（静态），（动态）23.（二义性文法）24.（规范推导），（规范）25.（自上而下），（自下而上）26.（句子）27.（从开始符号出发，向下推导，推出句子）28.（单词符号），（语法单位）29.（局部优化）30.（分析表），（符号栈）31.（上下文无关文法），（正规）32.（指令访问主存次数

50、加 1）33.（最左素短语）三、名词解释题：1.局部优化局限于基本块范围的优化称。2.二义性文法一如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义性文法。3.DISPLAY表一过程的嵌套层次显示表，记录该过程的各外层过程的最新活动记录的起始地址。4.词法分析器-执行词法分析的程序。5.最左推导任何一步 a=B都是对 a 中的最右非终结符

展开阅读全文