第3章文法和语言
第1题
文法G＝({A,B,S},{a,b,c},P,S)其中P为：
S→Ac|aB
A→ab
B→bc
写出L(G[S])的全部元素。
答案：
L(G[S])={abc}
第 11题
令文法 G[E]为：
E→T|E+T|E-T
T→F|T*F|T/F
F→(E)|i
证明 E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。
答案：
此句型对应语法树如右，故为此文法一个句型。
或者：因为存在推导序列: E=>E+T=>E+T*F，所
以E+T*F句型
此句型相对于E的短语有:E+T*F；相对于 T的短语
有 T*F
直接短语为：T*F
句柄为：T*F
第 13题
一个上下文无关文法生成句子abbaa的推导树如下：
(1)给出串abbaa最左推导、最右推导。
(2)该文法的产生式集合 P可能有哪些元素？
(3)找出该句子的所有短语、直接短语、句柄。
A
S
a S
B
B B A
S
a
《编译原理》课后习题答案第三章
答案：
(1)串abbaa最左推导:
S=>ABS=>aBS=>aSBBS=>aBBS=>abBS=>abbS=>abbAa=>abbaa
最右推导：
S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Abbaa=>abbaa (2)产生式有：S→ABS |Aa|ε A→a B→SBB|b
abbaa aaabbaa ⋯
可能元素有：ε aa ab
(3)该句子的短语有：
a是相对 A的短语
ε是相对 S的短语
b是相对 B的短语
εbb是相对 B的短语
aa是相对 S的短语
aεbbaa是相对 S的短语
直接短语有：a ε b
句柄是：a
第 14题
给出生成下述语言的上下文无关文法：
（1）{ a n b n a m b m| n，m>=0}
（2）{ 1n0m 1m0n| n，m>=0}
（3）{WaWr|W属于{0|a}*，Wr表示W的逆}
答案：
（１）
S→AA
A→aAb|ε
（２）
S→1S0|A
A→0A1|ε
（３）
S→0S0|1S1|ε
第 16题
给出生成下述语言的三型文法：
(1){an|n >=0 }
(2) { a n b m|n,m>=1 }
(3){a n b m c k|n,m,k>=0 }
答案：
(1) S→aS|ε
(2)
S→aA
A→aA|B
B→bB|b
(3)
A→aA|B
B→bB|C
问题 6：
已知文法G[E]:
E→ET+|T
T→TF* | F
F→F^ | a
试证：FF^^*是文法的句型，指出该句型的短语、简单短语和句柄. 答案：
该句型对应的语法树如下：
该句型相对于E的短语有FF^^*
相对于T的短语有FF^^*,F
相对于F的短语有F^;F^^
简单短语有F;F^
句柄为 F.
C→cC|ε
第4章词法分析
第1题
（３）a((a|b)*|ab*a)*b
（４）b((ab)*|bb)*ab 答案：
(1)先构造NFA：
用子集法将 NFA确定化
. X A AB AC ABY
.
A
AC
A
AC
1
A
AB
AB
ABY
AB
除X，A外，重新命名其他状态，令AB为B、AC为C、ABY为D，因为D含有Y（NFA 的终态），所以 D为终态。
.01
X.
AA A
BB C
BC A
DD C
B
DFA的状态图：:
盛威网（）专业的计算机学习网站 1
(2)先构造 NFA：
0 ε
X 1 A ε
ε
B 1
C 0
ε
D 1
E ε
ε
L 0 Y F
用子集法将 NFA确定化1 G 0 H 1 I 0
ε
J 1 K ε
X
T0=X
A
T1= ABFL
Y
CG
T2= Y
T3= CGJ
DH
K
T4= DH
EI
T5= ABFKL
T6= ABEFIL EJY
T7= ABEFGJLY EHY
CGK
T8= ABEFHLY EY
CGI
T9= ABCFGJKL DHY
T10= ABEFLY T11= CGJI
DHJ
T12= DHY
T13= DHJ
EIK
T14= ABEFIKL ε
X
ABFL
Y
CGJ
DH
ABFKL
ABEFIL
ABEFGJLY
ABEFHLY
ABCFGJKL
ABEFLY
CGJI
DHY
DHJ
ABEFIKL
Y
DH
Y
EJY
EHY
EY
DHY
EY
DHJ
EJY
1
A
CG
K
EI
CG
CG
CGK
CGI
CGK
CG
K
EI
EIK
CG
将T0、T1、T2、T3、T4、T5、T6、T7、T8、T9、T10、T11、T12、T13、T14重新命名，分别用0、1、2、3、4、5、6、7、8、9、10、11、12、13、14表示。
因为2、7、8、10、12中含有Y，所以它们都为终态。
0 1 2 3 4 5 6 7 8 9
10
11
12
13
14
2
4
2
7
8
10
12
10
13
7
1
13
5
633
9
11
9356
14
3
1
1
1
1
3
4
1
1
1
1
1
2
5
6
1
1
10
7
8
1
1
9
11
1
12
13
1
14
《编译原理》课后习题答案第四章
(3)先构造NFA：
先构造 NFA：
a,b
X a ε
A
ε
ε
B
D a E
b
a
ε
F
ε
C
ε
b
Y
用子集法将 NFA确定化
X
T0=X
A
T1=ABCD BE
BY
T2=ABCDE BEF
BEY
T3=ABCDY T4=ABCDEF T5=ABCDEY ε
X
ABCD
ABCDE
ABCDY
ABCDEF
ABCDEY
a
A
BE
BEF
BE
BEF
BEF
b
BY
BEY
BY
BEY
BEY
将T0、T1、T2、T3、T4、T5重新命名，分别用0、1、2、3、4、5表示。
因为3、5中含有Y，所以它们都为终态。
1
2
3
4
5
0 a a
1
2
4
2
4
4
1 b 3
b
b
3
535
5 2
a a
a 4
a
bb
a
b
5
《编译原理》课后习题答案第四章(4)先构造NFA：
X b
ε
A
ε
ε
ε
B
a
C
b
ε
D ε
E a I b Y
F b
G b
Hεε
用子集法将 NFA确定化：
εa b
X
T0=X
A
T1=ABDEF CI
G
T2=CI
DY
T3=G
H
T4=ABDEFY T5=ABEFH X
ABDEF
CI
G
ABDEFY
ABEFH
CI
CI
CI
A
G
DY
H
G
G
将T0、T1、T2、T3、T4、T5重新命名，分别用0、1、2、3、4、5表示。
因为4中含有Y，
所以它为终态。
a b
0112
3243
542
3523
DFA的状态图：
5
《编译原理》课后习题答案第四章
b
1
2
a
b
b
3
b
b
b
5
用子集法将 NFA确定化：。