编译原理及实践教程(黄贤英-王柯柯-编著)-习题答案

第2章参考答案：1，2，3：解答：略！4.解答：A：①B：③C：①D：②5.解答：用E表示表达式，T表示项，F表示因子，上述文法可以写为：E→T|E+TT→F|T*FF→(E)|i最左推导：E=E+T=E+T+T=T+T+T=F+T+T=i+T+T=i+F+T=i+i+T=i+i+F=i+i+iE=E+T=T+T=F+T=i+T=i+T*F=i+F*F=i+i*F=i+i*i最右推导：E=E+T=E+F=E+i=E+T+i=E+F+i=E+i+i=T+i+i=F+i+i=i+i+iE=E+T=E+T*F=E+T*i=E+F*i=E+i*i=T+i*i=F+i*i=i+i*ii+i+i和i+i*i的语法树如下图所示。i+i+i、i+i*i的语法树6.解答：(1)终结符号为：{or,and,not,(,),true,false}非终结符号为：{bexpr,bterm,bfactor}开始符号为：bexpr(2)句子not(trueorfalse)的语法树为：7.解答：(1)把anbnci分成anbn和ci两部分，分别由两个非终结符号生成，因此，生成此文法的产生式为：S→ABA→aAb|abB→cB|(2)令S为开始符号，产生的w中a的个数恰好比b多一个，令E为一个非终结符号，产生含相同个数的a和b的所有串，则产生式如下：S→aE|Ea|bSS|SbS|SSbE→aEbE|bEaE|(3)设文法开始符号为S，产生的w中满足|a|≤|b|≤2|a|。因此，可想到S有如下的产生式（其中B产生1到2个b）：S→aSBS|BSaSB→b|bb(4)解法一：S→〈奇数头〉〈整数〉〈奇数尾〉|〈奇数头〉〈奇数尾〉|〈奇数尾〉〈奇数尾〉→1|3|5|7|9〈奇数头〉→2|4|6|8|〈奇数尾〉〈整数〉→〈整数〉〈数字〉|〈数字〉〈数字〉→0|〈奇数头〉解法二：文法G=({S,A,B,C,D},{0,1,2,3,4,5,6,7,8,9},P,S)S→AB|BA→AC|DB→1|3|5|7|9D→2|4|6|8|BC→0|D(5)文法G=({N,S,N,M,D},{0,1,2,3,4,5,6,7,8,9},S,P)S→N0|N5N→MD|M→1|2|3|4|5|6|7|8|9D→D0|DM|(6)G[S]：S→aSa|bSb|cSc|a|b|c|8.解答：(1)句子abab有如下两个不同的最左推导：S=aSbS=abS=abaSbS=ababS=ababS=aSbS=abSaSbS=abaSbS=ababS=abab所以此文法是二义性的。(2)句子abab的两个相应的最右推导：S=aSbS=aSbaSbS=aSbaSb=aSbab=ababS=aSbS=aSb=abSaSb=abSab=abab(3)句子abab的两棵分析树：(a)(b)(4)此文法产生的语言是：在{a，b}上由相同个数的a和b组成的字符串。9，10：解答：略！第3章习题解答：1.解答：(1)√(2)√(3)×(4)×(5)√(6)√2.[分析]有限自动机分为确定有限自动机和非确定有限自动机。确定有限自动机的确定性表现在映射：Q×VT--q是单值函数，也就是说，对任何状态q∈Q和输入字符串a∈VT，(q,a)唯一确定下一个状态。显然，本题给出的是一个确定的有限自动机，它的状态转换图是C中的②。它所接受的语言可以用正则表达式表示为00(0|1)*，表示的含义为由两个0开始的后跟任意个（包含0个）0或1组成的符号串的集合。2.解答：A:④B:③C:②D:②E:④3，4．解答：略！5．解答：6．解答：(1)(0|1)*01(2)((1|2|…|9)(0|1|2|…|9)*|)(0|5)(3)(0|1)*(011)(0|1)*(4)1*|1*0(0|10)*(1|)(5)a*b*c*…z*(6)(0|10*1)*1(7)(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*(8)[分析]设S是符合要求的串，|S|=2k+1(k≥0）。则S→S10|S21，|S1|=2k(k0），|S2|=2k(k≥0）。且S1是{0,1}上的串，含有奇数个0和奇数个1。S2是{0,1}上的串，含有偶数个0和偶数个1。考虑有一个自动机M1接受S1，那么自动机M1如下：和L(M1)等价的正规式，即S1为：((00|11)|(01|10)(00|11)*(01|10))*(01|10)(00|11)*类似的考虑有一个自动机M2接受S2，那么自动机M2如下：和L(M2)等价的正规式，即S2为：((00|11)|(01|10)(00|11)*(01|10))*因此，S为：((00|11)|(01|10)(00|11)*(01|10))*(01|10)(00|11)*0|((00|11)|(01|10)(00|11)*(01|10))*17．解答：(1)以0开头并且以0结尾的，由0和1组成的符号串。(2){|∈{0,1}*}(3)由0和1组成的符号串，且从右边开始数第3位为0。(4)含3个1的由0和1组成的符号串。{|∈{0,1}+，且中含有3个1}(5)包含偶数个0和1的二进制串，即{|∈{0,1}*，且中有偶数个0和1}8.解答：01Q0*Q1Q2Q3Q2Q3Q0Q1Q1Q0Q3Q29.解答：(1)DFAM=({0，1}，{q0，q1，q2}，q0，{q2}，)其中定义如下:(q0，0)=q1(q0，1)=q0(q1，0)=q2(q1，1)=q0(q2，0)=q2(q2，1)=q0状态转换图为：(2)正规式:1*01*01*01*DFAM=({0，1}，{q0，q1，q2，q3}，q0，{q3}，)，其中定义如下：(q0，0)=q1(q0，1)=q0(q1，0)=q2(q1，1)=q1(q2，0)=q3(q2，1)=q2(q3，1)=q3状态转换图为：10.解答：(1)DFAM=({0，1}，{q0，q1，q2，q3}，q0，{q3}，)，其中定义如下：(q0，0)=q1(q0，1)=q2(q1，0)=q1(q1，1)=q3(q2，0)=q3(q2，1)=q1状态转换图为：(2)DFAM=({0，1}，{q0}，q0，{q0}，)，其中定义如下:(q0，0)=q0(q0，1)=q0状态转换图为：11解答：(1)(a|b)*a(a|b)①求出NFAM:②确定化，得到DFAM:③化简:在第②步中求出的DFAM中没有等价状态，因此它就是最小化的DFAM。(2)(a)b)*a(a|b)(a|b)①求NFAM：②确定化，得到DFAM：③化简，在第②步中求出的DFAM中没有等价状态，因此它已经是最小化的DFAM了。12.解答：对应的NFA为：增加状态X、Y，再确定化：IIaIb{x,5}{A,T,Y}{}{A,T,Y}{A,T,Y}{B}{B}{}{B,T,Y}{B,T,Y}{}{T,Y}{T,Y}{}{}得到的DFA为：最小化：该自动机已经是最小化的DFA了。13．解答：其中a代表1元硬币，b代表5角硬币14．解答：正规式为：(0|1)*(00|01)化简：(0|1)*0(0|1)不确定的有穷自动机为：确定化，并最小化得到：正规文法为：S→1S|0AA→0B|0|1C|1B→0B|0|1C|1C→1S|0A15.解答：①正规式：(dd*:|)dd*(.dd*|)，d代表a~z的字母②NFA为：③DFA为：16.解答：词法分析器对源程序采取非常局部的观点，因此象C语言的语句fi(a==f(x))…中，词法分析器把fi当作一个普通的标识符交给编译的后续阶段，而不会把它看成是关键字if的拼写错。PASCAL语言要求作为实型常量的小数点后面必须有数字，如果程序中出现小数点后面没有数字情况，它由词法分析器报错。17.解答：此时编译器认为/*thenpartreturnqelse/*elsepart*/是程序的注释，因此它不可能再发现else前面的语法错误。分析这是注释用配对括号表示时的一个问题。注释是在词法分析时忽略的，而词法分析器对程序采取非常局部的观点。当进入第一个注释后，词法分析器忽略输入符号，一直到出现注释的右括号为止，由于第一个注释缺少右括号，所以词法分析器在读到第二个注释的右括号时，才认为第一个注释处理结束。为克服这个问题，后来的语言一般都不用配对括号来表示注释。例如Ada语言的注释始于双连字符（--），随行的结束而终止。如果用Ada语言的注释格式，那么上面函数应写成longgcd(p,q)longp,q;{if(p%q==0)--thenpartreturnqelse--elsepartreturngcd(q,p%q);}18.解答：略！第4章习题解答：1，2，3，4解答略！5.解答：(1)×(2)√(3)×(4)√(5)√(6)√(7)×(8)×6.解答：(1)A：④B：③C：③D：④E：②(2)A：④B：④C：③D：③E：②7.解答：(1)消除给定文法中的左递归，并提取公因子：bexpr→bterm{orbterm}bterm→bfactor{andbfactor}bfactor→notbfactor|(bexpr)|true|false(2)用类C语言写出其递归分析程序:voidbexpr();{bterm();WHILE(lookahead=='or'){match('or');bterm();}}voidbterm();{bfactor();WHILE(lookahead=='and'){match('and');bfactor();}}voidbfactor();{if(llokahead=='not')then{match('not');bfactor();}elseif(lookahead=='(')then{match(‘(');bexpr();match(')');}elseif(lookahead=='true')thenmatch('true)elseif(lookahead=='false')thenmatch('false');elseerror;}8.解答：消除所给文法的左递归，得G'：S→(L)|aL→SL'L'→,SL'|实现预测分析器的不含递归调用的一种有效方法是使用一张分析表和一个栈进行联合控制，下面构造预测分析表：根据文法G'有：First(S)={(,a)Follow(S)={),,,#}First(L)={(,a)Follow(L)={)}First(L')={,}Follow(L')={)}按以上结果，构造预测分析表M如下：文法G'是LL(1)的，因为它的LL(1)分析表不含多重定义入口。预测分析器对输入符号串(a,(a,a))做出的分析动作如下：步骤栈剩余输入串输出1#S(a,(a,a))##2#)L(a,(a,a))#S→(L)3#)La,(a,a))#4#)L'Sa,(a,a))#L→SL'5#)L'aa,(a,a))#S→a6#)L',(a,a))#7#)L'S,,(a,a))#L'→,SL'8#)L'S(a,a))#9#)L')L((a,a))#S→(L)10#)L')La,a))#11#)L')L'Sa,a))#L→SL'12#)L')L'aa,a))#S→a13#)L')L',a))#14#)L')L'S,,a))#L'→,SL'15#)L')L'Sa))#16#)L')L'aa))#S→a17#)L')L'))#18#)L')))#L'→19#)L')#20#))#L'→21##9.解答：各非终结符的First集：First(S)={First(A)\{}}∪{First(B)\{}}∪{}∪{b}={a,b,}First(A)={b}∪{}={b,}First(B)＝{}∪{a