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

12007级计软编译原理补考复习参考一、单项选择题1．在嵌套过程语言的栈式实现中，如果当前过程为第i层，则当前过程的display表有（）个表项。A.1B.2C.iD.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)*bD.(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.D2．B3.C4．C5.D6．C7．C8.A9．C10.A二、是非判断题21．当文法非终结符的所有候选首字符集两两不相交时，该文法对应的句子分析不含回溯。()2．对任何正规式e，都存在一个NFAM，满足L(M)=L(e).()3．终结符可以有综合属性，开始符号可以有继承属性。()4.一个文法所有句子组成的集合构成该文法定义的语言。()5．逆波兰表示法表示表达式时无需使用括号。()6．一个有穷自动机有且只有一个终态。()7．规范规约是对句型中最右的直接短语进行替换。()8．如果文法存在某个句子有两个不同的推导，则称该文法是二义的。()9．SLR(1)通过查看非终结符的Follow集来处理LR(0)分析表的冲突项。()10．只要消除了左递归就可以构造不带回溯的递归下降分析程序。()答：1．V2．V3．X4.V5．V6．X7．X8．X9．V10．X三、填空题1.乔姆斯基把文法分成4类,其中，2型文法又称为上下文无关文法，3型文法又称为正规文法。2.式子(A∧B)∨(C∧┒D∧E)的逆波兰表示是AB∧CD┒∧E∧∨。3.在一个移入-归约的分析中采用以下的语法制导翻译模式，在按一个产生式归约时，立即执行括号中的动作。S→bSR{print“a”;}S→Rf{print“b”;}R→Sa{print“c”;}R→d{print“d”;}当分析器的输入为bdfd时，打印的字符串是dbda.4.对于下面程序流程图：3节点4的必经节点集D(4)={1,2,4}四、简答题1.语句whileCDdocallpro(C,D);经翻译后的四元式是什么？设四元式起始地址为100。语句翻译的属性文法相关部分：W→while{W.codebegin:=nextstat;}Wd→WEdo{backpatch(E.true,nextstat);Wd.chain:=E.false;Wd.codebegin:=W.codebegin;}S→WdS1{backpatch(S1.chain,Wd.codebegin);emit(‘GOTO’Wd.codebegin);S.chain:=Wd.chain;}S→calli(arglist){for队列arglist.queue的每一项pdo:GEN(par,_,_,p);GEN(call,_,_,entry(i))}arglist→arglist1,E{把E.place排在arglist1.queue的末端；arglist.queue:=arglist1.queue}arglist→E{建立一个arglist.queue,它只包含一项E.place}E→id1ropid2{E.true:=nextstat;E.codebegin:=nextstat;E.false:=nextstat+1;emit(‘if’id1.place‘rop’id2.place‘goto’__);emit(‘goto’___);}L→S{L.chain:=S.chain}Ls→L;{backpatch(L.chain,nextstat)}答：100（j,C,D,102）101(jmp,,,106)102(par,,,C)103(par,,,D)104(call,,,pro)105(jmp,,,100)1124341062.下面程序采用栈式动态存储分配方案。当执行到语句15时（语句15尚未执行），说明在运行栈中的每一帧属于哪个过程的活动记录？1.programdemo:2.vara,b,c:integer;3.procedurep():integer;4.vars,t:boolean;5.procedurer():boolean;6.varv:integer;7.begin(*r*)8.v:=p();9.return10.end(*r*)11.begin(*p*)12.s:=ab;13.a:=a+1;14.ifsthent:=r();15.return16.end(*p*)17.begin(*demo*)18.a:=1;19.b:=2;20.c:=p();21.end(*demo*).t3t2t10运行栈帧4帧3帧2帧15答：t3t2t10运行栈3.对下面程序画出其程序流图，并指出所有的循环。（1）readx（2）ready（3）r:=xmody（4）ifr=0goto(8)（5）x:=y（6）y:=r（7）goto(3)（8）writey（9）halt答：B1B2B3B4p活动记录r活动记录p活动记录Demo活动记录(1)readx(2)ready(3)r:=xmody(4)ifr=0goto(8)(5)x:=y(6)y:=r(7)goto(3)(8)writey(9)halt6循环：｛B2,B3｝4.给定文法G[E]:E→ETP|TT→TFM|FF→a|b|cP→+|-M→*|/给出符号串abc*+的所有短语、直接短语、句柄。答：符号串abc*+的所有短语:abc*+bc*abc*+直接短语:abc*+句柄:a五、分析题1.有文法:G[A]A→aAd|aAb|ε证明该文法是SLR(1)，并构造相应分析表。SLR(1)分析表ACTIONGOTOabd#A答：证明：拓广文法：(0)S’→A(1)A→aAd(2)A→aAb(3)A→ε构造识别活前缀的DFA:7aAdaAb对I0及I2:FOLLOW(A)={b,d,#}移入集合=｛a｝上述两者不相交故文法为SLR(1)SLR(1)分析表ACTIONGOTOabd#A0S2r3r3r311acc2S2r3r3r333S5S44r1r1r15r2r2r22．考虑文法G[S]:S→SdA|AA→AhV|VV→iW|WW→pSq|r请将该文法变换到等价的LL(1)文法G’[S]，并构造G’的LL(1)分析表(填写下表)。给出分析过程。G’[S]的LL(1)分析表dhipqr#SI0:S’→.AA→.aAdA→.aAbA→.I1:S’→A.I2:A→a.AdA→a.AbA→.aAdA→.aAbA→.I3:A→aA.dA→aA.bI4:A→aAd.I5:A→aAb。8AVW答：文法：S→SdA|AA→AhV|VV→iW|WW→pSq|r消除左递归：S→AS’S’→dAS’|εA→VA’A’→hVA’|εV→iW|WW→pSq|rFOLLOW(S)={q，#}FOLLOW(S’)=FOLLOW(S’)∪FOLLOW(S)FOLLOW(S’)={q,#}FIRST(S’)={ε,d}FOLLOW(A)={d}∪FOLLOW(S)∪FOLLOW(S’)={d,q,#}FOLLOW(A’)=FOLLOW(A)={d,q,#}SELECT(S→AS’)={i,p,r}SELECT(S’→dAS’)={d}SELECT(S’→ε)={q,#}SELECT(A→VA’)={i,p,r}SELCTCT(A’→hVA’)={h}SELECT(A’→ε)={d,q,#}SELECT(V→iW)={i}SELECT(V→W)={p,r}SELECT(W→pSq)={p}SELECT(W→r)={r}G’的LL(1)分析表dhipqr#SAS’AS’AS’S’dAS’εεAVA’VA’VA’A’εhVA’εεVi没有冲突，改写后文法为LL(1).93．构造一个最小DFA，它接受正规式(a|b)*ab的正规集。给出分析过程。答：正规式(a|b)*ab的NFA为：aabb确定化：ab{1}=T0{1,2}=T1{1}=T0{1,2}=T1{1,2}=T1{1,3}=T2{1,3}=T2{1,2}=T1{1}=T0DFA:baaabb最小化：初始划分：｛T0,T1｝｛T2｝f(T0,b)=TOf(T1,b)=T2落在不同划分所以｛T0,T1｝可区别。最终划分｛T0｝｛T1｝｛T2｝上图已经是最小DFA.1233T0T1T2