《编译课后习题解答》由会员分享，可在线阅读，更多相关《编译课后习题解答（39页珍藏版）》请在金锄头文库上搜索。
1、习题解答 第2章上下文无关文法西北大学软件工程研究所 龚晓庆第 139页2010-06-226. 令文法G6为 N D|ND D 0|1|2|3|4|5|6|7|8|9 （1）G6的语言L(G6)是什么？ （2）给出句子0127、34和568的最左推导和最右推导解答（1）G6的语言是由09这10个数字组成的字符串（1）G6的语言是由09这10个数字组成的字符串（2）最左推导N=ND =NDD =DDDD =0DDD =01DD =012D =0127N=ND =NDD =DDDD =0DDD =01DD =012D =0127N =ND =DD =3D =4DN =ND =NDD =DDD =
2、5DD =56D =568 5 56 568最右推导N =ND =N7 =ND7 =N27 =ND27 =N127 =D127 =0127N =ND =N4 =D4 =34N =ND =N8 =ND8 =N68 =D68 =568西北大学软件工程研究所 龚晓庆第 239页2010-06-227 写个文法使其语言是奇数集且每个奇数不以0开头7.写一个文法，使其语言是奇数集，且每个奇数不以0开头解答?分析结构?D代表单个奇数，C代表非0数字，A代表所有数字，B代表任意数字D代表单个奇数，C代表非0数字，A代表所有数字，B代表任意数字 串?G(S)：S D | CD |CBDG(S)：S | C |
3、CD 1|3|5|7|9C 2|4|6|8|DC 2|4|6|8|DA 0|CB BA | A西北大学软件工程研究所 龚晓庆第 339页2010-06-228.令文法为 E T | E+T | E-T T F | T*F |T/F F (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*F ET+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
4、+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西北大学软件工程研究所 龚晓庆第 439页2010-06-229. 证明下面的文法是二义的： S iSeS | iS | iS iSeS | iS | i 解答考虑句子iiiei，存在如下
5、两个最右推导：考虑句子iiiei，存在如下两个最右推导：S = iSeS =iSei =iiSei =iiieiS =iS = iiSeS = iiSei = iiieiS iS iiSeS iiSei iiiei由此，该文法是二义的10 把下面的文法改写为无二义的10. 把下面的文法改写为无二义的： S SS | (S) | ( ) ?思路：S SS 是产生二义性的根源将其变为等价的递归结构?思路：S SS 是产生二义性的根源，将其变为等价的递归结构解答将文法改造成G(S)：将文法改造成G(S)：S TS | TT (S) | ( )(S) | ( )西北大学软件工程研究所 龚晓庆第 539
6、页2010-06-2211. 给出下面语言的相应文法 iL1 anbnci| n 1, i 0 L2 aibncn| n 1, i 0 L3 anbnambm| n ,m0 3 L4 1n0m1m0n| n ,m0 解答解答L1的文法：SAC A aAb | abC cC | L2的文法：SAB A aA | B bBc | bc|L3的文法：SAB A aAb | B aBb | L4的文法：S 1S0 | A A 0A1 | 西北大学软件工程研究所 龚晓庆第 639页2010-06-22习题解答 第3章词法分析西北大学软件工程研究所 龚晓庆第 739页2010-06-227. 构造下列正规
7、式相应的DFA构造下列规式相应的1(0|1)*101解答解答?第一步：根据正规式构造NFA如图?第二步：NFA确定化，得到状态转换矩阵和相应DFA如图II0I1II0I101111,21,21,31,21,311,2,41 2 41 31 21,2,41,31,2西北大学软件工程研究所 龚晓庆第 839页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 | 50*
8、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* 西北大学软件工程研究所 龚晓庆第 939页2010-06-2212. 将图3.18的(a)和(b)分别确定化和最小化解答(a)确定化得到状态转换矩阵如表(b)首先将状态划分为0,12,3,4,5；有0,1a = 1 0,1b = 2,4( )确定化得到状转换矩阵如表DFA如图2,3,4,5a = 1,3,0,52,3,4,
9、5b = 2,3,4,5IIaIb所以可以进一步划分为0,1 2,4 3,5;有0,1a = 1 0,1b = 2,400,110,10,11102,4a = 1,0 2,4b = 3,53,5a = 3,5 3,5b = 2,410因此最后划分结果为0,1 2,4 3,5;DFA如图西北大学软件工程研究所 龚晓庆第 1039页2010-06-2214. 构造一个DFA，它接受=0,1上所有满足如下条件的字符串： 每个1都有0直接跟在右边每个1都有0直接跟在右边。解答构造相应的正规式为 (0|10)*构造NFA如右图确定化得到状态转换矩阵和DFA如下最小化DFAII0I10,1,31,32 ,
10、 , , 1,31,3221 321,3西北大学软件工程研究所 龚晓庆第 1139页2010-06-2215. 给定右线性文法G， S 0S | 1S | 1A | 0B A 1C | 1 B 0C | 0 C 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西北大学软件工程研究所 龚晓庆第 1239页2010-06-22习题解答 第4章自上而下语法分析西北大学软件工程研究所 龚晓庆第 1339
11、页2010-06-221. 考虑下面的文法： TTTS a | | (T) T T,S | S 消去左递归。改写后的文法是否为LL(1)的？给出预测分析表解答解答消除直接左递归，得到G(S)S a | | (T)T STFIRSTFOLLOWSa (# ， )S a | | (T) T ST T ,ST | 计算每个非终结符的FIRST和FOLLOW集合Ta () T， ) 计算每个非终结符的FIRST和FOLLOW集合构造预测分析表因为表中无多重定义项 所以文法G是LL(1)的因为表中无多重定义项,所以文法G 是LL(1)的a， ，()#SS aS S (T)TT ST T ST T ST
12、TTSTTT ,ST 西北大学软件工程研究所 龚晓庆第 1439页2010-06-222. 对下面的文法G TTTTTE TE E +E | T FT T T | F PF F *F | P (E) | a | b | (1)计算每个非终结符的FIRST和FOLLOW集合FIRSTFOLLOWE( a b # )E# )(2)证明这个文法是LL(1)的 (3)构造预测分析表解答（1）非终结符的FIRST和FOLLOW集合E+ # )T( a b + ) #T( a b + ) #解答（1）非终结符的FIRST和FOLLOW集合（2）构造预测分析表如下:因为表中无多重定义项，所以文法是LL(1)
13、的()F( a b ( a b + ) #F* ( a b + ) #P( a b * ( a b + ) #因为表中无多重定义项，所以文法是LL(1)的（3）分析表如（2）所示P( a b * ( a b + ) #ab()+*#ETETETETEE+ETFTFTFTFTTFTFTFTFTTTTTTFPFPFPFPFF*F Pab(E)西北大学软件工程研究所 龚晓庆第 1539页2010-06-223. 下面文法中，哪些是LL(1)文法，说明理由 (1) S ABc A a |B b | (2) S Ab A a | B |B b | (3) S ABBA A a |B b | (4) S
14、aSe | B B bBe |C C cCe | d解答文法不含左递归；first(S) = a,b,c followS = # first(A) = a, follow(A) = b,c first(B) = b , f ll(B) 可见满足LL(1)文法的三个条件是LL(1)文法follow(B) = c；可见满足LL(1)文法的三个条件，是LL(1)文法文法不含左递归；first(S) = a,b followS = # first(A) = a b 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)文法，理由略西北大学软件工程研究所 龚晓庆第 1639页2010-06-224. 对下面文法 TTExpr
