《编译原理》课后习答案第三章 问题8： 构造产生如下语言的上下文无关文法： (1)1,m≥W (2)de1n,m≥0明 (3){|m≥) (4){a"b“c'd|m+n=p+g} (5){uawb l uwefa*lu=w 答案 (1)根据上下文无关文法的特点，要产生形如b”的串，可以分别产生形如db和 形如的串。设计好的文法是否就是该语言的文法？严格地说，应该给出证明。但若不是 特别指明，通常可以忽略这一点。 对于该语言，存在一个由以下产生式定义的上下文无关文法GS]: S→AB A→E|aAbb B→E|cB (2)同样，要产生形如dbc的串，可以分别产生形如d和形如b2的串。对于该语 言，存在一个由以下产生式定义的上下文无关文法GS: SAB 4a4 B→E|bBcc (3)考虑在先产生同样数目的ab,然后再生成多余的a。以下GS]是一种解法 s→aSb|aS|e (4)以下GS是一种解法： S→ad|A|D 4→bd|B D→aDeB B→bBe|g 注：a不多于d时，b不少于c:反之，a不少于d时，b不多于c。前一种情形通过 对应A,后一种情形对应D。 (5)以下GS]是一种解法 S-Ab A→BAB|a 盛威网(www.snwei.com)专业的计算机学习网站
《编译原理》课后习题答案第三章 问题 8： 构造产生如下语言的上下文无关文法： （1） {an b2n c m | n，m ≥ 0} （2） {an bmc 2m | n，m ≥ 0} （3） { ambn ⏐ m ≥ n } （4）{ a m b n c p d q ⏐ m+n = p+q } （5）{ uawb ⏐ u,w ∈{a, b}* ∧ | u | = | w | } 答案： （1）根据上下文无关文法的特点，要产生形如an b2n c m的串，可以分别产生形如 an b2n 和 形如 c m 的串。设计好的文法是否就是该语言的文法？严格地说，应该给出证明。但若不是 特别指明，通常可以忽略这一点。 对于该语言，存在一个由以下产生式定义的上下文无关文法 G[S]： S → AB A → ε ⏐ aAbb B → ε ⏐ cB （2）同样，要产生形如an bmc 2m的串，可以分别产生形如 an 和形如 bmc 2m 的串。对于该语 言，存在一个由以下产生式定义的上下文无关文法G[S]： S → AB A → ε ⏐ aA B → ε ⏐ bBcc （3）考虑在先产生同样数目的 a,b，然后再生成多余的 a。以下 G[S]是一种解法： S → aSb ⏐ aS ⏐ ε （4）以下 G[S]是一种解法： S → aSd ⏐ A ⏐ D A → bAd ⏐ B D → aDc ⏐ B B → bBc ⏐ ε 注：a 不多于 d 时，b 不少于 c；反之，a 不少于 d 时，b 不多于 c。前一种情形通过 对应 A，后一种情形对应 D。 （5）以下 G[S]是一种解法： S → Ab A → BAB ⏐ a 盛威网（www.snwei.com）专业的计算机学习网站 13
《编译原理》课后习题答案第三章 B→a|b 下面的文法GS)描述由命题变量p、q,联结词A(合取)、V(析取)、一（否定）构 成的命题公式集合： s→SvTIT T→TAF F→FI Pq 试指出句型一FV一qAp的直接短语（全部）以及句柄。 答案， 直接短语：p,q,f 句枘：一F 问题10： 设字母表A=a,符号串=aa,写出下列符号串及其长度：0，x5以及A+ 答案： x-(aaa°=e1x1=0 xx=aaaaaa x=6 x'=aaaaaaaaaaaaaaa Ix=15 A+=A!U A2 U.UAU.=(a,aa,aaa,aaaa.aaaaa. A+=AUA!U A2 U.U AU.=IE ,aaa,aaa,aaaa.aaaaa. 问题11： 令∑=a,b,c,又令x=abe,=b,2=aah,写出如下符号串及它们的长度：y,y (y)3 答案 xy=abcb xyl=4 xyz=abcbaab lxyz=7 (xy)=(abcb)=abcbabcbabcb (xy)=12 问题12： 已知文法GZ小：Z:=U0V1、U:=Z1|1、V:=Z0|0,请写出全部由此文 法描述的只含有四个符号的句子， 盛成网(www.snwei.com)专业的计算机学习网站
《编译原理》课后习题答案第三章 B → a ⏐ b 问题 9： 下面的文法 G(S)描述由命题变量 p、q ，联结词 ∧（合取）、∨（析取）、¬（否定）构 成的命题公式集合： S → S ∨ T ⏐ T T → T ∧ F ⏐ F F → ¬ F ⏐ p ⏐ q 试指出句型 ¬ F ∨ ¬ q ∧ p 的直接短语（全部）以及句柄。 答案： 直接短语：p，q，¬F 句柄：¬F 问题 10： 设字母表 A={a}，符号串 x=aaa，写出下列符号串及其长度：x0,xx,x5 以及 A+. 答案： x 0 =(aaa)0 =ε | x0 |=0 xx=aaaaaa |xx|=6 x 5 =aaaaaaaaaaaaaaa | x5 |=15 A+ =A1 ∪ A2 . A ∪ ∪ n .∪ ={a,aa,aaa,aaaa,aaaaa.} A* = A0 ∪A1 ∪ A2 ∪ . ∪ A n ∪.={ε,a,aa,aaa,aaaa,aaaaa.} 问题 11： 令∑={a，b，c}，又令 x=abc，y=b，z=aab，写出如下符号串及它们的长度：xy，xyz， （xy）3 答案： xy=abcb |xy|=4 xyz=abcbaab |xyz|=7 (xy)3 =(abcb)3 =abcbabcbabcb | (xy)3 |=12 问题 12： 已知文法 G[Z]：Z∷=U0∣V1 、 U∷=Z1∣1 、 V∷=Z0∣0 ,请写出全部由此文 法描述的只含有四个符号的句子。 盛威网（www.snwei.com）专业的计算机学习网站 14
《编译原理》课后习恩答案第三章 答案 Z=>U0=>Z10=>U010=>1010 Z=>U0=>Z10=>V110=>0110 Z=>V1=>Z00=>U000=>1000 Z=>V1=>Z00=>V100=>0100 问题13： 已知文法GSl:S:=ABA:=aA|B:=bBc|bc,写出该文法描述的语言。 答案 A:=aA|e描述的语言：{an>-0} B:=bBc|bc描述的语言：{，bc"n>=1) L(G[S])=(a"b"c"n>=0.m>=1) 问题14： 已知文法E:=T|E+T1ET、T:=F|T*F|T/F、F:=(E)i,写出该文法的开 始符号、终结符号集合V非终结符号集合V。 答案： 开始符号：E V+,*,1,（,）,i Vx-[E,F,T} 问题15： 设有文法GS:S=SSS+SSa,该文法是二义性文法吗？ 答案： 根据所给文法推导出句子a+a*a,画出了两棵不同的语法树，所以该文法是二义性文法。 盛威网(www.snwei.com)专业的计算机学习网站
《编译原理》课后习题答案第三章 答案： Z=>U0=>Z10=>U010=>1010 Z=>U0=>Z10=>V110=>0110 Z=>V1=>Z00=>U000=>1000 Z=>V1=>Z00=>V100=>0100 问题 13： 已知文法 G[S]： S∷=AB A∷=aA︱ε B∷=bBc︱bc , 写出该文法描述的语言。 答案： A∷=aA︱ε描述的语言: {an |n>=0} B∷=bBc︱bc描述的语言:{,bn c n |n>=1} L(G[S])={an bmc m|n>=0,m>=1} 问题 14： 已知文法E∷=T∣E+T∣E-T 、 T∷=F∣T*F∣T/F 、 F∷=(E)∣i，写出该文法的开 始符号、终结符号集合VT、非终结符号集合VN。 答案： 开始符号：E VT={+, - , * , / ,（ , ）, i} VN={E , F , T} 问题 15： 设有文法 G[S]：S∷=S*S|S+S|(S)|a，该文法是二义性文法吗？ 答案： 根据所给文法推导出句子 a+a*a，画出了两棵不同的语法树，所以该文法是二义性文法。 盛威网（www.snwei.com）专业的计算机学习网站 15
《编译原理》课后习题答案第三章 的力中中 力的白中 白中 问题16： 写一文法，使其语言是奇正整数集合。 答案： A=3151719INA 盛成网(www.snwei.com)专业的计算机学习网站
《编译原理》课后习题答案第三章 S S * S S + S a a a S S + S a S * S a a 问题 16： 写一文法，使其语言是奇正整数集合。 答案： A::=1|3|5|7|9|NA N::=N0|N1|N2|N3|N4|N5|N6|N7|N8|N9| N::=0|1|2|3|4|5|6|7|8|9 盛威网（www.snwei.com）专业的计算机学习网站 16
《编译原理》课后习恩答案第四章 第4章词法分析 第1题 构造下列正规式相应的DFA (1)101)101 （2）110101010*1)*0 (3)a((ab)"jab"a)"b （4)b(ab,*bb)*ab 答案： ()先构造NFA: -080'o+@ 用子集法将NFA确定化 0 1 X A A AB AB AC AB AC A ABY ABY AC AB 除X,A外，重新命名其他状态，令AB为B、AC为C、ABY为D,因为D含有Y(NFA 的终态)，所以D为终态。 0 1 A A A B B B C A D D B DFA的状态图： -0880 盛咸网(www.snwei.com)专业的计算机学习网站 1
《编译原理》课后习题答案第四章 第 4 章 词法分析 第 1 题 构造下列正规式相应的 DFA. （１） 1(0|1) *101 （２） １(1010*|1(010)*1）*0 （３） a((a|b)*|ab*a)*b （４） b((ab)*|bb)*ab 答案： (1) 先构造 NFA： 用子集法将 NFA 确定化 . 0 1 X . A A A AB AB AC AB AC A ABY ABY AC AB 除 X，A 外，重新命名其他状态，令 AB 为 B、AC 为 C、ABY 为 D，因为 D 含有 Y（NFA 的终态），所以 D 为终态。 . 0 1 X . A A A B B C B C A D D C B DFA 的状态图：: 盛威网（www.snwei.com）专业的计算机学习网站 1