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

编译原理试题
计算机学院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)分析法中，若a,βÎV*且aÎ则称“A ®a.”为　规约　 　项目，称“S ®a.aβ”为　　移进 　项目。
4．在PL/0的目标代码解释执行时，寄存器B总是指向当前执行过程活动记录的　起始地址　 　，而寄存器T总是指向　栈顶　 　。
四（7分）有穷自动机M接受字母表S＝{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<C∧B<D　do
　　if A=1 then C:=C+1
　 else while A<D 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 ) 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

Z
S
A
B
D
Q
a
b
a
a
b
b
b
b
b
b
a
a
四． 五． 六．G： S→AB
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’→ε)＝F
Select(B’→bB’) Select(B’→ε)＝F
G’[A]为LL(1)文法
预测分析表：

a
b
d
#
A
A→aA’

A’
A’→AB

A’→ε
A’→ε
B

B→dB’

B’

B’→bB’

B’→ε

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

九．100（J<, A, C, 102） 或： 100 if A<C goto 102
101（J, , , 113） 101 goto 113
102（J<, B, D, 104） 102 if B<D goto 104
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)
108（J, A, D, 110） 108 if AD goto 110
109（J, , , 112） 109 goto 112 (或goto 100)
110（+， A, 2, A） 110 A:=A+2
111（J, , , 108） 111 goto 108
112（J, , , 100） 112 goto 100
113 113

十． （1） 9 十一．34242421 十二． GetSym()
（2） 8 SYM!=ELSESYM
cx (或者cx2+1)
CODE[cx2].A=cx

- 7 -