2007级计软编译原理补考复习.doc

2007级计软编译原理补考复习参考一、单项选择题1在嵌套过程语言的栈式实现中，如果当前过程为第i层，则当前过程的display表有（ ）个表项。A. 1 B.2 C. i D. i+12在属性文法中，继承属性可以把属性信息沿着语法树（ ）传递。A从下向上 B从左到右 C从右到左 D任何方向3. 若项目集Ik含有A，则在状态K时，仅当面临的输入符号a跟在栈顶符号串后形成一个规范句型前缀时，才采取“A”归约动作的一定是（ ）。A. LALR(1)文法 B.LR(0)文法 C.LR(1)文法 D.SLR(1)文法4正规式M1和M2等价是指（ ）。A. M1和M2 所对应有穷自动机的状态数相等 B. M1和M2 所对应有穷自动机的有向弧条数相等 C. M1和M2 所识别的语言相等 D. M1和M2 所对应有穷自动机的有向弧条数、状态数相等5. 令=a.b,则上所有包含ab子串的全体对应的正规式为（ ）。 A. b(ab)* B. b(ab)+ C.(ba)*b D.(a|b)*ab(a|b)*6有限状态自动机能识别（ ）的符号串。 A.上下文无关文法 B.上下文有关文法 C.正规文法 D.短语文法7由文法的开始符号经0步或多步推导产生的文法符号序列是（ ）。 A.短语 B.句柄 C.句型 D.句子8. 将一个自动机进行化简，通常采用算法（ ） A. 分割法 B.子集法 C.最小化法 D.-closure(I)9过程调用的参数传送方式之一是（ ）。 A. 传参数 B.传结果 C.传值 D.传表达式10.属于基本块内的优化技术是（ ）。 A删除公共子表达式 B.代码外提 C.强度削弱 D.删除归纳变量答：1.D 2B 3. C 4 C 5. D6C 7C 8. A 9 C 10. A二、是非判断题1当文法非终结符的所有候选首字符集两两不相交时，该文法对应的句子分析不含回溯。 ( )2对任何正规式e，都存在一个NFA M，满足L(M)=L(e). ( )3终结符可以有综合属性，开始符号可以有继承属性。 ( )4.一个文法所有句子组成的集合构成该文法定义的语言。 ( )5逆波兰表示法表示表达式时无需使用括号。 ( )6一个有穷自动机有且只有一个终态。 ( )7规范规约是对句型中最右的直接短语进行替换。 ( )8如果文法存在某个句子有两个不同的推导，则称该文法是二义的。 ( )9SLR(1)通过查看非终结符的Follow集来处理LR(0)分析表的冲突项。 ( )10只要消除了左递归就可以构造不带回溯的递归下降分析程序。 ( )答：1 V 2 V 3 X 4. V 5 V6 X 7 X 8 X 9 V 10 X三、填空题1.乔姆斯基把文法分成4类,其中，2型文法又称为 上下文无关 文法，3型文法又称为 正规 文法。2.式子 (AB)(CDE)的逆波兰表示是 ABC DE 。3.在一个移入-归约的分析中采用以下的语法制导翻译模式，在按一个产生式归约时，立即执行括号中的动作。SbSR print “a”; SRf print “b”;RSa print “c”;Rd print “d”;当分析器的输入为bdfd时，打印的字符串是 dbda .4.对于下面程序流程图：11234节点4的必经节点集D(4)= 1,2,4 四、 简答题1.语句 while CD do call pro(C,D); 经翻译后的四元式是什么？设四元式起始地址为100。语句翻译的属性文法相关部分：Wwhile W.codebegin:=nextstat;WdW E do backpatch(E.true,nextstat); Wd.chain:=E.false; Wd.codebegin:=W.codebegin; SWd S1 backpatch(S1.chain, Wd.codebegin); emit(GOTO Wd.codebegin);S.chain:= Wd.chain;Scall i() for 队列arglist.queue的每一项p do:GEN(par,_,_,p);GEN(call,_,_,entry(i) 1,E 把E.place排在arglist1.queue的末端；arglist.queue:=arglist1.queueE 建立一个arglist.queue,它只包含一项E.placeEid1 rop id2 E.true:=nextstat;E.codebegin:=nextstat;E.false:=nextstat+1;emit(ifid1.place rop id2.place goto_);emit(goto_);LS L.chain:=S.chainLsL; backpatch(L.chain,nextstat)答：100 （j,C,D, 102） 101 (jmp, , ,106 ) 102 (par, , , C) 103 (par, , , D) 104 (call, , ,pro) 105 (jmp, , ,100) 1062. 下面程序采用栈式动态存储分配方案。当执行到语句15时（语句15尚未执行），说明在运行栈中的每一帧属于哪个过程的活动记录？1. program demo:2. var a,b,c:integer;3. procedure p():integer;4. var s,t:boolean;5. procedure r():boolean;6. var v:integer;7. begin (*r*)8. v:=p();9. return10. end (*r*)11. begin (*p*)12. s:=ab;13. a:=a+1;14. if s then t:=r();15. return16. end (*p*)17. begin (*demo*)18. a:=1;19. b:=2;20. c:=p();21. end (*demo*).帧4帧3帧2帧1 t3 t2 t1 0 运行栈答：p活动记录r活动记录p活动记录Demo活动记录 t3 t2 t1 0 运行栈 3. 对下面程序画出其程序流图，并指出所有的循环。（1） read x（2） read y（3） r:=x mod y（4） if r=0 goto (8)（5） x:=y（6） y:=r（7） goto(3)（8） write y（9） halt答：(1) read x(2) read y B1(3)r:=x mod y(4)if r=0 goto (8) B2(5)x:=y(6)y:=r(7)goto(3) B3(8)write y(9)halt B4循环：B2,B34. 给定文法GE: EETP|T TTFM|F Fa|b|c P+|- M*|/ 给出符号串abc*+的所有短语、直接短语、句柄。答：符号串abc*+的所有短语:a b c * + bc* abc*+ 直接短语: a b c * + 句柄:a 五、 分析题1 . 有文法:GAAaAd|aAb|证明该文法是SLR(1)，并构造相应分析表。 SLR(1)分析表 ACTIONGOTOabd#A答：证明：拓广文法： (0)SA(1)AaAd(2)AaAb(3)A构造识别活前缀的DFA:I4:AaAd.I1:SA. aI2:Aa.AdAa.AbA.aAdA.aAbA. A dI0: S.AA.aAdA.aAbA.I3:AaA.dAaA.b a A bI5:AaAb。对I0及I2:FOLLOW(A)=b,d,#移入集合=a上述两者不相交故文法为SLR(1) SLR(1)分析表 ACTIONGOTOabd#A0S2r3r3r311acc2S2r3r3r333S5S44r1r1r15r2r2r22考虑文法GS:SSdA|AAAhV|VViW|WWpSq|r请将该文法变换到等价的LL(1)文法GS，并构造G的LL(1)分析表(填写下表)。给出分析过程。 GS的LL(1)分析表dhipqr#SAVW答：文法： SSdA|AAAhV|VViW|WWpSq|r消除左递归：SAS SdAS|AVA AhVA|ViW|W WpSq|r FOLLOW(S)=q，#FOLLOW(S)=FOLLOW(S)FOLLOW(S)FOLLOW(S)=q,#FIRST(S)= ,dFOLLOW(A)=dFOLLOW(S)FOLLOW(S)=d,q,#FOLLOW(A)=FOLLOW(A)= d,q,#SELECT(SAS)=i,p,r SELECT(SdAS)=dSELECT(S )=q,#SELECT(AVA)=i,p,rSELCTCT( AhVA)=hSELECT(A )=d,q,#SELECT(ViW)=iSELECT(VW)=p,rSELECT(WpSq)=pSELECT(Wr)=r G的LL(1)分析表dhipqr#SASASASSdASAVAVAVAAhVAViWWWWpSqr 没有冲突，改写后文法为LL(1). 3构造一个最小DFA，它接受正规式(a|b)*ab