内容发布更新时间 : 2024/5/18 17:06:03星期一 下面是文章的全部内容请认真阅读。

E→E+T|E-T|T T→T*F|T/F|F F→(E)|i

试给出下述表达式的推导及语法树 (1) i; (2) i*i+i (3) i+i*i (4) i+(i+i) 答案：

(1)E=>T=>F=>i

(2)E=>E+T=>T+T=>T*F+T=>F*F+T=>i*F+T=>i*i+T=>i*i+F=>i*i+i (3)E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i

(4)E=>E+T=>T+T=>F+T=>i+T=>i+F=>i+(E)=>i+(E+T)=>i+(T+T)=>i+(F+T) =>i+(i+T)=>i+(i+F)=>i+(i+i) E E E + T T T * F F i i E + T i T F i F i E E + T E + T i T F F ( E ) i T F i F T F i F i

(1) (2) (3) (4)

盛威网（www.snwei.com）专业的计算机学习网站 11 《编译原理》课后习题答案第三章 问题6：

已知文法G[E]: E→ET+|T T→TF* | F F→F^ | a

试证：FF^^*是文法的句型，指出该句型的短语、简单短语和句柄. 答案：

该句型对应的语法树如下： 该句型相对于E 的短语有FF^^* 相对于T 的短语有FF^^*,F 相对于F 的短语有F^;F^^ 简单短语有F;F^ 句柄为F. 问题7：

适当变换文法，找到下列文法所定义语言的一个无二义的文法： S → SaS ? SbS ? ScS ? d 答案：

该文法的形式很典型，可以先采用优先级联规则变换文法，然后再规定结合性对文法做 进一步变换，即可消除二义性。

设a、b 和c 的优先级别依次增高，根据优先级联规则将文法变换为： S → SaS ? A A → AbA ? C C → CcC ? d

规定结合性为左结合，进一步将文法变换为： S → SaA? A A → AbC ?C C → CcF ? F F → d

该文法为非二义的。

盛威网（www.snwei.com）专业的计算机学习网站 12 《编译原理》课后习题答案第三章 问题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 ? ε

（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 问题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 答案：

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：

已知文法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} 问题15：

设有文法G[S]：S∷=S*S|S+S|(S)|a，该文法是二义性文法吗？ 答案：

根据所给文法推导出句子a+a*a，画出了两棵不同的语法树，所以该文法是二义性文法。 盛威网（www.snwei.com）专业的计算机学习网站 15 《编译原理》课后习题答案第三章 S S * S S + S a a a S