,第一章緒論第二章詞法分析第三章語法分析,1,第一章緒論1.1完成下列選擇題：(1)下面敘述中正確的是。A編譯程序是將高級語言程序翻譯成等價(jià)的機(jī)器語言程序的程序B機(jī)器語言因其使用過于困難，所以現(xiàn)在計(jì)算機(jī)根本不使用機(jī)器語言C匯編語言是計(jì)算機(jī)唯一能夠直接識別并接受的語言D高級語言接近人們的自然語言，但其依賴具體機(jī)器的特性是無法改變的,2,(2)將編譯過程分成若干“遍”是為了。A提高程序的執(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)語言C編譯方法DAC項(xiàng),3,(4)編譯程序絕大多數(shù)時(shí)間花在上。A出錯(cuò)處理B詞法分析B目標(biāo)代碼生成D表格管理(5)編譯程序是對。A匯編程序的翻譯B高級語言程序的解釋執(zhí)行C機(jī)器語言的執(zhí)行D高級語言的翻譯,4,【解答】(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)容。故選D。,5,(4)編譯各階段的工作都涉及到構(gòu)造、查找或更新有關(guān)表格，即編譯過程的絕大部分時(shí)間都用在造表、查表和更新表格的事務(wù)上。故選D。(5)由(1)可知，編譯程序?qū)嶋H上實(shí)現(xiàn)了對高級語言程序的翻譯。故選D。,6,1.2計(jì)算機(jī)執(zhí)行用高級語言編寫的程序有哪些途徑？它們之間的主要區(qū)別是什么？【解答】計(jì)算機(jī)執(zhí)行用高級語言編寫的程序主要有兩種途徑：解釋和編譯。在解釋方式下，翻譯程序事先并不采用將高級語言程序全部翻譯成機(jī)器代碼程序，然后執(zhí)行這個(gè)機(jī)器代碼程序的方法，而是每讀入一條源程序的語句，就將其解釋(翻譯)成對應(yīng)其功能的機(jī)器代碼語句串并執(zhí)行，然后再讀入下一條源程序語句并解釋執(zhí)行，而所翻譯的機(jī)器代碼語句串在該語句執(zhí)行后并不保留。這種方法是按源程序中語句的動態(tài)執(zhí)行順序逐句解釋(翻譯)執(zhí)行的，如果一語句處于一循環(huán)體中，則每次循環(huán)執(zhí)行到該語句時(shí)，都要將其翻譯成機(jī)器代碼后再執(zhí)行。,7,在編譯方式下，高級語言程序的執(zhí)行是分兩步進(jìn)行的：第一步首先將高級語言程序全部翻譯成機(jī)器代碼程序，第二步才是執(zhí)行這個(gè)機(jī)器代碼程序。因此，編譯對源程序的處理是先翻譯，后執(zhí)行。從執(zhí)行速度上看，編譯型的高級語言比解釋型的高級語言要快，但解釋方式下的人機(jī)界面比編譯型好，便于程序調(diào)試。這兩種途徑的主要區(qū)別在于：解釋方式下不生成目標(biāo)代碼程序，而編譯方式下生成目標(biāo)代碼程序。,8,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è)備及軟件工具等諸因素對編譯程序構(gòu)造的影響。,9,圖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,(3)詞法分析器的輸出是。A單詞的種別編碼B單詞的種別編碼和自身的值C單詞在符號表中的位置D單詞自身值(4)狀態(tài)轉(zhuǎn)換圖(見圖2-1)接受的字集為_。A以0開頭的二進(jìn)制數(shù)組成的集合B以0結(jié)尾的二進(jìn)制數(shù)組成的集合C含奇數(shù)個(gè)0的二進(jìn)制數(shù)組成的集合D含偶數(shù)個(gè)0的二進(jìn)制數(shù)組成的集合,12,圖2-1習(xí)題2.1的DFAM,13,(5)對于任一給定的NFAM，一個(gè)DFAM，使L(M)=L(M)。A一定不存在B一定存在C可能存在D可能不存在(6)DFA適用于。A定理證明B語法分析C詞法分析D語義加工,14,(7)下面用正規(guī)表達(dá)式描述詞法的論述中，不正確的是。A詞法規(guī)則簡單，采用正規(guī)表達(dá)式已足以描述B正規(guī)表達(dá)式的表示比上下文無關(guān)文法更加簡潔、直觀和易于理解C正規(guī)表達(dá)式描述能力強(qiáng)于上下文無關(guān)文法D有限自動機(jī)的構(gòu)造比下推自動機(jī)簡單且分析效率高(8)與(a|b)*(a|b)等價(jià)的正規(guī)式是。A(a|b)(a|b)*Ba*|b*C(ab)*(a|b)*D(a|b)*,15,【解答】(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,(5)NFA可以有DFA與之等價(jià)，即兩者描述能力相同；也即，對于任一給定的NFAM，一定存在一個(gè)DFAM，使L(M)=L(M)。故選B。(6)DFA便于識別，易于計(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,2.2什么是掃描器？掃描器的功能是什么？【解答】掃描器就是詞法分析器，它接受輸入的源程序，對源程序進(jìn)行詞法分析并識別出一個(gè)個(gè)單詞符號，其輸出結(jié)果是單詞符號，供語法分析器使用。通常把詞法分析器作為一個(gè)子程序，每當(dāng)語法分析器需要一個(gè)單詞符號時(shí)就調(diào)用這個(gè)子程序。每次調(diào)用時(shí)，詞法分析器就從輸入串中識別出一個(gè)單詞符號交給語法分析器。,18,2.3設(shè)M=(x,y,a,b,f,x,y)為一非確定的有限自動機(jī)，其中f定義如下：f(x,a)=x,yfx,b=yf(y,a)=fy,b=x,y試構(gòu)造相應(yīng)的確定有限自動機(jī)M?！窘獯稹繉φ兆詣訖C(jī)的定義M=(S,f,s0,Z)，由f的定義可知f(x,a)、f(y,b)均為多值函數(shù)，因此M是一非確定有限自動機(jī)。先畫出NFAM相應(yīng)的狀態(tài)圖，如圖2-2所示。,19,圖2-2習(xí)題2.3的NFAM,20,用子集法構(gòu)造狀態(tài)轉(zhuǎn)換矩陣，如表2-1所示。表2-1狀態(tài)轉(zhuǎn)換矩陣將轉(zhuǎn)換矩陣中的所有子集重新命名，形成表2-2所示的狀態(tài)轉(zhuǎn)換矩陣，即得到,21,將圖2-3所示的DFAM最小化。首先，將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。最后，得到如圖2-4所示的化簡了的DFAM。,圖2-3習(xí)題2.3的DFAM,其狀態(tài)轉(zhuǎn)換圖如圖2-3所示。,22,圖2-4圖2-3化簡后的DFAM,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-5正規(guī)式(ab)*a對應(yīng)的NFA,25,圖2-6正規(guī)式a(ba)*對應(yīng)的NFA,26,圖2-7圖2-5和圖2-6確定化后的狀態(tài)轉(zhuǎn)換矩陣,27,圖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)*對應(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,圖2-9(ab)*a和a(ba)*分別對應(yīng)的NFA,30,2.5設(shè)有L(G)=a2n+1b2ma2p+1|n0,p0,m1。(1)給出描述該語言的正規(guī)表達(dá)式；(2)構(gòu)造識別該語言的確定有限自動機(jī)(可直接用狀態(tài)圖形式給出)。【解答】該語言對應(yīng)的正規(guī)表達(dá)式為a(aa)*bb(bb)*a(aa)*，正規(guī)表達(dá)式對應(yīng)的NFA如圖2-10所示。,31,圖2-10習(xí)題2.5的NFA,32,用子集法將圖2-10確定化，如圖2-11所示。由圖2-11重新命名后的狀態(tài)轉(zhuǎn)換矩陣可化簡為(也可由最小化方法得到)0,213,54,67,圖2-11習(xí)題2.5的狀態(tài)轉(zhuǎn)換矩陣,33,按順序重新命名為0、1、2、3、4后得到最簡的DFA，如圖2-12所示。,圖2-12習(xí)題2.5的最簡DFA,34,2.6有語言L=w|w(0,1)+，并且w中至少有兩個(gè)1，又在任何兩個(gè)1之間有偶數(shù)個(gè)0，試構(gòu)造接受該語言的確定有限狀態(tài)自動機(jī)(DFA)?！窘獯稹繉τ谡Z言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-13習(xí)題2.6的NFA,36,用子集法將圖2-13所示的NFA確定化，如圖2-14所示由圖2-14可看出非終態(tài)2和4的下一狀態(tài)相同，終態(tài)6和8的下一狀態(tài)相同，即得到最簡狀態(tài)為012,4356,87,37,按順序重新命名為0、1、2、3、4、5、6，則得到最簡DFA，如圖2-15所示。,圖2-15習(xí)題2.6的最簡DFA,38,2.7已知正規(guī)式(a|b)*|aa)*b和正規(guī)式(a|b)*b。(1)試用有限自動機(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-16正規(guī)式(a|b)*|aa)*b對應(yīng)的NFA,40,圖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所示的狀態(tài)轉(zhuǎn)換矩陣。,42,表2-3合并后的狀態(tài)轉(zhuǎn)換矩陣,43,圖2-18習(xí)題2.7的最簡DFA,44,圖2-19正規(guī)式(a|b)*b對應(yīng)的NFA,45,比較圖2-20與圖2-17，重新命名后的轉(zhuǎn)換矩陣是完全一樣的，也即正規(guī)式(a|b)*b可以同樣得到化簡后的DFA如圖2-18所示。因此，兩個(gè)自動機(jī)完全一樣，即兩個(gè)正規(guī)文法等價(jià)。,圖2-20圖2-19確定化后的狀態(tài)轉(zhuǎn)換矩陣,46,2.8構(gòu)造一個(gè)DFA，它接收=a,b上所有不含abb的字符串。解：=a,b上所有不含abb的字符串可表示為b*(a*b)a*。,47,2.9構(gòu)造一個(gè)DFA，它接收=a,b上所有含偶數(shù)個(gè)a的字符串。解：=a,b上所有含偶數(shù)個(gè)a的字符串可表示為(b|ab*a)*,48,2.10下列程序段以B表示循環(huán)體，A表示初始化，I表示增量，T表示測試：I=1;while(I=n)sun=sun+aI;I=I+1;請用正規(guī)表達(dá)式表示這個(gè)程序段可能的執(zhí)行序列?！窘獯稹坑谜?guī)表達(dá)式表示程序段可能的執(zhí)行序列為AT(BIT)*。,49,2.9將圖2-21所示的非確定有限自動機(jī)(NFA)變換成等價(jià)的確定有限自動機(jī)(DFA)。其中，X為初態(tài)，Y為終態(tài)?！窘獯稹坑米蛹▽FA確定化，如圖2-22所示。,50,圖2-21習(xí)題2.9的NFA,51,圖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,52,圖2-22所對應(yīng)的DFA如圖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-23習(xí)題2.9的DFA,54,圖2-24習(xí)題2.9的最簡DFA,55,2.10有一臺自動售貨機(jī)，接收1分和2分硬幣，出售3分錢一塊的硬糖。顧客每次向機(jī)器中投放大于等于3分的硬幣，便可得到一塊糖(注意：只給一塊并且不找錢)。(1)寫出售貨機(jī)售糖的正規(guī)表達(dá)式；(2)構(gòu)造識別上述正規(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-25習(xí)題2.10的NFA,57,由圖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,按順序重新命名為0、1、2、3，則得到最簡DFA，如圖2-27所示。,圖2-27習(xí)題2.10的最簡DFA,59,第三章語法分析3.1完成下列選擇題：(1)程序語言的語義需要用來描述。A上下文無關(guān)文法B上下文有關(guān)文法C正規(guī)文法D短語文法(2)2型文法對應(yīng)。A圖靈機(jī)B有限自動機(jī)C下推自動機(jī)D線性界限自動機(jī),60,(3)下述結(jié)論中，是正確的。A1型語言0型語言B2型語言1型語言C3型語言2型語言DAC均不成立(4)有限狀態(tài)自動機(jī)能識別_。A上下文無關(guān)文法B上下文有關(guān)文法C正規(guī)文法D短語文法(5)文法GS：SxSx|y所識別的語言是。AxyxB(xyx)*Cxnyxn(n0)Dx*yx*,61,(6)只含有單層分枝的子樹稱為“簡單子樹”，則句柄的直觀解釋是。A子樹的末端結(jié)點(diǎn)(即樹葉)組成的符號串B簡單子樹的末端結(jié)點(diǎn)組成的符號串C最左簡單子樹的末端結(jié)點(diǎn)組成的符號串D最左簡單子樹的末端結(jié)點(diǎn)組成的符號串且該符號串必須含有終結(jié)符,62,(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,(9)設(shè)文法GS：SSA|AAa|b則對句子aba的規(guī)范推導(dǎo)是。ASSASAAAAAaAAabAabaBSSASAAAAAAAaAbaabaCSSASAASAaSbaAbaabaDSSASaSAaSbaAbaaba,64,(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,(12)規(guī)范歸約中的“可歸約串”由定義。A直接短語B最右直接短語C最左直接短語D最左素短語(13)規(guī)范歸約是指。A最左推導(dǎo)的逆過程B最右推導(dǎo)的逆過程C規(guī)范推導(dǎo)D最左歸約的逆過程,66,(14)文法GS：SaAcB|BdAAaB|cBbScA|b則句型aAcbBdcc的短語是。ABdBccCaDb(15)文法GE：EE+T|TTT*P|PP(E)|i則句型P+T+i的句柄和最左素短語是。AP+T和TBP和P+TCi和P+T+iDP和P,67,(16)采用自頂向下分析，必須。A消除左遞歸B消除右遞歸C消除回朔D提取公共左因子(17)對文法GE：EE+S|SSS*F|FF(E)|i則FIRST(S)=。A(B(,iCiD(,),68,(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和FOLLOWBFIRSTVT和FOLLOWCFIRST和LASTVTDFIRSTVT和LASTVT,69,(21)設(shè)a、b、c是文法的終結(jié)符且滿足優(yōu)先關(guān)系ab和bc,則。A必有acB必有caC必有baDAC都不一定成立(22)算符優(yōu)先分析法要求。A文法不存在QR的句型且任何終結(jié)符對(a,b)滿足ab、ab和ab三種關(guān)系B文法不存在QR的句型且任何終結(jié)符對(a,b)至多滿足ab、ab和ab三種關(guān)系之一,70,C文法可存在QR的句型且任何終結(jié)符對(a,b)至多滿足ab、ab和ab三種關(guān)系之一D文法可存在QR的句型且任何終結(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,(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,(27)對文法GE：EE*T|TTT+i|i句子1+2*8+6歸約的值為。A23B42C30D17(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,(29)若文法GS的產(chǎn)生式有AB出現(xiàn)，則對A求FOLLOW集正確的是。AFOLLOW(B)FOLLOW(A)BFIRSTVT(B)FOLLOW(A)CFIRST(B)FOLLOW(A)DLASTVT(B)FOLLOW(A)(30)下面是自底向上分析方法。A預(yù)測分析法B遞歸下降分析法CLL(1)分析法D算符優(yōu)先分析法,74,(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,(34)在LR(0)的ACTION子表中，如果某一行中存在標(biāo)記為“rj”的欄，則。A該行必定填滿rjB該行未填滿rjC其他行也有rjDGOTO子表中也有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,(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,【解答】(1)參見第四章4.1.1節(jié)，語義分析不像詞法分析和語法分析那樣可以分別用正規(guī)文法和上下文無關(guān)文法描述，由于語義是上下文有關(guān)的，因此語義分析須用上下文有關(guān)文法描述。即選B。(2)2型文法對應(yīng)下推自動機(jī)。故選C。(3)由于不存在：3型語言2型語言1型語言0型語言。故選D。(4)3型文法即正規(guī)文法，它的識別系統(tǒng)是有限狀態(tài)自動機(jī)。故選C。,78,(5)由SxSx|y可知該文法所識別的語言一定是：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)過零步或多步推導(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,(10)文法GS的一個(gè)句子如果能找到兩種不同的最左推導(dǎo)(或最右推導(dǎo))，或存在兩棵不同的語法樹，則它的任何句子其最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹必定相同。故選A。(11)一個(gè)句型的分析樹代表了該句型的歸約過程。故選B。(12)規(guī)范歸約中的“可歸約串”即為句柄，也就是最左直接短語。故選C。(13)規(guī)范歸約的逆過程是規(guī)范推導(dǎo)，而規(guī)范推導(dǎo)即為最右推導(dǎo)。故選B。(14)由圖3-1可知應(yīng)選A。,80,圖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)自頂向下分析，回溯則使自頂向下分析效率下降。故選D。,82,圖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ù)。故選D。(24)在算符優(yōu)先分析中是以“最左素短語”來刻畫可歸約串的。故選D。,84,(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(B)FOLLOW(A)。故選C。,85,圖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)目；形如AB的項(xiàng)目(其中B為非終結(jié)符)稱為“待約”項(xiàng)目。故選D。,87,(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,3.2令文法GN為GN:ND|NDD0|1|2|3|4|5|6|7|8|9(1)GN的語言L(G)是什么?(2)給出句子0127、34和568的最左推導(dǎo)和最右推導(dǎo)。,89,【解答】(1)GN的語言L(GN)是非負(fù)整數(shù)。(2)最左推導(dǎo)：最右推導(dǎo)：,90,3.3已知文法GS為SaSb|Sb|b，試證明文法GS為二義文法。【解答】由文法GS：SaSb|Sb|b，對句子aabbbb可對應(yīng)如圖3-4所示的兩棵語法樹。因此，文法GS為二義文法(對句子abbb也可畫出兩棵不同的語法樹)。,91,圖3-4句子aabbbb對應(yīng)的兩棵不同語法樹,92,3.4已知文法GS為SSaS|，試證明文法GS為二義文法?！窘獯稹坑晌姆℅S：SSaS|，句子aa的語法樹如圖3-5所示。由圖3-5可知，文法GS為二義文法。,93,圖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知，所求該語言對應(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|b,95,(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|bBAaS|bC|bBbS|aC|aCbA|aB|,96,圖3-6,97,(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|aBaBB|b,98,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,能否不畫出語法樹，而直接由定義(即在句型中)尋找滿足某個(gè)產(chǎn)生式的候選式這樣一個(gè)最左子串(即句柄)呢？例如，對句型aAaBcbbdcc，我們可以由左至右掃描找到第一個(gè)子串AaB，它恰好是滿足AAaB右部的子串；與樹(a)對照，AaB的確是該句型的句柄。是否這一方法始終正確呢？我們繼續(xù)檢查句型aAcbBdcc，由左至右找到第一個(gè)子串c，這是滿足Ac右部的子串，但由樹(b)可知，c不是該句型的句柄。由此可知，畫出對應(yīng)句型的語法樹然后尋找最左直接短語是確定句柄的好方法。,100,圖3-7習(xí)題3.6的語法樹(a)aAaBcbbdcc;(b)aAcbBdcc,101,(2)句子acabcbbdcc的最左推導(dǎo)如下：,102,3.7對于文法GS:S(L)|aS|aLL,S|S(1)畫出句型(S,(a)的語法樹；(2)寫出上述句型的所有短語、直接短語、句柄、素短語和最左素短語。,103,【解答】(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,圖3-8句型(S,(a)的語法樹,105,3.8下述文法描述了C語言整數(shù)變量的聲明語句：GD:DTLTint|long|shortLid|L,id(1)改造上述文法，使其接受相同的輸入序列，但文法是右遞歸的；(2)分別以上述文法GD和改造后的文法GD為輸入序列inta,b,c構(gòu)造分析樹。,106,【解答】(1)消除左遞歸后，文法GD如下：DTLTint|long|shortLidLL,idL|(2)未消除左遞歸的文法G(D)和消除左遞歸的文法GD為輸入序列inta,b,c構(gòu)造的分析樹分別如圖3-9的(a)、(b)所示。,107,圖3-9兩種文法為inta,b,c構(gòu)造的分析樹(a)文法G(D)；(b)文法G(D),108,3.9考慮文法GS:S(T)|a+S|aTT,S|S消除文法的左遞歸及提取公共左因子，然后對每個(gè)非終結(jié)符寫出不帶回溯的遞歸子程序?！窘獯稹肯姆℅S的左遞歸：S(T)|a+S|aTSTT,ST|,109,提取公共左因子：S(T)|aSS+S|TSTT,ST|,110,改造后的文法已經(jīng)是LL(1)文法，不帶回溯的遞歸子程序如下：voidmatch(tokent)if(lookahead=t)lookahead=nexttoken;elseerror();voidS(),111,if(lookahead=a)match(a);S();elseif(lookahead=()match();T();if(lookahead=)match();elseerror();,112,voidS()if(lookahead=+)match(+);S();voidT()S();T();,113,voidT()if(lookahead=,)match(,);S();T();,114,對于文法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()，而將T()和T()改為,115,圖3-10非終結(jié)符T的狀態(tài)轉(zhuǎn)換圖,116,voidT()S();while(lookahead=,)match(,);S();,117,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|的產(chǎn)生式改造為PPPP|,118,來消除左遞歸。由此，將產(chǎn)生式BBb|d改造為BdBBbB|其次，應(yīng)通過提取公共左因子的方法來消除GA中的回溯，即將產(chǎn)生式AaABl|a改造為AaAAABl|最后得到改造后的文法為GA：AaAAABl|BdBBbB|,119,求得：FIRST(A)=aFIRST(A)=a,FIRST(B)=dFIRST(B)=b,對文法開始符號A，有FOLLOW(A)=#。由AABl得FIRST(B)FOLLOW(A)，即FOLLOW(A)=#,d；由AABl得FIRST(l)FOLLOW(B)，即FOLLOW(B)=l；,120,由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,(2)構(gòu)造預(yù)測分析表的方法如下：對文法GA的每個(gè)產(chǎn)生式A執(zhí)行、步。對每個(gè)終結(jié)符aFIRST(A)，把A加入到MA,a中，其中為含有首字符a的候選式或?yàn)槲ㄒ坏暮蜻x式。若FIRST(A)，則對任何屬于FOLLOW(A)的終結(jié)符b，將A加入到MA,b中。把所有無定義的MA,a標(biāo)記上“出錯(cuò)”。由此得到GA的預(yù)測分析表，見表3-1。(3)輸入串a(chǎn)adl的分析過程見表3-2。,122,表3-1預(yù)測分析表,123,表3-2輸入串a(chǎn)adl的分析過程,124,3.11將下述文法改造為LL(1)文法：GV:VN|NEEV|V+ENi【解答】LL(1)文法的基本條件是不含左遞歸和回溯(公共左因子)，而文法GV中含有回溯，所以先消除回溯，得到文法GV：GV：VNVV|EEVEE|+ENi,125,一個(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,由VE得FIRST()FOLLOW(E)，即FOLLOW(E)=；由VNV得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,則，對V|E有：FIRST()FIRST()=；對E|+E有：FIRST()FIRST(+)=；對V|E有：FIRST()FOLLOW(V)=#,+=；對E|+E有：FIRST(+)FOLLOW(E)=+=。故文法GV為LL(1)文法。,128,3.12對文法GE:EE+T|TTT*P|PPi(1)構(gòu)造該文法的優(yōu)先關(guān)系表(不考慮語句括號#)，并指出此文法是否為算符優(yōu)先文法；(2)構(gòu)造文法GE的優(yōu)先函數(shù)。,129,【解答】(1)FIRSTVT集構(gòu)造方法：由Pa或PQa，則aFIRSTVT(P)。若aFIRSTVT(Q)，且PQ，則aFIRSTVT(P)，也即FIRSTVT(Q)FIRSTVT(P)。由得：由EE+得FIRSTVT(E)=+；由TT*得FIRSTVT(T)=*；由Pi得FIRSTVT(P)=i。由得：由TP得FIRSTVT(P)FIRSTVT(T)，即FIRSTVT(T)=*，i；由ET得FIRSTVT(T)FIRSTVT(E)，即FIRSTVT(E)=+，*，i。,130,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,由得：由TP得LASTVT(P)LASTVT(T)，即LASTVT(T)=*，i；由ET得LASTVT(T)LASTVT(E)，即LASTVT(E)=+，*，i。優(yōu)先關(guān)系表構(gòu)造方法：對Pab或PaQb，有ab；對PaR而bFIRSTVT(R)，有ab；對PRb而aLASTVT(R)，有ab。解之無。,132,由得：E+T，即+FIRSTVT(T)，有+*，+i；T*P，即*FIRSTVT(P)，有*i。由得：EE+，即LASTVT(E)+，有+，*+，i+；TT*，即LASTVT(T)*，有*，i*。得到優(yōu)先關(guān)系表見表3-3。由于該文法的任何產(chǎn)生式的右部都不含兩個(gè)相繼并列的非終結(jié)符，故屬算符文法，且該文法中的任何終結(jié)符對(見優(yōu)先關(guān)系表)至多滿足、和三種關(guān)系之一，因而是算符優(yōu)先文法。,133,表3-3習(xí)題3.12的優(yōu)先關(guān)系表,134,(2)用關(guān)系圖構(gòu)造優(yōu)先函數(shù)的方法是：對所有終結(jié)符a用有下腳標(biāo)的fa、ga為結(jié)點(diǎn)名畫出全部終結(jié)符所對應(yīng)的結(jié)點(diǎn)。若存在優(yōu)先關(guān)系ab或ab，則畫一條從fa到ga的有向??；若ab或ab，則畫一條從gb到fa的有向弧。最后，對每個(gè)結(jié)點(diǎn)都賦一個(gè)數(shù)，此數(shù)等于從該結(jié)點(diǎn)出發(fā)所能到達(dá)的結(jié)點(diǎn)(包括出發(fā)結(jié)點(diǎn))的個(gè)數(shù)，賦給fa的數(shù)作為f(a)，賦給gb的數(shù)作為g(b)。用關(guān)系圖法構(gòu)造本題的優(yōu)先函數(shù)，如圖3-11所示。得到優(yōu)先函數(shù)見表3-4。,135,圖3-11習(xí)題3.1,136,表3-4習(xí)題3.12的優(yōu)先函數(shù)表,137,該優(yōu)先函數(shù)表經(jīng)檢查與優(yōu)先關(guān)系表沒有矛盾，故為所求優(yōu)先函數(shù)。也可由定義直接構(gòu)造優(yōu)先函數(shù)，其方法是：對每個(gè)終結(jié)符a，令f(a)=g(a)=1；如果ab，而f(a)g(b)，則令f(a)=g(b)+1；如果ab，而f(a)g(b)，則令g(b)=f(a)+1；如果ab，而f(a)g(b)，則令minf(a),g(b)=maxf(a),g(b)。重復(fù)上述過程，直到每個(gè)終結(jié)符的函數(shù)值不再變化為止。如果有一個(gè)函數(shù)值大于2n(n為終結(jié)符個(gè)數(shù))，則不存在優(yōu)先函數(shù)。優(yōu)先函數(shù)的計(jì)算過程如表3-5所示。,138,表3-5優(yōu)先函數(shù)的計(jì)算過程,139,3.13設(shè)有文法GS:Sa|b|(A)ASdA|S(1)構(gòu)造算符優(yōu)先關(guān)系表；(2)給出句型(SdSdS)的短語、簡單短語、句柄、素短語和最左素短語；(3)給出輸入串(adb)#的分析過程。,140,【解答】(1)先求文法GS的FIRSTVT集和LASTVT集：由Sa|b|(A)得FIRSTVT(S)=a,b,(；由ASd得FIRSTVT(A)=d，又由AS得FIRSTVT(S)FIRSTVT(A)，即FIRSTVT(A)=d,a,b,(；由Sa|b|(A)得LASTVT(S)=a,b,)；由AdA得LASTVT(A)=d，又由AS得LASTVT(S)LASTVT(A)，即LASTVT(A)=d,a,b,)。,141,構(gòu)造優(yōu)先關(guān)系表方法如下：對Pab或PaQb，有ab；對PaR而bFIRSTVT(R)，有ab；對PRb而aFIRSTVT(R)，有ab。由此得到：由S(A)得()；由S(A得(FIRSTVT(A)，即(d,(a,(b,(；由AdA得dFIRSTVT(A)，即dd,da,db,d(；,142,由SA)得LASTVT(A)，即d),a),b),)；由ASd得LASTVT(S)d，即ad,bd,)d；此外，由#S#得#；由#FIRSTVT(S)得#a,#b,#(；由LASTVT(S)#得a#,b#,)#。最后得到算符優(yōu)先關(guān)系表，見表3-6。由表3-6可以看出，任何兩個(gè)終結(jié)符之間至多只滿足、三種優(yōu)先關(guān)系之一，故GS為算符優(yōu)先文法。,143,表3-6習(xí)題3.13的算符優(yōu)先關(guān)系表,144,(2)為求出句型(SdSdS)的短語、簡單短語、句柄，我們先畫出該句型對應(yīng)的語法樹，如圖3-12所示。由圖3-12得到：短語：S，SdS，SdSdS，(SdSdS)簡單短語(即直接短語)：S句柄(即最左直接短語)：S可以通過分析圖3-12所示的語法樹來求素短語和最左素短語，即找出語法樹中的所有相鄰終結(jié)符(中間可有一個(gè)非終結(jié)符)之間的優(yōu)先關(guān)系。確定優(yōu)先關(guān)系的原則是：,145,圖3-12句型(SdSdS)的語法樹,146,同層的優(yōu)先關(guān)系為；不同層時(shí)，層次離樹根遠(yuǎn)者優(yōu)先級高，層次離樹根近者優(yōu)先級低(恰好驗(yàn)證了優(yōu)先關(guān)系表的構(gòu)造算法)；在句型兩側(cè)加上語句括號“#”，即#，則有#和#，由此我們得到句型(SdSdS)的優(yōu)先關(guān)系如圖3-13所示。注意，句型中的素短語具有如下形式：,147,圖3-13句型(SdSdS