编译原理复习例题.doc

编译原理复习例题(有些内容没有覆盖，比如优化、SLR（1）、LR（1）、LALR（1）等。但要求至少要按照作业题的范围复习。)

一 选择题
1．编译的各阶段工作都涉及 。
[A]词法分析 [B]表格管理 [C]语法分析 [D]语义分析
2． 型文法也称为正规文法。
　[A] 0 [B] 1 [C] 2 [D] 3
3． 文法不是LL(1)的。
　[A]递归 [B]右递归 [C]2型 [D]含有公共左因子的
4．文法E→E+E|E*E|i的句子i*i+i*i有 棵不同的语法树。
　[A] 1 [B] 3 [C] 5 [D] 7
5．文法 S→aaS|abc 定义的语言是 。
[A]{a2kbc|k>0} [B]{akbc|k>0}
[C]{a2k-1bc|k>0} [D]{akakbc|k>0}
6．若B为非终结符，则 A→a.Bb 为 。
[A]移进项目 [B]归约项目 [C]接受项目 [D]待约项目
7．同心集合并可能会产生新的 冲突。
[A]二义 [B]移进/移进 [C]移进/归约 [D]归约/归约
8．代码优化时所依据的是 。
[A]语法规则 [B]词法规则
[C]等价变换规则 [D]语义规则
9．表达式a-(-b)*c的逆波兰表示（@为单目减）为 。
[A]a-b@c* [B]ab@c*- [C]ab@- [D]ab@c-*
10．过程的DISPLAY表是用于存取过程的 。
[A]非局部变量 [B]嵌套层次 [C]返回地址 [D]入口地址
二 填空题
1．词法分析阶段的任务式从左到右扫描 　字符流　 ，从而逐个识别 一个个的单词 　。
2．对于文法G[E]：E→T|E+T T→F|T*F F→P^F|P
P→(E)|i，句型T+T*F+i的句柄是　 　。
3．最右推导的逆过程称为 规范归约 ，也称为 最左归约 。
4．符号表的每一项是由名字栏和 两个栏目组成。在目标代码生成阶段，符号表是 的依据。
三 判断题（认为正确的填“T”，错的填“F”）
【 】1．同心集的合并有可能产生“归约/归约”冲突。
【 】2．一个文法所有句子的集合构成该文法定义的语言。
【 】3．非终结符可以有综合属性，但不能有继承属性。
【 】4．逆波兰表示法表示表达式时无需使用括号。
【 】5．一个有穷自动机有且只有一个终态。
【 】6．若过程p第k次被调用，则p的DISPLAY表中就有k+1个元素。

四 解答题
1．给定文法G和句型(T+F)*i+T,
G: E→E+T | T T→T*F | F F→(E) | i
（1）画出句型的语法树；
（2）写出句型的全部短语、简单短语和句柄。
解：（略）

2．设有文法G：S→S+S|S*S|i|(S)。
（1）对于输入串i+i*i 给出一个最左推导；
（2）该文法是否是二义性文法？请证明你的结论。
解：（1）i+i*i的最左推导：
S => S+S => i+S => i+S*S => i+i*S => i+i*i
（2）该文法是二义性的。因为对于句子i+i*i可以画出两棵语法树（语法树略）。

3．给出语言{ambmcn|m≥1,n≥0}的上下文无关文法（2型）。
解： G: S→AB|A
A→aAb|ab
B→cB|c

4．给出语言{akbmcn|k,m,n≥1}的正规文法（3型）。
解： G: A→aA|aB
B→bB|bC
C→cC|c

5．将文法G改写成等价的正规文法（3型）。
G: S→dAB
A→aA|a
B→bB|b
解： G: S→dA
A→aA|aB
B→bB|b

6．构造一文法产生任意长的a，b串，使得
|a|≤|b|≤2|a|
其中，“|a|”和“|b|”分别表示串中的字符a和b的个数。
解：b的个数在a的个数和其2倍之间，串的结构形如aSBS和BSaS，其中B为1或2个b。故得文法
G: S→aSBS|BSaS|ε
B→b|bb

7．设有字母表{a，b}上的正规式R=(ab|a)*。
（1）构造R的相应有限自动机；
解：
0
1
2
3
b
a
a
ε
ε
-
+

（2）构造R的相应确定有限自动机；
解：将（1）所得的非确定有限自动机确定化

ε
a
b
-0
1

1
3
12

2

1
+3

a
b
-+013
123

+123
123
13
+13
123

0
1
2
a
a
b
a
-+
+
+

（3）构造R的相应最小确定有限自动机；
解：对（2）得到的DFA化简，合并状态0和2 为状态2：
1
2
a
a
b
-+
+

（4）构造与R等价的正规文法
解：令状态1和2分别对应非终结符B和A
G: A→aB|a|ε
B→aB|bA|a|b|ε
可化简为：
G: A→aB|ε
B→aB|bA|ε

8．写出如图所示的自动机描述的语言的正规式
1
3
2
4
b
a
b
a
b
-
+
0
a
a
+

解：abb*|abb*aa*b|aaa*b

9．写出在{a,b}上，不以a开头，但以aa结尾的字符串集合的正规式（并构造与之等价的最简DFA）。
解：依题意，“不以a开头”，则必以b开头，又要“以aa结尾”，故正规式为：b(a|b)*aa
（构造与之等价的最简DFA，此略）

10．写一个LL(1)文法G，使其语言是
L(G)={ ambnc2n | m>=0,n>0 }
并证明文法是LL(1)。
解：文法G（S）：S ® aS | E
E ® bE’
E’® Ecc | cc
Select(S ® aS)∩Select (S ® E)= Ф
Select(E’® Ecc)∩Select (E’® cc) =Ф
故文法为LL(1)的

11．将文法G改写成等价的LL(1)文法，并构造预测分析表。
G：S→S*aT|aT|*aT
T→+aT|+a
（编写递归下降子程序）
解：消除左递归后的文法G’: S→aTS’|*aTS’
S’→*aTS’|ε
T→+aT|+a
提取左公因子得文法G’’:S→aTS’|*aTS’
S’→*aTS’|ε
T→+aT’
T’→T|ε
Select(S→aTS’)={a}
Select(S→*aTS’)={*}
Select(S→aTS’)∩Select(S→*aTS’)=Ф
Select(S’→*aTS’)={*}
Select(S’→ε)=Follow(s’)={#}
Select(S’→*aTS’)∩Select(S’→ε)= Ф
Select(T→+aT’)={+}
Select(T’→T)=First(T) ={+}
Select(T’→ ε)=Follow(T’)={*,#}
Select(T’→T)∩Select(T’→ε)= Ф
所以该文法是LL(1)文法。
预测分析表：

*
+
a
#
S
S’Ta, N

TS’T, N

S’
S’Ta, N

ε, P
T

T’a, N

T’
ε, P
T, P

ε, P
a

ε, N

#

OK
（递归下降子程序，略）

12．对文法G[S]: S → aSb | P
P → bPc | bQc
Q → Qa | a
构造简单优先关系表。该文法是否是简单优先文法？
解：简单优先关系矩阵如下：

S
a
b
P
Q
c
S

=

a
=
< >
<
<

>
b

<
< >
=
= <

P

>

=
Q

=

=
c

>

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

13．考虑文法 G: S → AS | b
A → SA | a
（1）构造文法的可归前缀图（活前缀的DFA）；
（2）判断文法是否是LR(0)文法，并说明理由。
解：（1）可归前缀图

（2）因为存在冲突，所以不是LR(0)文法。

14．文法G及其LR分析表如下，请给出对串dada#的分析过程。
G: S → VdB ①
V → e ②
V → ε ③
B → a ④
B → Bda ⑤
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

解：对输入串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 归约
接受
15．对传值、传地址和传名3种参数传递方法分别写出下列程序的输出：
void p(int x, int y, int z) {
y *= 3;
z += x;
}
void main() {
int a=5, b=2;
p(a*b,a,a);
printf(“%d\n”, a);
}
这些参数传递机制如何实现？
解：（1）传值 5； （2）传地址 25； （3）传名 45
（参数传递机制，略）
16．将下面程序划分为基本块，并画出其程序流图。
b := 1
b := 2
if w <= x goto L2
e := b
goto L2
L1:goto L3
L2:c := 3
b := 4
c := 6
L3:if y <= z goto L4
halt
L4:g := g + 1
h := 8
goto L1
解：（1）基本块： （2）程序流图

b := 1
1
4
2
3
7
6
5
b := 2
if w <= x goto L2 （1）
e := b
goto L2 （2）
L1: goto L3 （3）
L2: c := 3
b := 4
c := 6 （4）
L3: if y <= z goto L4 （5）
halt （6）
L4: g := g + 1
h := 8
goto L1 （7）

- 8 -