编译课后习题解答

习题解答第2章上下文无关文法西北大学软件工程研究所龚晓庆第1／39页2010-06-226.令文法G6为N→D|NDD→0|1|2|3|4|5|6|7|8|9（1）G6的语言L(G6)是什么？（2）给出句子0127、34和568的最左推导和最右推导解答（1）G6的语言是由09这10个数字组成的字符串（1）G6的语言是由0～9这10个数字组成的字符串（2）最左推导N=ND=NDD=DDDD=0DDD=01DD=012D=0127N=ND=NDD=DDDD=0DDD=01DD=012D=0127N=ND=DD=3D=4DN=ND=NDD=DDD=5DD=56D=568556568最右推导N=ND=N7=ND7=N27=ND27=N127=D127=0127N=ND=N4=D4=34N=ND=N8=ND8=N68=D68=568西北大学软件工程研究所龚晓庆第2／39页2010-06-227写个文法使其语言是奇数集且每个奇数不以0开头7.写一个文法，使其语言是奇数集，且每个奇数不以0开头解答f分析结构fD代表单个奇数，C代表非0数字，A代表所有数字，B代表任意数字D代表单个奇数，C代表非0数字，A代表所有数字，B代表任意数字串fG(S)：S→D|CD|CBDG(S)：S|C|CD→1|3|5|7|9C→2|4|6|8|DC→2|4|6|8|DA→0|CB→BA|A西北大学软件工程研究所龚晓庆第3／39页2010-06-228.令文法为E→T|E+T|E-TT→F|T*F|T/FF→(E)|iE|||||(1)给出i+i*i、i*(i+i)的最左推导和最右推导(2)给出i+i+i、i+i*i、i-i-i的语法树解答EET+解答（1）最左推导E=E+T=T+T=F+T=i+T=i+T*FET+FFiT=i+F*F=i+i*F=i+i*iE=T=T*F=F*F=i*F=i*(E)=i*(E+T)FiiTF=i*(T+T)=i*(F+T)=i*(i+T)=i*(i+F)=i*(i+i)最右推导iEE=E+T=E+T*F=E+T*i=E+F*i=E+i*i=T+i*i=F+i*i=i*i+iET+TF*TE=T=T*F=T*(E)=T*(E+T)=T*(E+F)=T*(E+i)=T*(T+i)=T*(F+i)=T*(i*i)=F*(i*i)FFi=i*(i+i)（2）语法树如图ii西北大学软件工程研究所龚晓庆第4／39页2010-06-229.证明下面的文法是二义的：S→iSeS|iS|iS→iSeS|iS|i解答考虑句子iiiei，存在如下两个最右推导：考虑句子iiiei，存在如下两个最右推导：S=iSeS=iSei=iiSei=iiieiS=iS=iiSeS=iiSei=iiieiSiSiiSeSiiSeiiiiei由此，该文法是二义的10把下面的文法改写为无二义的10.把下面的文法改写为无二义的：S→SS|(S)|()f思路：S→SS是产生二义性的根源将其变为等价的递归结构f思路：S→SS是产生二义性的根源，将其变为等价的递归结构解答将文法改造成G(S)：将文法改造成G(S)：S－TS|TT－(S)|()(S)|()西北大学软件工程研究所龚晓庆第5／39页2010-06-2211.给出下面语言的相应文法iL1＝{anbnci|n≥1,i≥0}L2＝{aibncn|n≥1,i≥0}L3＝{anbnambm|n,m≥0}3L4＝{1n0m1m0n|n,m≥0}解答解答L1的文法：S→ACA→aAb|abC→cC|εL2的文法：S→ABA→aA|εB→bBc|bc||L3的文法：S→ABA→aAb|εB→aBb|εL4的文法：S→1S0|AA→0A1|ε西北大学软件工程研究所龚晓庆第6／39页2010-06-22习题解答第3章词法分析西北大学软件工程研究所龚晓庆第7／39页2010-06-227.构造下列正规式相应的DFA构造下列规式相应的1(0|1)*101解答解答f第一步：根据正规式构造NFA如图f第二步：NFA确定化，得到状态转换矩阵和相应DFA如图II0I1II0I1{0}Φ{1}{1}{1}{1,2}{1,2}{1,3}{1,2}{1,3}{1}{1,2,4}{124}{13}{12}{1,2,4}{1,3}{1,2}西北大学软件工程研究所龚晓庆第8／39页2010-06-228.给出下面正规表达式串（1）以01结尾的二进制数串（2）能被5整除的十进制整数（3）包含奇数个1或奇数个0的二进制数串解答①(0|1)*01①(|)②(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*(0|5)|0|5③0*1(0|10*1)*|1*0(1|01*0)*③(|)|(|)9.对下面的情况给出DFA及正规式（1）{0,1}上含有子串010的所有串（2）{0,1}上不含子串010的所有串解答①(0|1)*010(0|1)*②1*(0|111*)*1*西北大学软件工程研究所龚晓庆第9／39页2010-06-2212.将图3.18的(a)和(b)分别确定化和最小化解答(a)确定化得到状态转换矩阵如表(b)首先将状态划分为{0,1}{2,3,4,5}；有{0,1}a={1}{0,1}b={2,4}()确定化得到状转换矩阵如表DFA如图{2,3,4,5}a={1,3,0,5}{2,3,4,5}b={2,3,4,5}IIaIb所以可以进一步划分为{0,1}{2,4}{3,5};有{0,1}a={1}{0,1}b={2,4}{0}{0,1}{1}{0,1}{0,1}{1}{1}{0}Φ{2,4}a={1,0}{2,4}b={3,5}{3,5}a={3,5}{3,5}b={2,4}{1}{0}Φ因此最后划分结果为{0,1}{2,4}{3,5};DFA如图西北大学软件工程研究所龚晓庆第10／39页2010-06-2214.构造一个DFA，它接受∑={0,1}上所有满足如下条件的字符串：每个1都有0直接跟在右边每个1都有0直接跟在右边。解答①构造相应的正规式为(0|10)*②构造NFA如右图③确定化得到状态转换矩阵和DFA如下④最小化DFAII0I1{0,1,3}{1,3}{2}{,,}{,}{}{1,3}{1,3}{2}{2}{13}Φ{2}{1,3}Φ西北大学软件工程研究所龚晓庆第11／39页2010-06-2215.给定右线性文法G，S→0S|1S|1A|0BA→1C|1B→0C|0C→0C|1C|0|1求出一个与G等价的左线性文法解答文法G对应的FA如图根据FA，构造左线性文法为|||F→C0|C1|A1|B0A→S1|1B→S0|0C→A1|B0|C0|C1S→S0|S1|0|1西北大学软件工程研究所龚晓庆第12／39页2010-06-22习题解答第4章自上而下语法分析西北大学软件工程研究所龚晓庆第13／39页2010-06-221.考虑下面的文法：TTTS→a|^|(T)T→T,S|S消去左递归。改写后的文法是否为LL(1)的？给出预测分析表解答解答消除直接左递归，得到G'(S)S→a|^|(T)T→ST'FIRSTFOLLOWSa^(#，)Sa||(T)TSTT'→,ST'|ε计算每个非终结符的FIRST和FOLLOW集合Ta^()T'，ε)计算每个非终结符的FIRST和FOLLOW集合构造预测分析表因为表中无多重定义项所以文法G'是LL(1)的因为表中无多重定义项,所以文法G是LL(1)的a^，()#SS→aS→^S→(T)TT→ST'T→ST'T→ST'T'T'ST'T'T'→,ST'ε西北大学软件工程研究所龚晓庆第14／39页2010-06-222.对下面的文法GTTTTTE→TE'E'→+E|εT→FT'T'→T|εF→PF'F'→*F'|εP→(E)|a|b|^(1)计算每个非终结符的FIRST和FOLLOW集合FIRSTFOLLOWE(ab^#)E'#)(2)证明这个文法是LL(1)的(3)构造预测分析表解答（1）非终结符的FIRST和FOLLOW集合E'+ε#)T(ab^+)#T'(ab^ε+)#解答（1）非终结符的FIRST和FOLLOW集合（2）构造预测分析表如下:因为表中无多重定义项，所以文法是LL(1)的()F(ab^(ab^+)#F'*ε(ab^+)#P(ab^*(ab^+)#因为表中无多重定义项，所以文法是LL(1)的（3）分析表如（2）所示P(ab^*(ab^+)#ab^()+*#ETE'TE'TE'TE'E'ε+EεTFT'FT'FT'FT'TFTFTFTFTT'TTTTεεεFPF'PF'PF'PF'F'εεεεεε*F'εPab^(E)西北大学软件工程研究所龚晓庆第15／39页2010-06-223.下面文法中，哪些是LL(1)文法，说明理由(1)S→ABcA→a|εB→b|ε(2)S→AbA→a|B|εB→b|ε(3)S→ABBAA→a|εB→b|ε(4)S→aSe|BB→bBe|CC→cCe|d解答①文法不含左递归；first(S)={a,b,c}follow{S}={#}first(A)={a,ε}follow(A)={b,c}first(B)={b,ε}fll(B){}可见满足LL(1)文法的三个条件是LL(1)文法follow(B)={c}；可见满足LL(1)文法的三个条件，是LL(1)文法②文法不含左递归；first(S)={a,b}follow{S}={#}first(A)={abε}follow(A)={b}first(B)={bε}follow(B)=={a,b,ε}follow(A)={b}first(B)={b,ε}follow(B)={b}；考虑A的产生式，first(A)∩follow(A)={b}≠Φ，所以文法不是LL(1)的。③不是LL(1)文法，理由略④是LL(1)文法，理由略西北大学软件工程研究所龚晓庆第16／39页2010-06-224.对下面文法TTExpr→－Expr|(Expr)|VarExprTailExprTail→－Expr|εVar→idVarTailVarTail→(Expr)|ε(1)构造LL(1)分析表(2)给出句子id—id(id)的分析过程解答FIRSTFOLLOW(1)计算每个非终结符的FIRST和FOLLOW集合构造分析表如Expr－，(，id#，)ExprTail－，ε#，)Varid)#构造预测分析表如下(2)分析过程略Varid－,),#VarTail(，ε－,),#－id()#Expr－ExprVarExprTail(Expr)ExprTail－ExprεεVaridVarTailVarTailε(Expr)εεVarTailε(Expr)εε西北大学软件工程研究所龚晓庆第17／39页2010-06-22习题解答第5章自下而上语法分析西北大学软件工程研究所龚晓庆第18／39页2010-06-221.令文法G1为E→E+T|TT→T*F|FF→(E)|i令文法为||()|证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。和句柄。解答：E+T*F是文法G1的句型，因为存在如下图所示的语法树短语T*F和E+T*F短语：T*F和E+T*F直接短语：T*FE句柄：T*FET+TF*TF西北大学软件工程研究所龚晓庆第19／39页2010-06-223.考虑表格文法G2:S→a|^|(T)T→T,S|S（1）计算G2的FIRSTVT和LASTVT（1）计算G2的FIRSTVT和LASTVT（2）计算G2的优先关系，G2是算符优先文法吗？（3）计算G2的优先函数（4）给出输入串(a,(a,a))的算符优先分析过程。解答（1）FIRSTVT(S){^(}FIRSTVT(T){^(}（1）FIRSTVT(S)={a(