编译原理试题

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 为文法的终结符， 且有优先关系 a b 和 b c，则 。A必有 a c B必有

2、 c aC必有 b a 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有多个入口语句和多个出口语句二 判断题（

3、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 T F|T*F F PF|P P (E)|i, 句型 T+T*F+i的直接短语为 ，句柄为 。* 且

4、a3在 LR(0) 分析法中，若 , VV 则称“ 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 | aQQ aQ | bD | bD bB | aAE aB | bFF bD | aE | b六（8 分）写一个文法，

5、使其语言是：L ambman bn | m,n 0 七（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 分）将下面程序段翻译成四元式序列。while A<CB<D doif A=1 then C:=C+1else while A<D doA:=A+2;十（6 分）设有以下程序段program main;var a,b:

6、integer;procedure p(x,y,z:integer);beginy:=y+1;z:=z+xend ;begina:=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 子句:

7、< 条件语句 > := 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!=

8、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答案题号 一 二 三 备 注1 B 自顶向下 自底向上2 C T,T*F , i T3 D 归约 移进4 D 起始地址 栈顶5 D 6 C 7 B8 A四 五 六G： SABa* (00 |11)(0 |1)*(0 |1) A A baAb| Bab aaB SaBb| Z b bbb DQ ba七修改后的文法 GA ：A aA Selec

9、t (A aA)=aA AB| Select (A AB)=a Select(A )=#,dB dB Select(B dB)=dBbB| Select(B bB)=b Select(B )=#Select(A AB) Select(A ) Select(B bB ) Select(B ) GA 为 LL(1) 文法预测分析表：a b d #A AaAA AAB A AB BdBB BbB B八（1）可归前缀图 （2）因为存在冲突，所以不是 LR(0) 文法。I1:S S.I5:A S.AA S.AA .SASA .SAA .aSA .aS .ASAS .ASS .b bS .b SA aaI

10、7:A SA.I0:S .S I2:A a. S A.SabS .AS S .ASaS .bA .SA aA .a A .a Sba bI6:S AS.SA AI4:S A.S A S.AA A .SAS .ASS .b A .aSA .SA S .ASAA .a S .b九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+1107 （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