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

编译原理试题

计算机学院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 所识别的语言是

。

A．xy*x B．(xyx)* C．xx*yxx* D．x*yx*

【 】4．设a,b,c为文法的终结符，且有优先关系ab和bc，则 。

A．必有ac B．必有ca

C．必有ba D．选项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．有多个入口语句和多个出口语句 二 判断题（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+T T→F|T*F F→P↑F|P P→(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 | 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,n≥0 }

七（12分）已知文法

G[A]： A → aAB | a

B → Bb | d

（1）构造与G[A]等价的LL(1)文法；

（2）构造G’[A]的预测分析表。

八（12分）考虑文法

G[S]: S → AS | b

A → SA | a

（1）构造文法的可归前缀图（活前缀的DFA）；

（2）判断文法是否是LR(0)文法，并说明理由。

九（7分）将下面程序段翻译成四元式序列。

while A

if A=1 then C:=C+1

else while A

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 ) 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; „„

}

CP_sample答案

题号 一 二 三 备 注

1 B ○ 自顶向下 自底向上

2 C ○ T,T*F , i T

3 D ╳ 归约 移进

4 D ○ 起始地址 栈顶

5 D ╳

6 C ╳

7 B

8 A

四．

五． 六．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)文法

预测分析表：

a b d # Z S A

B

D

Q a

b

a a

b

b b

b b b

a a A A→aA’

A’ A’→AB A’→ε A’→ε

B B→dB’

B’ B’→bB’ B’→ε

八．（1）可归前缀图 （2）因为存在冲突，所以不是LR(0)文法。

I0:S’.S

S.AS

S.b

A.SA

A.a I1:S’S.

AS.A

A.SA

A.a

S.AS

S.b

I2:Aa.

I3:Sb.

I4:SA.S

S.AS

S.b

A.SA

A.a I5:AS.A

A.SA

A.a

S.AS

S.b

I6:SAS.

AS.A

A.SA

A.a

S.AS

S.b I7:ASA.

SA.S

S.AS

S.b

A.SA

A.a SbSaAabAAabSabS AbaASSAba

九．100（J<, A, C, 102） 或： 100 if A

101（J, , , 113） 101 goto 113

102（J<, B, D, 104） 102 if B

103（J, , , 113） 103 goto 113

104（J=, A, 1, 106） 104 if A=1 goto 106

105（J, , , 108） 105 goto 108

106（+, C, 1, C） 106 C:=C+1

107（J, , , 112） 107 goto 112 (或goto 100)