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

- 1 -编译原理试题计算机学院 2001 级 班 学号 姓名 题号 一 二 三 四 五 六 七 八 九 十 十一 十二 总分满分 12 6 8 7 8 8 12 12 7 6 6 8 100得分一 选择题（12 分）【 】1词法分析器的输入是 。A符号串 B源程序 C语法单位 D目标程序【 】2两个有穷自动机等价是指它们的 。A状态数相等 B有向弧数相等C所识别的语言相等 D状态数和有向弧数相等【 】3文法 G：S xSx | y 所识别的语言是 。Axy*x B(xyx)* Cxx*yxx* Dx*yx*【 】4设 a,b,c 为文法的终结符，且有优先关系 ab 和 bc，则 。A必有 ac B必有 ca C必有 ba D选项 A、B 和 C 都不一定成立【 】5若状态 k 含有项目“A.” ，且仅当输入符号 aFOLLOW(A)时，才用规则“A ”归约的语法分析方法是 。AALR 分析法 BLR(0)分析法 CLR(1)分析法 DSLR(1)分析法【 】6生成中间代码时所依据的是 。A语法规则 B词法规则 C语义规则 D等价变换规则【 】7表达式（ab）（cd）的逆波兰表示为 。Aabcd BabcdCabcd Dabcd【 】8基本块 。A只有一个入口语句和一个出口语句 B有一个入口语句和多个出口语句- 2 -C有多个入口语句和一个出口语句 D有多个入口语句和多个出口语句二 判断题（6 分。认为正确的填“T”，错的填“F”）【T 】1同心集的合并有可能产生“归约/归约”冲突。【T 】2一个文法所有句子的集合构成该文法定义的语言。【 】3非终结符可以有综合属性，但不能有继承属性。【T 】4逆波兰表示法表示表达式时无需使用括号。【 】5一个有穷自动机有且只有一个终态。【】6若过程 p 第 k 次被调用，则 p 的 DISPLAY 表中就有 k+1 个元素。三 填空题（8 分）1最常用的两类语法分析方法是 自顶向下 和 自低向上 分析法。2对于文法 GE：ET|E+T TF|T*F FPF|P P(E)|i,句型 T+T*F+i的直接短语为 ，句柄为 。3在 LR(0)分析法中，若 ,V*且 a 则称“A .”为规约 T项目，称“S .a”为 移进 项目。4在 PL/0 的目标代码解释执行时，寄存器 B 总是指向当前执行过程活动记录的起始地址 ，而寄存器 T 总是指向 栈顶 。四（7 分）有穷自动机 M 接受字母表0,1上所有满足下述条件的串：串中至少包含两个连续的 0 或两个连续的 1。请写出与 M 等价的正规式。五（8 分）构造下列文法相应的有穷自动机。GS： S aA | bQA aA | bB | bB bD | aQ- 3 -Q aQ | bD | bD bB | aAE aB | bFF bD | aE | b 六（8 分）写一个文法，使其语言是：L ambmanbn | m,n0 七（12 分）已知文法GA： A aAB | aB Bb | d（1）构造与 GA等价的 LL(1)文法；（2）构造 GA的预测分析表。八（12 分）考虑文法GS: S AS | bA SA | a（1）构造文法的可归前缀图（活前缀的 DFA） ；（2）判断文法是否是 LR(0)文法，并说明理由。九（7 分）将下面程序段翻译成四元式序列。whileA := IF THEN ELSE 请在空缺处填空，完成条件语句的编译算法：switch (SYM) case IFSYM:GetSym() ;CONDITION(SymSetUnion(SymSetNew(THENSYM),FSYS),LEV,TX);if (SYM=THENSYM) GetSym();else Error(16);CX1=CX; GEN(JPC,0,0);STATEMENT(SymSetUnion(SymSetNew(ELSESYM),FSYS),LEV,TX);if ( SYM!=ELSESYM ) CODECX1.A=CX;else CX2=CX; GEN(JMP,0,0);CODECX1.A= cx (或者 cx2+1) ;STATEMENT(FSYS,LEV,TX);CODEcx2.A=cx ;- 5 -break;CP_sample 答案题号 一 二 三 备 注1 B 自顶向下 自底向上2 C T,T*F , i T3 D 归约 移进4 D 起始地址 栈顶5 D 6 C 7 B8 A四 五 六G： SAB*1)|(0|1)|0(A aAb|BaBb|七修改后的文法 GA ：AaA Select (AaA)=aAAB| Select (AAB)=a Select(A)=#,dBdB Select(BdB)=dB bB| Select(BbB)=b Select(B)=#Select(AAB) Select(A)Select(BbB) Select(B)GA为 LL(1)文法预测分析表：ZSABDQabaabbbb bbaa- 6 -a b d #A AaAA AAB A AB BdBB B bB B 八 （1）可归前缀图 （2）因为存在冲突，所以不是 LR(0)文法。 I0:S.S .A S.b A.SA .a I1:SS. A.A .S A.a S.S .b I2:Aa. I3:Sb. I4:SA.S . S.b A.SA .a I5:AS.A . A.a S.S .b I6:SAS. A. .SA A.a S.S .b I7:AS. S. .AS S.b A.SA .a S b SaAabA AabSa bS A ba AS SAba九100（J<, A, C, 102） 或： 100 if A<C goto 102101（J, , , 113） 101 goto 113102（J<, B, D, 104） 102 if B<D goto 104103（J, , , 113） 103 goto 113104（J=, A, 1, 106） 104 if A=1 goto 106105（J, , , 108） 105 goto 108106（+, C, 1, C） 106 C:=C+1- 7 -107（J, , , 112） 107 goto 112 (或 goto 100)108（J , A, D, 110） 108 if A D goto 110109（J, , , 112） 109 goto 112 (或 goto 100)110（+， A, 2, A） 110 A:=A+2111（J, , , 108） 111 goto 108112（J, , , 100） 112 goto 100113 113十 （1） 9 十一34242421 十二 GetSym()（2） 8 SYM!=ELSESYMcx (或者 cx2+1)CODEcx2.A=cx