编译原理作业与答案.doc

编译原理独立作业
2010.5
一、简答题
1、 构造一个文法使其生成的语言是不允许0打头的偶正整数集合。
2、文法：，，，构造句型的语法树，并指出该句型的短语、直接短语、句柄、素短语和最左素短语。
3、 某LL(1)文法的预测分析表如下，请在下述分析过程表中填入输入串（ a , a ）$ 的分析过程。

a
^
,
(
)
$
S
S®a
S®^

S®(A)

A
A®SB
A®SB

A®SA

B

B®,SB

B®ε

分析过程表：
步骤
符号栈
输入串
动作

4、 文法：，，，，，求增广文法中LR(1)项目集的初态项目集I0。
5、文法：，，，求出各非终结符的FISTVT和LASTVT集合。

二、分析题：
1、构造自动机，使得它能识别字母表{0,1}上以00结尾的符号串，将构造的自动机确定化，并写出相应的正规文法。
2、文法： ，写出每个非终结符的FIRST集和FOLLOW集，并判断该文法是否为LL(1)文法。
3、若有文法：
(1)试证明该文法是SLR(1) 文法，并构造SLR(1)分析表。
（2）给出输入串aa# 的分析过程。

参考答案
一、 简答题
1、构造一个文法使其生成的语言是不允许0打头的偶正整数集合。

2、文法：，，，构造句型的语法树，并指出该句型的短语、直接短语、句柄、素短语和最左素短语。
E
E
T
+
T
*
F
E
-
T
i
T
短语：T，T-T，i，T*i，T-T+T*i
直接短语：T， i
句柄： T
素短语（P72）：T-T,i
最左素短语：T-T

3 某LL(1)文法的预测分析表如下，请在下述分析过程表中填入输入串（ a , a ）$ 的分析过程。

a
^
,
(
)
$
S
S®a
S®^

S®(A)

A
A®SB
A®SB

A®SA

B

B®,SB

B®ε

（P68）
分析过程表：
步骤
符号栈
输入串
动作
1
$S
(a,a)$
符号栈出栈，对应产生式反向进栈
2
$)A(
(a,a)$
匹配
3
$)A
a,a)$
栈顶出栈，读下一个符号
4
$)BS
a,a)$
对应产生式A®SB反向进栈
5
$)Ba
a,a$
匹配

$)B
,a)$
栈顶出栈，读下一个符号

$)BS,
,a)$
匹配

$)BS
a)$
栈顶出栈，读下一个符号

$)Ba
a)$
匹配

$)B
)$
栈顶出栈，读下一个符号

$)
)$
B®ε出栈

$)
)$
匹配，出栈

$
$
匹配，分析成功
4、文法：，，，，，求增广文法中LR(1)项目集的初态项目集I0
(P90)
I0：

5. 文法：，，，求出各非终结符的FISTVT和LASTVT集合。
(P71)

FIRSTVT
LASTVT
S
G
H
; ( a
（ a
（ a
； ） a
） a
） a

二、分析题
1. 构造自动机，使得它能识别字母表{0,1}上以00结尾的符号串，将构造的自动机确定化，并写出相应的正规文法。(P41)
NFA:
S
A
B
0
1
0
0

0
1
S
A’
B’
S
S,A
S,A,B
S,A
S,A,B
S,A,B
S
S
S

1
0
0
S
A’
B’
1
1
0
DFA:
1
0
0
S
A’
B’
1
1
0
最小DFA:

最小化：
{S,A’}{B’}
0:{S}{A’}{B'}

正规文法： ’

2、 文法： ，写出每个非终结符的FIRST集和FOLLOW集，并判断该文法是否为LL(1)文法。
(P61)
FIRST(S)={a,b,d,e, }
FIRST(T)={a,b, }
FIRST(R)={d, }
FIRST(D)={a,b}
FOLLOW(S)={$ }
FOLLOW(T)=FOLLOW(S)={$ }
FOLLOW(R)={a,b,$}
FOLLOW(D)={d,$}
SELECT()={e}
SELECT()={a,b,d}
SELECT()={a,b}
SELECT()={$}
SELECT()={a,b}
SELECT()={d}
SELECT()={a}
SELECT()={d}
SELECT()∩SELECT()=
SELECT()∩SELECT()=
SELECT()∩SELECT()=
SELECT()∩SELECT()=

∴该文法是LL(1)文法。

3、若有文法：
(1)试证明该文法是SLR(1) 文法，并构造SLR(1)分析表。
（2）给出输入串aa# 的分析过程。
增广文法:
0) S'®S 1) S®AB 2) A®aBa 3) A®e 4) B®bAb 5) B®e

FOLLOW(S)={$} FOLLOW(A)={b,$} FOLLOW(B)={a,$}

ACTION
GOTO

a
b
$
S
A
B
0
S3

1
2

1

acc

2
r5
S5
r5

4
3
r5
S5
r5

6
4

r1

5
S3
r3
r3

7

6
S9

7

S8

8
r4

r4

9

r2
r2

步骤
状态栈
符号栈
输入串
动作
0
1
2
3
4
5
6
0
03
036
0369
02
024
01
＃
#a
#aB
#aBa
#A
#AB
#S
aa#
a#
a#
#
#
#
#
S3
r5
S9
r2
r5
r1
acc