编译原理样题(含答案).doc

编译原理试题
计算机学院_____级 班 学号 姓名
题号
一
二
三
四
五
六
七
八
九
十
总分
满分

得分

一 选择题
1、编译原理各阶段工作都涉及 (第1章)：
A.词法分析 B.表格管理 C.语法分析 D.语义分析
2、正则表达式R1和R2等价是指 (第4章)
A.R1和R2都是定义在一个字母表上的正则表达式
B.R1和R2中使用的运算符相同
C.R1和R2代表同一正则集
D.R1和R2代表不同正则集
3、在以下的语法分析中， 特别适合于表达式的分析。(第5，6，7章)
A.LR分析
B.LL(1)分析
C.递归下降分析
D.算符优先分析
4、与（a|b）*(a|b)等价的正规式是 。(第4章)
A.a*| b* B.(ab)*(a|b) C.（a|b）（a|b）* D.（a|b）*
5、在语法制导翻译中不采用拉链回填技术的语句是 。(第8章)
A.跳转语句 B.赋值语句 C.条件语句 D.循环语句
6、在属性文法中，终结符只具有 属性。(第8章)
A.传递 B.继承 C.抽象 D.综合
7、过程的Display表中记录了_ _____。(第10章)
A. 过程的连结数据 B. 过程的嵌套层数
C. 过程的返回地址 D. 过程的入口地址

二 判断题
1、最左归约也称为规范归约。(第3章)
2、逆波兰法表示的表达式把运算对象放在运算符的后面。(第8章)
3、同心集的合并有可能产生“归约/归约”冲突。(第7章)
4、DFA可以通过多条路径识别一个符号串。(第4章)
5、动态数组的存储空间在编译时就可完全确定。(第10章)

三 填空题
1、词法分析所依循的是语言的 ；而中间代码生成所依循的是 。(第4，8章)
2、在LR(0)分析法中，若a,βÎV*且aÎ则称“S ®a.A”为　　 　项目，称“S ®a.aβ”为　　 　项目。(第7章)
3、规范规约每次规约的是句型的______________。 (第6章)
4、无符号常数的识别和计算该常数的工作，通常在____________阶段完成的。(第4章)

四、设字母表为{a,b}的语言L的句子是满足下述条件的串：每个a都有b直接跟在右边。构造该语言的正则式。（第4章）

五、将下图的NFA确定化为DFA,图中初态为X，终态为Y。(第4章)
+

六、写一个2型文法G，使得L(G)={ai+2bi|i>=0}∪{aibi+2|i>=0}。(第3章)

七、设文法G（S）：(第5章)
   S → S＋aF|aF|＋aF
   F → *aF|*a
（1）消除左递归和左因子；
（2）构造相应的FIRST和FOLLOW集合；
（3）构造预测分析表。

八、对文法G[S]:S → aSb | P (第6章)
P → bPc | bQc
Q → Qa | a
请构造简单优先关系表，该文法是否是简单优先文法？
九、设有以下程序段(第10章)
program main;
var a,b:integer;
procedure p(x,y,z:integer);
begin
y:=y*2;
z:=z+x
end;
begin
a:=5; b:=2; p(a*b,a,a); write(a)
end.
对于下列参数传递方式，分别写出执行程序后a的输出值。
（1）传值； （2）传地址； （3）值结果； （4）传名。
十、文法G[S]及其LR分析表如下，请给出对串dada#的分析过程。(第7章)
　　 G[S]: 1) S →VdB　　　　2) V →e
　　 　　　3) V →ε 　　　　 4) B →a
　　　 　　5) B →Bda 　　　 6) B →ε
状态
ACTION
GOTO
d
e
a
#
S
B
V
0
r3
S3

1

2
1

acc

2
S4

3
r2

4
r6

S5
r6

6

5
r4

r4

6
S7

r1

7

S8

8
r5

r5

十一、试将下述程序段翻译成三地址形式的中间代码表示。(第8章)
while ( a+b<c OR a=b )
while ( a<5 AND b<10 )
{
a=a+1;
b=b+1;
}
}
十二、将下面程序划分为基本块，并画出其程序流图。
read(A,B)
F:=1
C:=A*A
D:=B*B
if C<D goto L1
E:=A*A
F:=F+1
E:=E+F
write(E)
halt
L1: E:=B*B
F:=F+2
E:=E+F
write(E)
if E>100 goto L2
halt
L2: F:=F-1
goto L1

十三、对PL/0语言扩充单词-=和--: (第2章)
请完成下列识别单词‘-’，‘-＝’和‘--’（设单词内码分别为MINUS，MINUSBECOME和MINUSMINUS）的词法分析算法：
if ( CH=='-' ) {
① ;
if ( ② ) {
SYM=MINUSBECOME;
GetCh();
} else if ( CH=='-' ) {
③
} else
④
}

答案
一 选择题
b,c,d,c,b,d,b

二 判断题
√×√××

三 填空题
1、文法 　 语义 2、待约项目 移进项目
3、句柄 4、词法

四 (b|ab)*

五
解：用子集法确定化如下表
I
Ia
Ib
状态
{X,0,1,3}
{0,1,3}..
{2,3,Y}..
{1,3}....
{2,Y}....
{Y}....
{0,1,3}
{0,1,3}
{1,3}

{1,3}

{2,3,Y}
{2,3,Y}
{Y}....
{2,Y}..
{Y}....

-X
1
+2
3
+4
+Y

确定化后如下图

六 解：文法G（S）：
　　 S ®aSb
　　 S ®aa
　　 S ®bb

七 解：
　  （1）（消除左递归，提公因左因子）
　　　　  S→aFS'|＋aFS'
　　　　  S'→＋aFS'|ε
　　　　  F→*aF'
　　　　  F'→F|ε

　  （2）
　　　　  FIRST（S）＝｛a，十｝ 　 FOLLOW（S）＝｛＃｝
　　　　  FIRST（50）＝｛＋，ε ｝  FOLLOW（S'）＝｛＃｝
　　　　  FIRST（F）＝｛*｝ 　　 FOLLOW（F）＝（＋，＃）
　　　　  FIRST（F'）＝｛*，ε｝   FOLLOW（＋，＃｝
　   （3）

八 Head(S)={a,P,b} Head(P)={b} Head(Q)={Q,a}
Tail(S)={b,P,c} Tail(P)={c} Tail(Q)={a}
（1）“=”关系： a=S S=b b=P P=c b=Q Q=c Q=a
（2）“<”关系： a<Head(S) b<Head(P) b<Head(Q)
（3）“>”关系： Tail(S)>b Tail(P)>c Tail(Q)>a
简单优先关系矩阵如下：

S
a
b
P
Q
c
S

=

a
=
< >
<
<

>
b

<
< >
=
= <

P

>

=
Q

=

=
c

>

>
由于矩阵中有元素存在多种优先关系，故不是简单优先文法。

九 （1）5； （2）20； （3）15； （4）30。

十 对输入串dada#的分析过程
步骤
状态栈
文法符号栈
剩余输入符号
动作
1
2
3
4
5
6
7
8
9
0
02
024
0245
0246
02467
024678
0246
01
#
#V
#Vd
#Vda
#VdB
#VdBd
#VdBda
#VdB
#S
dada#
dada#
ada#
da#
da#
a#
#
#
#
用V →ε归约
移进
移进
用B →a归约
移进
移进
用B →Bda 归约
用S →VdB 归约
接受

十一 解：三地址代码如下：
100: t:=a+b
101: if t<c goto 105
102: goto 103
103: if a=b goto 105
104: goto 112
105: if a<5 goto 107
106: goto 100
107: if b<10 goto 109
108: goto 100
109: a:=a+1
110: b:=b+1
111: goto 105
112:

十二 将程序划分为五个基本块，B1、B2、B3、B4和B5，如流图所示。

read(A,B) B1
F:=1
C:=A*A
D:=B*B
if C<D goto L1

E:=A*A B2
F:=F+1
E:=E+F
write(E)
halt

L1: E:=B*B B3
F:=F+2
E:=E+F
write(E)
if E>100 goto L2

halt B4
L2: F:=F-1 B5
goto L1
十三
GetCh();
CH=='='
SYM=MINUSMINUS
SYM=MINUS