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

《編譯原理復(fù)習(xí)例題.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、編譯原理復(fù)習(xí)例題(有些內(nèi)容沒有覆蓋，比如優(yōu)化、SLR（1）、LR（1）、LALR（1）等。但要求至少要按照作業(yè)題的范圍復(fù)習(xí)。)一選擇題1．編譯的各階段工作都涉及。[A]詞法分析[B]表格管理[C]語法分析[D]語義分析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有棵不同的語法樹。　[A]1[B]3[C]5[D]75．文法S→aaS

4、abc定義的語言是

5、。[A]{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]移進項目[B]歸約項目[C]接受項目[D]待約項目7．同心集合并可能會產(chǎn)生新的沖突。[A]二義[B]移進/移進[C]移進/歸約[D]歸約/歸約8．代碼優(yōu)化時所依據(jù)的是。[A]語法規(guī)則[B]詞法規(guī)則[C]等價變換規(guī)則[D]語義規(guī)則9．表達式a-(-b)*c的逆波蘭表示（@為單目減）為。[A]a-b@c*[B]ab@c*-[C]ab@-[D

10、]ab@c-*10．過程的DISPLAY表是用于存取過程的。[A]非局部變量[B]嵌套層次[C]返回地址[D]入口地址-8-二填空題1．詞法分析階段的任務(wù)式從左到右掃描　字符流　，從而逐個識別一個個的單詞　。2．對于文法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．符號表的每一項是由名字欄和兩個欄目組成。在目標代碼生成階段，符號表是的依據(jù)。三判斷題（認為正確的填“T”，錯的填“F”）【】1

15、．同心集的合并有可能產(chǎn)生“歸約/歸約”沖突?！尽?．一個文法所有句子的集合構(gòu)成該文法定義的語言?！尽?．非終結(jié)符可以有綜合屬性，但不能有繼承屬性。【】4．逆波蘭表示法表示表達式時無需使用括號。【】5．一個有窮自動機有且只有一個終態(tài)?！尽?．若過程p第k次被調(diào)用，則p的DISPLAY表中就有k+1個元素。四解答題1．給定文法G和句型(T+F)*i+T,G:E→E+T

16、TT→T*F

17、FF→(E)

18、i（1）畫出句型的語法樹；（2）寫出句型的全部短語、簡單短語和句柄。解：（略）2．設(shè)有文法G：S→S+S

19、

20、S*S

21、i

22、(S)。（1）對于輸入串i+i*i給出一個最左推導(dǎo)；（2）該文法是否是二義性文法？請證明你的結(jié)論。解：（1）i+i*i的最左推導(dǎo)：S=>S+S=>i+S=>i+S*S=>i+i*S=>i+i*i（2）該文法是二義性的。因為對于句子i+i*i可以畫出兩棵語法樹（語法樹略）。3．給出語言{ambmcn

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

24、AA→aAb

25、abB→cB

26、c4．給出語言{akbmcn

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

28、aBB→

29、bB

30、bCC→cC

31、c5．將文法G改寫成等價的正規(guī)文法（3型）。G:S→dABA→aA

32、aB→bB

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

34、aBB→bB

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

36、a

37、≤

38、b

39、≤2

40、a

41、其中，“

42、a

43、”和“

44、b

45、”分別表示串中的字符a和b的個數(shù)。解：b的個數(shù)在a的個數(shù)和其2倍之間，串的結(jié)構(gòu)形如aSBS和BSaS，其中B為1或2個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)有限自動機；解：012

50、3baaεε-+（2）構(gòu)造R的相應(yīng)確定有限自動機；解：將（1）所得的非確定有限自動機確定化εab-01131221+3ab-8--+013123+12312313+13123012aaba-+++（3）構(gòu)造R的相應(yīng)最小確定有限自動機；解：對（2）得到的DFA化簡，合并狀態(tài)0和2為狀態(tài)2：12aab-++（4）構(gòu)造與R等價的正規(guī)文法解：令狀態(tài)1和2分別對應(yīng)非終結(jié)符B和AG:A→aB

51、a

52、εB→aB

53、bA

54、a

55、b

56、ε可化簡為：G:A→aB

57、εB→aB

58、bA

59、ε8．寫出如圖所示的自動機描述的語言的正規(guī)

60、式1324babab-+0aa+解：abb*

61、abb*aa*b

62、aaa*b9．寫出在{a,b}上，不以a開頭，但以aa結(jié)尾的字符串集合的正規(guī)式（并構(gòu)造與之等價的最簡DFA）。解：依題意，“不以a開頭”，則必以b開頭，又要“以aa結(jié)尾”，故正規(guī)式為：b(a

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

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

65、EE?bE’E’?Ecc

66、ccSelect(S?aS)∩