1、- -/16.已知文法GS:Salablb求該文法所定義的語言。答：從規(guī)則2可推出：a,aa,aaa,從規(guī)則3可推出：b,bb,bbb,再從規(guī)則1可推出句子：ab,aab,aabb,aaab,abbb,即，從S出發(fā)可推出多個(gè)a后跟多個(gè)b的字符串，且a的個(gè)數(shù)與b的個(gè)數(shù)不盡相同。故：L(G)=ambnlm,n三1.考慮下面上下文無關(guān)文法GS：S-SS*|SS+|a(1)對(duì)于符號(hào)串a(chǎn)a+a*分別給出最左推導(dǎo)和最右推導(dǎo)過程，并為該串構(gòu)造語法樹。(2)GS的語言是什么？答：此文法生成串a(chǎn)a+a*的最右推導(dǎo)：S=SS*=SS*=Sa*=SS+a*=Sa+a*=aa+a*此文法生成串a(chǎn)a+a*的最左推導(dǎo)：S

2、=SS*=SS+S*=*=aS+S*=aa+S*=aa+a*(2)該文法生成的語言是：*和+的后綴表達(dá)式，即逆波蘭式。7令文法G為NfDINDDf0I1I2I3I4I5I6I7I8I9G的語言L(G)是什么？(2)給出句子0127、34和568的最左推導(dǎo)和最右推導(dǎo)。答：NNnNDnNDDnNDDDnNDDDDnDDD.L(G)=d(n+k)N0,de0,1,9允許以0開頭的自然數(shù)(十進(jìn)制無符號(hào)整數(shù))；0127最左推導(dǎo)：NnNDnNDDnNDDDnDDDDn0DDDn01DDn012Dn01270127最右推導(dǎo)：NnNDnN7nND7nN27nND27nN127nD127n01278寫一個(gè)文法，

3、使其語言是奇數(shù)集，且每個(gè)奇數(shù)不以0開頭。答：(首先分析題意，本題是希望構(gòu)造一個(gè)文法，由它產(chǎn)生的句子是奇數(shù)，并且不以0開頭，也就是說它的每個(gè)句子都是以1、3、5、7、9中的某個(gè)數(shù)結(jié)尾。如果數(shù)字只有一位，則1、3、5、7、9就滿足要求，如果有多位，則要求第1位不能是0，而中間有多少位，每位是什么數(shù)字(必須是數(shù)字)則沒什么要求，因此，我們可以把這個(gè)文法分3部分來完成。分別用3個(gè)非終結(jié)符來產(chǎn)生句子的第1位、中間部分和最后一位。引入幾個(gè)非終結(jié)符，其中，一個(gè)用作產(chǎn)生句子的開頭，可以是19之間的數(shù)，不包括0；一個(gè)用來產(chǎn)生句子的結(jié)尾，為奇數(shù)；另一個(gè)則用來產(chǎn)生以非0整數(shù)開頭后面跟任意多個(gè)數(shù)字的數(shù)字串，進(jìn)行分解之

4、后，這個(gè)文法就很好寫了。)令S表示不以0開始的奇數(shù)集合。S奇數(shù)頭整數(shù)奇數(shù)尾I奇數(shù)頭奇數(shù)尾I奇數(shù)尾奇數(shù)尾1I3I5I7I9奇數(shù)頭2I4I6I8I奇數(shù)尾整數(shù)整數(shù)數(shù)字I數(shù)字?jǐn)?shù)字0I奇數(shù)頭9寫一個(gè)上下文無關(guān)文法CFG,使其語言是能被5整除且不以0開頭的無符號(hào)整數(shù)的集合。(如5,10,15,.)答：能被5整除的數(shù)從形式上看，是以0和5結(jié)尾的數(shù)字串。題目要求的不以0開頭，并要注意0不是該語言的句子。所求文法為：G（S）：SfMFI5FTI0MfMDINDfNI0Nf1I2I3I4I5I6I7I8I910證明下面的文法是二義的：SiSeSIiSIi答：（根據(jù)文法的二義性的定義，如果要證明該文法是二義的，必須

5、找到一個(gè)句子，使得該句子具有兩個(gè)不同的最右推導(dǎo)或兩個(gè)不同的語法樹。我們首先分析這個(gè)文法，根據(jù)我們對(duì)程序語言的了解，不難發(fā)現(xiàn)，這個(gè)文法應(yīng)該是用來表示if：else.結(jié)構(gòu)的（用“i”代表“if”或語句集，“e”代表“else”）。因此我們就要到if.else結(jié)構(gòu)中去找二義性。我們知道，程序語言一般都規(guī)定else部分是和它前面離它最近的沒有被匹配的的if語句進(jìn)行匹配。而上面的這個(gè)文法體現(xiàn)不出這種限制，因此我們可以找這樣一個(gè)句子，在else前面有兩個(gè)if（如句子iiiei）,else和不同的if進(jìn)行匹配時(shí)就會(huì)產(chǎn)生不同的語義。）解答：考慮句子iiiei,存在如下兩個(gè)最右推導(dǎo)：S=iSeS=iSei=ii

6、Sei=iiieiS=iS=iiSeS=iiSei=iiiei11某程序設(shè)計(jì)語言的表達(dá)式由運(yùn)算符1、2、3、標(biāo)識(shí)符、（、）組成，其中1和2的優(yōu)先級(jí)相同，3的優(yōu)先級(jí)低于1、2的優(yōu)先級(jí)，優(yōu)先級(jí)相同的運(yùn)算符從右往左計(jì)算，可以用括號(hào)改變運(yùn)算的順序，則下述四種文法中哪一個(gè)可以描述上述的表達(dá)式文法？設(shè)E為識(shí)別符號(hào)，終結(jié)符號(hào)集=1、2、3、（、）、I,非終結(jié)符號(hào)集=E、T、F。ETE1TE2TTFT3FF（E）IETT1ET2ETFF3TF（E）IETE3T(E)d.ETT3E(E)d.ETT3E1T2T(E)答：（對(duì)于一個(gè)包含運(yùn)算符的語言，運(yùn)算符的結(jié)合順序、運(yùn)算符的優(yōu)先級(jí)在文法中反映為遞歸的方向和推導(dǎo)（或規(guī)約）的先后，左遞歸表明左邊的運(yùn)算先處理，對(duì)應(yīng)的運(yùn)算符左結(jié)合；右遞歸表明右邊的運(yùn)算先處理，對(duì)應(yīng)的運(yùn)算符右結(jié)合。兩個(gè)運(yùn)算符連續(xù)出現(xiàn)，后推導(dǎo)出（或先被規(guī)約）的，表明其運(yùn)算先被處理，因此優(yōu)先級(jí)高；反之，先推導(dǎo)出（或后被規(guī)約）的，表明其運(yùn)算后被處理，因此優(yōu)先級(jí)低。）題意要求：1和2的優(yōu)先級(jí)相同，3的優(yōu)先級(jí)低于1、2的優(yōu)先級(jí)，因此3比1、2先推導(dǎo)出來，即應(yīng)為圖3所示的四種情形。UUUUUUUUU3VVVV12(2)(3)U(1)UUUUUUUUU3VVVV12(2)(3)U(1)(4)圖3可能的文法推導(dǎo)順序