《编译技术原理及方法 第三章习题解答.docx》由会员分享，可在线阅读，更多相关《编译技术原理及方法 第三章习题解答.docx（10页珍藏版）》请在装配图网上搜索。
1、第三章一一习题解答1. 什么叫超前搜索？扫描缓冲区的作用是什么？词法分析程序在识别单词的时候，为进一步判明情况，确定下一步要做什么, 一般采用超前读字符的方法，称超前搜索，扫描缓冲区的作用是为了更好识别单 词符号，采用将缓冲区一分为二的机制有效避免了某个单词符号串被单一的扫描 缓冲区的边界所打断。2. 画出下列文法的状态图，并使用该状态图检查下列句子是否该文法的合法句 子：f, eeff, eefe由状态图可知只有eefe是该文法的合法句子。3. 设右线性文法G=(S,A,B, a,b,S,P),其中P组成如下:S：=bA A：=bB A：=aA A：=bB：=a画出该文法的状态转换图。4.
2、构造下述文法GZ的自动机，该自动机是确定的吗？它相应的语言是什么？Z：=A0A：=AO|Z1|O解1：将左线性文法转换为右线性文法，由于在规则中出现了识别符号出现 在规则右部的情形，因此不能直接使用书上的左右线性文法对应规则，可以引入 非终结符号B,将左线性文法变为Z：=A()A：=A()|B1|OB：=A(),具体为：另一种答案是 S= c(ac | c)*( ac*aa*c | ba*c | aa | a) | a#二；= 如 T1 =将所得的新左线性文法转换成右线性文法：此时利用书上规则，其对应的右线性文法为：A：=0A|0B|0Z：=0AB： =1A我们从右线性文法规则A：=0A|0B
3、可以看出在状态A读入0到达的状态为 A,B,因此是非确定有穷自动机。解2：先画出该文法状态转换图:NFA=(S, A, Z), (0, 1), M, 其中 M： M(S,0)=AM(A, ()=A, ZM(Z, 0)=0S, (ZD M(S, 1)=0 M(A, 1)=0 M(Z, 1)=A显然该文法的自动机是非确定的；它相应的语言为：0，1上所有满足以 00开头以0结尾且每个1必有0直接跟在其后的字符串的集合；那么如何构造 其相应的有穷自动机呢？先构造其转换系统：根据其转换系统可得状态转换集、状态子集转换矩阵如下表所示:IIoIiS01S,SA01O(A)A, Z, ZO12OA, Z,ZA
4、,Z, ZA)221则其相应的DFA为:5. 构造一个DFA,它接受0, 1上所有满足下述条件的字符串，其条件是：字 符串中每个1都有。直接跟在右边，然后，再构造该语言的正规文法。解L先画出其状态转换图为形式化 DFA=(S, A, Z, 其中 M： M(S, ()=Z0, 1, M, S, (Z)M(S, 1)=AM(A, 0)=ZM(Z, 0)=ZM(乙 1)=A该语言的正规文法GZ为: 右线性文法：S：二0|lA|0Z左线性文法:A：=0|0ZZ：=0|lA|0ZA： = 1|Z1Z：=0|A0|Z0解2：可以先写出该文法的正规表达式为(0|1()*,根据该正规式构造转换系统 对于该转换
5、系统可以采用子集法将其转变为DFA,再根据DFA写出其正规文法; 但是注意观察后，发现开始状态S通过到达A状态，可以直接删去S状态， 由A状态作为新的开始状态，同理，只有A状态通过才能到达终止状态Z, 因此可以删去Z状态，由A状态作为终止状态。这样，A状态就既为开始状态 又为终止状态。可画出化简后的转换图。可写出右线性文法为：S：=0|0S|lBB：=0|0S6. 设(NFA)M = (A,B, a,b,M, A,B),其中 M 定义如下： M(A,a)=A,B M(A,b)=B M(B,a) = 0M(B,b)=A,B请构造相应确定有穷自动机(DFA)M解：构造一个如下的自动机(DFA)M
6、(DFA)M，=K, a,b,M，,S,Z K的元素是A B A,B由于 M(A, a)=(A, B),故有 M，(A, a)=A, B同样 MXA, b)=BM(B,a)=0M，(B, b)=A, B由于 M(A, B,a)= M(A, a) U M(B, a)= (A,BU0= (A,B|故 M，(A, B, a)= A, B由于 M(A, B, b)= M(A, b) U M(B, b)=BU (A,B = (A,B)故 M，(A, B, b)= A, BS=A,终态集Z=A,B, B重新定义：令O=AJ 1=B2=A,B,则DFA如下所示：7. 设有穷自动机M=(S,A,E, a,b,
7、c,M,S, E),其中M定义为 M(S, c)=A M(A, b)=A M(A, a)=E,请构造一个左线性文法。解：先求右线性文法ScA AbA Aa | aE其左线性文法G= ( Vn, Vt,P, S)Vn= A,S Vt= a, b,cP：A-c AAb S-Aa (EaA实际上是多余的规则，应该去掉)8. 已知正规文法G=(S,B,C, a,b,c,ES),其中P内包含如下产生式:S：=aS|aBB：=bB|bCC：=cC|c请构造一个等价的有穷自动机。解：M=(S, B, C, T, (a, b, c, M, S, T)M(S,a)=SM (S, a)=BM (S, b)=0M
8、(S, c)=0M (B, a)=0M (B, b)=BM (B, b)=C M (B, c)=0M (C, a)=0 M (C, b)=0 M (C, c)=T M (C, c)=C9. 构造下列正规表达式相应的DFA,并进行最小化的化简。(1) b(a|b)”bab (a|bb”a)*(3) (0| 1 )* | (11 )*(1)解:b(a|b)*bab对应的转换系统为下表由子集法将转换系统转换为DFA：bbILI、KabS1,2,3S11,2,32,32,3,41232,32,32,3,42232,3,4(2,3,52,3,43432,3,52,32,3,4,Z42Z2,3,4,Z2,
9、3,52,3,4Z43DFA的状态转换图:化简后的DFA状态转换图如下:(2)解:(a|bb*a)对应的转换系统为由上述转换系统可得转换集如下表所示:ILh、Ka1)S,1,Z1,Z2,3,40121,Z1,Z2,3,41122,3,41,Z3,42133,41,Z3,4313由状态子集表可知，状态0和1是等价的，而2和3是等价的。因此，合并等价 状态之后只剩下2个状态，也即是最少状态的DFAo(3)解:(0|1)*|(11)*对应的转换系统为:由上述转换系统可得转换集如下表所示:IIoIiK01S,1,3,Z1,31,2,3,ZS121,31,31,2,3,Z1121,2,3,Z1,31,2
10、,3,Z212DFA状态转换图:化简后的DFA状态转换图如下:10. 将下图非确定有穷自动机NFA确定化和最少化：(1)假设1为开始状态；(2) 假设0既是开始状态又是终止状态。(1)解：设(DFA)M= K,Vt,M,S,Z,其中,K=0, 0, 1, 1, VT=(a,b), M：M(l,a) =0M(l,b) =0)M(0, l,a)=0, 1M(0, 1, b) =1M (), a) =(), 1 M (), b)=lS=l, Z=0, 0J)令0, 1=2,则其相应的状态转换图为：现在对该DFA进行化简，先把状态分为两组： 终态组0,2和非终态组(1),易于发现0,2 不可以继续划分
11、，因此化简后的状态转换图如下:(2)解：此时结果和(1)相同。11. 己知 ei=(a|b) e2=(a*b*)*,试证明 ei=e2 。 证明：L(ei)=L(a|b)*)= (L (a|b)*= (L (a)UL(b)*=(a, b*；L(e2)= L(a*b*)*)= (L (a*b*)*=(L(a*)L(b*)*=a * b * *= a, b*；因此ei= e?(得证)根据F血正规文法构造等价的正规表达式S：=cC|aA： ：=cA|aBB：二aB|cC：=aS|aA|bB|cC|a解：由式可得B= aB + c B=a*c由式可得 A= cA + aB A= c*aa*c由式可得S= cC + a由式可得 C= aS + aA + bB + cC + a 一 C= c*( aS + aA + bB + a) C= c*( aS + ac*aa*c + ba*c + a) S= cc*( aS + ac*aa*c + ba*c + a) + a = cc*aS+ cc*( ac*aa*c + ba*c + a) + a = (cc*a)*( cc*( ac*aa*c + ba*c + a) + a)= (cc*a)*( cc*( ac*aa*c | ba*c | a) | a)
编译技术原理及方法 第三章习题解答.docx
