编译原理(第2版)课后习题答案详解 下载本文

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 ,请写出全部由此文 法描述的只含有四个符号的句子。

答案:

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,画出了两棵不同的语法树,所以该文法是二义性文法。