資源描述：
《編譯原理(第2版)陳意云+張昱編著課后答案.》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、編譯原理習(xí)題2003.41目錄chap1基本知識(shí)chap3詞法分析chap4語(yǔ)法分析chap5語(yǔ)法制導(dǎo)翻譯chap6運(yùn)行時(shí)刻環(huán)境chap7中間代碼生成chap8代碼生成2第一章練習(xí)1.1文法S?(L)
2、aL?L,S
3、S(a)指出文法的終結(jié)符號(hào),非終結(jié)符號(hào),開(kāi)始符號(hào).文法的四個(gè)組成部分:終結(jié)符號(hào)VT:語(yǔ)言不可再分的基本符號(hào)非終結(jié)符號(hào)VN:語(yǔ)法范疇(語(yǔ)法概念)開(kāi)始符號(hào)S:最終感興趣的語(yǔ)法范疇產(chǎn)生式P:定義語(yǔ)法范疇的一種書(shū)寫(xiě)形式終結(jié)符號(hào):(,)a非終結(jié)符號(hào):SL開(kāi)始符號(hào):S元語(yǔ)言符號(hào):?表示“定義為”
4、表示“或
5、”3(b)給出句子的分析樹(shù)分析樹(shù):(推導(dǎo)樹(shù))表示一個(gè)句型的推導(dǎo)?(a,(a,a))S(L)L,SS(L)aSa4(c)給出句子的最左推導(dǎo)給出每次推導(dǎo)后得到的句型的短語(yǔ),直接短語(yǔ)最左推導(dǎo)?:推導(dǎo)中任何一步???都是對(duì)?中的最左非終結(jié)lm符號(hào)進(jìn)行替換的推導(dǎo).短語(yǔ)????是文法的句型(S*????)?S*??A?且A+??則?是關(guān)于A的句型???的短語(yǔ).直接短語(yǔ)????是文法的句型(S*????)?S*??A?且A??則?是關(guān)于A的句型???的直接短語(yǔ).句柄:一個(gè)句型的最左直接短語(yǔ)稱(chēng)為句柄.5S?(L)?(L,
6、S)?(S,S)?(a,S)?(a,(L))短語(yǔ)(L)L,SSaa(L,S)S,Sa,Sa,(L)(S,S)(a,S)(a,(L))(L)直接(L)L,SSaa短語(yǔ)(L)?(a,(L,S))?(a,(S,S))?(a,(a,S))?(a,(a,a))短語(yǔ)aaaaa,(L,S)a,(S,S)a,(a,S)a,(a,a)(a,(L,S))(a,(S,S))(a,(a,S))(a,(a,a))L,SSaa(L,S)S,Sa,Sa,a(S,S)(a,S)(a,a)直接aaaa短語(yǔ)L,SSaaa6(d)構(gòu)造各個(gè)句子
7、的最右推導(dǎo).最右推導(dǎo)(規(guī)范推導(dǎo))(e)這個(gè)文法產(chǎn)生的語(yǔ)言是什么?a(a)(a,a)((a,a),a)......a和數(shù)據(jù)元素為a的廣義表全體71.2考慮文法S?aSbS
8、bSaS
9、?(a)試說(shuō)明此文法是二義性的.(定義1.5)如果一文法的句子存在兩棵分析樹(shù),則該句子是二義性的.如果一文法包含二義性的句子,則這個(gè)文法是二義性的.可以從句子abab有兩個(gè)不同的最左推導(dǎo)來(lái)說(shuō)明.S?aSbS?abS?abaSbS?ababS?abablmlmlmlmlmS?aSbS?abSaSbS?abaSbS?ababS?ab
10、ablmlmlmlmlm句子abab有兩個(gè)不同的最左推導(dǎo),該句子是二義性的.所以此文法是二義性的.8(b)對(duì)于句子abab構(gòu)造兩個(gè)相應(yīng)的最右推導(dǎo).S?aSbS?aSb?abSaSb?abSab?ababrmrmrmrmrmS?aSbS?aSbaSbS?aSbaSb?aSbab?ababrmrmrmrmrm(c)對(duì)于句子abab構(gòu)造兩個(gè)相應(yīng)的分析樹(shù).SSaSbSaSbSbSaS??aSbS????(d)此文法產(chǎn)生的語(yǔ)言是什么?由相同個(gè)數(shù)的a和b組成的字符串.91.3考慮文法bexpr?bexprorbter
11、m
12、btermbterm?btermandbfactor
13、bfactorbfactor?notbfactor
14、(bfactor)
15、true
16、false(a)請(qǐng)指出此文法的終結(jié)符號(hào),非終結(jié)符號(hào)和開(kāi)始符號(hào).終結(jié)符號(hào):or,and,not,(,),true,false非終結(jié)符號(hào):bexpr,bterm,bfactor開(kāi)始符號(hào):bexpr10(b)試對(duì)于句子not(trueorfalse)構(gòu)造一棵分析樹(shù).bexprbtermbfactornotbfactor(bexpr)bexprorbtermbtermbfac
17、torbfactorfalsetrue11(c)試說(shuō)明此文法產(chǎn)生的語(yǔ)言是全體布爾表達(dá)式.12練習(xí):長(zhǎng)度為n的字符串,分別有多少個(gè)前綴,后綴,子串,真前綴,子序列?前綴:n+1后綴:n+1子串:1+n+(n-1)+...+1=1+n(n+1)/2真前綴:n子序列:1+Cn1+Cn2+Cn3+...+Cnn=2n13EE+TT*Fi給出句型E+T*i的短語(yǔ),直接短語(yǔ)和句柄EE+TFT*F給出句型F+T*F的短語(yǔ),直接短語(yǔ)和句柄短語(yǔ):i,T*i,E+T*i直接短語(yǔ):i句柄:i短語(yǔ):F,T*F,F+T*F直接短語(yǔ)
18、:F,T*F句柄:F14第三章練習(xí)3.3試描述下列正規(guī)表達(dá)式所表示的語(yǔ)言:(a)0(0
19、1)*0(b)((?
20、0)1*)*由0和1組成且以0開(kāi)始和結(jié)束的符號(hào)串全體.(c)(0
21、1)*0(0
22、1)(0
23、1)由0和1組成的符號(hào)串全體.由0和1組成且以000,001,010或011結(jié)束的符號(hào)串全體.長(zhǎng)度大于等于3且倒數(shù)第3個(gè)字符為0的01符號(hào)串全體.15(d)0*10*10*10*(e)(00
24、11)*((01
25、10)(00
26、11)
