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

《編譯原理復(fù)習(xí)例題》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫(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

5、]{a2kbc

6、k>0}[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、*10．過(guò)程的DISPLAY表是用于存取過(guò)程的。[A]非局部變量[B]嵌套層次[C]返回地址[D]入口地址-8-二填空題1．詞法分析階段的任務(wù)式從左到右掃描　字符流　，從而逐個(gè)識(shí)別一個(gè)個(gè)的單詞　。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ò)程稱為規(guī)范歸約，也稱為最左歸約。4．符號(hào)表的每一項(xiàng)是由名字欄和兩個(gè)欄目組成。在目標(biāo)代碼生成階段，符號(hào)表是的依據(jù)。三判斷題（認(rèn)為正確的填“T”，錯(cuò)的填“F”）【】1．同心集的合并有可

15、能產(chǎn)生“歸約/歸約”沖突?！尽?．一個(gè)文法所有句子的集合構(gòu)成該文法定義的語(yǔ)言?！尽?．非終結(jié)符可以有綜合屬性，但不能有繼承屬性?！尽?．逆波蘭表示法表示表達(dá)式時(shí)無(wú)需使用括號(hào)?！尽?．一個(gè)有窮自動(dòng)機(jī)有且只有一個(gè)終態(tài)。【】6．若過(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)。（

22、1）對(duì)于輸入串i+i*i給出一個(gè)最左推導(dǎo)；（2）該文法是否是二義性文法？請(qǐng)證明你的結(jié)論。解：（1）i+i*i的最左推導(dǎo)：S=>S+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型）。-8-解：G:S→AB

24、AA→aAb

25、abB→cB

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

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

28、aBB→bB

29、bCC→cC

30、c5．將文

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

32、aB→bB

33、b解：G:S→dAA→aA

34、aBB→bB

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

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)確

50、定有限自動(dòng)機(jī)；解：將（1）所得的非確定有限自動(dòng)機(jī)確定化εab-01131221+3ab-8--+013123+12312313+13123012aaba-+++（3）構(gòu)造R的相應(yīng)最小確定有限自動(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、*

61、abb*aa*b

62、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ī)式為：b(a

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

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

65、EE?bE’E’?Ecc

66、ccSelect(S?aS)∩