编译原理第2章习题解答.doc

第二章 习题解答2.1该文法定义的是0到9这10个数字0，1，2，3，4，5，6，7，8，9;同;该文法定义的是bna2n0;2.2因为语言的句子要求由3的整数倍的a组成，所以在构造产生式时，要保证每次产生的a的个数是3。得到文法 GS：Saaa|Saaa因为符号串中a、b的个数没有直接关系，所以，将句子分成两部分：an和b2m1，分别进行构造，然后再合并。可由产生式 Aa|aA得到an。而由产生式 Bb|bbB得到b2m1。由于n1，m1，所以得到文法 GS：SAB Aa|aA Bb|bbB因为句子中，a和b的个数一样多，且a全部在句子的前半部分，b全部在句子的后半部分，所以在构造产生式时，可让a和b对称出现。得文法 GS：SaSb|ab因为句子中a、b、c的个数没有直接关系，所以分别构造生成an、bm、ck的产生式，然后再合成。可由产生式 AaA|e得到an。而由产生式 BbB|e得到bm。再由产生式 CcC|e得到ck。所以得到文法 GS： SABC AaA|e BbB|e CcC|e文法为GS：S(+|)(ABC|2|4|6|8)|0 C0|2|4|6|8 BBA|B0|e A1|2|3|9能被5整除的整数的末位数必定是0或5。所以只要保证生成的整数末位数字是0或5即可。据此，构造描述能被5整除的整数集合的文法如下：GS：S(+|-)A(0|5)A0|1|2|3|4|5|6|7|8|9|AA如果还要求整数除0外，均不以0开头，则文法为GS：S(+|-)(A(0|5)|0|5) AAB|C B0|C|BB C1|2|3|4|5|6|7|8|9由于文法的句子aa, b+，因此文法的句子可分解为两种情形： 以a打头的符号串； 以b打头的符号串。于是只要在构造产生式时保证每次产生相同个数的a和b即可。可以构造文法如下。GS：SaSbS|bSaS|ab|ba或GS：SaSb|bSa|abS|Sab|baS|Sba|ab|ba2.3略2.4 0型文法2.5 P=SaDeE，DbF，FcA，EdB，AbC，CeB，Bd2.63274的最左推导为:NNDNDDNDDDDDDD3DDD32DD 327D32743274的最右推导为:NNDN4ND4N74ND74N274 D274327465173的最左推导为:NNDNDDNDDDNDDDDDDDDD6DDDD 65DDD651DD6517D6517365173的最右推导为:NNDN3ND3N73ND73N173 ND173N5173D5173651732.7句型 +*TP*i(+ET)的短语有*TP、i、+ET、(+ET)、*i(+ET)、+*TP*i(+ET)句型 +*TP*i(+ET)的简单短语有*TP、i、+ET句型 +*TP*i(+ET)的句柄为*TP2.8要判别文法是否具有二义性，只要判别文法是否定义有这样的句子：该句子对应着两棵(包括两棵)以上语法树，或者说有两个(包括两个)以上不同的最右(左)推导；或者说在对该句子进行规范归约过程中，其规范句型的句柄不唯一。本题文法是二义性的。因为对于句子abc，存在两个不同的最左推导序列： SABabBabc 和 SABaBabc文法是二义性的。因为对于句子123，存在两个不同的最左推导序列：1212134124123和 123421421221232.9产生式EE和FF、GG是有害产生式，应删去。F，P，G三个非终结符号无法推导出终结符号串，因此，它们对应的产生式为无用产生式，应删去。非终结符号Q无法从识别符号推导出来，因此，Q所对应的产生式也为无用产生式，也应删去。由于删去了F所对应的产生式后，S也无法从识别符号推导出来，故也应删去。压缩后的文法为GZ： ZE+T ET TT*i|i使其不含有形如AB(A、B均为非终结符号)的产生式。将M代入F，然后将改写后的F代入T，最后将改写后的T代入S，于是将文法改为GS：SaFbT|Tcb|Fa