編譯復(fù)習(xí)例題

編譯復(fù)習(xí)例題

ID:20624217

大?。?79.50 KB

頁(yè)數(shù):8頁(yè)

時(shí)間:2018-10-14

編譯復(fù)習(xí)例題_第1頁(yè)
編譯復(fù)習(xí)例題_第2頁(yè)
編譯復(fù)習(xí)例題_第3頁(yè)
編譯復(fù)習(xí)例題_第4頁(yè)
編譯復(fù)習(xí)例題_第5頁(yè)
資源描述:

《編譯復(fù)習(xí)例題》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、編譯原理復(fù)習(xí)例題(有些內(nèi)容沒(méi)有覆蓋,比如優(yōu)化、SLR(1)、LR(1)、LALR(1)等。但要求至少要按照作業(yè)題的范圍復(fù)習(xí)。)一選擇題1.編譯的各階段工作都涉及。[A]詞法分析[B]表格管理[C]語(yǔ)法分析[D]語(yǔ)義分析2.型文法也稱為正規(guī)文法?!A]0[B]1[C]2[D]33.文法不是LL(1)的?!A]遞歸[B]右遞歸[C]2型[D]含有公共左因子的4.文法E→E+E

2、E*E

3、i的句子i*i+i*i有棵不同的語(yǔ)法樹(shù)?!A]1[B]3[C]5[D]75.文法S→aaS

4、abc定義的語(yǔ)言是。[A]{a2kbc

5、k>0}

6、[B]{akbc

7、k>0}[C]{a2k-1bc

8、k>0}[D]{akakbc

9、k>0}6.若B為非終結(jié)符,則A→a.Bb為。[A]移進(jìn)項(xiàng)目[B]歸約項(xiàng)目[C]接受項(xiàng)目[D]待約項(xiàng)目7.同心集合并可能會(huì)產(chǎn)生新的沖突。[A]二義[B]移進(jìn)/移進(jìn)[C]移進(jìn)/歸約[D]歸約/歸約8.代碼優(yōu)化時(shí)所依據(jù)的是。[A]語(yǔ)法規(guī)則[B]詞法規(guī)則[C]等價(jià)變換規(guī)則[D]語(yǔ)義規(guī)則9.表達(dá)式a-(-b)*c的逆波蘭表示(@為單目減)為。[A]a-b@c*[B]ab@c*-[C]ab@-[D]ab@c-*10.過(guò)程的DISPLAY表是用于存取過(guò)程的。

10、[A]非局部變量[B]嵌套層次[C]返回地址[D]入口地址-8-二填空題1.詞法分析階段的任務(wù)式從左到右掃描  ,從而逐個(gè)識(shí)別 。2.對(duì)于文法G[E]:E→T

11、E+TT→F

12、T*FF→P^F

13、PP→(E)

14、i,句型T+T*F+i的句柄是  。3.最右推導(dǎo)的逆過(guò)程稱為,也稱為。4.符號(hào)表的每一項(xiàng)是由名字欄和兩個(gè)欄目組成。在目標(biāo)代碼生成階段,符號(hào)表是的依據(jù)。三判斷題(認(rèn)為正確的填“T”,錯(cuò)的填“F”)【】1.同心集的合并有可能產(chǎn)生“歸約/歸約”沖突?!尽?.一個(gè)文法所有句子的集合構(gòu)成該文法定義的語(yǔ)言?!尽?.非終結(jié)符可以有綜合屬

15、性,但不能有繼承屬性?!尽?.逆波蘭表示法表示表達(dá)式時(shí)無(wú)需使用括號(hào)?!尽?.一個(gè)有窮自動(dòng)機(jī)有且只有一個(gè)終態(tài)?!尽?.若過(guò)程p第k次被調(diào)用,則p的DISPLAY表中就有k+1個(gè)元素。四解答題1.給定文法G和句型(T+F)*i+T,G:E→E+T

16、TT→T*F

17、FF→(E)

18、i(1)畫(huà)出句型的語(yǔ)法樹(shù);(2)寫(xiě)出句型的全部短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄。解:(略)2.設(shè)有文法G:S→S+S

19、S*S

20、i

21、(S)。(1)對(duì)于輸入串i+i*i給出一個(gè)最左推導(dǎo);(2)該文法是否是二義性文法?請(qǐng)證明你的結(jié)論。解:(1)i+i*i的最左推導(dǎo):S=>S+

22、S=>i+S=>i+S*S=>i+i*S=>i+i*i(2)該文法是二義性的。因?yàn)閷?duì)于句子i+i*i可以畫(huà)出兩棵語(yǔ)法樹(shù)(語(yǔ)法樹(shù)略)。3.給出語(yǔ)言{ambmcn

23、m≥1,n≥0}的上下文無(wú)關(guān)文法(2型)。解:G:S→AB

24、AA→aAb

25、ab-8-B→cB

26、c4.給出語(yǔ)言{akbmcn

27、k,m,n≥1}的正規(guī)文法(3型)。解:G:A→aA

28、aBB→bB

29、bCC→cC

30、c5.將文法G改寫(xiě)成等價(jià)的正規(guī)文法(3型)。G:S→dABA→aA

31、aB→bB

32、b解:G:S→dAA→aA

33、aBB→bB

34、b6.構(gòu)造一文法產(chǎn)生任意長(zhǎng)的a,b串,使得

35、

36、a

37、≤

38、b

39、≤2

40、a

41、其中,“

42、a

43、”和“

44、b

45、”分別表示串中的字符a和b的個(gè)數(shù)。解:b的個(gè)數(shù)在a的個(gè)數(shù)和其2倍之間,串的結(jié)構(gòu)形如aSBS和BSaS,其中B為1或2個(gè)b。故得文法G:S→aSBS

46、BSaS

47、εB→b

48、bb7.設(shè)有字母表{a,b}上的正規(guī)式R=(ab

49、a)*。(1)構(gòu)造R的相應(yīng)有限自動(dòng)機(jī);解:0123baaεε-+(2)構(gòu)造R的相應(yīng)確定有限自動(dòng)機(jī);解:將(1)所得的非確定有限自動(dòng)機(jī)確定化εab-01131221+3ab-+013123-8-+12312313+13123012aaba-+++(3)構(gòu)造R的相應(yīng)

50、最小確定有限自動(dòng)機(jī);解:對(duì)(2)得到的DFA化簡(jiǎn),合并狀態(tài)0和2為狀態(tài)2:12aab-++(4)構(gòu)造與R等價(jià)的正規(guī)文法解:令狀態(tài)1和2分別對(duì)應(yīng)非終結(jié)符B和AG:A→aB

51、a

52、εB→aB

53、bA

54、a

55、b

56、ε可化簡(jiǎn)為:G:A→aB

57、εB→aB

58、bA

59、ε8.寫(xiě)出如圖所示的自動(dòng)機(jī)描述的語(yǔ)言的正規(guī)式1324babab-+0aa+解:abb*

60、abb*aa*b

61、aaa*b9.寫(xiě)出在{a,b}上,不以a開(kāi)頭,但以aa結(jié)尾的字符串集合的正規(guī)式(并構(gòu)造與之等價(jià)的最簡(jiǎn)DFA)。解:依題意,“不以a開(kāi)頭”,則必以b開(kāi)頭,又要“以aa結(jié)尾”,故正規(guī)式

62、為:b(a

63、b)*aa(構(gòu)造與之等價(jià)的最簡(jiǎn)DFA,此略)10.寫(xiě)一個(gè)LL(1)文法G,使其語(yǔ)言是-8-L(G)={ambnc2n

64、m>=0,n>0}并證明文法是LL(1)。解:文法G(S):S?aS

65、EE?bE’E’?Ecc

66、ccSelect(S?aS)∩Select(S?E)=ФSele

當(dāng)前文檔最多預(yù)覽五頁(yè),下載文檔查看全文

此文檔下載收益歸作者所有

當(dāng)前文檔最多預(yù)覽五頁(yè),下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動(dòng)畫(huà)的文件,查看預(yù)覽時(shí)可能會(huì)顯示錯(cuò)亂或異常,文件下載后無(wú)此問(wèn)題,請(qǐng)放心下載。
2. 本文檔由用戶上傳,版權(quán)歸屬用戶,天天文庫(kù)負(fù)責(zé)整理代發(fā)布。如果您對(duì)本文檔版權(quán)有爭(zhēng)議請(qǐng)及時(shí)聯(lián)系客服。
3. 下載前請(qǐng)仔細(xì)閱讀文檔內(nèi)容,確認(rèn)文檔內(nèi)容符合您的需求后進(jìn)行下載,若出現(xiàn)內(nèi)容與標(biāo)題不符可向本站投訴處理。
4. 下載文檔時(shí)可能由于網(wǎng)絡(luò)波動(dòng)等原因無(wú)法下載或下載錯(cuò)誤,付費(fèi)完成后未能成功下載的用戶請(qǐng)聯(lián)系客服處理。