编译原理三四章答案清华版.docx
《编译原理三四章答案清华版.docx》由会员分享，可在线阅读，更多相关《编译原理三四章答案清华版.docx（19页珍藏版）》请在冰点文库上搜索。
编译原理三四章答案清华版
第三章习题解答
6．每个表达式的推导及语法树分别如下：
（1）<表达式>
=><项>
=><因子>
=>i
（2）<表达式>
=><项>
=><因子>
=>（<表达式>）
=>（<项>）
=>（<因子>）
=>（i）
（3）<表达式>
=><项>
=><项>*<因子>
=><因子>*<因子>
=>i*<因子>
=>i*i
（4）<表达式>
=><表达式>+<项>
=><项>+<项>
=><项>*<因子>+<项>
=><因子>*<因子>+<项>
=>i*<因子>+<项>
=>i*i+<项>
=>i*i+<因子>
=>i*i+i
（5）<表达式>
=><表达式>+<项>
=><项>+<项>
=><因子>+<项>
=>i+<项>
=>i+<因子>
=>i+<表达式>
=>i+（<表达式>+<项>）
=>i+（<项>+<项>）
=>i+（<因子>+<项>）
=>i+（i+<项>）
=>i+（i+<因子>）
=>i+（i+i）
（6）<表达式>
=><表达式>+<项>
=><项>+<项>
=><因子>+<项>
=>i+<项>
=>i+<项>*<因子>
=>i+<因子>*<因子>
=>i+i*<因子>
=>i+i*i
11．根据文法G给定的规则，从文法的开始符E出发可推导出E+T*F，推导过程如下：
E=>E+T=>E+T*F，所以E+T*F是该文法的一个句型。
由右图的语法树也可以看出，E+T*F是该文法的一个句型。
这个句型的所有短语为：
E+T*F,T*F
直接短语为：
T*F
句柄为：
T*F
13．
（1）最左推导：
S=>ABS
=>a1BS
=>a1SBBS
=>a1BBS
=>a1b1BS
=>a1b1b2S
=>a1b1b2Aa3
=>a1b1b2a2a3
最右推导：
S=>ABS
=>ABAa3
=>ABa2a3
=>ASBBa2a3
=>ASBb2a2a3
=>ASb1b2a2a3
=>Ab1b2a2a3
=>a1b1b2a2a3
（2）该文法产生式集合P可能有如下规则：
S→ABS|Aa|ε
A→a
B→SBB|b
（3）该句子的所有短语为：
a1b1b2a2a3,a1,b1b2,ε,b1,b2,a2a3,a2
直接短语为：
a1,ε,b1,b2,a2
句柄为：
a1
第四章习题答案
1．
（1）对应NFA如图：
对其进行确定化操作：
0
1
-{S}
{A}
{A}
{A}
{A,B}
{A,B}
{A,C}
{A,B}
{A,C}
{A}
{A,B,Z}
+{A,B,Z}
{A,C}
{A,B}
T0=ε-closure（{S}）={S}
计算ε-closure（move（{S},0））=Ф
计算ε-closure（move（{S},1））={A}，标记为T1
计算ε-closure（move（{A},0））={A}=T1
计算ε-closure（move（{A},1））={A,B}，标记为T2
计算ε-closure（move（{A,B},0））={A,C}，标记为T3
计算ε-closure（move（{A,B},1））={A,B}=T2
计算ε-closure（move（{A,C},0））={A}=T1
计算ε-closure（move（{A,C},1））={A,B,Z}，标记为T4
计算ε-closure（move（{A,B,Z},0））={A,C}=T3
计算ε-closure（move（{A,B,Z},1））={A,B}=T2
得到的DFA存在五种状态：
[T0]，[T1]，[T2]，[T3]，[T4]
其中：
[T0]为初态，[T4]为终态，对应的转换矩阵如右上表格所示，令S,A,B,C,D分别表示这五种状态，则其对应的DFA状态转换图及状态转换矩阵分别为：
0
1
-S
A
A
A
B
B
C
B
C
A
D
+D
C
B
（3）对应NFA如图：
对其进行确定化操作：
T0=ε-closure（{S}）={S}
计算ε-closure（move（{S},a））={A,B,D}，标记为T1
计算ε-closure（move（{S},b））=Ф
计算ε-closure（move（{A,B,D},a））={A,B,C,D}，标记为
计算ε-closure（move（{A,B,D},b））={A,B,D,Z}，标记为T3
计算ε-closure（move（{A,B,C,D},a））={A,B,C,D}=T2
计算ε-closure（move（{A,B,C,D},b））={A,B,C,D,Z}，标记为T4
计算ε-closure（move（{A,B,D,Z},a））={A,B,C,D}=T2
计算ε-closure（move（{A,B,D,Z},b））={A,B,D,Z}=T3
计算ε-closure（move（{A,B,C,D,Z},a））={A,B,C,D}=T2
计算ε-closure（move（{A,B,C,D,Z},b））={A,B,C,D,Z}=T4
得到的DFA存在五种状态：
[T0]，[T1]，[T2]，[T3]，[T4]
其中：
[T0]为初态，[T3],[T4]为终态，对应的转换矩阵如左下表格所示，令S,A,B,C,D分别表示这五种状态，则其对应的DFA状态转换图及状态转换矩阵分别为：
a
b
-{S}
{A,B,D}
{A,B,D}
{A,B,C,D}
{A,B,D,Z}
{A,B,C,D}
{A,B,C,D}
{A,B,C,D,Z}
+{A,B,D,Z}
{A,B,C,D}
{A,B,D,Z}
+{A,B,C,D,Z}
{A,B,C,D}
{A,B,C,D,Z}
a
b
-S
A
A
B
C
B
B
D
+C
B
C
+D
B
D
2．根据题意，可以得其NFA状态转换图如下图所示：
对其进行确定化操作：
0
1
-{x}
{z}
{x}
+{z}
{x,z}
{y}
+{x,z}
{x,z}
{x,y}
{y}
{x,y}
{x,y}
{x,y,z}
{x}
+{x,y,z}
{x,y,z}
{x,y}
T0=ε-closure（{x}）={x}
计算ε-closure（move（{x},0））={z}，标记为T1
计算ε-closure（move（{x},1））={x}=T0
计算ε-closure（move（{z},0））={x,z}，标记为T2
计算ε-closure（move（{z},1））={y}，标记为T3
计算ε-closure（move（{x,z},0））={x,z}=T2
计算ε-closure（move（{x,z},1））={x,y}，标记为T4
计算ε-closure（move（{y},0））={x,y}=T4
计算ε-closure（move（{y},1））=Ф
计算ε-closure（move（{x,y},0））={x,y,z}，标记为T5
计算ε-closure（move（{x,y},1））={x}=T0
计算ε-closure（move（{x,y,z},0））={x,y,z}=T5
计算ε-closure（move（{x,y,z},1））={x,y}=T4
得到的DFA存在六种状态：
[T0]，[T1]，[T2]，[T3]，[T4]，[T5]
其中：
[T0]为初态，[T1],[T2],[T5]为终态，对应的转换矩阵如右上表格所示，令A,B,C,D,E,F分别表示这六种状态，则其对应的DFA状态转换图及状态转换矩阵分别为：
0
1
-A
B
A
+B
C
D
+C
C
E
D
E
E
F
A
+F
F
E
3．状态转换图如图所示：
对其进行确定化操作：
0
1
-{S}
{V,Q}
{Q,U}
{V,Q}
{V,Z}
{Q,U}
{Q,U}
{V}
{Q,U,Z}
+{V,Z}
{Z}
{Z}
{V}
{Z}
+{Q,U,Z}
{V,Z}
{Q,U,Z}
+{Z}
{Z}
{Z}
T0=ε-closure（{S}）={S}
计算ε-closure（move（{S},0））={V,Q}，标记为T1
计算ε-closure（move（{S},1））={Q,U}，标记为T2
计算ε-closure（move（{V,Q},0））={V,Z}，标记为T3
计算ε-closure（move（{V,Q},1））={Q,U}=T2
计算ε-closure（move（{Q,U},0））={V}，标记为T4
计算ε-closure（move（{Q,U},1））={Q,U,Z}，标记为T5
计算ε-closure（move（{V,Z},0））={Z}=T3
计算ε-closure（move（{V,Z},1））={Z}=T3
计算ε-closure（move（{V},0））={Z}=T4
计算ε-closure（move（{V},1））=Ф
计算ε-closure（move（{Q,U,Z},0））={V,Z}，标记为T6
计算ε-closure（move（{Q,U,Z},1））={Q,U,Z}=T5
计算ε-closure（move（{Z},0））={Z}=T6
计算ε-closure（move（{Z},1））={Z}=T3
得到的DFA存在七种状态：
[T0]，[T1]，[T2]，[T3]，[T4]，[T5]，[T5]
0
1
-A
B
C
B
D
C
C
E
F
+D
G
G
E
G
+F
D
F
+G
G
G
其中：
[T0]为初态，[T3],[T5],[T6]为终态，对应的转换矩阵如右上表格所示，令A,B,C,D,E,F,G分别表示这七种状态，则其对应的DFA状态转换图及状态转换矩阵分别为：
4．（a）
对其进行确定化操作：
T0=ε-closure（{0}）={0}
a
b
-+{0}
{0,1}
{1}
+{0,1}
{0,1}
{1}
{1}
{0}
计算ε-closure（move（{0},a））={0,1}，标记为T1
计算ε-closure（move（{0},b））={1}，标记为T2
计算ε-closure（move（{0,1},a））={0,1}=T1
计算ε-closure（move（{0,1},b））={1}=T2
计算ε-closure（move（{1},a））={0}=T0
计算ε-closure（move（{1},b））=Ф
得到的DFA存在三种状态：
[T0]，[T1]，[T2]
其中，[T0]为初态，[T0],[T1]为终态，对应的转换矩阵如右上表格所示，令A,B,C分别表示这三种状态，则其对应的DFA状态转换图及状态转换矩阵如下：
a
b
-+A
B
C
+B
B
C
C
A
对其进行最小化操作：
该DFA无多余状态，进行初始划分，得终态组{A,B}，非终态组{C}
对终态组{A,B}进行审查，输入符号a后，状态A,B均转换成状态B；输入符号b后，状态A,B均转换成状态C，由此可知，状态A,B等价，不能再分。
令A代表{A,B}，则得其最小化的DFA为：
a
b
-+A
A
C
C
A
（b）
由此状态转换图可知，该NFA已经是DFA，直接对其进行最小化操作。
该DFA无多余状态，进行初始划分，得终态组{0}，非终态组{1,2,3,4,5}
对非终态组{1,2,3,4,5}进行审查，输入符号a后，状态4转换为状态0，其余状态转换为{1,2,3,4,5}中的状态，到达了不等价的状态，因此将{1,2,3,4,5}划分为{4},{1,2,3,5}
对状态集合{1,2,3,5}进行审查，输入符号b后，状态1,5转换为状态4，状态2,3转换为状态2，到达了不等价的状态，因此将{1,2,3,5}划分为{1,5},{2,3}
对状态集合{2,3}进行审查，输入符号a后，状态2转换为状态1，状态3转换为状态3，到达了不等价的状态，因此将{2,3}划分为{2},{3}
对状态集合{1,5}进行审查，输入符号a后均到达集合{1,5}中的状态，输入符号b后均到达状态4，因此不能再划分。
最终得到划分：
{0},{1,5},{2},{3},{4}
令1代表状态集合{1,5}，则得其最小化的DFA为：
a
b
-+0
1
2
1
1
4
2
1
3
3
3
2
4
0
1
7．对应的NFA状态转换图为：
对其进行确定化操作：
T0=ε-closure（{S}）={S}
a
b
-{S}
{A}
{Q}
{A}
{A}
{B,Z}
{Q}
{Q}
{D,Z}
+{B,Z}
{Q}
{D}
+{D,Z}
{A}
{B}
{D}
{A}
{B}
{B}
{Q}
{D}
计算ε-closure（move（{S},a））={A}，标记为T1
计算ε-closure（move（{S},b））={Q}，标记为T2
计算ε-closure（move（{A},a））={A}=T1
计算ε-closure（move（{A},b））={B,Z}，标记为T3
计算ε-closure（move（{Q},a））={Q}=T2
计算ε-closure（move（{Q},b））={D,Z}，标记为T4
计算ε-closure（move（{B,Z},a））={Q}=T2
计算ε-closure（move（{B,Z},b））={D}，标记为T5
计算ε-closure（move（{D,Z},a））={A}=T1
计算ε-closure（move（{D,Z},b））={B}，标记为T6
计算ε-closure（move（{D},a））={A}=T1
计算ε-closure（move（{D},b））={B}=T6
计算ε-closure（move（{B},a））={Q}=T2
计算ε-closure（move（{B},b））={D}=T5
得到的DFA存在七种状态：
[T0]，[T1]，[T2]，[T3]，[T4]，[T5]，[T5]
其中，[T0]为初态，[T3],[T4]为终态，对应的转换矩阵如右上表格所示，令A,B,C,D,E,F,G分别表示这七种状态，则其对应的DFA状态转换图及状态转换矩阵如下：
a
b
-A
B
C
B
B
D
C
C
E
+D
C
F
+E
B
G
F
B
G
G
C
F
对其进行最小化操作：
该DFA无多余状态，对其进行初始划分：
得终态组{D,E}，非终态组{A,B,C,F,G}
对非终态组{A,B,C,F,G}进行审查，输入符号a后，状态B,C分别转换为状态D,E，其余状态转换为{A,B,C,F,G}中的状态，到达了不等价的状态，因此将{A,B,C,F,G}划分为{B,C},{A,F,G}
对状态集合{A,F,G}进行审查，输入符号b后，状态A转换为状态C，而状态F,G转换为状态集合{A,F,G}中的状态，到达了不等价的状态，因此将{A,F,G}划分为{A},{F,G}
考察状态集合{A},{B,C},{D,E},{F,G}，均不能再分。
重新命名，以A,B,D,F分别取代上述状态集合，则得其最小化DFA为：
a
b
-A
B
B
B
B
D
+D
B
F
F
B
F
8．A=1S|1=1（S|ε）
B=0S|0=0（S|ε）
S=0A|1B=01（S|ε）|10（S|ε）=（01|10）（S|ε）=（01|10）S|（01|10）=（01|10）*（01|10）=（01|10）+
9．
对其进行最小化操作：
该DFA无多余状态，对其进行初始划分，得非终态组{1,2,3,4,5}，终态组{6,7}
对非终态组{1,2,3,4,5}进行审查，输入符号b后，状态3,4分别转换为状态6,7，状态1,2转换为状态2，状态5到达Ф，到达了不等价的状态，因此将{1,2,3,4,5}划分为{1,2},{3,4},{5}
考察状态集合{1,2},{3,4},{5},{6,7}，均不能再分。
重新命名，以1,3,5,6分别取代上述状态集合，则得其最小化的DFA为：
a
b
c
d
-1
3
1
3
6
3
5
5
3
+6
6
对应的正规式为：
r=b*a（c|da）*bb*
升级会员 