编译原理 第二章习题答案.docx

编译原理 第二章习题答案第2章 习题解答 1.文法GS为： S->Ac|aB A->ab B->bc 写出L(GS)的全部元素。 答案 S=>Ac=>abc 或S=>aB=>abc 所以L(GS)=abc = 2. 文法GN为： N->D|ND D->0|1|2|3|4|5|6|7|8|9 GN的语言是什么？ 答案 GN的语言是V+。V=0,1,2,3,4,5,6,7,8,9 N=>ND=>NDD. =>NDDDD.D=>D.D = 3.已知文法GS： SdAB AaA|a B|bB 问：相应的正规式是什么？GS能否改写成为等价的正规文法？ 答案 正规式是daa*b*； 相应的正规文法为(由自动机化简来)： GS:SdA Aa|aB BaB|a|b|bC CbC|b 也可为(观察得来):GS:SdA Aa|aA|aB BbB| = 4.已知文法GZ： Z->aZb|ab 写出L(GZ)的全部元素。 答案 Z=>aZb=>aaZbb=>aaa.Z.bbb=> aaa.ab.bbb L(GZ)=anbn|n>=1 = 5.给出语言anbncm|n>=1,m>=0的上下文无关文法。 分析 本题难度不大，主要是考上下文无关文法的基本概念。上下文无关文法的基本定义是：A->,AVn，*，注意关键问题是保证anbn的成立，即“a与b的个数要相等”，为此，可以用一条形如A->aAb|ab的产生式即可解决。 答案 构造上下文无关文法如下： S->AB|A A->aAb|ab B->Bc|c 扩展 凡是诸如此类的题都应按此思路进行，本题可做为一个基本代表。基本思路是这样的： 要求符合abc，因为a与b要求个数相等，所以把它们应看作一个整体单元进行，而cm做为另一个单位，初步产生式就应写为S->AB，其中A推出anbn，B推出cm。因为m可为0，故上式进一步改写为S->AB|A。接下来考虑A,凡是要求两个终结符个数相等的问题，都应写为A->aAb|ab形式，对于B就很容易写成B->Bc|c了。 = 6 .写一文法，使其语言是偶正整数集合。 要求： (1)允许0开头； (2)不允许0开头。 答案 (1)允许0开头的偶正整数集合的文法 E->NT|G|SFM T->NT|G N->D|1|3|5|7|9 D->0|G G->2|4|6|8 S->NS| F->1|3|5|7|9|G M->M0|0 (2)不允许0开头的偶正整数集合的文法 E->NT|D T->FT|G nnmN->D|1|3|5|7|9 D->2|4|6|8 F->N|0 G->D|0 = 7.已知文法G： 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) 8 .为句子i+i*i构造两棵语法树，从而证明下述文法G<表达式>是二义的。 表达式->表达式运算符表达式|(表达式)|i 运算符->+|-|*|/ 答案 可为句子i+i*i构造两个不同的最右推导: 最右推导1 表达式=>表达式运算符表达式 =>表达式运算符i =>表达式* i =>表达式运算符表达式* i =>表达式运算符i * i =>表达式+ i * i => i + i * i 最右推导2 表达式=>表达式运算符表达式 =>表达式运算符表达式运算符表达式> =>表达式运算符表达式运算符 i =>表达式运算符表达式 * i => 表达式运算符i * i =>表达式+ i * i => i + i * i 所以，该文法是二义的。 = 9. 文法GS为： S->Ac|aB A->ab B->bc 该文法是否为二义的？为什么？ 答案 对于串abc (1)S=>Ac=>abc (2)S=>aB=>abc 即存在两不同的最右推导 所以，该文法是二义的。 = 10.考虑下面上下文无关文法： S->SS*|SS+|a (1)表明通过此文法如何生成串aa+a*，并为该串构造语法树。 (2) GS的语言是什么？ 答案 (1)此文法生成串aa+a*的最右推导如下 S=>SS*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a* (2)该文法生成的语言是即加法和乘法的逆波兰式, = 11. 令文法GE为: E->E+T|E-T T->T*F|T/F|F F->(E)|I 证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。 答案 此句型对应语法树如右，故为此文法一个句型。 或者：因为存在推导序列: E=>E+T=>E+T*F，所以 E+T*F句型 此句型相对于E的短语有:E+T*F；相对于T的短语有T*F, 直接短语为：T*F；。 句柄为：T*F 12.已知文法GE: EET+|T TTF* | F FF | a 试证：FF*是文法的句型，指出该句型的短语、简单短语和句柄. 答案 该句型对应的语法树如下： 该句型相对于E的短语有FF*；相对于T的短语有FF*,F;相对于F的短语有F;F;简单短语有F;F;句柄为F. 13.一个上下文无关文法生成句子abbaa的推导树如下： (1)给出串abbaa最左推导、最右推导。 (2)该文法的产生式集合P可能有哪些元素？ (3)找出该句子的所有短语、直接短语、句柄。 (1)串abbaa最左推导: S=>ABS=>aBS=>aSBBS=>aBBS=>abBS=>abbS=>abbAa=>abbaa 最右推导： S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Abbaa=>abbaa (2)产生式有：SABS |Aa| Aa BSBB|b (3)该句子的短语有a1b1b2a2a3、a1、b1、b2、b1b2、a2a3、a2； 直接短语有a1、b1、b2、a2； 句柄是a1。 = 14.给出生成下列语言的上下文无关文法。 anbnambm |n，m>=0 (2) 1n0m 1m0n| n，m>=0 WaWr|W属于0|a*，Wr表示W的逆 答案 anbnambm| n，m>=0 S->AA A->aAb| (2) 1n0m 1m0n| n，m>=0 S->1S0|A A->0A1| WaWr|W属于0|a*，Wr表示W的逆 S->0S0|1S1| = 15 .给出生成下列语言的三型文法。 (1) a|n >=0 (2) ab|n,m>=1 (3)anbmck|n,m,k>=0 答案 (1) an|n >=0 的三型文法为： S->aS| (2) anbm|n,m>=1 的三型文法为： S->aA A->aA|bB B->bB| (3)anbmck|n,m,k>=0 的三型文法为: A->aA|bB|cC| nmnB->bB|cC| C->cC| = 16.构造一文法产生任意长的a,b串，使得 |a|<=|b|<=2|a| 其中，“|a|”表示a字符的个数;“|b|”表示b字符的个数。 分析 b的个数在a与2a之间，所以应想到形如aSBS和BSaS的形式，B为1到2个b，即可满足条件。 答案 如分析中所述，可得文法如下： S-aSBS|BSaS| B->bb|b 第1个产生式为递归定义，由于在第2个产生式中B被定义为1或2个b，所以第1个产生式可以保证b的个数在|a|与2|a|之间，而a与b的位置可以任意排布，所以此文法即为所求，注意第1个产生式中要包括s。 = 17.下面的文法产生a的个数和b的个数相等的非空a,b串 S->aB|bA B->bS|aBB|b A->aS|bAA|a 其中非终结符B推出b比a的个数多1个的串，A则反之。 说明该文法是二义的。 对上述文法略作修改，使之非二义，并产生同样的语言。 答案 句子aabbab有两种不同的推导。 S=>aB=>aaBB=>aabB=>aabbS=>aabbaB=>aabbab S=>aB=>aaBB=>aabSB=>aabbAB=>aabbaB=>aabbab 即它可以产生两棵不同的语法树，故它是二义的。 修改后的无二义文法如下： S->aBS|bAS|aB|bA B->aBB|b A->bAA|a = 18.给出0，1，2，3型文法的定义。 答案 乔姆斯基(chomsky)把文法分成类型，即0型，1型，2型和3型，0型强于1型，1型强于2型，2型强于3型。 如果它的每个产生式->的结构是*且至少含有一个非终结符,而*，我们说G=是一个0型文法。 0型文法也称短语文法。一个非常重要的理论结果是，0型文法的能力相当于图灵(Tunring)机。或者说，任何0型语言都是递归可枚举的；反之，递归可枚举集必定是一个0型语言。 如果把0型文法分别加上以下的第i条限制，则我们就得i型文法为： 1G的任何产生式-> 均满足|<=|；仅仅S->例外，但S不得出现在任何产生式的右部。 2G的任何产生式为A->，AVn，* 3G的任何产生式为A->aB或A->a，其中A，BVn 1型文法也称上下文有关文法。这种文法意味着，对非终结符进行替换时务必考虑上下文，而且，般不允许替换成空串。 2型文法对非终结符进行替换时无须考虑上下文， 3型文法也称线性文法。