編譯原理習題及答案ppt演示課件

1、.,1,,第一章 緒 論第二章 詞 法 分 析第三章 語 法 分 析,.,2,第一章 緒 論　　1.1 完成下列選擇題：　　(1) 下面敘述中正確的是 ?！　　　．編譯程序是將高級語言程序翻譯成等價的機器語言程序的程序　　　　B．機器語言因其使用過于困難，所以現(xiàn)在計算機根本不使用機器語言　　　　C．匯編語言是計算機唯一能夠直接識別并接受的語言　　　　D．高級語言接近人們的自然語言，但其

2、依賴具體機器的特性是無法改變的,,.,3,(2) 將編譯過程分成若干“遍”是為了 。　　　　A．提高程序的執(zhí)行效率　　　　B．使程序的結構更加清晰　　　　C．利用有限的機器內(nèi)存并提高機器的執(zhí)行效率　　　　D．利用有限的機器內(nèi)存但降低了機器的執(zhí)行效率　　(3) 構造編譯程序應掌握 。 　　　　A．源程序 B．目標語

3、言 　　　　C．編譯方法 D．A～C項,,.,4,(4) 編譯程序絕大多數(shù)時間花在 上。　　　　A．出錯處理 B．詞法分析 　　　　B．目標代碼生成 D．表格管理　　(5) 編譯程序是對 ?！　　．匯編程序的翻譯 B．高級語言程序的解釋執(zhí)行　　　　C．機器語言的執(zhí)行

4、 D．高級語言的翻譯,,.,5,【解答】 　　(1) 編譯程序可以將用高級語言編寫的源程序轉(zhuǎn)換成與之在邏輯上等價的目標程序，而目標程序可以是匯編語言程序或機器語言程序。故選A?！　?2) 分多遍完成編譯過程可使整個編譯程序的邏輯結構更加清晰。故選B?！　?3) 構造編譯程序應掌握源程序、目標語言和編譯方法這三方面內(nèi)容。故選D。,,.,6,(4) 編譯各階段的工作都涉及到構造、查找或更新有關表格，即編譯過程的絕大部

5、分時間都用在造表、查表和更新表格的事務上。故選D。　　(5) 由(1)可知，編譯程序?qū)嶋H上實現(xiàn)了對高級語言程序的翻譯。故選D。,,.,7,1.2 計算機執(zhí)行用高級語言編寫的程序有哪些途徑？它們之間的主要區(qū)別是什么？　　【解答】 計算機執(zhí)行用高級語言編寫的程序主要有兩種途徑：解釋和編譯?！　≡诮忉尫绞较?，翻譯程序事先并不采用將高級語言程序全部翻譯成機器代碼程序，然后執(zhí)行這個機器代碼程序的方法，而是每讀入一條源程序的語句，就將其解

6、釋(翻譯)成對應其功能的機器代碼語句串并執(zhí)行，然后再讀入下一條源程序語句并解釋執(zhí)行，而所翻譯的機器代碼語句串在該語句執(zhí)行后并不保留。這種方法是按源程序中語句的動態(tài)執(zhí)行順序逐句解釋(翻譯)執(zhí)行的，如果一語句處于一循環(huán)體中，則每次循環(huán)執(zhí)行到該語句時，都要將其翻譯成機器代碼后再執(zhí)行。,,.,8,在編譯方式下，高級語言程序的執(zhí)行是分兩步進行的：第一步首先將高級語言程序全部翻譯成機器代碼程序，第二步才是執(zhí)行這個機器代碼程序。因此，編譯對源程序的處

7、理是先翻譯，后執(zhí)行?！　膱?zhí)行速度上看，編譯型的高級語言比解釋型的高級語言要快，但解釋方式下的人機界面比編譯型好，便于程序調(diào)試?！　∵@兩種途徑的主要區(qū)別在于：解釋方式下不生成目標代碼程序，而編譯方式下生成目標代碼程序。,,.,9,1.3 請畫出編譯程序的總框圖。如果你是一個編譯程序的總設計師，設計編譯程序時應當考慮哪些問題？　　【解答】 編譯程序總框圖如圖1-1所示?！　∽鳛橐粋€編譯程序的總設計師，首先要深刻理解被編譯的源

8、語言其語法及語義；其次，要充分掌握目標指令的功能及特點，如果目標語言是機器指令，還要搞清楚機器的硬件結構以及操作系統(tǒng)的功能；第三，對編譯的方法及使用的軟件工具也必須準確化?？傊?，總設計師在設計編譯程序時必須估量系統(tǒng)功能要求、硬件設備及軟件工具等諸因素對編譯程序構造的影響。,,.,10,,圖1-1 編譯程序總框圖,,.,11,第二章 詞 法 分 析　　2.1 完成下列選擇題：　　(1) 詞法分析所依據(jù)的是 。　　　　

9、A．語義規(guī)則 B．構詞規(guī)則 　　　　C．語法規(guī)則 D．等價變換規(guī)則　　(2) 詞法分析器的輸入是 ?！　　　．單詞符號串 B．源程序 　　　　C．語法單位 D．目標程序,,.,12,(3) 詞法分析器的輸出是 ?！　　　．單詞的種別編碼 　　　　　　B．單詞的種別編碼和自身的值　　　　C．單

10、詞在符號表中的位置 　　　　　　D．單詞自身值　　(4) 狀態(tài)轉(zhuǎn)換圖(見圖2-1)接受的字集為 _______?！　　　．以0開頭的二進制數(shù)組成的集合　　　　B．以0結尾的二進制數(shù)組成的集合 　　　　C．含奇數(shù)個0的二進制數(shù)組成的集合 　　　　D．含偶數(shù)個0的二進制數(shù)組成的集合,,.,13,,圖2-1 習題2.1的DFA M,.,14,(5) 對于任一給定的NFA M， 一個DF

11、A M′，使L(M)= L(M′)?！　　　．一定不存在 B．一定存在 　　　　C．可能存在 D．可能不存在　　(6) ?DFA適用于 ?！　　　．定理證明 B．語法分析 　　　　C．詞法分析 D．語義加工,,.,15,(7) 下面用正規(guī)表達式描述詞法的論述中，不正確的是 ?！　　　．詞法規(guī)則簡單，采用正規(guī)表達式已足以描述　　　　B．正規(guī)表達式的表示比

12、上下文無關文法更加簡潔、直觀和易于理解　　　　C．正規(guī)表達式描述能力強于上下文無關文法　　　　D．有限自動機的構造比下推自動機簡單且分析效率高　　(8) 與(a|b)*(a|b)等價的正規(guī)式是 ?！　　　．(a|b) (a|b)* B．a(chǎn)*|b* 　　　　　C．(ab)*(a|b)* D．(a|b)*,,.,16,【解答】　　(1) 由教材第一章1.3節(jié)中的詞法分析，可知詞法分析所遵循的

13、是語言的構詞規(guī)則。故選B?！　?2) 詞法分析器的功能是輸入源程序，輸出單詞符號。故選B?！　?3) 詞法分析器輸出的單詞符號通常表示為二元式：(單詞種別，單詞自身的值)。故選B?！　?4) 雖然選項A、B、D都滿足題意，但選項D更準確。故選D。,,.,17,(5) ?NFA可以有DFA與之等價，即兩者描述能力相同；也即，對于任一給定的NFA M，一定存在一個DFA M'，使L(M)=L(M′)。故選B。　　(6) ?D

14、FA便于識別，易于計算機實現(xiàn)，而NFA便于定理的證明。故選C。　　(7) 本題雖然是第二章的題，但答案參見第三章3.1.3節(jié)。即選C?！　?8) 由于正則閉包R+=R*R=RR*，故(a|b)*(a|b)=(a|b)(a|b)*。故選A。,,.,18,2.2 什么是掃描器？掃描器的功能是什么？　　【解答】 掃描器就是詞法分析器，它接受輸入的源程序，對源程序進行詞法分析并識別出一個個單詞符號，其輸出結果是單詞符號，供語法分析器使

15、用。通常把詞法分析器作為一個子程序，每當語法分析器需要一個單詞符號時就調(diào)用這個子程序。每次調(diào)用時，詞法分析器就從輸入串中識別出一個單詞符號交給語法分析器。,,.,19,2.3 設M=({x,y}, {a,b}, f, x, {y})為一非確定的有限自動機，其中f定義如下：　　 f(x,a)={x,y} f{x,b}={y}　　 f(y,a)= Φ

16、 f{y,b}={x,y}　　試構造相應的確定有限自動機M′。　　【解答】 對照自動機的定義M=(S,Σ,f,?s0,?Z)，由f的定義可知f(x,a)、f(y,b)均為多值函數(shù)，因此M是一非確定有限自動機?！　∠犬嫵鯪FA M相應的狀態(tài)圖，如圖2-2所示。,,.,20,,圖2-2 習題2.3的NFA M,.,21,用子集法構造狀態(tài)轉(zhuǎn)換矩陣，如表2-1所示。 表2-1 狀態(tài)轉(zhuǎn)換矩陣

17、 將轉(zhuǎn)換矩陣中的所有子集重新命名，形成表2-2所示的狀態(tài)轉(zhuǎn)換矩陣，即得到,.,22,將圖2-3所示的DFA M′最小化。首先，將M′的狀態(tài)分成終態(tài)組{1,2}與非終態(tài)組{0}。其次，考察{1,2}。由于{1,2}a={1,2}b={2}?{1,2}，因此不再將其劃分了，也即整個劃分只有兩組：{0}和{1,2}。令狀態(tài)1代表{1,2}，即把原來到達2的弧都導向1，并刪除狀態(tài)2。最后，得到如圖2-4所示的化簡了的DFA M′。,,

18、圖2-3 習題2.3的DFA M′,其狀態(tài)轉(zhuǎn)換圖如圖2-3所示。,.,23,,圖2-4 圖2-3化簡后的DFA M′,.,24,2.4 正規(guī)式(ab)*a與正規(guī)式a(ba)*是否等價？請說明理由?！　　窘獯稹?正規(guī)式(ab)*a對應的NFA如圖2-5所示，正規(guī)式a(ba) *對應的NFA如圖2-6所示。　　用子集法將圖2-5和圖2-6分別確定化為如圖2-7(a)和(b)所示的狀態(tài)轉(zhuǎn)換矩陣，它們最終都可以得到最簡DFA，如圖2

19、-8所示。因此，這兩個正規(guī)式等價。,,.,25,,圖2-5 正規(guī)式(ab)*a對應的NFA,.,26,,圖2-6 正規(guī)式a(ba)*對應的NFA,.,27,,圖2-7 圖2-5和圖2-6確定化后的狀態(tài)轉(zhuǎn)換矩陣,—,.,28,,圖2-8 最簡DFA,.,29,實際上，當閉包*取0時，正規(guī)式(ab) *a與正規(guī)式a(ba)*由初態(tài)X到終態(tài)Y之間僅存在一條a弧。由于(ab)*在a之前，故描述(ab)*的弧應在初態(tài)結點X上；而(ba)*

20、在a之后，故(ba)*對應的弧應在終態(tài)結點Y上。因此，(ab)*a和a(ba)*所對應的NFA也可分別描述為如圖2-9(a)和(b)所示的形式，它們確定化并化簡后仍可得到圖2-8所示的最簡DFA。,,.,30,,圖2-9 (ab)*a和a(ba)*分別對應的NFA,.,31,2.5 設有L(G)={a2n+1b2ma2p+1| n≥0,p≥0,m≥1}?！　?1) 給出描述該語言的正規(guī)表達式；　　(2) 構造識別該語言

21、的確定有限自動機(可直接用狀態(tài)圖形式給出)?！　　窘獯稹?該語言對應的正規(guī)表達式為a(aa)*bb(bb)*a(aa)*，正規(guī)表達式對應的NFA如圖2-10所示。,,.,32,,圖2-10 習題2.5的NFA,.,33,用子集法將圖2-10確定化，如圖2-11所示。由圖2-11重新命名后的狀態(tài)轉(zhuǎn)換矩陣可化簡為(也可由最小化方法得到)　　{0,2} {1} {3,5} {4,6} {7},圖2-11 習題

22、2.5的狀態(tài)轉(zhuǎn)換矩陣,.,34,按順序重新命名為0、1、2、3、4后得到最簡的DFA，如圖2-12所示。,,圖2-12 習題2.5的最簡DFA,.,35,2.6 有語言L={w?|?w∈(0,1)+，并且w中至少有兩個1，又在任何兩個1之間有偶數(shù)個0}，試構造接受該語言的確定有限狀態(tài)自動機(DFA)。　　【解答】 對于語言L，w中至少有兩個1，且任意兩個1之間必須有偶數(shù)個0；也即在第一個1之前和最后一個1之后，對0的個數(shù)沒有要求

23、。據(jù)此我們求出L的正規(guī)式為0*1(00(00)*1)*00(00)*10*，畫出與正規(guī)式對應的NFA，如圖2-13所示。,,.,36,,圖2-13 習題2.6的NFA,.,37,用子集法將圖2-13所示的NFA確定化，如圖2-14所示由圖2-14可看出非終態(tài)2和4的下一狀態(tài)相同，終態(tài)6和8的下一狀態(tài)相同，即得到最簡狀態(tài)為　　{0} {1} {2,4} {3} {5} {6,8} {7},.,38,按順序重

24、新命名為0、1、2、3、4、5、6，則得到最簡DFA，如圖2-15所示。,圖2-15 習題2.6的最簡DFA,.,39,2.7 已知正規(guī)式((a?|?b)*|?aa)*b和正規(guī)式(a?|?b)*b。　　(1) 試用有限自動機的等價性證明這兩個正規(guī)式是等價的；　　(2) 給出相應的正規(guī)文法?！　　窘獯稹?(1) 正規(guī)式((a?|?b)*|?aa)*b對應的NFA如圖2-16所示。　　用子集法將圖2-16所示的NFA確定化為D

25、FA，如圖2-17所示。,,.,40,,圖2-16 正規(guī)式((a?|?b)*|aa)*b對應的NFA,.,41,,圖2-17 圖2-16確定化后的狀態(tài)轉(zhuǎn)換矩陣,.,42,由于對非終態(tài)的狀態(tài)1、2來說，它們輸入a、b的下一狀態(tài)是一樣的，故狀態(tài)1和狀態(tài)2可以合并，將合并后的終態(tài)3命名為2，則得到表2-3(注意，終態(tài)和非終態(tài)即使輸入a、b的下一狀態(tài)相同也不能合并)。由此得到最簡DFA，如圖2-18所示?！　≌?guī)式(a?|?b)*b對應

26、的NFA如圖2-19所示?！　∮米蛹▽D2-19所示的NFA確定化為如圖2-20所示的狀態(tài)轉(zhuǎn)換矩陣。,,.,43,表2-3 合并后的狀態(tài)轉(zhuǎn)換矩陣,.,44,,圖2-18 習題2.7的最簡DFA,.,45,,圖2-19 正規(guī)式(a?|?b)*b對應的NFA,.,46,比較圖2-20與圖2-17，重新命名后的轉(zhuǎn)換矩陣是完全一樣的，也即正規(guī)式(a?|?b)*b可以同樣得到化簡后的DFA如圖2-18所示。因此，兩個自動機完全一樣，即兩

27、個正規(guī)文法等價。,圖2-20 圖2-19確定化后的狀態(tài)轉(zhuǎn)換矩陣,.,47,2.8 構造一個DFA，它接收 Σ ={a,b}上所有不含abb的字符串。解：Σ ={a,b}上所有不含abb的字符串可表示為b*(a*b)a*。,,.,48,2.9構造一個DFA，它接收 Σ ={a,b}上所有含偶數(shù)個a的字符串。解：Σ ={a,b}上所有含偶數(shù)個a的字符串可表示為(b|ab*a)*,,.,49,2.10 下列程序段以B表示循環(huán)體，A表示

28、初始化，I表示增量，T表示測試：　　 I=1;　　 while (I<=n)　　 {　　 sun=sun+a[I];　　 I=I+1;　　 }　　請用正規(guī)表達式表示這個程序段可能的執(zhí)行序列?！　　窘獯稹?用正規(guī)表達式表示程序段可能的執(zhí)行序列為AT(BIT)*。,,.,50,2.9 將圖2-21所示的非確定有限自動機(NFA)變換成等價的確定有限自動機(DF

29、A)?！　∑渲校琗為初態(tài)，Y為終態(tài)。 　【解答】 用子集法將NFA確定化，如圖2-22所示。,,.,51,,圖2-21 習題2.9的NFA,.,52,,圖2-22 習題2.9的狀態(tài)轉(zhuǎn)換矩陣,{2},{2,Y},{2,4},{2},{2,Y},{2,4},{2,4},{2,4},{2,4,Y},{2,4,Y},{2,4,Y},.,53,圖2-22所對應的DFA如圖2-23所示。　　對圖2-23所示的DFA進行最小化。首先將狀態(tài)

30、分為非終態(tài)集和終態(tài)集兩部分：{0,1,2,5}和{3,4,6,7}。由終態(tài)集可知，對于狀態(tài)3、6、7，無論輸入字符是a還是b的下一狀態(tài)均為終態(tài)集，而狀態(tài)4在輸入字符b的下一狀態(tài)落入非終態(tài)集，故將其劃分為　　　　　　　{0,1,2,5}，{4}，{3,6,7}　　對于非終態(tài)集，在輸入字符a、b后按其下一狀態(tài)落入的狀態(tài)集不同而最終劃分為　　　　　　　{0}，{1}，{2}，{5}，{4}，{3,6,7}　　按順序重新命名為0、1、2

31、、3、4、5，得到最簡DFA如圖2-24所示。,,.,54,,圖2-23 習題2.9的DFA,.,55,,圖2-24 習題2.9的最簡DFA,.,56,2.10 有一臺自動售貨機，接收1分和2分硬幣，出售3分錢一塊的硬糖。顧客每次向機器中投放大于等于3分的硬幣，便可得到一塊糖(注意：只給一塊并且不找錢)?！　?1) 寫出售貨機售糖的正規(guī)表達式；　　(2) 構造識別上述正規(guī)式的最簡DFA?！　　窘獯稹?(1) 設a=1，b=

32、2，則售貨機售糖的正規(guī)表達式為a (b?|?a(a?|?b))?|?b(a?|?b)?！　?2) 畫出與正規(guī)表達式a(b?|?a(a?|?b))?|?b(a?|?b)對應的NFA，如圖2-25所示?！　∮米蛹▽D2-25所示的NFA確定化，如圖2-26所示。,,.,57,,圖2-25 習題2.10的NFA,.,58,由圖2-26可看出，非終態(tài)2和非終態(tài)3面對輸入符號a或b的下一狀態(tài)相同，故合并為一個狀態(tài)，即最簡狀態(tài){0}、{1}

33、、{2，3}、{4}。,圖2-26 習題2.10的狀態(tài)轉(zhuǎn)換矩陣,.,59,按順序重新命名為0、1、2、3，則得到最簡DFA，如圖2-27所示。,,圖2-27 習題2.10的最簡DFA,.,60,第三章 語 法 分 析　　3.1 完成下列選擇題：　　(1) 程序語言的語義需要 用來描述?！　．上下文無關文法 B．上下文有關文法　　C．正規(guī)文法 　 D．短語文法　　(2) 2型文法

34、對應 ?！　．圖靈機 B．有限自動機 　　C．下推自動機 D．線性界限自動機,,.,61,(3) 下述結論中， 是正確的?！　．1型語言? 0型語言 B．2型語言? 1型語言 　　C．3型語言? 2型語言 D．A～C均不成立　　(4) 有限狀態(tài)自動機能識別_________?！　．上下文無關文法

35、 B．上下文有關文法 　　C．正規(guī)文法 D．短語文法　　(5) 文法G[S]： S→xSx | y 所識別的語言是 。　　A．xyx B．(xyx)* 　　C．xnyxn (n≥0) D．x*yx*,,.,62,(6) 只含有單層分枝的子樹稱為“簡單子樹”，則句柄的直觀解釋是 ?！　．子樹的末端結點(即樹葉)組成的符號串

36、　　B．簡單子樹的末端結點組成的符號串　　C．最左簡單子樹的末端結點組成的符號串　　D．最左簡單子樹的末端結點組成的符號串且該符號串必須含有終結符,,.,63,(7) 下面對語法樹錯誤的描述是 ?！　．根結點用文法G[S]的開始符S標記　　B．每個結點用G[S]的一個終結符或非終結符標記　　C．如果某結點標記為ε，則它必為葉結點　　D．內(nèi)部結點可以是非終結符　　(8) 由文法開始符S經(jīng)過零步或多步推導產(chǎn)生的

37、符號序列是 ?！　．短語 　B．句柄 C．句型 D．句子,,.,64,(9) 設文法G[S]： S→SA | A　　A→a | b　　則對句子aba的規(guī)范推導是 ?！　．S? SA? SAA ? AAA ? aAA ? abA ? aba 　　B．S? SA ? SAA ? AAA? AAa ? Aba ? aba　　C．S ? SA? SAA ? SAa ? Sba

38、 ? Aba ? aba　　D．S ? SA ? Sa ? SAa ? Sba ? Aba ? aba,,.,65,(10) 如果文法G[S]是無二義的，則它的任何句子α其 。　　A．最左推導和最右推導對應的語法樹必定相同　　B．最左推導和最右推導對應的語法樹可能不同　　C．最左推導和最右推導必定相同　　D．可能存在兩個不同的最右推導，但它們對應的語法樹相同 　　(11) 一個句型的分析樹代表了該句型的

39、?！　．推導過程 B．歸約過程 　　C．生成過程 D．翻譯過程,,.,66,(12) 規(guī)范歸約中的“可歸約串”由 定義?！　．直接短語 B．最右直接短語 　　C．最左直接短語 D．最左素短語　　(13) 規(guī)范歸約是指 ?！　．最左推導的逆過程 B．最右推導的逆過程　　C．規(guī)范推導 D．最左歸約的逆過程,,.,6

40、7,(14) 文法G[S]：S→aAcB | Bd　　 A→AaB | c　　 B→bScA | b　　則句型aAcbBdcc的短語是 ?！　．Bd B．cc C．a(chǎn) D．b　　(15) 文法G[E]：E→E+T | T　　 T→T*P | P　　

41、 P→(E) | i　　則句型P+T+i的句柄和最左素短語是 ?！　．P+T和T B．P和P+T 　　C．i和P+T+i D．P和P,,.,68,(16) 采用自頂向下分析，必須 ?！　．消除左遞歸 B．消除右遞歸 　　C．消除回朔 D．提取公共左因子　　(17) 對文法G[E]：E→E+S | S　　 S→S*F | F　　

42、 F→(E) | i　　則FIRST(S)= ?！　．{( } B．{ ( , i } 　　C．{ i } D．{ ( , ) },,.,69,(18) 確定的自頂向下分析要求文法滿足 。　　A．不含左遞歸 B．不含二義性 　　C．無回溯 D．A～C項　　(19) 遞歸下降分析器由一組遞歸函數(shù)組成，且每一個函數(shù)對應文法的

43、 ?！　．一個終結符 B．一個非終結符 　　C．多個終結符 D．多個非終結符　　(20) ?LL(1)分析表需要預先定義和構造兩族與文法有關的集合 ?！　．FIRST和FOLLOW B．FIRSTVT和FOLLOW 　　C．FIRST和LASTVT D．FIRSTVT和LASTVT,,.,70,(21) 設a、b、c是文法的終結符且滿足

44、優(yōu)先關系ab和bc,則 ?！　．必有ac B．必有ca 　　C．必有ba D．A～C 都不一定成立　　(22) 算符優(yōu)先分析法要求 ?！　．文法不存在…QR…的句型且任何終結符對(a,b)滿足ab、a?b和a?b三種關系 　　B．文法不存在…QR…的句型且任何終結符對(a,b)至多滿足ab、a?b和a?b三種關系之一,,.,71,C．文法可存在…QR…的句型且任何終結符對(a,b)至多滿足a

45、b、a?b和a?b三種關系之一　　D．文法可存在…QR…的句型且任何終結符對(a,b)滿足ab、a?b和a?b三種關系　　(23) 任何算符優(yōu)先文法 優(yōu)先函數(shù)?！　．有一個 B．沒有 　　C．有若干個 D．可能有若干個　　(24) 在算符優(yōu)先分析中，用 來刻畫可歸約串?！　．句柄 B．直接短語 　　C．素短語 D．最左素短語,,.,72,(

46、25) 下面最左素短語必須具備的條件中有錯誤的是 。　　A．至少包含一個終結符 　　B．至少包含一個非終結符 　　C．除自身外不再包含其他素短語 　　D．在句型中具有最左性　　(26) 對文法G[S]：S→b | ∧ | (T)　　 T→T，S | S　　其FIRSTVT(T)為 。　　A．{b, ∧ ,( } B．{b, ∧ , ) }

47、 　　C．{，,b, ∧, ( } D．{，,b, ∧, ) },,.,73,(27) 對文法G[E]：E→E*T | T　　 T→T+i | i　　句子1+2*8+6歸約的值為 。　　A．23 B．42 C．30 D．17 　　(28) 下述FOLLOW集構造方法中錯誤的是 ?！　．對文法開始符S有#∈FOLLOW(S

48、)　　B．若有A→αBβ，則有FIRST(β)\{ε}FOLLOW(B) 　　C．若有A→αB，則有FOLLOW(B)FOLLOW(A)　　D．若有A→αB，則有FOLLOW(A)FOLLOW(B),,.,74,(29) 若文法G[S]的產(chǎn)生式有…AB…出現(xiàn)，則對A求FOLLOW集正確的是 ?！　．FOLLOW(B)FOLLOW(A) 　　B．FIRSTVT(B) FOLLOW(A) 　　

49、C．FIRST(B) \{ε}FOLLOW(A) 　　　　D．LASTVT(B)FOLLOW(A)　　(30) 下面 是自底向上分析方法?！　．預測分析法 B．遞歸下降分析法 　　C．LL(1)分析法 D．算符優(yōu)先分析法,,.,75,(31) 下面 是采用句柄進行歸約的?！　．算符優(yōu)先分析法

50、B．預測分析法 　　C．SLR(1)分析法 D．LL(1)分析法　　(32) 一個 指明了在分析過程中某時刻能看到產(chǎn)生式多大一部分?！　．活前綴 B．前綴 　　C．項目 D．項目集　　(33) 若B為非終結符，則A→α·Bβ為 項目。　　A．接受 B．歸約 　　C．移進 D．待約,,.,

51、76,(34) 在LR(0)的ACTION子表中，如果某一行中存在標記為“rj”的欄，則 ?！　．該行必定填滿rj B．該行未填滿rj 　　C．其他行也有rj D．GOTO子表中也有rj　　(35) ?LR分析法解決“移進—歸約”沖突時，左結合意味著 。　　A．打斷聯(lián)系實行移進 B．打斷聯(lián)系實行歸約 　　C．建立

52、聯(lián)系實行移進 D．建立聯(lián)系實行歸約,,.,77,(36) ?LR分析法解決“移進—歸約”沖突時，右結合意味著 ?！　．打斷聯(lián)系實行歸約 B．建立聯(lián)系實行歸約 　　C．建立聯(lián)系實行移進 D．打斷聯(lián)系實行移進,,.,78,【解答】 　　(1) 參見第四章4.1.1節(jié)，語義分析不像詞法分析和語法分析那樣可以分別用正規(guī)文法和上下文無關文法描述，由于語義是上下文有關的，因此語義分

53、析須用上下文有關文法描述。即選B?！　?2) 2型文法對應下推自動機。故選C?！　?3) 由于不存在：3型語言? 2型語言? 1型語言? 0型語言。故選D?！　?4) 3型文法即正規(guī)文法，它的識別系統(tǒng)是有限狀態(tài)自動機。故選C。,,.,79,(5) 由S→xSx | y可知該文法所識別的語言一定是：y左邊出現(xiàn)的x與y右邊出現(xiàn)的x相等。故選C。　　(6) 最左簡單子樹的末端結點組成的符號串為句柄。故選C?！　?7) 內(nèi)部結點(

54、指非樹葉結點)一定是非終結符。故選D。　　(8) 由文法開始符S經(jīng)過零步或多步推導產(chǎn)生的符號序列一定是句型，僅當推導產(chǎn)生的符號序列全部由終結符組成時才是句子，即句子是句型的陣列。故選C?！　?9) 規(guī)范推導即最右推導，也即每一步推導都是對句型中的最右非終結符用相應產(chǎn)生式的右部進行替換。故選D。,,.,80,(10) 文法G[S]的一個句子如果能找到兩種不同的最左推導(或最右推導)，或存在兩棵不同的語法樹，則它的任何句子α其最左推導和

55、最右推導對應的語法樹必定相同。故選A?！　?11) 一個句型的分析樹代表了該句型的歸約過程。故選B?！　?12) 規(guī)范歸約中的“可歸約串”即為句柄，也就是最左直接短語。故選C。　　(13) 規(guī)范歸約的逆過程是規(guī)范推導，而規(guī)范推導即為最右推導。故選B?！　?14) 由圖3-1可知應選A。,,.,81,,圖3-1 句型aAcbBdcc對應的語法樹,.,82,(15) 由圖3-2可知，句柄(最左直接短語)為P，最左素短語為P+T。故

56、選B?！　?16) 回溯使自頂向下分析效率降低，左遞歸使得自頂向下的分析無法實現(xiàn)；二者相比消除左遞歸更為重要。故選A?！　?17) ?FIRST(F)={(,i}，而由S→F可知FIRST(F)\{ε}? FIRST(S)，即FIRST(S)={(,i}。故選B。　　(18) 左遞歸和二義性將無法實現(xiàn)自頂向下分析，回溯則使自頂向下分析效率下降。故選D。,,.,83,,圖3-2 句型P+T+i對應的語法樹及優(yōu)先關系示意,.,84,

57、(19) 遞歸下降分析器由一組遞歸函數(shù)組成，且每一個函數(shù)對應文法的一個非終結符。故選B?！　?20) ?LL(1)分析表需要預先定義和構造兩族與文法有關的集合FIRST和FOLLOW。故選A?！　?21) 由于ab和bc并不能使選項A、B、C成立。故選D?！　?22) 由算法優(yōu)先文法可知應選B。　　(23) 有些算符優(yōu)先文法不存在優(yōu)先函數(shù)；有些算符優(yōu)先文法存在優(yōu)先函數(shù)，且只要存在一對優(yōu)先函數(shù)，就存在無窮多對優(yōu)先函數(shù)。故選D?！?/p>

58、　(24) 在算符優(yōu)先分析中是以“最左素短語”來刻畫可歸約串的。故選D。,,.,85,(25) 最左素短語必須具備的三個條件是：① 至少包含一個終結符；② 除自身外不得包含其他素短語；③ 在句型中具有最左性。故選B?！　?26) ?FIRSTVT(T)={，}，F(xiàn)IRSTVT(S)={b, ∧,(}；由T→S可知FIRSTV(S)?FIRSTVT(T)，即FIRSTVT(T)={，,b, ∧, ( }。故選C?！　?27) 由圖3-

59、3可知應選B?！　?28) 若有A→αB則有FOLLOW(A)?FOLLOW(B)，即選項C錯。故選C?！　?29) 若文法G[S]的產(chǎn)生式有…AB…出現(xiàn)，則有FIRST(B)\{ε}?FOLLOW(A)。故選C。,,.,86,,圖3-3 句子1+2*8+6的語法樹及值變化示意,.,87,(30) 自底向上的分析方法有算符優(yōu)先分析法和LR分析法。故選D?！　?31) 自底向上分析采用歸約方法，但算符優(yōu)先分析用“最左素短語”歸約，

60、而LR分析用“句柄”歸約。SLR(1)是LR分析法的一種，故選C?！　?32) 在LR分析中，一個項目指明了在分析過程的某個時刻所看到產(chǎn)生式的多大一部分。故選C?！　?33) 對文法G[S’]，S'→α·稱為“接受”項目；形如A→α·aβ的項目(其中a為終結符)稱為“移進”項目；形如A→α·Bβ的項目(其中B為非終結符)稱為“待約”項目。故選D。,,.,88,(34) 在LR(0)的ACTION

61、子表中，如果某一行存在標注為“rj”的欄，則該行必定填滿rj，而在SLR(1)的ACTION子表中，如果某一行存在標注為“rj”的欄，則該行可能未填滿rj。因此選A。　　(35) ?LR分析法解決“移進—歸約”沖突時，左結合意味著打斷聯(lián)系而實行歸約，右結合意味著維持聯(lián)系而實行移進。故選B?！　?36) 由(35)可知應選C。,,.,89,3.2 令文法G[N]為　　 G[N]: N→D?|?ND　　D→0?|?1

62、?|?2?|?3?|?4?|?5?|?6?|?7?|?8?|?9　　(1) ?G[N]的語言L(G)是什么?　　(2) 給出句子0127、34和568的最左推導和最右推導。,,.,90,【解答】 　　(1) ?G[N]的語言L(G[N])是非負整數(shù)。　　(2) 最左推導： 最右推導：,.,91,3.3 已知文法G[S]為S→aSb?|?Sb?|?b，試證明文法G[S]為二義文法?！　　窘獯稹?由文法

63、G[S]：S→aSb?|?Sb?|?b，對句子aabbbb可對應如圖3-4所示的兩棵語法樹。　　因此，文法G[S]為二義文法(對句子abbb也可畫出兩棵不同的語法樹)。,,.,92,,圖3-4 句子aabbbb對應的兩棵不同語法樹,.,93,3.4 已知文法G[S]為S→SaS?|?ε，試證明文法G[S]為二義文法。　　【解答】 由文法G[S]：S→SaS?|?ε，句子aa的語法樹如圖3-5所示?！　∮蓤D3-5可知，文法G[

64、S]為二義文法。,,.,94,,圖3-5 句子aa對應的兩棵不同的語法樹,.,95,3.5 按指定類型，給出語言的文法。 　　(1) ?L={aibj?|?j＞i≥0}的上下文無關文法；　　(2) 字母表Σ={a,b}上的同時只有奇數(shù)個a和奇數(shù)個b的所有串的集合的正規(guī)文法；　　(3) 由相同個數(shù)a和b組成句子的無二義文法。　　【解答】 (1) 由L={aibj?|?j＞i≥0}知，所求該語言對應的上下文

65、無關文法首先應有S→aSb型產(chǎn)生式，以保證b的個數(shù)不少于a的個數(shù)；其次，還需有S→Sb或S→b型的產(chǎn)生式，用以保證b的個數(shù)多于a的個數(shù)。因此，所求上下文無關文法G[S]為　　　　　　　G[S]：S→aSb?|?Sb?|?b,,.,96,(2) 為了構造字母表Σ={a,b}上同時只有奇數(shù)個a和奇數(shù)個b的所有串集合的正規(guī)式，我們畫出如圖3-6所示的DFA，即由開始符S出發(fā)，經(jīng)過奇數(shù)個a到達狀態(tài)A，或經(jīng)過奇數(shù)個b到達狀態(tài)B；而由狀態(tài)A出發(fā)，

66、經(jīng)過奇數(shù)個b到達狀態(tài)C(終態(tài))；同樣，由狀態(tài)B出發(fā)經(jīng)過奇數(shù)個a到達終態(tài)C?！　∮蓤D3-6可直接得到正規(guī)文法G[S]如下：　　 G[S]：S→aA?|?bB　　　　　　　 A→aS?|?bC?|?b　　　　　　　 B→bS?|?aC?|?a　　　　　　　 C→bA?|?aB?|?ε,,.,97,,圖3-6,.,98,(3) 我們用一個非終結符A代表一個a(即有A→a)，用一個非終結符B代表一個b(

67、即有B→b)；為了保證a和b的個數(shù)相同，則在出現(xiàn)一個a時應相應地出現(xiàn)一個B，出現(xiàn)一個b時則相應出現(xiàn)一個A。假定已推導出bA，如果下一步要推導出連續(xù)兩個b，則應有bA?bbAA。也即為了保證b和A的個數(shù)一致，應有A→bAA；同理有B→aBB。此外，為了保證遞歸地推出所要求的ab串，應有S→aBS和S→bAS。由此得到無二義文法G[S]為　　 G[S]：S→aBS?|?bAS?|?ε　　

68、 A→bAA?|?a　　 B→aBB?|?b,,.,99,3.6 有文法G[S]: S→aAcB?|?Bd　　　　　　　　　A→AaB?|?c　　　　　　　　　B→bScA?|?b　　(1) 試求句型aAaBcbbdcc和aAcbBdcc的句柄；　　(2) 寫出句子acabcbbdcc的最左推導過程。　　【解答】 (1) 分別畫出對應句型aAaBcbbdcc和aAcb