清华大学编译原理第二版课后习答案.docx

。编译原理课后习题答案第一章 第4题 对下列错误信息，请指出可能是编译的哪个阶段（词法分析、语法分析、语义分析、 代码生成）报告的。 （1）else没有匹配的if （2）数组下标越界 （3）使用的函数没有定义 （4）在数中出现非数字字符 答案： （1）语法分析 （2）语义分析 （3）语法分析 （4）词法分析 编译原理课后习题答案第三章 第1题 文法G(A,B,S,a,b,c,P,S)其中P为： SAc|aB Aab Bbc 写出L(GS)的全部元素。 答案： L(GS)=abc 第2题 文法GN为： ND|ND D0|1|2|3|4|5|6|7|8|9 GN的语言是什么？ 答案: GN的语言是V+。V=0,1,2,3,4,5,6,7,8,9 N=ND=NDD.=NDDDD.D=D.D 或者：允许0开头的非负整数？ 第题 为只包含数字、加号和减号的表达式，例如9-25，3-1，等构造一个文法。 答案： GS: S-S+D|S-D|D D-0|1|2|3|4|5|6|7|8|9 第4题 已知文法GZ： ZaZb|ab 写出L(GZ)的全部元素。 答案： Z=aZb=aaZbb=aaa.Z.bbb=aaa.ab.bbb L(GZ)=anbn|n=1 第5题 写一文法，使其语言是偶正整数的集合。要求： (1)允许0打头； (2)不允许0打头。 答案： (1)允许0开头的偶正整数集合的文法 ENT|D TNT|D ND|1|3|5|7|9 D0|2|4|6|8 (2)不允许0开头的偶正整数集合的文法 ENT|D TFT|G ND|1|3|5|7|9 D2|4|6|8 FN|0 GD|0 第6题 已知文法G： := :=* :=（）i 试给出下述表达式的推导及语法树。 （）i+(i+i) （）i+i*i 答案： + + i i i （) (5) = = =（） =（） =（） =（i） =（i） =（i） =（ii） =（ii） =（ii） =i（ii） + * i i i (6) = =* =*i =*i =i*i =i*i =i*i =ii*i 第7题 证明下述文法G表达式是二义的。 表达式=a|(表达式)|表达式运算符表达式 运算符=+|-|*|/ 答案： 可为句子a+a*a构造两个不同的最右推导: 最右推导1表达式表达式运算符表达式 表达式运算符a 表达式*a 表达式运算符表达式*a 表达式运算符a*a 表达式+a*a a+a*a 最右推导2表达式表达式运算符表达式 表达式运算符表达式运算符表达式 表达式运算符表达式运算符a 表达式运算符表达式*a 表达式运算符a*a 表达式+a*a a+a*a 第8题 文法GS为： SAc|aB Aab Bbc 该文法是否为二义的？为什么？ 答案： 对于串abc (1)S=Ac=abc(2)S=aB=abc 即存在两不同的最右推导。所以，该文法是二义的。 或者： 对输入字符串abc，能构造两棵不同的语法树，所以它是二义的。 S aB bc S Ac ab 第9题 考虑下面上下文无关文法： SSS*|SS+|a (1)表明通过此文法如何生成串aa+a*，并为该串构造语法树。 S SS* SS+a aa (2)GS的语言是什么？ 答案： (1)此文法生成串aa+a*的最右推导如下 S=SS*=SS*=Sa*=SS+a*=Sa+a*=aa+a* (2)该文法生成的语言是：*和+的后缀表达式，即逆波兰式。 第10题 文法SS(S)S| (1)生成的语言是什么？ (2)该文法是二义的吗？说明理由。 答案： （）嵌套的括号 （）是二义的，因为对于（）（）可以构造两棵不同的语法树。 第11题 令文法GE为： ET|E+T|E-T TF|T*F|T/F F(E)|i 证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。 答案： 此句型对应语法树如右，故为此文法一个句型。 或者：因为存在推导序列:E=E+T=E+T*F，所 以E+T*F句型 此句型相对于E的短语有:E+T*F；相对于T的短语 有T*F 直接短语为：T*F 句柄为：T*F 第13题 一个上下文无关文法生成句子abbaa的推导树如下： (1)给出串abbaa最左推导、最右推导。 (2)该文法的产生式集合P可能有哪些元素？ (3)找出该句子的所有短语、直接短语、句柄。 B a S ABS a SBA bba 答案： (1)串abbaa最左推导: S=ABS=aBS=aSBBS=aBBS=abBS=abbS=abbAa=abbaa 最右推导： S=ABS=ABAa=ABaa=ASBBaa=ASBbaa=ASbbaa=Abbaa=abbaa (2)产生式有：SABS|Aa|AaBSBB|b 可能元素有：aaababbaaaaabbaa (3)该句子的短语有： a是相对A的短语是相对S的短语 b是相对B的短语 bb是相对B的短语 aa是相对S的短语 abbaa是相对S的短语 直接短语有：ab 句柄是：a 编译原理课后习题答案第四章 第1题 构造下列正规式相应的DFA. （）1(0|1)*101 （）(1010*|1(010)*1）*0 （）a(a|b)*|ab*a)*b （）b(ab)*|bb)*ab 答案： (1)先构造NFA： 用子集法将NFA确定化 .01 X.A AAAB ABACAB ACAABY ABYACAB 除X，A外，重新命名其他状态，令AB为B、AC为C、ABY为D，因为D含有Y（NFA 的终态），所以D为终态。 .01 X.A AAB BCB CAD DCB DFA的状态图：: (2)先构造NFA： X1A B 1C0D1E 0 F1G0H1I0J1K L 0 Y 用子集法将NFA确定化 01 XX T0=XA AABFL T1=ABFLYCG YY CGCGJ T2=Y T3=CGJDHK DHDH KABFKL T4=DHEI EIABEFIL T5=ABFKLYCG T6=ABEFILEJYCG EJYABEFGJLY T7=ABEFGJLYEHYCGK EHYABEFHLY CGKABCFGJKL T8=ABEFHLYEYCGI EYABEFLY CGICGJI T9=ABCFGJKLDHYCGK DHYDHY T10=ABEFLYEYCG T11=CGJIDHJK DHJDHJ T12=DHYEI T13=DHJEIK EIKABEFIKL T14=ABEFIKLEJYCG 将T0、T1、T2、T3、T4、T5、T6、T7、T8、T9、T10、T11、T12、T13、T14重新命名，分别用0、 1、2、3、4、5、6、7、8、9、10、11、12、13、14表示。因为2、7、8、10、12中含有Y， 所以它们都为终态。 01 01 123 2 345 46 523 673 789 81011 9129 10103 11135 126 1314 1473 010 12 12 7 108 3 4 5 6 9 111314 1 1 0 1 0 1 0 1 1 0 1 1 0 1 0 1 01 0 1 0 1 (3)先构造NFA： 先构造NFA： XaA B a,b DaEaF C Y b b 用子集法将NFA确定化 ab XX T0=XA AABCD T1=ABCDBEBY BEABCDE BYABCDY T2=ABCDEBEFBEY BEFABCDEF BEYABCDEY T3=ABCDYBEBY T4=ABCDEFBEFBEY T5=ABCDEYBEFBEY 将T0、T1、T2、T3、T4、T5重新命名，分别用0、1、2、3、4、5表示。因为3、5中含有Y， 所以它们都为终态。 ab 01 123 245 323 445 545 0a1b3 2 a 5 a4 b a b a b a b (4)先构造NFA： XA b B a FbGbH E Y a CDb Ib 用子集法将NFA确定化： ab XX T0=XA AABDEF T1=ABDEFCIG CICI GG T2=CIDY DYABDEFY T3=GH HABEFH T4=ABDEFYCIG T5=ABEFHCIG 将T0、T1、T2、T3、T4、T5重新命名，分别用0、1、2、3、4、5表示。因为4中含有Y， 所以它为终态。 ab 01 123 24 35 423 523 DFA的状态图： 0b1b 2 a 4 5 3 b b a b a b 第题 已知NFA（x,y,z,0,1,M,x,z），其中：M(x,0)=z，M(y,0)=x,y，,M(z,0)=x,z， M(x,1)=x，M(y,1)=，M(z,1)=y，构造相应的DFA。 答案： 先构造其矩阵 01 xzx yx,y zx,zy 用子集法将NFA确定化： 01 xzx zxzy xzxzxy yxy xyxyzx xyzxyzxy 将x、z、xz、y、xy、xyz重新命名，分别用A、B、C、D、E、F表示。因为B、C、F 中含有z，所以它为终态。 01 ABA BCD CCE DE EFA FFE DFA的状态图： A 01 0 F E D 0 B 1 0 1 0 1 0 1 C 第3题 将下图确定化： 答案： 用子集法将NFA确定化： .01 SVQQU VQVZQU QUVQUZ VZZZ VZ. QUZVZQUZ ZZZ 重新命名状态子集，令VQ为A、QU为B、VZ为C、V为D、QUZ为E、Z为F。 .01 SAB ACB BDE CFF DF. ECE FFF DFA的状态图： 第4题 将下图的（a）和（b）分别确定化和最小化： 答案： 初始分划得 0：终态组0，非终态组1,2,3,4,5 对非终态组进行审查： 1,2,3,4,5a0,1,3,5 而0,1,3,5既不属于0，也不属于1,2,3,4,5 4a0，所以得到新分划 1：0，4，1,2,3,5 对1,2,3,5进行审查： 1,5b4 2,3b1,2,3,5，故得到新分划 2：0，4，1,5，2,3 1,5a1,5 2,3a1,3，故状态2和状态3不等价，得到新分划 3：0，2，3，4，1,5 这是最后分划了 最小DFA： 第5题 构造一个DFA，它接收=0,1上所有满足如下条件的字符串：每个1都有0直接跟在 右边。并给出该语言的正规式。 答案： 按题意相应的正规表达式是(0*10)*0*，或0*(0|10)*0*构造相应的DFA，首先构造NFA为 用子集法确定化： II0I1 X,0,1,3,Y 0,1,3,Y 2 1,3,Y 0,1,3,Y 0,1,3,Y 1,3,Y 1,3,Y 2 2 2 重新命名状态集： S01 1 2 3 4 2 2 4 4 3 3 3 DFA的状态图： 可将该DFA最小化： 终态组为1,2,4，非终态组为3，1,2,401,2,4，1,2,413，所以1,2,4为等价状 态，可合并。 第题 设无符号数的正规式为： =dd*|dd*.dd*|.dd*|dd*10(s|)dd* |10(s|)dd*|.dd*10(s|)dd* |dd*.dd*10(s|)dd* 化简，画出的DFA，其中d=0,1,2,9，s=， 答案： 先构造NFA： X d .B d FG d H 10 d A C 10 d D s Ed Y d s d 用子集法将NFA确定化： s10d XXA T0=XABFA BB FFG AA T1=BC CC T2=FGGH GG HH T3=ABFA T4=CDC DDE T5=GH T6=HH T7=DEEY EE YY T8=EY T9=YY 将XA、B、FG、A、C、G、H、DE、E、Y重新命名，分别用0、1、2、3、4、5、6、 7、8、9表示。终态有0、3、4、6、9。 s10d 0123 14 256 3123 474 56 66 789 89 99 DFA的状态图： d 6 25 d 3 d d 47 8 9 0 1 10 d s 10 10 d d s d d d 第7题 给文法GS： SaA|bQ AaA|bB|b BbD|aQ QaQ|bD|b DbB|aA EaB|bF FbD|aE|b 构造相应的最小的DFA。 答案： 先构造其NFA： S a A a Z Q b B D a E b F b b a b a a b bb b a b 用子集法将NFA确定化： ab SAQ AABZ QQDZ BZQD DZAB DAB BQD 将S、A、Q、BZ、DZ、D、B重新命名，分别用0、1、2、3、4、5、6表示。因为3、 4中含有z，所以它们为终态。 ab 012 113 224 325 416 516 625 DFA的状态图： 0 a a 5 2 b 3 a a b 4 1 6 b a a b b b a b 令P0（0,1,2,5,6,3,4）用b进行分割： P1（0,5,6,1,2,3,4）再用b进行分割： P2（0,5,6,1,2,3,4）再用a、b进行分割，仍不变。 再令为A，1，2为B，3，4为C，5，6为D。 最小化为： A a,b DC a a B b a b b 第题 给出下述文法所对应的正规式： S0A|1B A1S|1 B0S|0 答案： 解方程组S的解： S=0A|1B A=1S|1 B=0S|0 将A、B产生式的右部代入S中 S=01S|01|10S|10=（01|10）S|（01|10） 所以：S=(01|10)*(01|10) 第9题 将下图的DFA最小化，并用正规式描述它所识别的语言。 1 a 2 6 c 3 c b 5 47 b b ab b b d d a 答案： 令P0（1,2,3,4,5,6,7）用b进行分割： P1（1,2,3,4,5,6,7）再用a、b、c、d进行分割，仍不变。 再令1,2为A，3，4为B，5为C，6，7为D。 最小化为： A a CD b d B b c a b r=b*a(c|da)*bb*=b*a(c|da)*b+ 编译原理课后习题答案第五章 第1题 对文法GS Sa|(T) TT,S|S (1)给出(a,(a,a)和(a,a),(a),a)的最左推导。 (2)对文法G，进行改写，然后对每个非终结符写出不带回溯的递归子程序。 (3)经改写后的文法是否是LL(1)的?给出它的预测分析表。 (4)给出输入串(a,a)#的分析过程，并说明该串是否为G的句子。 答案： (1)对(a,(a,a)的最左推导为： S(T) (T,S) (S,S) (a,S) (a,(T) (a,(T,S) (a,(S,S) (a,(a,S) (a,(a,a) 对(a,a),(a),a)的最左推导为： S(T) (T,S) (S,S) (T),S) (T,S),S) (T,S,S),S) (S,S,S),S) (T),S,S),S) (T,S),S,S),S) (S,S),S,S),S) (a,S),S,S),S) (a,a),S,S),S) (a,a),S),S) (a,a),(T),S) (a,a),(S),S) (a,a),(a),S) (a,a),(a),a) (2)改写文法为： 0)Sa 1)S 2)S(T) 3)TSN 4)N,SN 5)N 非终结符FIRST集FOLLOW集 Sa,(#,) Ta,(). N,.). 对左部为N的产生式可知： FIRST（,SN）=， FIRST（）= FOLLOW（N）=) 由于SELECT(N,SN)SELECT(N)=，)= 所以文法是LL(1)的。 预测分析表（PredictingAnalysisTable） a(),# Sa(T) TSNSNSN N,SN 也可由预测分析表中无多重入口判定文法是LL(1)的。 (3)对输入串（a,a）#的分析过程为： 栈（STACK） 当前输入符 （CUR_CHAR） 剩余输入符 （INOUT_STRING） 所用产生式 （OPERATION） #S #)T( #)T #)NS #)Na #)N #)NS, #)NS #)Na #)N #) # ( ( a a a , , a a ) ) # a,a)#. a,a)#. ,a)#. ,a)#. ,a)#. a)#. a)#. )#. )#. #. #. S(T) . TSN Sa . N,SN . Sa . N 可见输入串（a,a）#是文法的句子。 第3题 已知文法GS： SMH|a HLSo| KdML| LeHf MK|bLM 判断G是否是LL(1)文法，如果是，构造LL(1)分析表。 答案： 文法展开为： 0）SMH 1）Sa 2）HLSo 3）H 4）KdML 5）K 6）LeHf 7）MK 8）MbLM 非终结符FIRST集FOLLOW集 Sa,d,b,e#,o. Md,b.e,#,o. H,e.#,f,o. Le.a,d,b,e,o,# Kd,.e,#,o. 对相同左部的产生式可知： SELECT(SMH)SELECT(Sa)=d,b,e，#,oa= SELECT(HLSo)SELECT(H)=e#,f,o= SELECT(KdML)SELECT(K)=de,#,o= SELECT(MK)SELECT(MbLM)=d，e,#,ob= 所以文法是LL(1)的。 预测分析表： aodefb# SaMHMHMHMHMH MKKKbLMK HLSo LeHf KdML 由预测分析表中无多重入口也可判定文法是LL(1)的。 第7题 对于一个文法若消除了左递归，提取了左公共因子后是否一定为LL(1)文法?试对下面 文法进行改写，并对改写后的文法进行判断。 ()AbaB| BAbb|a (2)AaABe|a BBb|d (3)SAa|b ASB Bab 答案： ()先改写文法为： 0)AbaB 1)A 2)BbaBbb 3)Bbb 4)Ba 再改写文法为： 0)AbaB 1)A 2)BbN 3)Ba 4)NaBbb 5)Nb FIRSTFOLLOW Ab# Bb,a#,b Nb,a#,b 预测分析表： ab# AbaB BabN NaBbbb 由预测分析表中无多重入口判定文法是LL(1)的。 （2）文法： AaABe|a BBb|d 提取左公共