編譯原理習(xí)題及答案(課堂)課件

1、第一章 緒 論第二章 詞 法 分 析第三章 語 法 分 析1.第一章 緒 論1. 第一章 緒 論1.1 完成下列選擇題：(1) 下面敘述中正確的是 。A編譯程序是將高級語言程序翻譯成等價(jià)的機(jī)器語言程序的程序B機(jī)器語言因其使用過于困難，所以現(xiàn)在計(jì)算機(jī)根本不使用機(jī)器語言C匯編語言是計(jì)算機(jī)唯一能夠直接識(shí)別并接受的語言D高級語言接近人們的自然語言，但其依賴具體機(jī)器的特性是無法改變的2. 第一章 緒 論1.1 完成下(2) 將編譯過程分成若干“遍”是為了 。A提高程序的執(zhí)行效率B使程序的結(jié)構(gòu)更加清晰C利用有限的機(jī)器內(nèi)存并提高機(jī)器的執(zhí)行效率D利用有限的機(jī)器內(nèi)存但降低了機(jī)器的執(zhí)行效率(3) 構(gòu)造編譯程序應(yīng)掌

2、握 。 A源程序 B目標(biāo)語言 C編譯方法 DAC項(xiàng)3.(2) 將編譯過程分成若干“遍”是為了 。(4) 編譯程序絕大多數(shù)時(shí)間花在 上。A出錯(cuò)處理 B詞法分析 B目標(biāo)代碼生成 D表格管理(5) 編譯程序是對 。A匯編程序的翻譯 B高級語言程序的解釋執(zhí)行C機(jī)器語言的執(zhí)行 D高級語言的翻譯4.(4) 編譯程序絕大多數(shù)時(shí)間花在 上?！窘獯稹?(1) 編譯程序可以將用高級語言編寫的源程序轉(zhuǎn)換成與之在邏輯上等價(jià)的目標(biāo)程序，而目標(biāo)程序可以是匯編語言程序或機(jī)器語言程序。故選A。(2) 分多遍完成編譯過程可使整個(gè)編譯程序的邏輯結(jié)構(gòu)更加清晰。故選B。(3) 構(gòu)造編譯程序應(yīng)掌握源程序、目標(biāo)語言和編譯方法這三方面內(nèi)容

3、。故選D。5.【解答】 (1) 編譯程序可以將用高級語言編寫的(4) 編譯各階段的工作都涉及到構(gòu)造、查找或更新有關(guān)表格，即編譯過程的絕大部分時(shí)間都用在造表、查表和更新表格的事務(wù)上。故選D。(5) 由(1)可知，編譯程序?qū)嶋H上實(shí)現(xiàn)了對高級語言程序的翻譯。故選D。6.(4) 編譯各階段的工作都涉及到構(gòu)造、查找或更新有關(guān)表格1.2 計(jì)算機(jī)執(zhí)行用高級語言編寫的程序有哪些途徑？它們之間的主要區(qū)別是什么？【解答】 計(jì)算機(jī)執(zhí)行用高級語言編寫的程序主要有兩種途徑：解釋和編譯。在解釋方式下，翻譯程序事先并不采用將高級語言程序全部翻譯成機(jī)器代碼程序，然后執(zhí)行這個(gè)機(jī)器代碼程序的方法，而是每讀入一條源程序的語句，就將

4、其解釋(翻譯)成對應(yīng)其功能的機(jī)器代碼語句串并執(zhí)行，然后再讀入下一條源程序語句并解釋執(zhí)行，而所翻譯的機(jī)器代碼語句串在該語句執(zhí)行后并不保留。這種方法是按源程序中語句的動(dòng)態(tài)執(zhí)行順序逐句解釋(翻譯)執(zhí)行的，如果一語句處于一循環(huán)體中，則每次循環(huán)執(zhí)行到該語句時(shí)，都要將其翻譯成機(jī)器代碼后再執(zhí)行。7.1.2 計(jì)算機(jī)執(zhí)行用高級語言編寫的程序有哪些途徑？它們在編譯方式下，高級語言程序的執(zhí)行是分兩步進(jìn)行的：第一步首先將高級語言程序全部翻譯成機(jī)器代碼程序，第二步才是執(zhí)行這個(gè)機(jī)器代碼程序。因此，編譯對源程序的處理是先翻譯，后執(zhí)行。從執(zhí)行速度上看，編譯型的高級語言比解釋型的高級語言要快，但解釋方式下的人機(jī)界面比編譯型好，

5、便于程序調(diào)試。這兩種途徑的主要區(qū)別在于：解釋方式下不生成目標(biāo)代碼程序，而編譯方式下生成目標(biāo)代碼程序。8.在編譯方式下，高級語言程序的執(zhí)行是分兩步進(jìn)行的：第一步首1.3 請畫出編譯程序的總框圖。如果你是一個(gè)編譯程序的總設(shè)計(jì)師，設(shè)計(jì)編譯程序時(shí)應(yīng)當(dāng)考慮哪些問題？【解答】 編譯程序總框圖如圖1-1所示。作為一個(gè)編譯程序的總設(shè)計(jì)師，首先要深刻理解被編譯的源語言其語法及語義；其次，要充分掌握目標(biāo)指令的功能及特點(diǎn)，如果目標(biāo)語言是機(jī)器指令，還要搞清楚機(jī)器的硬件結(jié)構(gòu)以及操作系統(tǒng)的功能；第三，對編譯的方法及使用的軟件工具也必須準(zhǔn)確化?？傊?，總設(shè)計(jì)師在設(shè)計(jì)編譯程序時(shí)必須估量系統(tǒng)功能要求、硬件設(shè)備及軟件工具等諸因素對

6、編譯程序構(gòu)造的影響。9.1.3 請畫出編譯程序的總框圖。如果你是一個(gè)編譯程序的圖1-1 編譯程序總框圖 10.圖1-1 編譯程序總框圖 10.第二章 詞 法 分 析2.1 完成下列選擇題：(1) 詞法分析所依據(jù)的是 。A語義規(guī)則 B構(gòu)詞規(guī)則 C語法規(guī)則 D等價(jià)變換規(guī)則(2) 詞法分析器的輸入是 。A單詞符號串 B源程序 C語法單位 D目標(biāo)程序11.第二章 詞 法 分 析2.1 完成下列選(3) 詞法分析器的輸出是 。A單詞的種別編碼 B單詞的種別編碼和自身的值C單詞在符號表中的位置 D單詞自身值(4) 狀態(tài)轉(zhuǎn)換圖(見圖2-1)接受的字集為 _。A以0開頭的二進(jìn)制數(shù)組成的集合B以0結(jié)尾的二進(jìn)制數(shù)

7、組成的集合 C含奇數(shù)個(gè)0的二進(jìn)制數(shù)組成的集合 D含偶數(shù)個(gè)0的二進(jìn)制數(shù)組成的集合12.(3) 詞法分析器的輸出是 。A單圖2-1 習(xí)題2.1的DFA M 13.圖2-1 習(xí)題2.1的DFA M 13.(5) 對于任一給定的NFA M， 一個(gè)DFA M，使L(M)= L(M)。A一定不存在 B一定存在 C可能存在 D可能不存在(6) DFA適用于 。A定理證明 B語法分析 C詞法分析 D語義加工14.(5) 對于任一給定的NFA M， 一個(gè)DFA(7) 下面用正規(guī)表達(dá)式描述詞法的論述中，不正確的是 。A詞法規(guī)則簡單，采用正規(guī)表達(dá)式已足以描述B正規(guī)表達(dá)式的表示比上下文無關(guān)文法更加簡潔、直觀和易于理解

8、C正規(guī)表達(dá)式描述能力強(qiáng)于上下文無關(guān)文法D有限自動(dòng)機(jī)的構(gòu)造比下推自動(dòng)機(jī)簡單且分析效率高(8) 與(a|b)*(a|b)等價(jià)的正規(guī)式是 。A(a|b) (a|b)* Ba*|b* C(ab)*(a|b)* D(a|b)*15.(7) 下面用正規(guī)表達(dá)式描述詞法的論述中，不正確的是 【解答】(1) 由教材第一章1.3節(jié)中的詞法分析，可知詞法分析所遵循的是語言的構(gòu)詞規(guī)則。故選B。(2) 詞法分析器的功能是輸入源程序，輸出單詞符號。故選B。(3) 詞法分析器輸出的單詞符號通常表示為二元式：(單詞種別，單詞自身的值)。故選B。(4) 雖然選項(xiàng)A、B、D都滿足題意，但選項(xiàng)D更準(zhǔn)確。故選D。16.【解答】(1)

9、 由教材第一章1.3節(jié)中的詞法分析，可(5) NFA可以有DFA與之等價(jià)，即兩者描述能力相同；也即，對于任一給定的NFA M，一定存在一個(gè)DFA M，使L(M)=L(M)。故選B。(6) DFA便于識(shí)別，易于計(jì)算機(jī)實(shí)現(xiàn)，而NFA便于定理的證明。故選C。(7) 本題雖然是第二章的題，但答案參見第三章3.1.3節(jié)。即選C。(8) 由于正則閉包R+=R*R=RR*，故(a|b)*(a|b)=(a|b)(a|b)*。故選A。17.(5) NFA可以有DFA與之等價(jià)，即兩者描述能力相同2.2 什么是掃描器？掃描器的功能是什么？【解答】 掃描器就是詞法分析器，它接受輸入的源程序，對源程序進(jìn)行詞法分析并識(shí)別

10、出一個(gè)個(gè)單詞符號，其輸出結(jié)果是單詞符號，供語法分析器使用。通常把詞法分析器作為一個(gè)子程序，每當(dāng)語法分析器需要一個(gè)單詞符號時(shí)就調(diào)用這個(gè)子程序。每次調(diào)用時(shí)，詞法分析器就從輸入串中識(shí)別出一個(gè)單詞符號交給語法分析器。18.2.2 什么是掃描器？掃描器的功能是什么？【解答2.3 設(shè)M=(x,y, a,b, f, x, y)為一非確定的有限自動(dòng)機(jī)，其中f定義如下： f(x,a)=x,y fx,b=y f(y,a)= fy,b=x,y試構(gòu)造相應(yīng)的確定有限自動(dòng)機(jī)M?！窘獯稹?對照自動(dòng)機(jī)的定義M=(S,f,s0,Z)，由f的定義可知f(x,a)、f(y,b)均為多值函數(shù)，因此M是一非確定有限自動(dòng)機(jī)。先畫出NFA

11、 M相應(yīng)的狀態(tài)圖，如圖2-2所示。19.2.3 設(shè)M=(x,y, a,b, f, x,圖2-2 習(xí)題2.3的NFA M 20.圖2-2 習(xí)題2.3的NFA M 20.用子集法構(gòu)造狀態(tài)轉(zhuǎn)換矩陣，如表2-1所示。 表2-1 狀態(tài)轉(zhuǎn)換矩陣 將轉(zhuǎn)換矩陣中的所有子集重新命名，形成表2-2所示的狀態(tài)轉(zhuǎn)換矩陣，即得到21.用子集法構(gòu)造狀態(tài)轉(zhuǎn)換矩陣，如表2-1所示。 將圖2-3所示的DFA M最小化。首先，將M的狀態(tài)分成終態(tài)組1,2與非終態(tài)組0。其次，考察1,2。由于1,2a=1,2b=21,2，因此不再將其劃分了，也即整個(gè)劃分只有兩組：0和1,2。令狀態(tài)1代表1,2，即把原來到達(dá)2的弧都導(dǎo)向1，并刪除狀態(tài)2

12、。最后，得到如圖2-4所示的化簡了的DFA M。圖2-3 習(xí)題2.3的DFA M其狀態(tài)轉(zhuǎn)換圖如圖2-3所示。22.將圖2-3所示的DFA M最小化。首先，將M的狀態(tài)分圖2-4 圖2-3化簡后的DFA M 23.圖2-4 圖2-3化簡后的DFA M 23.2.4 正規(guī)式(ab)*a與正規(guī)式a(ba)*是否等價(jià)？請說明理由?！窘獯稹?正規(guī)式(ab)*a對應(yīng)的NFA如圖2-5所示，正規(guī)式a(ba) *對應(yīng)的NFA如圖2-6所示。用子集法將圖2-5和圖2-6分別確定化為如圖2-7(a)和(b)所示的狀態(tài)轉(zhuǎn)換矩陣，它們最終都可以得到最簡DFA，如圖2-8所示。因此，這兩個(gè)正規(guī)式等價(jià)。24.2.4 正規(guī)式

13、(ab)*a與正規(guī)式a(ba)*是否等價(jià)圖2-5 正規(guī)式(ab)*a對應(yīng)的NFA 25.圖2-5 正規(guī)式(ab)*a對應(yīng)的NFA 25.圖2-6 正規(guī)式a(ba)*對應(yīng)的NFA 26.圖2-6 正規(guī)式a(ba)*對應(yīng)的NFA 26.圖2-7 圖2-5和圖2-6確定化后的狀態(tài)轉(zhuǎn)換矩陣 27.圖2-7 圖2-5和圖2-6確定化后的狀態(tài)轉(zhuǎn)換矩陣 27圖2-8 最簡DFA 28.圖2-8 最簡DFA 28.實(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)*在a之后，故(ba)*對

14、應(yīng)的弧應(yīng)在終態(tài)結(jié)點(diǎn)Y上。因此，(ab)*a和a(ba)*所對應(yīng)的NFA也可分別描述為如圖2-9(a)和(b)所示的形式，它們確定化并化簡后仍可得到圖2-8所示的最簡DFA。29.實(shí)際上，當(dāng)閉包*取0時(shí)，正規(guī)式(ab) *a與正規(guī)式a(圖2-9 (ab)*a和a(ba)*分別對應(yīng)的NFA 30.圖2-9 (ab)*a和a(ba)*分別對應(yīng)的NFA 302.5 設(shè)有L(G)=a2n+1b2ma2p+1|n0,p0,m1。(1) 給出描述該語言的正規(guī)表達(dá)式；(2) 構(gòu)造識(shí)別該語言的確定有限自動(dòng)機(jī)(可直接用狀態(tài)圖形式給出)?！窘獯稹?該語言對應(yīng)的正規(guī)表達(dá)式為a(aa)*bb(bb)*a(aa)*，正規(guī)

15、表達(dá)式對應(yīng)的NFA如圖2-10所示。31.2.5 設(shè)有L(G)=a2n+1b2ma2p+1|圖2-10 習(xí)題2.5的NFA 32.圖2-10 習(xí)題2.5的NFA 32.用子集法將圖2-10確定化，如圖2-11所示。由圖2-11重新命名后的狀態(tài)轉(zhuǎn)換矩陣可化簡為(也可由最小化方法得到)0,2 1 3,5 4,6 7圖2-11 習(xí)題2.5的狀態(tài)轉(zhuǎn)換矩陣 33.用子集法將圖2-10確定化，如圖2-11所示。按順序重新命名為0、1、2、3、4后得到最簡的DFA，如圖2-12所示。圖2-12 習(xí)題2.5的最簡DFA 34.按順序重新命名為0、1、2、3、4后得到最簡的DFA2.6 有語言L=w|w(0,1

16、)+，并且w中至少有兩個(gè)1，又在任何兩個(gè)1之間有偶數(shù)個(gè)0，試構(gòu)造接受該語言的確定有限狀態(tài)自動(dòng)機(jī)(DFA)?！窘獯稹?對于語言L，w中至少有兩個(gè)1，且任意兩個(gè)1之間必須有偶數(shù)個(gè)0；也即在第一個(gè)1之前和最后一個(gè)1之后，對0的個(gè)數(shù)沒有要求。據(jù)此我們求出L的正規(guī)式為0*1(00(00)*1)*00(00)*10*，畫出與正規(guī)式對應(yīng)的NFA，如圖2-13所示。35.2.6 有語言L=w|w(0,1)+，并且w中圖2-13 習(xí)題2.6的NFA 36.圖2-13 習(xí)題2.6的NFA 36.用子集法將圖2-13所示的NFA確定化，如圖2-14所示由圖2-14可看出非終態(tài)2和4的下一狀態(tài)相同，終態(tài)6和8的下一狀

17、態(tài)相同，即得到最簡狀態(tài)為0 1 2,4 3 5 6,8 737.用子集法將圖2-13所示的NFA確定化，如圖2-14所示按順序重新命名為0、1、2、3、4、5、6，則得到最簡DFA，如圖2-15所示。圖2-15 習(xí)題2.6的最簡DFA 38.按順序重新命名為0、1、2、3、4、5、6，則得到最簡D2.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對應(yīng)的NFA如圖2-16所示。用子集法將圖2-16所示的NFA確定化為DFA，如圖2-17所示。39.2

18、.7 已知正規(guī)式(a|b)*|aa)*b和正圖2-16 正規(guī)式(a|b)*|aa)*b對應(yīng)的NFA 40.圖2-16 正規(guī)式(a|b)*|aa)*b對應(yīng)的NF圖2-17 圖2-16確定化后的狀態(tài)轉(zhuǎn)換矩陣 41.圖2-17 圖2-16確定化后的狀態(tài)轉(zhuǎn)換矩陣 41.由于對非終態(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對應(yīng)的NFA如圖2-19所示。用子集法將圖2-19所示的NFA確定化為如圖2-20所示的

19、狀態(tài)轉(zhuǎn)換矩陣。42.由于對非終態(tài)的狀態(tài)1、2來說，它們輸入a、b的下一狀態(tài)是表2-3 合并后的狀態(tài)轉(zhuǎn)換矩陣 43.表2-3 合并后的狀態(tài)轉(zhuǎn)換矩陣 43.圖2-18 習(xí)題2.7的最簡DFA 44.圖2-18 習(xí)題2.7的最簡DFA 44.圖2-19 正規(guī)式(a|b)*b對應(yīng)的NFA 45.圖2-19 正規(guī)式(a|b)*b對應(yīng)的NFA 45.比較圖2-20與圖2-17，重新命名后的轉(zhuǎn)換矩陣是完全一樣的，也即正規(guī)式(a|b)*b可以同樣得到化簡后的DFA如圖2-18所示。因此，兩個(gè)自動(dòng)機(jī)完全一樣，即兩個(gè)正規(guī)文法等價(jià)。圖2-20 圖2-19確定化后的狀態(tài)轉(zhuǎn)換矩陣 46.比較圖2-20與圖2-17，重新

20、命名后的轉(zhuǎn)換矩陣2.8 構(gòu)造一個(gè)DFA，它接收 =a,b上所有不含abb的字符串。解： =a,b上所有不含abb的字符串可表示為b*(a*b)a*。47.2.8 構(gòu)造一個(gè)DFA，它接收 =a,b上所有不含a2.9構(gòu)造一個(gè)DFA，它接收 =a,b上所有含偶數(shù)個(gè)a的字符串。解： =a,b上所有含偶數(shù)個(gè)a的字符串可表示為(b|ab*a)*48.2.9構(gòu)造一個(gè)DFA，它接收 =a,b上所有含偶數(shù)個(gè)2.10 下列程序段以B表示循環(huán)體，A表示初始化，I表示增量，T表示測試： I=1; while (I=n) sun=sun+aI; I=I+1; 請用正規(guī)表達(dá)式表示這個(gè)程序段可能的執(zhí)行序列?！窘獯稹?用正規(guī)

21、表達(dá)式表示程序段可能的執(zhí)行序列為AT(BIT)*。49.2.10 下列程序段以B表示循環(huán)體，A表示初始化，I表2.9 將圖2-21所示的非確定有限自動(dòng)機(jī)(NFA)變換成等價(jià)的確定有限自動(dòng)機(jī)(DFA)。其中，X為初態(tài)，Y為終態(tài)。 【解答】 用子集法將NFA確定化，如圖2-22所示。50.2.9 將圖2-21所示的非確定有限自動(dòng)機(jī)(NFA)變圖2-21 習(xí)題2.9的NFA 51.圖2-21 習(xí)題2.9的NFA 51.圖2-22 習(xí)題2.9的狀態(tài)轉(zhuǎn)換矩陣 22,Y2,422,Y2,42,42,42,4,Y2,4,Y2,4,Y52.圖2-22 習(xí)題2.9的狀態(tài)轉(zhuǎn)換矩陣 22,Y2圖2-22所對應(yīng)的DF

22、A如圖2-23所示。對圖2-23所示的DFA進(jìn)行最小化。首先將狀態(tài)分為非終態(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、3、4、5，得到最簡DFA如圖2-24所示。53.圖2-22所對應(yīng)的DFA如圖2-23所示。對圖2-圖2-23 習(xí)題2.9的DFA 54.圖2-23 習(xí)題2.9的DFA 54. 圖

23、2-24 習(xí)題2.9的最簡DFA 55. 圖2-24 習(xí)題2.9的最簡DFA 55.2.10 有一臺(tái)自動(dòng)售貨機(jī)，接收1分和2分硬幣，出售3分錢一塊的硬糖。顧客每次向機(jī)器中投放大于等于3分的硬幣，便可得到一塊糖(注意：只給一塊并且不找錢)。(1) 寫出售貨機(jī)售糖的正規(guī)表達(dá)式；(2) 構(gòu)造識(shí)別上述正規(guī)式的最簡DFA?！窘獯稹?(1) 設(shè)a=1，b=2，則售貨機(jī)售糖的正規(guī)表達(dá)式為a (b|a(a|b)|b(a|b)。(2) 畫出與正規(guī)表達(dá)式a(b|a(a|b)|b(a|b)對應(yīng)的NFA，如圖2-25所示。用子集法將圖2-25所示的NFA確定化，如圖2-26所示。56.2.10 有一臺(tái)自動(dòng)售貨機(jī)，接收

24、1分和2分硬幣，出售3圖2-25 習(xí)題2.10的NFA57.圖2-25 習(xí)題2.10的NFA57.由圖2-26可看出，非終態(tài)2和非終態(tài)3面對輸入符號a或b的下一狀態(tài)相同，故合并為一個(gè)狀態(tài)，即最簡狀態(tài)0、1、2，3、4。圖2-26 習(xí)題2.10的狀態(tài)轉(zhuǎn)換矩陣 58.由圖2-26可看出，非終態(tài)2和非終態(tài)3面對輸入按順序重新命名為0、1、2、3，則得到最簡DFA，如圖2-27所示。圖2-27 習(xí)題2.10的最簡DFA 59.按順序重新命名為0、1、2、3，則得到最簡DFA，如圖2第三章 語 法 分 析3.1 完成下列選擇題：(1) 程序語言的語義需要 用來描述。A上下文無關(guān)文法 B上下文有關(guān)文法C正

25、規(guī)文法 D短語文法(2) 2型文法對應(yīng) 。A圖靈機(jī) B有限自動(dòng)機(jī) C下推自動(dòng)機(jī) D線性界限自動(dòng)機(jī)60.第三章 語 法 分 析3.1 完成下列(3) 下述結(jié)論中， 是正確的。A1型語言 0型語言 B2型語言 1型語言 C3型語言 2型語言 DAC均不成立(4) 有限狀態(tài)自動(dòng)機(jī)能識(shí)別_。A上下文無關(guān)文法 B上下文有關(guān)文法 C正規(guī)文法 D短語文法(5) 文法GS： SxSx | y 所識(shí)別的語言是 。Axyx B(xyx)* Cxnyxn (n0) Dx*yx*61.(3) 下述結(jié)論中， 是正確的。A1(6) 只含有單層分枝的子樹稱為“簡單子樹”，則句柄的直觀解釋是 。A子樹的末端結(jié)點(diǎn)(即樹葉)組成

26、的符號串B簡單子樹的末端結(jié)點(diǎn)組成的符號串C最左簡單子樹的末端結(jié)點(diǎn)組成的符號串D最左簡單子樹的末端結(jié)點(diǎn)組成的符號串且該符號串必須含有終結(jié)符62.(6) 只含有單層分枝的子樹稱為“簡單子樹”，則句柄的直(7) 下面對語法樹錯(cuò)誤的描述是 。A根結(jié)點(diǎn)用文法GS的開始符S標(biāo)記B每個(gè)結(jié)點(diǎn)用GS的一個(gè)終結(jié)符或非終結(jié)符標(biāo)記C如果某結(jié)點(diǎn)標(biāo)記為，則它必為葉結(jié)點(diǎn)D內(nèi)部結(jié)點(diǎn)可以是非終結(jié)符(8) 由文法開始符S經(jīng)過零步或多步推導(dǎo)產(chǎn)生的符號序列是 。A短語 B句柄 C句型 D句子63.(7) 下面對語法樹錯(cuò)誤的描述是 。A(9) 設(shè)文法GS： SSA | AAa | b則對句子aba的規(guī)范推導(dǎo)是 。AS SA SAA A

27、AA aAA abA aba BS SA SAA AAA AAa Aba abaCS SA SAA SAa Sba Aba abaDS SA Sa SAa Sba Aba aba 64.(9) 設(shè)文法GS： SSA | AAa (10) 如果文法GS是無二義的，則它的任何句子其 。A最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹必定相同B最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹可能不同C最左推導(dǎo)和最右推導(dǎo)必定相同D可能存在兩個(gè)不同的最右推導(dǎo)，但它們對應(yīng)的語法樹相同 (11) 一個(gè)句型的分析樹代表了該句型的 。A推導(dǎo)過程 B歸約過程 C生成過程 D翻譯過程65.(10) 如果文法GS是無二義的，則它的任何句子其(12)

28、規(guī)范歸約中的“可歸約串”由 定義。A直接短語 B最右直接短語 C最左直接短語 D最左素短語(13) 規(guī)范歸約是指 。A最左推導(dǎo)的逆過程 B最右推導(dǎo)的逆過程C規(guī)范推導(dǎo) D最左歸約的逆過程66.(12) 規(guī)范歸約中的“可歸約串”由 定義。(14) 文法GS：SaAcB | Bd AAaB | c BbScA | b則句型aAcbBdcc的短語是 。ABd Bcc Ca Db(15) 文法GE：EE+T | T TT*P | P P(E) | i則句型P+T+i的句柄和最左素短語是 。AP+T和T BP和P+T Ci和P+T+i DP和P 67.(14) 文法GS：SaAcB | Bd (16) 采

29、用自頂向下分析，必須 。A消除左遞歸 B消除右遞歸 C消除回朔 D提取公共左因子(17) 對文法GE：EE+S | S SS*F | F F(E) | i則FIRST(S)= 。A( B ( , i C i D ( , ) 68.(16) 采用自頂向下分析，必須 。A(18) 確定的自頂向下分析要求文法滿足 。A不含左遞歸 B不含二義性 C無回溯 DAC項(xiàng)(19) 遞歸下降分析器由一組遞歸函數(shù)組成，且每一個(gè)函數(shù)對應(yīng)文法的 。A一個(gè)終結(jié)符 B一個(gè)非終結(jié)符 C多個(gè)終結(jié)符 D多個(gè)非終結(jié)符(20) LL(1)分析表需要預(yù)先定義和構(gòu)造兩族與文法有關(guān)的集合 。AFIRST和FOLLOW BFIRSTVT和

30、FOLLOW CFIRST和LASTVT DFIRSTVT和LASTVT69.(18) 確定的自頂向下分析要求文法滿足 。(21) 設(shè)a、b、c是文法的終結(jié)符且滿足優(yōu)先關(guān)系ab和bc,則 。A必有ac B必有ca C必有ba DAC 都不一定成立(22) 算符優(yōu)先分析法要求 。A文法不存在QR的句型且任何終結(jié)符對(a,b)滿足ab、ab和ab三種關(guān)系 B文法不存在QR的句型且任何終結(jié)符對(a,b)至多滿足ab、ab和ab三種關(guān)系之一70.(21) 設(shè)a、b、c是文法的終結(jié)符且滿足優(yōu)先關(guān)系ab和C文法可存在QR的句型且任何終結(jié)符對(a,b)至多滿足ab、ab和ab三種關(guān)系之一D文法可存在QR的句

31、型且任何終結(jié)符對(a,b)滿足ab、ab和ab三種關(guān)系(23) 任何算符優(yōu)先文法 優(yōu)先函數(shù)。A有一個(gè) B沒有 C有若干個(gè) D可能有若干個(gè)(24) 在算符優(yōu)先分析中，用 來刻畫可歸約串。A句柄 B直接短語 C素短語 D最左素短語71.C文法可存在QR的句型且任何終結(jié)符對(a,b)至多(25) 下面最左素短語必須具備的條件中有錯(cuò)誤的是 。A至少包含一個(gè)終結(jié)符 B至少包含一個(gè)非終結(jié)符 C除自身外不再包含其他素短語 D在句型中具有最左性(26) 對文法GS：Sb | | (T) TT，S | S其FIRSTVT(T)為 。Ab, ,( Bb, , ) C，,b, , ( D，,b, , ) 72.(2

32、5) 下面最左素短語必須具備的條件中有錯(cuò)誤的是 (27) 對文法GE：EE*T | T TT+i | i句子1+2*8+6歸約的值為 。A23 B42 C30 D17 (28) 下述FOLLOW集構(gòu)造方法中錯(cuò)誤的是 。A對文法開始符S有#FOLLOW(S)B若有AB，則有FIRST()FOLLOW(B) C若有AB，則有FOLLOW(B)FOLLOW(A)D若有AB，則有FOLLOW(A)FOLLOW(B)73.(27) 對文法GE：EE*T | T (29) 若文法GS的產(chǎn)生式有AB出現(xiàn)，則對A求FOLLOW集正確的是 。AFOLLOW(B)FOLLOW(A) BFIRSTVT(B) FOL

33、LOW(A) CFIRST(B) FOLLOW(A) DLASTVT(B)FOLLOW(A)(30) 下面 是自底向上分析方法。A預(yù)測分析法 B遞歸下降分析法 CLL(1)分析法 D算符優(yōu)先分析法74.(29) 若文法GS的產(chǎn)生式有AB出現(xiàn)，則對A求(31) 下面 是采用句柄進(jìn)行歸約的。A算符優(yōu)先分析法 B預(yù)測分析法 CSLR(1)分析法 DLL(1)分析法(32) 一個(gè) 指明了在分析過程中某時(shí)刻能看到產(chǎn)生式多大一部分。A活前綴 B前綴 C項(xiàng)目 D項(xiàng)目集(33) 若B為非終結(jié)符，則AB為 項(xiàng)目。A接受 B歸約 C移進(jìn) D待約75.(31) 下面 是采用句柄進(jìn)行歸約的。A(34) 在LR(0)的

34、ACTION子表中，如果某一行中存在標(biāo)記為“rj”的欄，則 。A該行必定填滿rj B該行未填滿rj C其他行也有rj DGOTO子表中也有rj(35) LR分析法解決“移進(jìn)歸約”沖突時(shí)，左結(jié)合意味著 。A打斷聯(lián)系實(shí)行移進(jìn) B打斷聯(lián)系實(shí)行歸約 C建立聯(lián)系實(shí)行移進(jìn) D建立聯(lián)系實(shí)行歸約76.(34) 在LR(0)的ACTION子表中，如果某一行中存(36) LR分析法解決“移進(jìn)歸約”沖突時(shí)，右結(jié)合意味著 。A打斷聯(lián)系實(shí)行歸約 B建立聯(lián)系實(shí)行歸約 C建立聯(lián)系實(shí)行移進(jìn) D打斷聯(lián)系實(shí)行移進(jìn)77.(36) LR分析法解決“移進(jìn)歸約”沖突時(shí)，右結(jié)合意【解答】 (1) 參見第四章4.1.1節(jié)，語義分析不像詞法分

35、析和語法分析那樣可以分別用正規(guī)文法和上下文無關(guān)文法描述，由于語義是上下文有關(guān)的，因此語義分析須用上下文有關(guān)文法描述。即選B。(2) 2型文法對應(yīng)下推自動(dòng)機(jī)。故選C。(3) 由于不存在：3型語言 2型語言 1型語言 0型語言。故選D。(4) 3型文法即正規(guī)文法，它的識(shí)別系統(tǒng)是有限狀態(tài)自動(dòng)機(jī)。故選C。78.【解答】 (1) 參見第四章4.1.1節(jié)，語義分(5) 由SxSx | y可知該文法所識(shí)別的語言一定是：y左邊出現(xiàn)的x與y右邊出現(xiàn)的x相等。故選C。(6) 最左簡單子樹的末端結(jié)點(diǎn)組成的符號串為句柄。故選C。(7) 內(nèi)部結(jié)點(diǎn)(指非樹葉結(jié)點(diǎn))一定是非終結(jié)符。故選D。(8) 由文法開始符S經(jīng)過零步或多

36、步推導(dǎo)產(chǎn)生的符號序列一定是句型，僅當(dāng)推導(dǎo)產(chǎn)生的符號序列全部由終結(jié)符組成時(shí)才是句子，即句子是句型的陣列。故選C。(9) 規(guī)范推導(dǎo)即最右推導(dǎo)，也即每一步推導(dǎo)都是對句型中的最右非終結(jié)符用相應(yīng)產(chǎn)生式的右部進(jìn)行替換。故選D。 79.(5) 由SxSx | y可知該文法所識(shí)別的語言一定是(10) 文法GS的一個(gè)句子如果能找到兩種不同的最左推導(dǎo)(或最右推導(dǎo))，或存在兩棵不同的語法樹，則它的任何句子其最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹必定相同。故選A。(11) 一個(gè)句型的分析樹代表了該句型的歸約過程。故選B。(12) 規(guī)范歸約中的“可歸約串”即為句柄，也就是最左直接短語。故選C。(13) 規(guī)范歸約的逆過程是規(guī)范推

37、導(dǎo)，而規(guī)范推導(dǎo)即為最右推導(dǎo)。故選B。(14) 由圖3-1可知應(yīng)選A。80.(10) 文法GS的一個(gè)句子如果能找到兩種不同的最左圖3-1 句型aAcbBdcc對應(yīng)的語法樹 81.圖3-1 句型aAcbBdcc對應(yīng)的語法樹 81.(15) 由圖3-2可知，句柄(最左直接短語)為P，最左素短語為P+T。故選B。(16) 回溯使自頂向下分析效率降低，左遞歸使得自頂向下的分析無法實(shí)現(xiàn)；二者相比消除左遞歸更為重要。故選A。(17) FIRST(F)=(,i，而由SF可知FIRST(F) FIRST(S)，即FIRST(S)=(,i。故選B。(18) 左遞歸和二義性將無法實(shí)現(xiàn)自頂向下分析，回溯則使自頂向下分

38、析效率下降。故選D。82.(15) 由圖3-2可知，句柄(最左直接短語)為P，最左圖3-2 句型P+T+i對應(yīng)的語法樹及優(yōu)先關(guān)系示意 83.圖3-2 句型P+T+i對應(yīng)的語法樹及優(yōu)先關(guān)系示意 83.(19) 遞歸下降分析器由一組遞歸函數(shù)組成，且每一個(gè)函數(shù)對應(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ù)，且只要存在一對優(yōu)先函數(shù)，就存在無窮多對優(yōu)先函數(shù)。

39、故選D。(24) 在算符優(yōu)先分析中是以“最左素短語”來刻畫可歸約串的。故選D。84.(19) 遞歸下降分析器由一組遞歸函數(shù)組成，且每一個(gè)函數(shù)(25) 最左素短語必須具備的三個(gè)條件是： 至少包含一個(gè)終結(jié)符； 除自身外不得包含其他素短語； 在句型中具有最左性。故選B。(26) FIRSTVT(T)=，F(xiàn)IRSTVT(S)=b, ,(；由TS可知FIRSTV(S)FIRSTVT(T)，即FIRSTVT(T)=，,b, , ( 。故選C。(27) 由圖3-3可知應(yīng)選B。(28) 若有AB則有FOLLOW(A)FOLLOW(B)，即選項(xiàng)C錯(cuò)。故選C。(29) 若文法GS的產(chǎn)生式有AB出現(xiàn)，則有FIRST

40、(B)FOLLOW(A)。故選C。85.(25) 最左素短語必須具備的三個(gè)條件是： 至少包含一圖3-3 句子1+2*8+6的語法樹及值變化示意 86.圖3-3 句子1+2*8+6的語法樹及值變化示意 86.(30) 自底向上的分析方法有算符優(yōu)先分析法和LR分析法。故選D。(31) 自底向上分析采用歸約方法，但算符優(yōu)先分析用“最左素短語”歸約，而LR分析用“句柄”歸約。SLR(1)是LR分析法的一種，故選C。(32) 在LR分析中，一個(gè)項(xiàng)目指明了在分析過程的某個(gè)時(shí)刻所看到產(chǎn)生式的多大一部分。故選C。(33) 對文法GS，S稱為“接受”項(xiàng)目；形如Aa的項(xiàng)目(其中a為終結(jié)符)稱為“移進(jìn)”項(xiàng)目；形如A

41、B的項(xiàng)目(其中B為非終結(jié)符)稱為“待約”項(xiàng)目。故選D。87.(30) 自底向上的分析方法有算符優(yōu)先分析法和LR分析法(34) 在LR(0)的ACTION子表中，如果某一行存在標(biāo)注為“rj”的欄，則該行必定填滿rj，而在SLR(1)的ACTION子表中，如果某一行存在標(biāo)注為“rj”的欄，則該行可能未填滿rj。因此選A。(35) LR分析法解決“移進(jìn)歸約”沖突時(shí)，左結(jié)合意味著打斷聯(lián)系而實(shí)行歸約，右結(jié)合意味著維持聯(lián)系而實(shí)行移進(jìn)。故選B。(36) 由(35)可知應(yīng)選C。88.(34) 在LR(0)的ACTION子表中，如果某一行存3.2 令文法GN為 GN: ND|NDD0|1|2|3|4|5|6|7

42、|8|9(1) GN的語言L(G)是什么?(2) 給出句子0127、34和568的最左推導(dǎo)和最右推導(dǎo)。89.3.2 令文法GN為 GN【解答】 (1) GN的語言L(GN)是非負(fù)整數(shù)。(2) 最左推導(dǎo)： 最右推導(dǎo)：90.【解答】 (1) GN的語言L(GN3.3 已知文法GS為SaSb|Sb|b，試證明文法GS為二義文法。【解答】 由文法GS：SaSb|Sb|b，對句子aabbbb可對應(yīng)如圖3-4所示的兩棵語法樹。因此，文法GS為二義文法(對句子abbb也可畫出兩棵不同的語法樹)。91.3.3 已知文法GS為SaSb|Sb|b圖3-4 句子aabbbb對應(yīng)的兩棵不同語法樹 92.圖3-4 句子

43、aabbbb對應(yīng)的兩棵不同語法樹 92.3.4 已知文法GS為SSaS|，試證明文法GS為二義文法?！窘獯稹?由文法GS：SSaS|，句子aa的語法樹如圖3-5所示。由圖3-5可知，文法GS為二義文法。93.3.4 已知文法GS為SSaS|，試證明文圖3-5 句子aa對應(yīng)的兩棵不同的語法樹 94.圖3-5 句子aa對應(yīng)的兩棵不同的語法樹 94.3.5 按指定類型，給出語言的文法。 (1) L=aibj|ji0的上下文無關(guān)文法；(2) 字母表=a,b上的同時(shí)只有奇數(shù)個(gè)a和奇數(shù)個(gè)b的所有串的集合的正規(guī)文法；(3) 由相同個(gè)數(shù)a和b組成句子的無二義文法?！窘獯稹?(1) 由L=aibj|ji0知，所

44、求該語言對應(yīng)的上下文無關(guān)文法首先應(yīng)有SaSb型產(chǎn)生式，以保證b的個(gè)數(shù)不少于a的個(gè)數(shù)；其次，還需有SSb或Sb型的產(chǎn)生式，用以保證b的個(gè)數(shù)多于a的個(gè)數(shù)。因此，所求上下文無關(guān)文法GS為GS：SaSb|Sb|b95.3.5 按指定類型，給出語言的文法。 (2) 為了構(gòu)造字母表=a,b上同時(shí)只有奇數(shù)個(gè)a和奇數(shù)個(gè)b的所有串集合的正規(guī)式，我們畫出如圖3-6所示的DFA，即由開始符S出發(fā)，經(jīng)過奇數(shù)個(gè)a到達(dá)狀態(tài)A，或經(jīng)過奇數(shù)個(gè)b到達(dá)狀態(tài)B；而由狀態(tài)A出發(fā)，經(jīng)過奇數(shù)個(gè)b到達(dá)狀態(tài)C(終態(tài))；同樣，由狀態(tài)B出發(fā)經(jīng)過奇數(shù)個(gè)a到達(dá)終態(tài)C。由圖3-6可直接得到正規(guī)文法GS如下： GS：SaA|bB AaS|bC|b Bb

45、S|aC|a CbA|aB|96.(2) 為了構(gòu)造字母表=a,b上同時(shí)只有奇數(shù)個(gè)a和圖3-697.圖3-697.(3) 我們用一個(gè)非終結(jié)符A代表一個(gè)a(即有Aa)，用一個(gè)非終結(jié)符B代表一個(gè)b(即有Bb)；為了保證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)有bAbbAA。也即為了保證b和A的個(gè)數(shù)一致，應(yīng)有AbAA；同理有BaBB。此外，為了保證遞歸地推出所要求的ab串，應(yīng)有SaBS和SbAS。由此得到無二義文法GS為 GS：SaBS|bAS| AbAA|a BaBB|b98.(3) 我們用一個(gè)非終結(jié)符A

46、代表一個(gè)a(即有Aa)，用3.6 有文法GS: SaAcB|BdAAaB|cBbScA|b(1) 試求句型aAaBcbbdcc和aAcbBdcc的句柄；(2) 寫出句子acabcbbdcc的最左推導(dǎo)過程。【解答】 (1) 分別畫出對應(yīng)句型aAaBcbbdcc和aAcbBdcc的語法樹如圖3-7的(a)、(b)所示。對樹(a)，直接短語有3個(gè)：AaB、b和c，而AaB為最左直接短語(即為句柄)。對樹(b)，直接短語有兩個(gè)：Bd和c，而Bd為最左直接短語。99.3.6 有文法GS: SaAcB|Bd能否不畫出語法樹，而直接由定義(即在句型中)尋找滿足某個(gè)產(chǎn)生式的候選式這樣一個(gè)最左子串(即句柄)呢？

47、例如，對句型aAaBcbbdcc，我們可以由左至右掃描找到第一個(gè)子串AaB，它恰好是滿足AAaB右部的子串；與樹(a)對照，AaB的確是該句型的句柄。是否這一方法始終正確呢？我們繼續(xù)檢查句型aAcbBdcc，由左至右找到第一個(gè)子串c，這是滿足Ac右部的子串，但由樹(b)可知，c不是該句型的句柄。由此可知，畫出對應(yīng)句型的語法樹然后尋找最左直接短語是確定句柄的好方法。100.能否不畫出語法樹，而直接由定義(即在句型中)尋找滿足某個(gè)圖3-7 習(xí)題3.6的語法樹 (a) aAaBcbbdcc; (b) aAcbBdcc101.圖3-7 習(xí)題3.6的語法樹 101.(2) 句子acabcbbdcc的最左

48、推導(dǎo)如下：102.(2) 句子acabcbbdcc的最左推導(dǎo)如下：102.3.7 對于文法GS: S(L)|aS|aLL,S|S(1) 畫出句型(S,(a)的語法樹；(2) 寫出上述句型的所有短語、直接短語、句柄、素短語和最左素短語。103.3.7 對于文法GS: S(L)|aS|【解答】 (1) 句型(S, (a)的語法樹如圖3-8所示。(2) 由圖3-8可知：短語：S、a、(a)、S,(a)、(S,(a)；直接短語：a、S；句柄：S；素短語：素短語可由圖3-8中相鄰終結(jié)符之間的優(yōu)先關(guān)系求得，即： # (， (a)#因此，素短語為a。104.【解答】 (1) 句型(S, (a)的語法樹如圖3

49、-8圖3-8 句型(S,(a)的語法樹 105.圖3-8 句型(S,(a)的語法樹 105.3.8 下述文法描述了C語言整數(shù)變量的聲明語句：GD: DTLTint|long|shortLid|L,id(1) 改造上述文法，使其接受相同的輸入序列，但文法是右遞歸的；(2) 分別以上述文法GD和改造后的文法GD為輸入序列int a,b,c構(gòu)造分析樹。106.3.8 下述文法描述了C語言整數(shù)變量的聲明語句：【解答】 (1) 消除左遞歸后，文法GD如下：DTLTint|long|shortLidLL,idL|(2) 未消除左遞歸的文法G(D)和消除左遞歸的文法GD為輸入序列int a,b,c構(gòu)造的分析

50、樹分別如圖3-9的(a)、(b)所示。107.【解答】 (1) 消除左遞歸后，文法GD如下：圖3-9 兩種文法為int a,b,c構(gòu)造的分析樹(a) 文法G(D)； (b) 文法G(D)108.圖3-9 兩種文法為int a,b,c構(gòu)造的分析樹108.3.9 考慮文法GS: S(T) | a+S | aTT,S | S消除文法的左遞歸及提取公共左因子，然后對每個(gè)非終結(jié)符寫出不帶回溯的遞歸子程序?！窘獯稹?消除文法GS的左遞歸：S(T) | a+S | aTSTT,ST| 109.3.9 考慮文法GS: S(T) | a+S |提取公共左因子：S(T) | aSS+S | TSTT,ST| 11

51、0.提取公共左因子：S(T) | aS改造后的文法已經(jīng)是LL(1)文法，不帶回溯的遞歸子程序如下：void match (token t) if ( lookahead=t)lookahead=nexttoken; else error ( );void S ( )111.改造后的文法已經(jīng)是LL(1)文法，不帶回溯的遞歸子程序如 if ( lookahead=a) match (a);S(); else if ( lookahead=()match ();T ( );if ( lookahead=) )match () );else error ( );112. if ( lookahead=

52、a)void S( ) if ( lookahead=+)match (+);S ( );void T ( ) S ( );T( );113.void S( ) if ( lovoid T ( ) if ( lookahead=, )match (, );S ( );T ( );114.void T ( ) if對于文法GS中的產(chǎn)生式：TT,S | S，即將非終結(jié)符T由下面的正規(guī)表達(dá)式定義： TS,S然后將其用狀態(tài)轉(zhuǎn)換圖表示為圖3-10。這個(gè)狀態(tài)轉(zhuǎn)換圖的作用就如同一個(gè)遞歸過程(函數(shù))，并借助于這種轉(zhuǎn)換圖來得到遞歸過程(函數(shù))下降分析器。因此，前面的遞歸下降分析器程序可刪除函數(shù)T()和T()，而

53、將T()和T()改為115.對于文法GS中的產(chǎn)生式：TT,S | S，即將非終圖3-10 非終結(jié)符T的狀態(tài)轉(zhuǎn)換圖116.圖3-10 非終結(jié)符T的狀態(tài)轉(zhuǎn)換圖116.void T()S();while (lookahead = ,)match (,);S();117.void T()S();3.10 已知文法GA: AaABl|aBBb|d(1) 試給出與GA等價(jià)的LL(1)文法GA；(2) 構(gòu)造GA的LL(1)分析表；(3) 給出輸入串a(chǎn)adl#的分析過程。【解答】 (1) 文法GA存在左遞歸和回溯，故其不是LL(1)文法。要將GA改造為LL(1)文法，首先要消除文法的左遞歸，即將形如PP |

54、的產(chǎn)生式改造為PPPP| 118.3.10 已知文法GA: AaABl|a來消除左遞歸。由此，將產(chǎn)生式BBb|d改造為BdBBbB| 其次，應(yīng)通過提取公共左因子的方法來消除GA中的回溯，即將產(chǎn)生式AaABl|a改造為AaAAABl | 最后得到改造后的文法為GA：AaAAABl | BdBBbB| 119.來消除左遞歸。由此，將產(chǎn)生式BBb|d改造為求得： FIRST(A)=a FIRST(A)=a, FIRST(B)=d FIRST(B)=b, 對文法開始符號A，有FOLLOW(A)=#。由AABl得FIRST(B) FOLLOW(A)，即FOLLOW(A)=#,d； 由AABl得FIRST

55、(l) FOLLOW(B)，即FOLLOW(B)=l；120.求得： FIRST(A)=a 由AaA得FOLLOW(A) FOLLOW(A)，即FOLLOW(A)=#,d；由BdB得FOLLOW(B) FOLLOW(B)，即FOLLOW(B)=l。 對AABl來說，F(xiàn)IRST(A)FOLLOW(A)=a#,d=，所以文法GA為所求等價(jià)的LL(1)文法。121.由AaA得FOLLOW(A) FOLLOW(A)(2) 構(gòu)造預(yù)測分析表的方法如下： 對文法GA的每個(gè)產(chǎn)生式A執(zhí)行、步。 對每個(gè)終結(jié)符aFIRST(A)，把A加入到MA,a中，其中為含有首字符a的候選式或?yàn)槲ㄒ坏暮蜻x式。 若FIRST(A)

56、，則對任何屬于FOLLOW(A)的終結(jié)符b，將A加入到MA,b中。把所有無定義的MA,a標(biāo)記上“出錯(cuò)”。由此得到GA的預(yù)測分析表，見表3-1。(3) 輸入串a(chǎn)adl的分析過程見表3-2。122.(2) 構(gòu)造預(yù)測分析表的方法如下： 對文法G表3-1 預(yù)測分析表 123.表3-1 預(yù)測分析表 123.表3-2 輸入串a(chǎn)adl的分析過程 124.表3-2 輸入串a(chǎn)adl的分析過程 124.3.11 將下述文法改造為LL(1)文法： GV: VN | NEEV | V+ENi【解答】 LL(1)文法的基本條件是不含左遞歸和回溯(公共左因子)，而文法GV中含有回溯，所以先消除回溯，得到文法GV： GV：

57、VNV V | E EVE E | +E Ni125.3.11 將下述文法改造為LL(1)文法： 一個(gè)LL(1)文法的充要條件是：對每一個(gè)終結(jié)符A的任何兩個(gè)不同產(chǎn)生式A|有下面的條件成立：(1) FIRST()FIRST()=； (2) 假若 ，則有FIRST()FOLLOW(A)= 。即求出GV的FIRST和FOLLOW集如下：FIRST(N)=FIRST(V)=FIRST(E)=iFIRST(V)=, FIRST(E)=+, FOLLOW(V)=#126.一個(gè)LL(1)文法的充要條件是：對每一個(gè)終結(jié)符A的任何兩由VE得FIRST() FOLLOW(E)，即FOLLOW(E)= ；由VNV得

58、FIRST(V) FOLLOW(N)，即FOLLOW(N)= ；由EVE得FIRST(E) FOLLOW(V)，即FOLLOW(V)=#,+；由VNV得FOLLOW(V) FOLLOW(V)，即FOLLOW(V)=#,+；由VNV且V得FOLLOW(V) FOLLOW(N)， 即FOLLOW(N)=,#,+；由EVE得FOLLOW(E) FOLLOW(E)，即FOLLOW(E)= ；127.由VE得FIRST() FOLLO則，對V |E有：FIRST()FIRST()= ；對E | +E有：FIRST()FIRST(+)= ；對V | E有：FIRST()FOLLOW(V)=#,+=；對E

59、| +E有：FIRST(+)FOLLOW(E)=+=。故文法GV為LL(1)文法。128.則，對V |E有：FIRST()FIRST(3.12 對文法GE: EE+T|T TT*P|P Pi(1) 構(gòu)造該文法的優(yōu)先關(guān)系表(不考慮語句括號#)，并指出此文法是否為算符優(yōu)先文法；(2) 構(gòu)造文法GE的優(yōu)先函數(shù)。129.3.12 對文法GE: EE+T|T 【解答】 (1) FIRSTVT集構(gòu)造方法： 由Pa或PQa，則aFIRSTVT(P)。 若aFIRSTVT(Q)，且PQ，則aFIRSTVT(P)，也即FIRSTVT(Q) FIRSTVT(P)。由得：由EE+得FIRSTVT(E)=+； 由TT

60、*得FIRSTVT(T)=*； 由Pi得FIRSTVT(P)=i。由得：由TP得FIRSTVT(P) FIRSTVT(T)，即FIRSTVT(T)=*，i； 由ET得FIRSTVT(T) FIRSTVT(E)，即FIRSTVT(E)=+，*，i。 130.【解答】 (1) FIRSTVT集構(gòu)造方法：LASTVT集構(gòu)造方法： 由Pa或PaQ, 則aLASTVT(P)。 若aLASTVT(Q)，且PQ，則aLASTVT(P)，也即LASTVT(Q) LASTVT(P)。由得：E+T，得LASTVT(E)=+； T*P，得LASTVT(T)=*； Pi，得LASTVT(P)=i。131.LASTVT