《编译原理》期末复习资料(完整版).doc

给出语言{a n b n a mb m | n,m ≥0}的一个上下文无关文法。(6分)
解:G[S]:S—>AB
A—>aAb |ε
B—>aBb |ε
给出语言{1 n 0 m 1 m0 n | n,m ≥0}的一个上下文无关文法。
解: G[S]:S—>1S0 | A          
A—>0A1 |ε
P48 第6题(5)、(6).画语法树
6、已知文法G: 
<表达式>::=<项>|<表达式>+<项> 
<项>::=<因子>|<项>*<因子> 
<因子>::=(<表达式>)|i  
(5)i+(i+i) (6)i+i*i 
解:(5)语法树: (6)语法树:

P48第13题直接短语等
13、一个上下文无关文法生成句子abbaa的推导树如下:
(3)求直接短语
解:直接短语有:a ε b
.( 后加画语法树)
设文法G[S]为:
(1)S—>aAcBe
(2)A—>b
(3)A—>Ab
(4)B—>d
对输入串abbcde#进行分析,检查该符号串是否是G[S]的句子。
解:设一个先进后出的符号符,并把句子左括号“#”号放入栈底,其分析过程如下:
步骤
符号栈
输入符号串
动作
(1)
#
abbcde#
移进
(2)
#a
bbcde#
移进
(3)
#ab
bcde#
归约(A—>b)
(4)
#aA
bcde#
移进
(5)
#aAb
cde#
归约(A—>Ab)
(6)
#aA
cde#
移进
(7)
#aAc
de#
移进
(8)
#aAcd
e#
归约(B—>d)
(9)
#aAcB
e#
移进
(10)
#aAcBe
#
归约(S—>aAcBe)
(11)
#S
#
接受
语法树如下:

计算分析题(60%)
1、正规式→ NFA→ DFA→最简DFA
P72第1题(1)、(4);
第一题1、构造下列正规式相应的DFA.
(1)1(0|1)*101 
解:先构造NFA
用子集法将NFA确定化 
0
1
S
A
A
A
AB
AB
AC
AB
AC
A
ABZ
ABZ
AC
AB
除S,A外,重新命名其他状态,令AB为B、AC为C、ABZ为D,因为D含有Z(NFA的终态),所以D为终态,因此有:
0
1
S
A
A
A
B
B
C
B
C
A
D
D
C
B
得到DFA如下所示:
(4) b((ab)*|bb)*ab 
解:先构造NFA
得到DFA如下所示:
P72第4题(a)
4、把下图确定化和最小化
解:确定化:
用子集法将NFA确定化 
a
b
0
01
1
01
01
1
1
0
重新命名,以A、B、C代替{0}、{01}、{1},其中A为初态,A,B为终态,因此有:
a
b
A
B
C
B
B
C
C
A
最小化:: 
初始分划得终态组{A,B},非终态组{C} 
Π0:{A,B},{C},对终态组进行审查,判断A和B是等价的,故这是最后的划分。重新命名,以A、C代替{A,B}、{C},因此有:
a
b
A
A
C
C
A
即DFA最小化如下:
第7题
7、给文法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 
构造相应的最小的DFA。
解:先构造NFA:
用子集法将NFA确定化:
a
b
S
A
Q
A
A
BZ
BZ
Q
D
B
Q
D
Q
Q
DZ
DZ
A
B
D
A
B
将S、A、BZ、B、Q、DZ、D重新命名,分别用0、1、2、3、4、5、6表示。因为2、5中含有Z,所以它们为终态。因此有:
a
b
0
1
4
1
1
2
2
4
6
3
4
6
4
4
5
5
1
3
6
1
3
初始分划得:终态组{2,5},非终态组{0,1,3,46}
 Π0:{2,5},{0,1,3,4,6} 
对{0,1,3,4,6}进行审查: {1,4}输入b到达{2,5},而{0,3,6}输入b到达{3,4,6},故得到新分划{1,4},{0,3,6} 
Π1:{2,5},{1,4},{0,3,6}    
对{0,3,6}进行审查: {0}经过b到达{2},{3,6}经过b到达{3,6},故得到新分划{0},{3,6