编译原理期末试卷(含答案)

-1-编译原理试题计算机学院2001级班学号姓名题号一二三四五六七八九十十一十二总分满分126878812127668100得分一选择题（12分）【】1．词法分析器的输入是。A．符号串B．源程序C．语法单位D．目标程序【】2．两个有穷自动机等价是指它们的。A．状态数相等B．有向弧数相等C．所识别的语言相等D．状态数和有向弧数相等【】3．文法G：S→xSx|y所识别的语言是。A．xy*xB．(xyx)*C．xx*yxx*D．x*yx*【】4．设a,b,c为文法的终结符，且有优先关系ab和bc，则。A．必有acB．必有caC．必有baD．选项A、B和C都不一定成立【】5．若状态k含有项目“A→α.”，且仅当输入符号a∈FOLLOW(A)时，才用规则“A→α”归约的语法分析方法是。A．ALR分析法B．LR(0)分析法C．LR(1)分析法D．SLR(1)分析法【】6．生成中间代码时所依据的是。A．语法规则B．词法规则C．语义规则D．等价变换规则【】7．表达式（┐a∨b）∧（c∨d）的逆波兰表示为。A．┐ab∨∧cd∨B．a┐b∨cd∨∧C．ab∨┐cd∨∧D．a┐b∨∧cd∨【】8．基本块。A．只有一个入口语句和一个出口语句B．有一个入口语句和多个出口语句C．有多个入口语句和一个出口语句D．有多个入口语句和多个出口语句-2-二判断题（6分。认为正确的填“T”，错的填“F”）【T】1．同心集的合并有可能产生“归约/归约”冲突。【T】2．一个文法所有句子的集合构成该文法定义的语言。【】3．非终结符可以有综合属性，但不能有继承属性。【T】4．逆波兰表示法表示表达式时无需使用括号。【】5．一个有穷自动机有且只有一个终态。【】6．若过程p第k次被调用，则p的DISPLAY表中就有k+1个元素。三填空题（8分）1．最常用的两类语法分析方法是自顶向下和自低向上分析法。2．对于文法G[E]：E→T|E+TT→F|T*FF→P↑F|PP→(E)|i,句型T+T*F+i的直接短语为，句柄为。3．在LR(0)分析法中，若,βV*且aTV则称“A.”为规约项目，称“S.aβ”为移进项目。4．在PL/0的目标代码解释执行时，寄存器B总是指向当前执行过程活动记录的起始地址，而寄存器T总是指向栈顶。四（7分）有穷自动机M接受字母表＝{0,1}上所有满足下述条件的串：串中至少包含两个连续的0或两个连续的1。请写出与M等价的正规式。五（8分）构造下列文法相应的有穷自动机。G[S]：S→aA|bQA→aA|bB|bB→bD|aQQ→aQ|bD|bD→bB|aA-3-E→aB|bFF→bD|aE|b六（8分）写一个文法，使其语言是：L＝{ambmanbn|m,n≥0}七（12分）已知文法G[A]：A→aAB|aB→Bb|d（1）构造与G[A]等价的LL(1)文法；（2）构造G’[A]的预测分析表。八（12分）考虑文法G[S]:S→AS|bA→SA|a（1）构造文法的可归前缀图（活前缀的DFA）；（2）判断文法是否是LR(0)文法，并说明理由。九（7分）将下面程序段翻译成四元式序列。whileAC∧BDdoifA=1thenC:=C+1elsewhileADdoA:=A+2;十（6分）设有以下程序段programmain;vara,b:integer;procedurep(x,y,z:integer);beginy:=y+1;z:=z+xend;begina:=2;b:=3;p(a+b,a,a);write(a)end.对于下列参数传递方式，分别写出执行程序后a的输出值。-4-（1）传名；（2）传地址。十一（6分）有一语法制导翻译如下所示：S→bAb{print(”1”)}A→(B{print(”2”)}A→a{print(”3”)}B→Aa){print(”4”)}若对输入序列b(((aa)a)a)b进行自底向上分析，请写出输出序列。34242421十二（8分）对PL/0语言扩充ELSE子句:条件语句::=IF条件THEN语句[ELSE语句]请在空缺处填空，完成条件语句的编译算法：switch(SYM){……caseIFSYM:GetSym();CONDITION(SymSetUnion(SymSetNew(THENSYM),FSYS),LEV,TX);if(SYM==THENSYM)GetSym();elseError(16);CX1=CX;GEN(JPC,0,0);STATEMENT(SymSetUnion(SymSetNew(ELSESYM),FSYS),LEV,TX);if(SYM!=ELSESYM)CODE[CX1].A=CX;else{CX2=CX;GEN(JMP,0,0);CODE[CX1].A=cx(或者cx2+1);STATEMENT(FSYS,LEV,TX);CODE[cx2].A=cx;}break;-5-……}CP_sample答案题号一二三备注1B○自顶向下自底向上2C○T,T*F,iT3D╳归约移进4D○起始地址栈顶5D╳6C╳7B8A四．五．六．G：S→AB**1)|11)(0|00(1)|0(A→aAb|εB→aBb|ε七．修改后的文法G’[A]：A→aA’Select(A→aA’)={a}A’→AB|εSelect(A’→AB)={a}Select(A’→ε)={#,d}B→dB’Select(B→dB’)={d}B’→bB’|εSelect(B’→bB’)={b}Select(B’→ε)={#}Select(A’→AB)Select(A’→ε)＝Select(B’→bB’)Select(B’→ε)＝G’[A]为LL(1)文法预测分析表：abd#ZSABDQabaabbbbbbaa-6-AA→aA’A’A’→ABA’→εA’→εBB→dB’B’B’→bB’B’→ε八．（1）可归前缀图（2）因为存在冲突，所以不是LR(0)文法。I0:S’.SS.ASS.bA.SAA.aI1:S’S.AS.AA.SAA.aS.ASS.bI2:Aa.I3:Sb.I4:SA.SS.ASS.bA.SAA.aI5:AS.AA.SAA.aS.ASS.bI6:SAS.AS.AA.SAA.aS.ASS.bI7:ASA.SA.SS.ASS.bA.SAA.aSbSaAabAAabSabSAbaASSAba九．100（J,A,C,102）或：100ifACgoto102101（J,,,113）101goto113102（J,B,D,104）102ifBDgoto104103（J,,,113）103goto113104（J=,A,1,106）104ifA=1goto106105（J,,,108）105goto108106（+,C,1,C）106C:=C+1107（J,,,112）107goto112(或goto100)-7-108（J,A,D,110）108ifADgoto110109（J,,,112）109goto112(或goto100)110（+，A,2,A）110A:=A+2111（J,,,108）111goto108112（J,,,100）112goto100113113十．（1）9十一．34242421十二．GetSym()（2）8SYM!=ELSESYMcx(或者cx2+1)CODE[cx2].A=cx