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

1第三章文法和语言课后习题参考答案1.L(G)={abc}2.L(G[N])是无符号整数。3.G3:E→D+E|D-E|DD→0|1|2|3|4|5|6|7|8|94.L(G[Z])={anbn|n0}5.写一文法，使其语言是偶正整数的集合要求：(1)允许0打头(2)不允许0打头解：(1)G[S]=({S,P,D,N},{0,1,2,…,9},P,S)P:SPD|DP-NP|ND0|2|4|6|8N-0|1|2|3|4|5|6|7|8|9(2)G[S]=({S,P,R,D,N,Q},{0,1,2,…,9},P,S)P:SPD|P0|DP-NR|NR-QR|QD2|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*i2语法树见下图:7.为句子i+i*i构造两棵语法树，从而证明下述文法G[表达式]是二义的。表达式::=i|(表达式)|表达式运算符表达式运算符::=+|-|*|/解：为句子i+i*i构造的两棵语法树如下：所以，该文法是二义的。表达式项因子i表达式项因子(表达式)项因子i表达式项项*因子因子ii表达式表达式+项项项*因子因子ii因子i表达式表达式+项项因子i因子(表达式)表达式+项项因子i因子i表达式表达式+项项因子i项*因子因子ii(1)i(2)(i)(3)i*i(4)i*i+i(5)i+(i+i)(6)i+i*i表达式表达式+表达式i表达式*表达式ii表达式表达式*表达式表达式+表达式iii38.习题1中的文法G[S]是二义的吗？为什么？答：是二义的。因为对于句子abc可以有两种不同的生成树，即：S=Ac=abc和S=aB=abc11.令文法G[E]为：ET|E+T|E-TTF|T*F|T/FF(E)|i证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。解：可为E+T*F构造一棵语法树（见下图），所以它是句型。从语法树中容易看出，E+T*F的短语有：T*F是句型E+T*F的相对于T的短语，也是相对于规则TT*F的直接短语。E+T*F是句型E+T*F的相对于E的短语。句型E+T*F的句柄（最左直接短语）是T*F。12.下述文法G[E]生成的语言是什么？给出该文法的一个句子，该句子至少含五个终结符，构造该句子的语法树。证明：ETFMOPPOP是G[E]的句型，并指出该句型的所有短语、直接短语和句柄。EETPOP|TTTFMOP|FFa|b|cPOP+|-MOP*|/解：(1)计算文法G[E]的语言：由于L(T)={(a|b|c)((a|b|c)(*|/))n|n=0}所以L(E)={L(T)(L(T)(+|-))n|n=0}(2)该文法的一个句子是aab*+,它的语法树是：(3)证明：ETFMOPPOP是G[E]的句型，并指出该句型的所有短语、直接短语和句柄。EE+TT*FEETPOPTFMOPTFaFab*+4由于下面的语法树可以生成ETFMOPPOP，所以它是G[E]的句型。由于E=ETPOP,且T=TFMOP,所以TFMOP是句型ETFMOPPOP相对于T的短语，也是相对于规则TTFMOP的直接短语。由于E=E且E=ETFMOPPOP,所以ETFMOPPOP是句型ETFMOPPOP相对于E的短语。显然，句型ETFMOPPOP的句柄是TFMOP。13、一个上下文无关文法生成句子abbaa的语法树如下（1）给出该句子相应的最左、最右推导。（2）该文法产生式的集合可能有哪些元素？（3）找出该句子所有短语、直接短语、句柄。解：(1)最左推导：S=ABS=aBS=aSBBS=aBBS=abBS=abbS=abbAa=abbaa(2)S—ABS|Aa|εA—aB—SBB|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）所求文法为G[S]=({S,A},{a,b},P,S),其中P为：SAAAaAb|ε（2）所求文法为G[S]=({S,A},{0,1},P,S),其中P为：S1S0|AEETPOPTFMOP5A0A1|ε（3）W属于{0|a}*是指W可以的取值为{ε,0,a,00,a0,aa0,00aa,a0a0,…}如果W=aa0a00,则Wt=00a0aa。所求文法为G[S]=({S,P,Q},{0,a},P,S),其中P为：S0S0|aSa|a15.语言{WaW}和{anbmcndm}是上下文无关的吗？能看出它们反映程序设计语言的什么特性吗？答：生成语言{WaW}的文法非常简单，如G[S]:SWaWWaW|bW|ε可见G[S]是上下文无关的。生成语言{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型文法是：G[S]：SaS|ε(2)生成的2型文法是：G[S]:SABAaA|aBbB|b生成的3型文法是：G[S]：SaPPaP|bDDbD|ε(3)生成的2型文法是：G[S]:SABCAaA|εBbB|εC-cC|ε生成的3型方法是：G[S]：AaA|bB|cC|εBbB|cC|εCcC|ε17、习题6、习题7和习题7中的文法所描述的语言都是由变量i、+、-、*、/、（和）组成算术表达式，因此它们之间是等价的。19.刻画语言的语法有文法、正则式和自动机等方式。6