编译原理(习题课)(二)

1编译原理朱雪峰博士计算机科学与技术系Tel:89733787(O)Email:[e-mail]2第六题（P36第11题）解：分析L2，要求b和c的个数一样多，因此可以使用一个非终结符去生成bncn串，而用另外一个非终结符去生成ai，因此，可以模拟L1使用一个非终结符去生成bncn，而用另外一个非终结符去生成ai。L2的文法：S→ABA→aA|εB→bBc|bc3第六题（P36第11题）解：分析L3，可以将anbnambm分成两段考虑，即anbn和ambm，然后使用两个非终结符分别去产生它们。L3的文法：S→ABA→aAb|εB→aBb|ε4第六题（P36第11题）解：L4不能采用分段处理的方式，它要求中间的0和1的个数相同，而且一前一后的1和0的个数相同。对于这种文法我们可以采用从里向外扩展的方式进行，即先用一个非终结符生成处于中间的m个0和m个1，然后，使用另外一个非终结符在该串的基础上扩充前后的n个1和n个0。L4:A→0A1|εS→1S0|A5第七题（P64第7题）7.构造下列正规式相应的DFA①1(0|1)*101②1(1010*|1(010)*1)*0③0*10*10*10*④(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*6第七题（P64第7题①）7第七题（P64第7题①）{2,4,3}3{2,5,3}4{2,3,4,Y}5{2,3,4,Y}5{2,3}2{2,3,5}4{2,3,4}3{2,5,3}4{2,3,4}3{2,3,4}3{2,3}2{2,3}2{2,3,4}3{2,3}2{1,2,3}1{1,2,3}1ø{X}010状态8第七题（P64第7题①）{2,4,3}3{2,5,3}4{2,3,4,Y}5{2,3,4,Y}5{2,3}2{2,3,5}4{2,3,4}3{2,5,3}4{2,3,4}3{2,3,4}3{2,3}2{2,3}2{2,3,4}3{2,3}2{1,2,3}1{1,2,3}1ø{X}010状态9第七题（P64第7题①）á初始划分：{{0,1,2,3,4},{5}}，{0,1,2,3,4}0={2,4,_},{0,1,2,3,4}1={1,3,5}。由于0不能接受字符0，需要把状态0划分出来；另外，只有状态4读入字符1后进入状态5，因此将状态4划分出来，划分的结果为4个集合：{{0},{1,2,3},{4},{5}}。á对于集合{1,2,3}，由于{1,2,3}0={2,4}，因此需要对{1,2,3}进一步划分，划分结果为5个集合：{{0},{1,2},{3},{4},{5}}。检查集合{1,2}，由于{1,2}0={2},{1,2}1={3}，不需要进一步的划分。所以昀终划分结果为5个集合：{{0},{1,2},{3},{4},{5}}10第七题（P64第7题①）11第七题（P64第7题②）1(1010*|1(010)*1)*012第七题（P64第7题②）{3,6,2}{4,7,9}{3,6,2}{3,6,8}{5,2,9}{5,2,7,9}{3,6,2}{5,2,7,9}{5,2,6,9}{3,6}{5,2,6,9}{5,8,2}{5,8,2}ø{4,7}{2}{4,7}{3,6}øø{9}{3,6}{9}{2}{2}ø{1}10状态ø{6}{8}{8}ø{7}{2}{7}{6}{5,8,2}{7}{4,7,6}{2}{4,7,6}{3,6,8}{3,6}{5,2,9}{5,2,9}{5,8,2}ø{4,7,9}10状态13第七题（P64第7题②）14第七题（P64第7题③）0*10*10*10*15第七题（P64第7题④）(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*16第七题（P64第7题④）{11,4}{6}{14,7}{6}{11,4}{5,13}{14,7}{13,5}{11,4}{6}{11,4}{9,12}{11,4}{6}{8,10}{9,12}{8,10}{6}{1,4}{6}{3,7}{6}{1,4}{2,5}{3,7}{2,5}{1,4}{1,4}ø{3}ø{1,4}{2}{3}{2}{1}10状态17第七题（P64第7题④）18第八题（P64第8题）8.给出下面正规表达式：①以01结尾的二进制数串；②能被5整除的十进制整数；③包含奇数个1或奇数个0的二进制数串；④英文字母组成的所有符号串，要求符号串中的字母依照字典序排列；⑤没有重复出现的数字的数字符号串的全体；⑥昀多有一个重复出现的数字的数字符号串的全体；⑦不包含子串abb的由a和b组成的符号串的全体。19第八题（P64第8题）解：（1）本题要求的是二进制串，即由0和1构成的串，并且必须以01结尾，所以本题可以分两部分去完成，一部分实现由0和1构成的任意串，一部分即01，然后将它们连接到一起就可以了，因此答案为(1|0)*01。20第八题（P64第8题）（2）本题要求的是十进制整数，也就是由0~9这10个数字组成的字符串，并且不能以0开头（整数0除外），要求能够被5整除，则该串必须以0或5结尾。可以分成两种情况：一种情况是该整数只有1位，则该整数有0和5两种可能；另一种情况是该整数有多位，则该整数可以分为3部分来考虑。一是第一位必须不为0，二是昀后一位必须为0或5，三是中间部分可有可无，并且可以由0~9之间任意数字构成，所以本题的正规表达式为：(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*(0|5)|(0|5)21第八题（P64第8题）（3）由于0和1在二进制串中的奇数出现具有对偶性，因此我们只考虑一种情况，另一种情况可以类似求得，考虑包含奇数个0的字符串：由于只关心0的个数的奇偶性，我们可以把二进制串分成多段来考虑，第一段为二进制串的开始到第一个0为止，这一段包含1个0，并且0的前面有0个或多个1；对于剩下的二进制串按照每段包含两个0的方式去划分，即以0开始，以0结尾，中间可以有0个或多个1.如果一个二进制串被这样划分完后，剩下的部分如果全部是全1串（这些全1串在前面划分的串之间或昀后），则该二进制串就具有奇数个0，所以该二进制串可以这样描述：以第一段（1*0）开始，后面由全1串（1*）以及包含两个0的串（01*0）组成，所以包含奇数个0的正规式为：1*0(1|01*0)*。本题答案为1*0(1|01*0)*|0*1(0|10*1)*22第八题（P64第8题）（4）(a|A)*(b|B)*…(z|Z)*23第八题（P64第8题）（5）令ri=i|ε（i=0,1,2,…,9）R0|R1|R2|…|R9记为令P(0,1,2,…,9）表示i=0,1,2,…,9的全排列∑910iiirrrL)9,,1,0(,,910LLPiii∈其中∑∈)9,,2,1,0(LiiR24第八题（P64第8题）（6）∑910iiirrrL)9,,1,0(,,910LLPiii∈其中∑∈)9,,2,1,0(Lii25第八题（P64第8题）(7)直接写出满足条件的正规表达式。考虑满足条件的字符串：在串的开始部分可以有0个或多个b，但是一旦a出现以后，要么后面还是a，要么后面只能跟一个b然后还得跟a，由此我们得到满足条件的正规式为：b*(a|ab)*26第九题（P64第12题）12.将图3.18的(a)和(b)分别确定化和昀小化。27第九题（P64第12题）解：图(a)中为一个NFA，所以需要先将其确定化。得到DFA，然后再将其昀小化。第一步：确定化，得到DFA。确定化的结果见左表所列。给状态编号，得到右表所列的状态转换矩阵。ø{0}{1}{1}{0,1}{0,1}{1}{0,1}{0}ba状态02211210ba状态28第九题（P64第12题）解：根据状态转换矩阵得到如图所示的DFA29第九题（P64第12题）解：第二步：昀小化。首先将状态划分成两个集合{0,1}和{2}，由于{0,1}a={1}、{0,1}b={2}，所以{0,1}和{2}就是昀后的分划，因此得到如下图所示的昀小化的DFA。30第九题（P64第12题）解：图(b)中所示为一个DFA，不需要确定化，因此只需昀小化即可。首先将状态划分为两个集合{{0,1},{2,3,4,5}}，由于{0,1}a={1}、{0,1}b={2,4}和{2,3,4,5}a={1,3,0,5}、{2,3,4,5}b={2,3,4,5}，所以可以进一步划分为{{0,1},{2,4},{3,5}}。然后有{0,1}a={1}、{0,1}b={2,4}、{2,4}a={1,0}、{2,4}b={3,5}、{3,5}a={3,5}、{3,5}b={2,4}，因此，昀后划分结果就是{{0,1},{2,4},{3,5}}31第九题（P64第12题）解：昀小化后的DFA如下图所示：32第十题（P65第14题）14.构造一个DFA，它接受∑={0,1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。33第十题（P65第14题）第一步：写出正规表达式。根据题意，该DFA接受的字符串由0和1组成，并且每个1的后面都有0直接跟在右边，因此，可以将该字符串理解为由0和10构成的串，则相应的正规表达式就是(0|10)*第二步：构造NFA。首先得出图1。然后按照P50的替换规则对图1进行分解后得到如图2所示的NFA。34第十题（P65第14题）XY(0|10)*1NFA35第十题（P65第14题）第三步：确定化，得到DFA。确定化的结果见左表所列，给状态编号，得到如右表所列的状态转换矩阵。ø{1,Y}{2}{2}{1,Y}{1,Y}{2}{1,Y}{X,1,Y}10状态1221121010状态36第十题（P65第14题）根据状态转换矩阵得到的DFA如下图所示：37第十题（P65第14题）第四步，使用P57的方法对该DFA进行昀小化。昀小化分析过程如下：初始分划：{0,1}、{2}由于{0,1}0={1}，{0,1}1={2}昀小化后的DFA如下图所示，该DFA即为所求。0DFA101038第十一题（P81第1题）1.考虑下面文法G1：S→a|∧|(T)T→T,S|S①消去G1的左递归。然后，对每个非终结符，写出不带回溯的递归子程序。②经改写后的文法是否是LL(1)的？给出它的预测分析表。39第十一题（P81第1题）解：（1）按照T、S的顺序消除左递归，得到文法：G’(S)：S→a|∧|(T)T→ST’T’→,ST’|ε对每个非终结符，写出不带回溯的递归子程序（略，不讲）40第十一题（P81第1题）（2）首先计算每个非终结符的FIRST集合和FOLLOW集合（P78和P79页计算FIRST和FOLLOW的算法）FIRST(S)={a,∧,(}FIRST(T)={a,∧,(}FIRST(T’)={,,,ε}FOLLOW(S)={#,,,,)}FOLLOW(T)={)}FOLLOW(T’)={)}#∊FOLLOW(S))∊FOLLOW(T)FIRST(T’)/{ε}⊆FOLLOW(S)FOLLOW(T)⊆FOLLOW(T’)FOLLOW(T)⊆FOLLOW(S)41第十一题（P81第1题）（2）构造预测分析表如下：P79页构造分析表M的算法T→,ST’T→εT’T→ST’T→ST’T→ST’TS→(T)S→∧S→aS#,)(∧a从表中可以看出没有多重入口，所以改造后的文法是LL(1)文法42第十二题（P81第2题）2.对下面的文法G：E→TE’E’→+E|εT→FT’T’→T|εF→PF’F’→*F’|εP→(E)|a|b|∧①计算这个文法的每个非终结符的FIRST和FOLLOW。②证明这个文法是LL(1)的。③构造它的预测分析表。④构造它的递归下降分析程序。43第十二题（P81第2题）（1）计算每个非终结符的FIRST集合和FOLLOW集合：FIRST(E)={(,,a,b,∧}FIRST(E’)={+,ε}FIRST(T)={(,a,b,∧}FIRST(T’)={(,a,