《编译原理》课后习题答案第三章 C → CcC ? d
规定结合性为左结合，进一步将文法变换为： S → SaA? A
A → AbC ?C C → CcF ? F F → d
该文法为非二义的。
问题 8：构造产生如下语言的上下文无关文
法：
（1） {anb2ncm | n，m ≥ 0} （2） {anbmc2m | 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） 根据上下文无关文法的特点，要产生形如anb2ncm的串，可以分别产生形如 anb2n 和形如 cm 的串。设计好的文法是否就是该语言的文法？严格地说，应该给出证明。但若不是特别指明，通常可以忽略这一点。
对于该语言，存在一个由以下产生式定义的上下文无关文法 G[S]：
S → AB
A → ε ? aAbb B → ε ? cB
（2） 同样，要产生形如anbmc2m的串，可以分别产生形如 an 和形如 bmc2m 的串。对于该语言，存在一个由以下产生式定义的上下文无关文法G[S]：
S → AB A → ε ? aA B → ε ? bBcc
（3） 考虑在先产生同样数目的 a,b，然后再生成多余的 a。以下 G[S]是一种解法：
S → aSb ? aS ? ε
盛威网（www.snwei.com）专业的计算机学习网站
13
《编译原理》课后习题答案第三章 （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 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+. 答案：
x0=(aaa)0=ε | x0|=0 xx=aaaaaa
|xx|=6
x5=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
盛威网（www.snwei.com）专业的计算机学习网站
14
《编译原理》课后习题答案第三章 答案：
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 ,请写出全部由此文法描述的只含有四个符号的句子。 答案：
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描述的语言:{,bncn|n>=1} L(G[S])={anbmcm|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}
盛威网（www.snwei.com）专业的计算机学习网站
15
《编译原理》课后习题答案第三章
问题 15：
设有文法 G[S]：S∷=S*S|S+S|(S)|a，该文法是二义性文法吗？ 答案：
根据所给文法推导出句子 a+a*a，画出了两棵不同的语法树，所以该文法是二义性文法。
S S S * S S + S S + S a a S * S a a 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(0|1) *101
（２） １(1010*|1(010)*1）*0 （３） a((a|b)*|ab*a)*b （４） b((ab)*|bb)*ab 答案：
(1) 先构造 NFA：
用子集法将 NFA 确定化
. X A AB AC ABY 0 . A AC A AC
1 A AB AB ABY AB 除 X，A 外，重新命名其他状态，令 AB 为 B、AC 为 C、ABY 为 D，因为 D 含有 Y（NFA 的终态），所以 D 为终态。
. X A B C D DFA 的状态图：: 0 . A C A C 1 A B B D B
盛威网（www.snwei.com）专业的计算机学习网站
1
相关推荐：
loading