1、编译原理三四章答案清华版第三章 习题解答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*i11根据文法G给定的规则，从文法的开始符E出发可推导出E+T*F，推导过程如下：E = E+T =
2、E+T*F ，所以E+T*F是该文法的一个句型。由右图的语法树也可以看出，E+T*F是该文法的一个句型。这个句型的所有短语为：E+T*F, T*F 直接短语为：T*F 句柄为：T*F13(1)最左推导：S=ABS=a1BS= a1SBBS= a1BBS= a1b1BS= a1b1b2S= a1b1b2Aa3= a1b1b2a2a3最右推导：S=ABS= ABAa3= ABa2a3= ASBBa2a3= ASBb2a2a3= ASb1b2a2a3= Ab1b2a2a3= a1b1b2a2a3(2)该文法产生式集合P可能有如下规则：SABS|Aa| Aa BSBB|b(3)该句子的所有短语为：a1
3、b1b2a2a3, a1, b1b2, , b1, b2, a2a3, a2 直接短语为：a1, , b1, b2, a2 句柄为：a1第四章 习题答案1（1）对应NFA如图：对其进行确定化操作：01-SAAAA,BA,BA,CA,BA,CAA,B,Z+A,B,ZA,CA,BT0 = -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，标
4、记为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状态转换图及状态转换矩阵分别为：01-SAAABBCBCAD+DCB（3）对应NFA如图：对其进
5、行确定化操作：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(mov
6、e(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状态转换图及状态转换矩阵分别为：ab-SA,B,DA,B,DA,B,C,DA,B,D,ZA,B,C,DA,B,C,DA,B,C,D,Z+A,B,D,ZA,B,C,DA,B,D,Z+A,B,C,D,ZA
7、,B,C,DA,B,C,D,Zab-SAABCBBD+CBC+DBD2根据题意，可以得其NFA状态转换图如下图所示：对其进行确定化操作：01-xzx+zx, zy+x, zx, zx, yyx, yx, yx, y, zx+x, y, zx, y, zx, yT0 = -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
8、= 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为终态，对应的转换矩阵如
9、右上表格所示，令A,B,C,D,E,F分别表示这六种状态，则其对应的DFA状态转换图及状态转换矩阵分别为：01-ABA+BCD+CCEDEEFA+FFE3状态转换图如图所示：对其进行确定化操作：01-SV,QQ,UV,QV,ZQ,UQ,UVQ,U,Z+V,ZZZVZ+Q,U,ZV,ZQ,U,Z+ZZZT0 = -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= T
10、2计算-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)
11、= Z= T3得到的DFA存在七种状态：T0，T1，T2，T3，T4，T5，T501-ABCBDCCEF+DGGEG+FDF+GGG其中：T0为初态，T3,T5,T6为终态，对应的转换矩阵如右上表格所示，令A,B,C,D,E,F,G分别表示这七种状态，则其对应的DFA状态转换图及状态转换矩阵分别为：4（a）对其进行确定化操作：T0 = -closure(0) = 0ab-+00,11+0,10,1110计算-closure(move(0,a) = 0,1，标记为T1计算-closure(move(0,b) = 1，标记为T2计算-closure(move(0,1,a) = 0,1=T1计算-c
12、losure(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状态转换图及状态转换矩阵如下：ab-+ABC+BBCCA对其进行最小化操作：该DFA无多余状态，进行初始划分，得终态组A,B，非终态组C对终态组A,B进行审查，输入符号a后，状态A,B均转换成状态B；输入符号b后，状态A,B均转换成状态C，由此可知，状态A,B等价，不能再分。令A代表A,B，则
13、得其最小化的DFA为：ab-+AACCA（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
14、，到达了不等价的状态，因此将2,3划分为2,3对状态集合1,5进行审查，输入符号a后均到达集合1,5中的状态，输入符号b后均到达状态4，因此不能再划分。最终得到划分：0,1,5,2,3,4令1代表状态集合1,5，则得其最小化的DFA为：ab-+0121142133324017对应的NFA状态转换图为：对其进行确定化操作：T0 = -closure(S) = Sab-SAQAAB,ZQQD,Z+B,ZQD+D,ZABDABBQD计算-closure(move(S,a) = A，标记为T1计算-closure(move(S,b) = Q，标记为T2计算-closure(move(A,a) = A=
15、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计
16、算-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状态转换图及状态转换矩阵如下：ab-ABCBBDCCE+DCF+EBGFBGGCF对其进行最小化操作：该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,
17、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为：ab-ABBBBD+DBFFBF8A=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为：abcd-131363553+66对应的正规式为：r=b*a(c|da)*bb*
