第三章 文法和语言课后习题参考答案.doc

第三章 文法和语言课后习题参考答案1. L(G)=abc2. L(GN)是无符号整数。3. G3: ED+E | D-E | D D0|1|2|3|4|5|6|7|8|94. L(GZ)=anbn | n05. 写一文法，使其语言是偶正整数的集合要求：(1) 允许0打头(2) 不允许0打头解：(1) GS=(S,P,D,N,0,1,2,9,P,S)P:SPD|DP-NP|ND0|2|4|6|8N-0|1|2|3|4|5|6|7|8|9(2) GS=(S,P,R,D,N,Q ,0,1,2,9,P,S)P:SPD|P0|DP-NR|NR-QR|QD2|4|6|8N-1|2|3|4|5|6|7|8|9Q-0|1|2|3|4|5|6|7|8|96. 已知文法G：:=|+|-:=|*|/:=()|i。试给出下述表达式的推导及语法树。(1)i; (2)(i)(3)i*i;(4)i*i+i; (5)i+(i+i);(6)i+i*i。解：(1) =i(2) =()=()=()=(i)(3) =*=*=i*i(4) =+=+=*+=*+=i*i+i=w(5) =+=+=+=i+()= i+(+)=i+(+)= i+(+)=i+(i+i)(6) =+=+=+=i+=i+*= i+*= i+i*ii( )i * ii + * iii + i( ) + ii + i * ii(1) i(2) (i)(3) i*i(4) i*i+i(5) i+(i+i)(6) i+i*i语法树见下图:7. 为句子i+i*i构造两棵语法树，从而证明下述文法G是二义的。:=i|()|:=+|-|*|/解：为句子i+i*i构造的两棵语法树如下： 所以，该文法是二义的。 + i * ii * + iii8. 习题1中的文法GS是二义的吗？为什么？答：是二义的。因为对于句子abc可以有两种不同的生成树，即：S=Ac=abc和S=aB=abc11. 令文法GE为：ET|E+T|E-TTF|T*F|T/FF(E)|i证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。解：可为E+T*F构造一棵语法树（见下图），所以它是句型。EE + TT * F从语法树中容易看出，E+T*F的短语有：T*F是句型E+T*F的相对于T的短语，也是相对于规则TT*F的直接短语。E+T*F是句型E+T*F的相对于E的短语。句型E+T*F的句柄（最左直接短语）是T*F。12. 下述文法GE生成的语言是什么？给出该文法的一个句子，该句子至少含五个终结符，构造该句子的语法树。证明：是G的句型，并指出该句型的所有短语、直接短语和句柄。|a|b|c+|-*|/解：(1)计算文法GE的语言：由于L(T)=(a|b|c)(a|b|c)(*|/)n|n=0所以L(E)=L(T)(L(T)(+|-)n|n=0(2)该文法的一个句子是aab*+,它的语法树是： aab*+(3) 证明：是G的句型，并指出该句型的所有短语、直接短语和句柄。由于下面的语法树可以生成，所以它是G的句型。 由于 = ,且 = ,所以是句型相对于的短语，也是相对于规则 的直接短语。由于 = 且 = ,所以是句型相对于的短语。显然，句型的句柄是。13、 一个上下文无关文法生成句子abbaa的语法树如下（1）给出该句子相应的最左、最右推导。（2）该文法产生式的集合可能有哪些元素？（3）找出该句子所有短语、直接短语、句柄。解：(1) 最左推导：S = ABS = aBS = aSBBS = aBBS = abBS = abbS = abbAa = abbaa(2) SABS | Aa |Aa BSBB | b(3) 首先为了区别句子abbaa中的a和b，把它写成a1b1b2a2a3该句子的短语有：a1b1b2a2a3，b1b2，a2a3，a1，a2，b1，b2，直接短语有：a1，a2，b1，b2，句柄：a114. 给出生成下述语言的上下文无关文法：（1）anbnambm|n,m=0（2）1n0m1m0n|n,m=0（3）WaWt|W属于0|a*,W表示Wt的逆解：（1）所求文法为GS=(S,A,a,b,P,S),其中P为：SAAAaAb|（2）所求文法为GS=(S,A,0,1,P,S),其中P为：S1S0|AA0A1|（3）W属于0|a*是指W可以的取值为,0,a,00,a0,aa0,00aa,a0a0,如果W=aa0a00,则Wt=00a0aa。所求文法为GS=(S,P,Q,0,a,P,S),其中P为：S0S0|aSa|a15. 语言WaW和anbmcndm是上下文无关的吗？能看出它们反映程序设计语言的什么特性吗？答：生成语言WaW的文法非常简单，如GS: SWaWWaW|bW|可见GS是上下文无关的。生成语言anbmcndm的文法非常复杂，用上下文无关文法不可能办到，只能用上下文有关文法。这是因为要在ancn的中间插入bm而同时要在其后面插入dm。即a,c相关联，b,d相关联。这说明对语言的限定越多（特别是语言中的符号前后关联越多），生成它的文法越复杂，甚至于很难找到一个上下文法无关文法。16给出生成下述语言的三型文法：(1)an|n=0(2)anbm|n,m=1(3)anbmck|n,m,k=0解：(1) 生成的3型文法是：GS：SaS|(2) 生成的2型文法是：GS: SABAaA|aBbB|b生成的3型文法是：GS：SaPPaP|bDDbD|(3) 生成的2型文法是：GS: SABCAaA|BbB|C-cC|生