編譯原理習(xí)題及答案ppt演示課件

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

2、依賴(lài)具體機(jī)器的特性是無(wú)法改變的,,.,3,(2) 將編譯過(guò)程分成若干“遍”是為了 ?！　　　．提高程序的執(zhí)行效率　　　　B．使程序的結(jié)構(gòu)更加清晰　　　　C．利用有限的機(jī)器內(nèi)存并提高機(jī)器的執(zhí)行效率　　　　D．利用有限的機(jī)器內(nèi)存但降低了機(jī)器的執(zhí)行效率　　(3) 構(gòu)造編譯程序應(yīng)掌握 。 　　　　A．源程序 B．目標(biāo)語(yǔ)

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

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

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

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

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

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

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

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

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

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

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

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

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

16、 f{y,b}={x,y}　　試構(gòu)造相應(yīng)的確定有限自動(dòng)機(jī)M′?！　　窘獯稹?對(duì)照自動(dòng)機(jī)的定義M=(S,Σ,f,?s0,?Z)，由f的定義可知f(x,a)、f(y,b)均為多值函數(shù)，因此M是一非確定有限自動(dòng)機(jī)?！　∠犬?huà)出NFA M相應(yīng)的狀態(tài)圖，如圖2-2所示。,,.,20,,圖2-2 習(xí)題2.3的NFA M,.,21,用子集法構(gòu)造狀態(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}，因此不再將其劃分了，也即整個(gè)劃分只有兩組：{0}和{1,2}。令狀態(tài)1代表{1,2}，即把原來(lái)到達(dá)2的弧都導(dǎo)向1，并刪除狀態(tài)2。最后，得到如圖2-4所示的化簡(jiǎn)了的DFA M′。,,

18、圖2-3 習(xí)題2.3的DFA M′,其狀態(tài)轉(zhuǎn)換圖如圖2-3所示。,.,23,,圖2-4 圖2-3化簡(jiǎn)后的DFA M′,.,24,2.4 正規(guī)式(ab)*a與正規(guī)式a(ba)*是否等價(jià)？請(qǐng)說(shuō)明理由。　　【解答】 正規(guī)式(ab)*a對(duì)應(yīng)的NFA如圖2-5所示，正規(guī)式a(ba) *對(duì)應(yīng)的NFA如圖2-6所示?！　∮米蛹▽D2-5和圖2-6分別確定化為如圖2-7(a)和(b)所示的狀態(tài)轉(zhuǎn)換矩陣，它們最終都可以得到最簡(jiǎn)DFA，如圖2

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

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

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

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

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

24、新命名為0、1、2、3、4、5、6，則得到最簡(jiǎn)DFA，如圖2-15所示。,圖2-15 習(xí)題2.6的最簡(jiǎn)DFA,.,39,2.7 已知正規(guī)式((a?|?b)*|?aa)*b和正規(guī)式(a?|?b)*b?！　?1) 試用有限自動(dòng)機(jī)的等價(jià)性證明這兩個(gè)正規(guī)式是等價(jià)的；　　(2) 給出相應(yīng)的正規(guī)文法?！　　窘獯稹?(1) 正規(guī)式((a?|?b)*|?aa)*b對(duì)應(yīng)的NFA如圖2-16所示?！　∮米蛹▽D2-16所示的NFA確定化為D

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

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

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

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

29、A)?！　∑渲?，X為初態(tài)，Y為終態(tài)。 　【解答】 用子集法將NFA確定化，如圖2-22所示。,,.,51,,圖2-21 習(xí)題2.9的NFA,.,52,,圖2-22 習(xí)題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所對(duì)應(yīng)的DFA如圖2-23所示?！　?duì)圖2-23所示的DFA進(jìn)行最小化。首先將狀態(tài)

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

31、、3、4、5，得到最簡(jiǎn)DFA如圖2-24所示。,,.,54,,圖2-23 習(xí)題2.9的DFA,.,55,,圖2-24 習(xí)題2.9的最簡(jiǎn)DFA,.,56,2.10 有一臺(tái)自動(dòng)售貨機(jī)，接收1分和2分硬幣，出售3分錢(qián)一塊的硬糖。顧客每次向機(jī)器中投放大于等于3分的硬幣，便可得到一塊糖(注意：只給一塊并且不找錢(qián))?！　?1) 寫(xiě)出售貨機(jī)售糖的正規(guī)表達(dá)式；　　(2) 構(gòu)造識(shí)別上述正規(guī)式的最簡(jiǎn)DFA。　　【解答】 (1) 設(shè)a=1，b=

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

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

34、對(duì)應(yīng) 。　　A．圖靈機(jī) B．有限自動(dòng)機(jī) 　　C．下推自動(dòng)機(jī) D．線(xiàn)性界限自動(dòng)機(jī),,.,61,(3) 下述結(jié)論中， 是正確的?！　．1型語(yǔ)言? 0型語(yǔ)言 B．2型語(yǔ)言? 1型語(yǔ)言 　　C．3型語(yǔ)言? 2型語(yǔ)言 D．A～C均不成立　　(4) 有限狀態(tài)自動(dòng)機(jī)能識(shí)別_________?！　．上下文無(wú)關(guān)文法

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

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

37、符號(hào)序列是 ?！　．短語(yǔ) 　B．句柄 C．句型 D．句子,,.,64,(9) 設(shè)文法G[S]： S→SA | A　　A→a | b　　則對(duì)句子aba的規(guī)范推導(dǎo)是 。　　A．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]是無(wú)二義的，則它的任何句子α其 ?！　．最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹(shù)必定相同　　B．最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹(shù)可能不同　　C．最左推導(dǎo)和最右推導(dǎo)必定相同　　D．可能存在兩個(gè)不同的最右推導(dǎo)，但它們對(duì)應(yīng)的語(yǔ)法樹(shù)相同 　　(11) 一個(gè)句型的分析樹(shù)代表了該句型的

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

40、7,(14) 文法G[S]：S→aAcB | Bd　　 A→AaB | c　　 B→bScA | b　　則句型aAcbBdcc的短語(yǔ)是 ?！　．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的句柄和最左素短語(yǔ)是 ?！　．P+T和T B．P和P+T 　　C．i和P+T+i D．P和P,,.,68,(16) 采用自頂向下分析，必須 ?！　．消除左遞歸 B．消除右遞歸 　　C．消除回朔 D．提取公共左因子　　(17) 對(duì)文法G[E]：E→E+S | S　　 S→S*F | F　　

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

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

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

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

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

47、 　　C．{，,b, ∧, ( } D．{，,b, ∧, ) },,.,73,(27) 對(duì)文法G[E]：E→E*T | T　　 T→T+i | i　　句子1+2*8+6歸約的值為 ?！　．23 B．42 C．30 D．17 　　(28) 下述FOLLOW集構(gòu)造方法中錯(cuò)誤的是 ?！　．對(duì)文法開(kāi)始符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)，則對(duì)A求FOLLOW集正確的是 ?！　．FOLLOW(B)FOLLOW(A) 　　B．FIRSTVT(B) FOLLOW(A) 　　

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

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

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

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

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

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

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

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

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

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

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

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

61、子表中，如果某一行存在標(biāo)注為“rj”的欄，則該行必定填滿(mǎn)rj，而在SLR(1)的ACTION子表中，如果某一行存在標(biāo)注為“rj”的欄，則該行可能未填滿(mǎn)rj。因此選A?！　?35) ?LR分析法解決“移進(jìn)—?dú)w約”沖突時(shí)，左結(jié)合意味著打斷聯(lián)系而實(shí)行歸約，右結(jié)合意味著維持聯(lián)系而實(shí)行移進(jìn)。故選B?！　?36) 由(35)可知應(yīng)選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]的語(yǔ)言L(fǎng)(G)是什么?　　(2) 給出句子0127、34和568的最左推導(dǎo)和最右推導(dǎo)。,,.,90,【解答】 　　(1) ?G[N]的語(yǔ)言L(fǎng)(G[N])是非負(fù)整數(shù)。　　(2) 最左推導(dǎo)： 最右推導(dǎo)：,.,91,3.3 已知文法G[S]為S→aSb?|?Sb?|?b，試證明文法G[S]為二義文法?！　　窘獯稹?由文法

63、G[S]：S→aSb?|?Sb?|?b，對(duì)句子aabbbb可對(duì)應(yīng)如圖3-4所示的兩棵語(yǔ)法樹(shù)。　　因此，文法G[S]為二義文法(對(duì)句子abbb也可畫(huà)出兩棵不同的語(yǔ)法樹(shù))。,,.,92,,圖3-4 句子aabbbb對(duì)應(yīng)的兩棵不同語(yǔ)法樹(shù),.,93,3.4 已知文法G[S]為S→SaS?|?ε，試證明文法G[S]為二義文法?！　　窘獯稹?由文法G[S]：S→SaS?|?ε，句子aa的語(yǔ)法樹(shù)如圖3-5所示?！　∮蓤D3-5可知，文法G[

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

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

66、經(jīng)過(guò)奇數(shù)個(gè)b到達(dá)狀態(tài)C(終態(tài))；同樣，由狀態(tài)B出發(fā)經(jīng)過(guò)奇數(shù)個(gè)a到達(dá)終態(tài)C。　　由圖3-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) 我們用一個(gè)非終結(jié)符A代表一個(gè)a(即有A→a)，用一個(gè)非終結(jié)符B代表一個(gè)b(

67、即有B→b)；為了保證a和b的個(gè)數(shù)相同，則在出現(xiàn)一個(gè)a時(shí)應(yīng)相應(yīng)地出現(xiàn)一個(gè)B，出現(xiàn)一個(gè)b時(shí)則相應(yīng)出現(xiàn)一個(gè)A。假定已推導(dǎo)出bA，如果下一步要推導(dǎo)出連續(xù)兩個(gè)b，則應(yīng)有bA?bbAA。也即為了保證b和A的個(gè)數(shù)一致，應(yīng)有A→bAA；同理有B→aBB。此外，為了保證遞歸地推出所要求的ab串，應(yīng)有S→aBS和S→bAS。由此得到無(wú)二義文法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) 寫(xiě)出句子acabcbbdcc的最左推導(dǎo)過(guò)程?！　　窘獯稹?(1) 分別畫(huà)出對(duì)應(yīng)句型aAaBcbbdcc和aAcb