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

编译原理试题计算机学院2001级 班 学号 姓名 题号一二三四五六七八九十十一十二总分满分126878812127668100得分一 选择题（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有一个入口语句和多个出口语句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)分析法中，若a,V*且a则称“A a.”为规约 项目，称“S a.a”为移进 项目。4在PL/0的目标代码解释执行时，寄存器B总是指向当前执行过程活动记录的起始地址 ，而寄存器T总是指向栈顶 。四（7分）有穷自动机M接受字母表S0,1上所有满足下述条件的串：串中至少包含两个连续的0或两个连续的1。请写出与M等价的正规式。五（8分）构造下列文法相应的有穷自动机。GS：S aA | bQ A aA | bB | b B bD | aQ Q aQ | bD | b D bB | aA E aB | bF F bD | aE | b 六（8分）写一个文法，使其语言是：L ambmanbn | m,n0 七（12分）已知文法GA：A aAB | a B Bb | d（1）构造与GA等价的LL(1)文法；（2）构造GA的预测分析表。八（12分）考虑文法 GS: S AS | b A SA | a（1）构造文法的可归前缀图（活前缀的DFA）；（2）判断文法是否是LR(0)文法，并说明理由。九（7分）将下面程序段翻译成四元式序列。whileACBDdoif A=1 then C:=C+1 else while AD do A:=A+2;十（6分）设有以下程序段program main;var a,b:integer;procedure p(x,y,z:integer); begin y:=y+1; z:=z+x end;begin a:=2; b:=3; p(a+b,a,a); write(a)end.对于下列参数传递方式，分别写出执行程序后a的输出值。（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) 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 ;break; CP_sample答案题号一二三备 注1B自顶向下 自底向上2CT,T*F , i T3D归约 移进4D起始地址 栈顶5D6C7B8AZSABDQabaabbbbbbaa四 五 六G：SAB AaAb| BaBb|七修改后的文法GA ： AaA Select (AaA)=a AAB|Select (AAB)=a Select(A)=#,d BdB Select(BdB)=dBbB|Select(BbB)=b Select(B)=#Select(AAB) Select(A)FSelect(BbB) Select(B)F GA为LL(1)文法预测分析表： abd#AAaAAAABAABBdBBBbBB八（1）可归前缀图 （2）因为存在冲突，所以不是LR(0)文法。九100（J, A, C, 102） 或：100 if AC goto 102101（J, , , 113） 101 goto 113102（J, B, D, 104）102 if BD 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+1107（J, , , 112） 107 goto 112 (或goto 100)108（J, A, D, 110）108 if AD goto 110109（J, , , 112） 109 goto 112 (或goto 100)110（+， A, 2,