編譯原理課后習題答案解析+清華大學出版社第二版

"第1章引論第1題解釋下列術語：編譯程序源程序目標程序￥編譯程序的前端后端遍答案：編譯程序：如果源語言為高級語言，目標語言為某臺計算機上的匯編語言或機器語言，則此翻譯程序稱為編譯程序。源程序：源語言編寫的程序稱為源程序。目標程序：目標語言書寫的程序稱為目標程序。%編譯程序的前端：它由這樣一些階段組成：這些階段的工作主要依賴于源語言而與目標機無關。通常前端包括詞法分析、語法分析、語義分析和中間代碼生成這些階段，某些優(yōu)化工作也可在前端做，也包括與前端每個階段相關的出錯處理工作和符號表管理等工作。后端：指那些依賴于目標機而一般不依賴源語言，只與中間代碼有關的那些階段，即目標代碼生成，以及相關出錯處理和符號表操作。遍：是對源程序或其等價的中間語言程序從頭到尾掃視并完成規(guī)定任務的過程。第2題一個典型的編譯程序通常由哪些部分組成各部分的主要功能是什么并畫出編譯程序的總體結構圖。、答案：一個典型的編譯程序通常包含8個組成部分，它們是詞法分析程序、語法分析程序、語義分析程序、中間代碼生成程序、中間代碼優(yōu)化程序、目標代碼生成程序、表格管理程序和錯誤處理程序。其各部分的主要功能簡述如下。詞法分析程序：輸人源程序，拼單詞、檢查單詞和分析單詞，輸出單詞的機內表達形式。語法分析程序：檢查源程序中存在的形式語法錯誤，輸出錯誤處理信息。語義分析程序：進行語義檢查和分析語義信息，并把分析的結果保存到各類語義信息表中。中間代碼生成程序：按照語義規(guī)則，將語法分析程序分析出的語法單位轉換成一定形式的中間語言代碼，如三元式或四元式。中間代碼優(yōu)化程序：為了產(chǎn)生高質量的目標代碼，對中間代碼進行等價變換處理。目標代碼生成程序：將優(yōu)化后的中間代碼程序轉換成目標代碼程序。表格管理程序：負責建立、填寫和查找等一系列表格工作。表格的作用是記錄源程序的各類信息和編譯各階段的進展情況，編譯的每個階段所需信息多數(shù)都從表格中讀取，產(chǎn)生的中間結果都記錄在相應的表格中。可以說整個編譯過程就是造表、查表的工作過程。需要指出的是，這里的“表格管理程序”并不意味著它就是一個獨立的表格管理模塊，而是指編譯程序具有的表格管理功能。；錯誤處理程序：處理和校正源程序中存在的詞法、語法和語義錯誤。當編譯程序發(fā)現(xiàn)源程序中的錯誤時，錯誤處理程序負責報告出錯的位置和錯誤性質等信息，同時對發(fā)現(xiàn)的錯誤進行適當?shù)男Ｕㄐ迯停?，目的是使編譯程序能夠繼續(xù)向下進行分析和處理。注意：如果問編譯程序有哪些主要構成成分，只要回答六部分就可以。如果搞不清楚，就回答八部分。第3題}何謂翻譯程序、編譯程序和解釋程序它們三者之間有何種關系答案：翻譯程序是指將用某種語言編寫的程序轉換成另一種語言形式的程序的程序，如編譯程序和匯編程序等。編譯程序是把用高級語言編寫的源程序轉換（加工）成與之等價的另一種用低級語言編寫的目標程序的翻譯程序。解釋程序是解釋、執(zhí)行高級語言源程序的程序。解釋方式一般分為兩種：一種方式是，源程序功能的實現(xiàn)完全由解釋程序承擔和完成，即每讀出源程序的一條語句的第一個單詞，則依據(jù)這個單詞把控制轉移到實現(xiàn)這條語句功能的程序部分，該部分負責完成這條語句的功能的實現(xiàn)，完成后返回到解釋程序的總控部分再讀人下一條語句繼續(xù)進行解釋、執(zhí)行，如此反復；另一種方式是，一邊翻譯一邊執(zhí)行，即每讀出源程序的一條語句，解釋程序就將其翻譯成一段機器指令并執(zhí)行之，然后再讀人下一條語句繼續(xù)進行解釋、執(zhí)行，如此反復。無論是哪種方式，其加工結果都是源程序的執(zhí)行結果。目前很多解釋程序采取上述兩種方式的綜合實現(xiàn)方案，即先把源程序翻譯成較容易解釋執(zhí)行的某種中間代碼程序，然后集中解釋執(zhí)行中間代碼程序，最后得到運行結果。廣義上講，編譯程序和解釋程序都屬于翻譯程序，但它們的翻譯方式不同，解釋程序是邊翻譯（解釋）邊執(zhí)行，不產(chǎn)生目標代碼，輸出源程序的運行結果。而編譯程序只負責把源程序翻譯成目標程序，輸出與源程序等價的目標程序，而目標程序的執(zhí)行任務由操作系統(tǒng)來完成，即只翻譯不執(zhí)行。）第4題對下列錯誤信息，請指出可能是編譯的哪個階段（詞法分析、語法分析、語義分析、代碼生成）報告的。else沒有匹配的if數(shù)組下標越界使用的函數(shù)沒有定義在數(shù)中出現(xiàn)非數(shù)字字符|答案：語法分析語義分析語法分析詞法分析第5題|編譯程序大致有哪幾種開發(fā)技術答案：自編譯：用某一高級語言書寫其本身的編譯程序。交叉編譯：A機器上的編譯程序能產(chǎn)生B機器上的目標代碼。自展：首先確定一個非常簡單的核心語言L0，用機器語言或匯編語言書寫出它的編譯程序T0，再把語言L0擴充到L1，此時L0?L1,并用L0編寫L1的編譯程序T1，再把語￥言L1擴充為L2，有L1?L2,并用L1編寫L2的編譯程序T2，……，如此逐步擴展下去，好似滾雪球一樣，直到我們所要求的編譯程序。移植：將A機器上的某高級語言的編譯程序搬到B機器上運行。第６題？計算機執(zhí)行用高級語言編寫的程序有哪些途徑它們之間的主要區(qū)別是什么答案：計算機執(zhí)行用高級語言編寫的程序主要途徑有兩種，即解釋與編譯。像Basic之類的語言，屬于解釋型的高級語言。它們的特點是計算機并不事先對高級語言進行全盤翻譯，將其變?yōu)闄C器代碼，而是每讀入一條高級語句，就用解釋器將其翻譯為一條機器代碼，予以執(zhí)行，然后再讀入下一條高級語句，翻譯為機器代碼，再執(zhí)行，如此反復?？偠灾沁叿g邊執(zhí)行。像C，Pascal之類的語言，屬于編譯型的高級語言。它們的特點是計算機事先對高級語言進行全盤翻譯，將其全部變?yōu)闄C器代碼，再統(tǒng)一執(zhí)行，即先翻譯，后執(zhí)行。從速度上看，編譯型的高級語言比解釋型的高級語言更快。%第2章PL/0編譯程序的實現(xiàn)第1題PL/0語言允許過程嵌套定義和遞歸調用，試問它的編譯程序如何解決運行時的存儲管理。答案：PL/0語言允許過程嵌套定義和遞歸調用，它的編譯程序在運行時采用了棧式動態(tài)存儲管理。（數(shù)組CODE存放的只讀目標程序，它在運行時不改變。）運行時的數(shù)據(jù)區(qū)S是由解釋程序定義的一維整型數(shù)組，解釋執(zhí)行時對數(shù)據(jù)空間S的管理遵循后進先出規(guī)則，當每個過程(包括主程序)被調用時，才分配數(shù)據(jù)空間，退出過程時，則所分配的數(shù)據(jù)空間被釋放。應用動態(tài)鏈和靜態(tài)鏈的方式分別解決遞歸調用和非局部變量的引用問題。第2題若PL/0編譯程序運行時的存儲分配策略采用棧式動態(tài)分配，并用動態(tài)鏈和靜態(tài)鏈的方式分別解決遞歸調用和非局部變量的引用問題，試寫出下列程序執(zhí)行到賦值語句b∶=10時運行棧的布局示意圖。varx,y;procedurep;vara;procedureq;varb;begin(q)b∶=10;end(q);procedures;varc,d;procedurer;vare,f;begin(r)callq;end(r);begin(s)callr;end(s);begin(p)calls;end(p);begin(main)callp;end(main).答案：程序執(zhí)行到賦值語句b∶=10時運行棧的布局示意圖為：第3題寫出題2中當程序編譯到r的過程體時的名字表table的內容。namekindlevel/valadrsize答案：題2中當程序編譯到r的過程體時的名字表table的內容為：namekindlevel/valadrsizexvariable0dxyvariable0dx+1pprocedure0過程p的入口（待填）5avariable1dxqprocedure1過程q的入口4sprocedure1過程s的入口（待填）5cvariable2dxdvariable2dxrprocedure2過程r的入口5evariable3dxfvariable3dx+1注意：q和s是并列的過程，所以q定義的變量b被覆蓋。第4題指出棧頂指針T，最新活動記錄基地址指針B，動態(tài)鏈指針DL，靜態(tài)鏈指針SL與返回地址RA的用途。答案：棧頂指針T，最新活動記錄基地址指針B，動態(tài)鏈指針DL，靜態(tài)鏈指針SL與返回地址RA的用途說明如下：T：棧頂寄存器T指出了當前棧中最新分配的單元(T也是數(shù)組S的下標)。B：基址寄存器，指向每個過程被調用時，在數(shù)據(jù)區(qū)S中給它分配的數(shù)據(jù)段起始地址，也稱基地址。SL：靜態(tài)鏈，指向定義該過程的直接外過程（或主程序）運行時最新數(shù)據(jù)段的基地址，用以引用非局部（包圍它的過程）變量時，尋找該變量的地址。DL：動態(tài)鏈，指向調用該過程前正在運行過程的數(shù)據(jù)段基地址，用以過程執(zhí)行結束釋放數(shù)據(jù)空間時，恢復調用該過程前運行棧的狀態(tài)。RA：返回地址，記錄調用該過程時目標程序的斷點，即調用過程指令的下一條指令的地址，用以過程執(zhí)行結束后返回調用過程時的下一條指令繼續(xù)執(zhí)行。在每個過程被調用時在棧頂分配3個聯(lián)系單元，用以存放SL，DL，RA。第5題PL/0編譯程序所產(chǎn)生的目標代碼是一種假想棧式計算機的匯編語言，請說明該匯編語言中下列指令各自的功能和所完成的操作。INT0AOPR00CALLA答案：PL/0編譯程序所產(chǎn)生的目標代碼中有3條非常重要的特殊指令，這3條指令在code中的位置和功能以及所完成的操作說明如下：INT0A在過程目標程序的入口處，開辟A個單元的數(shù)據(jù)段。A為局部變量的個數(shù)+3。OPR00在過程目標程序的出口處，釋放數(shù)據(jù)段（退棧），恢復調用該過程前正在運行的過程的數(shù)據(jù)段基址寄存器B和棧頂寄存器T的值，并將返回地址送到指令地址寄存器P中，以使調用前的程序從斷點開始繼續(xù)執(zhí)行。CALLA調用過程，完成填寫靜態(tài)鏈、動態(tài)鏈、返回地址，給出被調用過程的基地址值，送入基址寄存器B中，目標程序的入口地址A的值送指令地址寄存器P中，使指令從A開始執(zhí)行。第6題給出對PL/0語言作如下功能擴充時的語法圖和EBNF的語法描述。擴充條件語句的功能使其為：if〈條件〉then〈語句〉[else〈語句〉]擴充repeat語句為：repeat〈語句〉{；〈語句〉}until〈條件〉答案：對PL/0語言作如下功能擴充時的語法圖和EBNF的語法描述如下：擴充條件語句的語法圖為：EBNF的語法描述為：〈條件語句〉::=if〈條件〉then〈語句〉[else〈語句〉]擴充repeat語句的語法圖為：EBNF的語法描述為：〈重復語句〉::=repeat〈語句〉{；〈語句〉}until〈條件〉第3章文法和語言第1題文法G＝({A,B,S},{a,b,c},P,S)其中P為：S→Ac|aBA→abB→bc寫出L(G[S])的全部元素。答案：L(G[S])={abc}第2題文法G[N]為：N→D|NDD→0|1|2|3|4|5|6|7|8|9G[N]的語言是什么答案:G[N]的語言是V+。V={0,1,2,3,4,5,6,7,8,9}N=>ND=>NDD....=>NDDDD...D=>D......D或者：允許0開頭的非負整數(shù)第３題為只包含數(shù)字、加號和減號的表達式，例如9-2＋5，3-1，７等構造一個文法。答案：G[S]:S->S+D|S-D|DD->0|1|2|3|4|5|6|7|8|9第4題已知文法G[Z]：Z→aZb|ab寫出L(G[Z])的全部元素。答案：Z=>aZb=>aaZbb=>aaa..Z...bbb=>aaa..ab...bbbL(G[Z])={ab|n>=1}第5題寫一文法，使其語言是偶正整數(shù)的集合。要求：(1)允許0打頭；(2)不允許0打頭。答案：(1)允許0開頭的偶正整數(shù)集合的文法E→NT|DT→NT|DN→D|1|3|5|7|9D→0|2|4|6|8(2)不允許0開頭的偶正整數(shù)集合的文法E→NT|DT→FT|GN→D|1|3|5|7|9D→2|4|6|8F→N|0G→D|0第6題已知文法G：<表達式>::=<項>｜<表達式>＋<項><項>::=<因子>｜<項>*<因子><因子>::=（<表達式>）｜i試給出下述表達式的推導及語法樹。i+(i+i)i+i*i答案：<表達式<表達式><表達式>+<項><因子><表達式><表達式>+<項><因子>i<項><因子>i<項><因子>i（)(5)<表達式>=><表達式>＋<項>=><表達式>＋<因子>=><表達式>＋（<表達式>）=><表達式>＋（<表達式>＋<項>）=><表達式>＋（<表達式>＋<因子>）=><表達式>＋（<表達式>＋i）=><表達式>＋（<項>＋i）=><表達式>＋（<因子>＋i）=><表達式>＋（i＋i）=><項>＋（i＋i）=><因子>＋（i＋i）=>i＋（i＋i）<表達式<表達式><表達式>+<項><項>*<因子>i<因子><項><因子>ii(6)<表達式>=><表達式>＋<項>=><表達式>＋<項>*<因子>=><表達式>＋<項>*i=><表達式>＋<因子>*i=><表達式>＋i*i=><項>＋i*i=><因子>＋i*i=>i＋i*i第7題證明下述文法G[〈表達式〉]是二義的?！幢磉_式〉∷=a|(〈表達式〉)|〈表達式〉〈運算符〉〈表達式〉〈運算符〉∷=+|-|*|/答案：可為句子a+a*a構造兩個不同的最右推導:最右推導1〈表達式〉〈表達式〉〈運算符〉〈表達式〉〈表達式〉〈運算符〉a〈表達式〉*a〈表達式〉〈運算符〉〈表達式〉*a〈表達式〉〈運算符〉a*a〈表達式〉+a*aa+a*a最右推導2〈表達式〉〈表達式〉〈運算符〉〈表達式〉〈表達式〉〈運算符〉〈表達式〉〈運算符〉〈表達式〉〈表達式〉〈運算符〉〈表達式〉〈運算符〉a〈表達式〉〈運算符〉〈表達式〉*a〈表達式〉〈運算符〉a*a〈表達式〉+a*aa+a*a第8題文法G[S]為：S→Ac|aBA→abB→bc該文法是否為二義的為什么答案：對于串a(chǎn)bc(1)S=>Ac=>abc(2)S=>aB=>abc即存在兩不同的最右推導。所以，該文法是二義的?；蛘撸簩斎胱址產(chǎn)bc，能構造兩棵不同的語法樹，所以它是二義的。SaBbcSAcab第9題考慮下面上下文無關文法：S→SS*|SS+|aSSS*aSSSS*aSS+aa(2)G[S]的語言是什么答案：(1)此文法生成串a(chǎn)a+a*的最右推導如下S=>SS*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*(2)該文法生成的語言是：*和+的后綴表達式，即逆波蘭式。第10題文法S→S(S)S|ε生成的語言是什么該文法是二義的嗎說明理由。答案：嵌套的括號是二義的，因為對于（）（）可以構造兩棵不同的語法樹。第11題令文法G[E]為：E→T|E+T|E-TT→F|T*F|T/FF→(E)|i證明E+T*F是它的一個句型，指出這個句型的所有短語、直接短語和句柄。答案：此句型對應語法樹如右，故為此文法一個句型?；蛘撸阂驗榇嬖谕茖蛄?E=>E+T=>E+T*F，所以E+T*F句型此句型相對于E的短語有:E+T*F；相對于T的短語有T*F直接短語為：T*F句柄為：T*F第13題一個上下文無關文法生成句子abbaa的推導樹如下：(1)給出串a(chǎn)bbaa最左推導、最右推導。(2)該文法的產(chǎn)生式集合P可能有哪些元素BSABBSABSaSBAbbaεa答案：(1)串a(chǎn)bbaa最左推導:S=>ABS=>aBS=>aSBBS=>aBBS=>abBS=>abbS=>abbAa=>abbaa最右推導：S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Abbaa=>abbaa(2)產(chǎn)生式有：S→ABS|Aa|εA→aB→SBB|b可能元素有：εaaababbaaaaabbaa……(3)該句子的短語有：a是相對A的短語ε是相對S的短語b是相對B的短語εbb是相對B的短語aa是相對S的短語aεbbaa是相對S的短語直接短語有：aεb句柄是：a第14題給出生成下述語言的上下文無關文法：{anbnambm|n，m>=0}{1n0m1m0n|n，m>=0}{WaWr|W屬于{0|a}*，Wr表示W(wǎng)的逆}答案：（１）S→AAA→aAb|ε（２）S→1S0|AA→0A1|ε（３）S→0S0|1S1|ε第16題給出生成下述語言的三型文法：(1){an|n>=0}(2){anbm|n,m>=1}(3){anbmck|n,m,k>=0}答案：(1)S→aS|ε(2)S→aAA→aA|BB→bB|b(3)A→aA|BB→bB|CC→cC|ε第17題習題７和習題11中的文法等價嗎答案：等價。第18題解釋下列術語和概念：（１）字母表串、字和句子語言、語法和語義答案：字母表：是一個非空有窮集合。串：符號的有窮序列。字：字母表中的元素。句子：如果Zx,x+ ∈V*T則稱x是文法G的一個句子。（３）語言：它是由句子組成的集合，是由一組記號所構成的集合。程序設計的語言就是所有該語言的程序的全體。語言可以看成在一個基本符號集上定義的，按一定規(guī)則構成的一切基本符號串組成的集合。語法：表示構成語言句子的各個記號之間的組合規(guī)律。程序的結構或形式。語義：表示按照各種表示方法所表示的各個記號的特定含義。語言所代表的含義。

附加題問題1：給出下述文法所對應的正規(guī)式：S→0A|1BA→1S|1B→0S|0答案：R=(01|10)(01|10)*問題2：已知文法G[A]，寫出它定義的語言描述G[A]:A→0B|1C→1|1A|0BB→0|0A|1CC答案:G[A]定義的語言由0、1符號串組成，串中0和1的個數(shù)相同.問題3：給出語言描述，構造文法.構造一文法,其定義的語言是由算符+,*,(,)和運算對象a構成的算術表達式的集合.答案一：G[E]E→E+T|TT→T*F|FF→(E)|a答案二：G[E]E→E+E|E*E|(E)|a問題4：已知文法G[S]:S→dABA→aA|aB→ε|bB相應的正規(guī)式是什么G[S]能否改寫成為等價的正規(guī)文法答案：正規(guī)式是daa*b*；相應的正規(guī)文法為(由自動機化簡來)：G[S]:S→dAA→a|aBB→aB|a|b|bCC→bC|b也可為(觀察得來):G[S]:S→dAA→a|aA|aBB→bB|ε問題5：已知文法G：E→E+T|E-T|TT→T*F|T/F|FF→(E)|i試給出下述表達式的推導及語法樹i;i*i+ii+i*ii+(i+i)答案：(1)E=>T=>F=>i(2)E=>E+T=>T+T=>T*F+T=>F*F+T=>i*F+T=>i*i+T=>i*i+F=>i*i+i(3)E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i(4)E=>E+T=>T+T=>F+T=>i+T=>i+F=>i+(E)=>i+(E+T)=>i+(T+T)=>i+(F+T)=>i+(i+T)=>i+(i+F)=>i+(i+i)EE+TE+EE+TE+TiTFF(E)iTFiF(4)E+TTT*FFiiE+TiTFiFiTF i(1) i(2) (3)問題6：已知文法G[E]:E→ET+|TT→TF*|FF→F^|a試證：FF^^*是文法的句型，指出該句型的短語、簡單短語和句柄.答案：該句型對應的語法樹如下：該句型相對于E的短語有FF^^*相對于T的短語有FF^^*,F相對于F的短語有F^;F^^簡單短語有F;F^句柄為F.問題7：適當變換文法，找到下列文法所定義語言的一個無二義的文法：S→SaS?SbS?ScS?d答案：該文法的形式很典型，可以先采用優(yōu)先級聯(lián)規(guī)則變換文法，然后再規(guī)定結合性對文法做進一步變換，即可消除二義性。設a、b和c的優(yōu)先級別依次增高，根據(jù)優(yōu)先級聯(lián)規(guī)則將文法變換為：S→SaS?AA→AbA?CC→CcC?d規(guī)定結合性為左結合，進一步將文法變換為：S→SaA?AA→AbC?CC→CcF?FF→d該文法為非二義的。問題8：構造產(chǎn)生如下語言的上下文無關文法：{anb2ncm|n，m≥0}{anbmc2m|n，m≥0}{ambn?m≥n}{ambncpdq?m+n=p+q}{uawb?u,w∈{a,b}*∧|u|=|w|}答案：根據(jù)上下文無關文法的特點，要產(chǎn)生形如anb2ncm的串，可以分別產(chǎn)生形如anb2n和形如cm的串。設計好的文法是否就是該語言的文法嚴格地說，應該給出證明。但若不是特別指明，通?？梢院雎赃@一點。對于該語言，存在一個由以下產(chǎn)生式定義的上下文無關文法G[S]：→ABA→ε?aAbbB→ε?cB同樣，要產(chǎn)生形如anbmc2m的串，可以分別產(chǎn)生形如an和形如bmc2m的串。對于該語言，存在一個由以下產(chǎn)生式定義的上下文無關文法G[S]：→AB→ε?aA→ε?bBcc考慮在先產(chǎn)生同樣數(shù)目的a,b，然后再生成多余的a。以下G[S]是一種解法：→aSb?aS?ε以下G[S]是一種解法：→aSd?A?DA→bAd?BD→aDc?BB→bBc?ε注：a不多于d時，b不少于c；反之，a不少于d時，b不多于c。前一種情形通過對應A，后一種情形對應D。以下G[S]是一種解法：→AbA→BAB?aB→a?b問題9：下面的文法G(S)描述由命題變量p、q，聯(lián)結詞∧（合?。ⅰ牛ㄎ鋈。?、?（否定）構成的命題公式集合：→S∨T?T→T∧F?FF→?F?p?q試指出句型?F∨?q∧p的直接短語（全部）以及句柄。答案：直接短語：p，q，?F句柄：?F問題10：設字母表A={a}，符號串x=aaa，寫出下列符號串及其長度：x0,xx,x5以及A+.答案：x0=(aaa)0=ε|x0|=0xx=aaaaaa|xx|=6x5=aaaaaaaaaaaaaaa|x5|=15A+=A1∪A2∪∪…. An∪…={a,aa,aaa,aaaa,aaaaa…}A*=A0∪A1∪A2∪….∪An∪…={ε,a,aa,aaa,aaaa,aaaaa…}問題11：令∑={a，b，c}，又令x=abc，y=b，z=aab，寫出如下符號串及它們的長度：xy，xyz，（xy）3答案：xy=abcb|xy|=4xyz=abcbaab|xyz|=7(xy)3=(abcb)3=abcbabcbabcb|(xy)3|=12問題12：已知文法G[Z]：Z∷=U0∣V1、U∷=Z1∣1、V∷=Z0∣0,請寫出全部由此文法描述的只含有四個符號的句子。答案：Z=>U0=>Z10=>U010=>1010Z=>U0=>Z10=>V110=>0110Z=>V1=>Z00=>U000=>1000Z=>V1=>Z00=>V100=>0100問題13：已知文法G[S]：S∷=ABA∷=aA︱εB∷=bBc︱bc,寫出該文法描述的語言。答案：A∷=aA︱ε描述的語言:{an|n>=0}B∷=bBc︱bc描述的語言:{,bncn|n>=1}L(G[S])={anbmcm|n>=0,m>=1}問題14：已知文法E∷=T∣E+T∣E-T、T∷=F∣T*F∣T/F、F∷=(E)∣i，寫出該文法的開始符號、終結符號集合VT、非終結符號集合VN。答案：開始符號：EVT={+,-,*,/,（,）,i}VN={E,F,T}問題15：設有文法G[S]：S∷=S*S|S+S|(S)|a，該文法是二義性文法嗎答案：根據(jù)所給文法推導出句子a+a*a，畫出了兩棵不同的語法樹，所以該文法是二義性文法。SSS*S+SaaaSSS+S*Saaa問題16：寫一文法，使其語言是奇正整數(shù)集合。答案：A::=1|3|5|7|9|NAN::=N0|N1|N2|N3|N4|N5|N6|N7|N8|N9|N::=0|1|2|3|4|5|6|7|8|9第4章詞法分析第1題構造下列正規(guī)式相應的DFA.1(0|1)*101１(1010*|1(010)*1）*0a((a|b)*|ab*a)*bb((ab)*|bb)*ab答案：(1)先構造NFA： 用子集法將NFA確定化.01X.AAAABABACABACAABYABYACAB除X，A外，重新命名其他狀態(tài)，令AB為B、AC為C、ABY為D，因為D含有Y（NFA的終態(tài)），所以D為終態(tài)。.01X.AAABBCBCADDCBDFA的狀態(tài)圖：:(2)(2)先構造NFA：XA1Bε1C0D1E0εF1G0H1I0J1KLεε0Yεεεε用子集法將NFA確定化ε01XXT0=XAAABFLT1=ABFLYCGYYCGCGJT2=YT3=CGJDHKDHDHKABFKLT4=DHEIEIABEFILT5=ABFKLYCGT6=ABEFILEJYCGEJYABEFGJLYT7=ABEFGJLYEHYCGKEHYABEFHLYCGKABCFGJKLT8=ABEFHLYEYCGIEYABEFLYCGICGJIT9=ABCFGJKLDHYCGKDHYDHYT10=ABEFLYEYCGT11=CGJIDHJKDHJDHJT12=DHYEIT13=DHJEIKEIKABEFIKLT14=ABEFIKLEJYCG將T0、T1、T2、T3、T4、T5、T6、T7、T8、T9、T10、T11、T12、T13、T14重新命名，分別用0、1、2、3、4、5、6、7、8、9、10、11、12、13、14表示。因為2、7、8、10、12中含有Y，所以它們都為終態(tài)。0101123234546523673789810119129101031113512613141473001012127810345691113141101010110110101100101(3)(3)先構造NFA：先構造NFA：XAaBεa,bεDaEaFCεYεεbεb用子集法將NFA確定化εabXXT0=XAAABCDT1=ABCDBEBYBEABCDEBYABCDYT2=ABCDEBEFBEYBEFABCDEFBEYABCDEYT3=ABCDYBEBYT4=ABCDEFBEFBEYT5=ABCDEYBEFBEY將T0、T1、T2、T3、T4、T5重新命名，分別用0、1、2、3、4、5表示。因為3、5中含有Y，所以它們都為終態(tài)。ab0112324532344554500ab132a54abababab(4)先構造NFA：XXAbBεaFbGbHEεYaεCDbεIbεεεε用子集法將NFA確定化：εabXXT0=XAAABDEFT1=ABDEFCIGCICIGGT2=CIDYDYABDEFYT3=GHHABEFHT4=ABDEFYCIGT5=ABEFHCIG將T0、T1、T2、T3、T4、T5重新命名，分別用0、1、2、3、4、5表示。因為4中含有Y，所以它為終態(tài)。ab011232435423523DFA的狀態(tài)圖：00bb12a453bbabab第２題已知NFA＝（｛x,y,z｝,{0,1},M,{x},{z}），其中：M(x,0)={z}，M(y,0)={x,y}，,M(z,0)={x,z}，M(x,1)={x}，M(y,1)=φ，M(z,1)={y}，構造相應的DFA。答案：先構造其矩陣01xzxyx,yzx,zy用子集法將NFA確定化：01xzxzxzyxzxzxyyxyxyxyzxxyzxyzxy將x、z、xz、y、xy、xyz重新命名，分別用A、B、C、D、E、F表示。因為B、C、F中含有z，所以它為終態(tài)。01ABABCDCCEDEEFAFFEDFADFA的狀態(tài)圖：A010FED0B1010101C第3題將下圖確定化：答案：用子集法將NFA確定化：.01SVQQUVQVZQUQUVQUZVZZZVZ.QUZVZQUZZZZ重新命名狀態(tài)子集，令VQ為A、QU為B、VZ為C、V為D、QUZ為E、Z為F。.01SABACBBDECFFDF.ECEFFFDFA的狀態(tài)圖：第4題將下圖的（a）和（b）分別確定化和最小化：答案：初始分劃得Π0：終態(tài)組{0}，非終態(tài)組{1,2,3,4,5}對非終態(tài)組進行審查：{1,2,3,4,5}a {0,1,3,5}而{0,1,3,5}既不屬于{0}，也不屬于{1,2,3,4,5}∵{4}a {0}，所以得到新分劃Π1：{0}，{4}，{1,2,3,5}對{1,2,3,5}進行審查：∵{1,5}b {4}{2,3}b {1,2,3,5}，故得到新分劃Π2：{0}，{4}，{1,5}，{2,3}{1,5}a {1,5}{2,3}a {1,3}，故狀態(tài)2和狀態(tài)3不等價，得到新分劃Π3：{0}，{2}，{3}，{4}，{1,5}這是最后分劃了最小DFA：第5題構造一個DFA，它接收Σ={0,1}上所有滿足如下條件的字符串：每個1都有0直接跟在右邊。并給出該語言的正規(guī)式。答案：按題意相應的正規(guī)表達式是(0*10)*0*，或0*(0|10)*0*構造相應的DFA，首先構造NFA為用子集法確定化：II0I1{X,0,1,3,Y}{0,1,3,Y}{2}{1,3,Y}{0,1,3,Y}{0,1,3,Y}{1,3,Y}{1,3,Y}{2}{2}{2}重新命名狀態(tài)集：S0112342244333DFA的狀態(tài)圖：可將該DFA最小化：終態(tài)組為{1,2,4}，非終態(tài)組為{3}，{1,2,4}0{1,2,4}，{1,2,4}1{3}，所以1,2,4為等價狀態(tài)，可合并。第６題設無符號數(shù)的正規(guī)式為θ：θ=dd*|dd*.dd*|.dd*|dd*10(s|ε)dd*|10(s|ε)dd*|.dd*10(s|ε)dd*|dd*.dd*10(s|ε)dd*化簡θ，畫出θ的DFA，其中d={0,1,2,…,9}，s={＋，－}答案：先構造先構造NFA：XdB.dFGdH10dAεC10dDsεEdYdsεd用子集法將NFA確定化：ε·s10dXXAT0=XABFABBFFGAAT1=BCCCT2=FGGHGGHHT3=ABFAT4=CDCDDET5=GHT6=HHT7=DEEYEEYYT8=EYT9=YY將XA、B、FG、A、C、G、H、DE、E、Y重新命名，分別用0、1、2、3、4、5、6、7、8、9表示。終態(tài)有0、3、4、6、9?！10d012314256312347456667898999DFA的狀態(tài)圖：d··d652d3d47890110ds·1010ddsddd第7題給文法G[S]：S→aA|bQA→aA|bB|bB→bD|aQQ→aQ|bD|bD→bB|aAE→aB|bFF→bD|aE|b構造相應的最小的DFA。答案：先構造其NFA：SaAaZQbBDaEbFbbabaabbbbab用子集法將NFA確定化：abSAQAABZQQDZBZQDDZABDABBQD將S、A、Q、BZ、DZ、D、B重新命名，分別用0、1、2、3、4、5、6表示。因為3、4中含有z，所以它們?yōu)榻K態(tài)。ab012113224325416516625DFA的狀態(tài)圖：00aa52b3aab416baabbbab令P0＝（｛0,1,2,5,6｝,｛3,4｝）用b進行分割：P1＝（｛0,5,6｝,｛1,2｝,｛3,4｝）再用b進行分割：P2＝（｛0｝,｛5,6｝,｛1,2｝,｛3,4｝）再用a、b進行分割，仍不變。再令｛０｝為A，｛1，2｝為B，｛3，4｝為C，｛5，6｝為D。最小化為：AAa,bDCaaBbabb第８題給出下述文法所對應的正規(guī)式：S→0A|1BA→1S|1B→0S|0答案：解方程組S的解：S=0A|1BA=1S|1B=0S|0將A、B產(chǎn)生式的右部代入S中S=01S|01|10S|10=（01|10）S|（01|10）所以：S=(01|10)*(01|10)第9題將下圖的DFA最小化，并用正規(guī)式描述它所識別的語言。11a26c3cb547bbabbbdda答案：令P0＝（｛1,2,3,4,5｝,｛6,7｝）用b進行分割：P1＝（｛1,2｝,｛3,4｝,｛5｝,｛6,7｝）再用a、b、c、d進行分割，仍不變。再令｛1,2｝為A，｛3，4｝為B，｛5｝為C，｛6，7｝為D。最小化為： cAAaCDbdBbabr=b*a(c|da)*bb*=b*a(c|da)*b+附加題問題1：為下邊所描述的串寫正規(guī)式，字母表是{a,b}.以ab結尾的所有串包含偶數(shù)個b但不含a的所有串包含偶數(shù)個b且含任意數(shù)目a的所有串只包含一個a的所有串包含ab子串的所有串不包含ab子串的所有串答案：注意正規(guī)式不唯一(a|b)*ab(bb)*(a*ba*ba*)*b*ab*(a|b)*ab(a|b)*b*a*問題2：請描述下面正規(guī)式定義的串.字母表{0，1}.0*(10+)*0*(0|1)*(00|11)(0|1)*1(0|1)*0答案：每個1至少有一個0跟在后邊的串所有含兩個相繼的0或兩個相繼的1的串必須以1開頭和0結尾的串問題3：構造有窮自動機.構造一個DFA，接受字母表{0,1}上的以01結尾的所有串構造一個DFA，接受字母表{0,1}上的不包含01子串的所有串.構造一個NFA，接受字母表{x,y}上的正規(guī)式x(x|y)*x描述的集合構造一個NFA，接受字母表{a,b}上的正規(guī)式(ab|a)*b+描述的集合并將其轉換為等價的DFA.以及最小狀態(tài)DFA答案：b)c)最小化的DFA問題4：設有如圖所示狀態(tài)轉換圖，求其對應的正規(guī)表達式?？赏ㄟ^消結法得出正規(guī)式R=(01)*((00|1)(0|1)*|0)也可通過轉換為正則文法，解方程得到正規(guī)式。問題5：已知正規(guī)式：(1)((a|b)*|aa)*b;(2)(a|b)*b.試用有限自動機的等價性證明正規(guī)式(1)和(2)是等價的，并給出相應的正規(guī)文法。分析：基本思路是對兩個正規(guī)式，分別經(jīng)過確定化、最小化、化簡為兩個最小DFA，如這兩個最小DFA一樣，也就證明了這兩個正規(guī)式是等價的。答案：狀態(tài)轉換表1abX1241234124Y12341234124Y124Y1234124Y狀態(tài)轉換表2aB123223323由于2與3完全一樣，將兩者合并，即見下表ab12323而對正規(guī)式(2)可畫NFA圖，如圖所示。abX121212Y121212Y12Y1212Y可化簡得下表ab123223得DFA圖兩圖完全一樣，故兩個自動機完全一樣，所以兩個正規(guī)文法等價。對相應正規(guī)文法,令A對應1，B對應2故為：A→aA|bB|bB→aA|bB|b即為S→aS|bS|B,此即為所求正規(guī)文法。問題6：考慮正規(guī)表達式r=a*b(a|b)，構造可以生成語言L(r)的一個正規(guī)文法。答案：S→a*b(a|b)變換為S→aA,S→b(a|b),A→aA,A→b(a|b)變換為S→aA,S→bB,B→(a|b),A→aA,A→bC,C→(a|b)變換為S→aA,S→bB,B→a,B→b,A→aA,A→bC,C→a,C→b所以，一個可能的正規(guī)文法為G[S]：S→aA,S→bB,B→a,B→b,A→aA,A→bC,C→a,C→b或表示為：S→aA|bB,B→a|b,A→aA|bC,C→a|b（適當?shù)葍r變換也可以，但要作說明，即要有步驟）問題7：考慮下圖所示的NFAN，構造可以生成語言L(N)的一個正規(guī)文法。答案：G[P]:→0P?1P?1Q→0R?1R→ε問題8：考慮如下文法G[S]：→0S?1S?1AA→0B?1BB→ε試構造語言為L(G)的一個正規(guī)表達式。試構造語言為L(G)的一個有限自動機。答案：a)由A→0B，B→ε得A→0;由A→1B，B→ε得A→1;由A→0，A→1得A→0?1;由S→1A，A→0?1得S→1(0?1);由S→1A，A→0?1得S→1(0?1);由S→0S，S→1(0?1)得S→0*1(0?1);由S→1S，S→1(0?1)得S→1*1(0?1);由S→0*1(0?1)，S→1*1(0?1)得S→0*1(0?1)?1*1(0?1);所以，一個可能的正規(guī)表達式為：0*1(0?1)?1*1(0?1)b)第5章自頂向下語法分析方法第1題對文法G[S]S→a|∧|(T)T→T,S|S給出(a,(a,a))和(((a,a),∧,(a)),a)的左推導。對文法G，進行改寫，然后對每個非終結符寫出不帶回溯的遞歸子程序。經(jīng)改寫后的文法是否是LL(1)的給出它的預測分析表。給出輸入串(a,a)#的分析過程，并說明該串是否為G的句子。答案：(1)對(a,(a,a)的左推導為：S(T)(T,S)(S,S)(a,S)(a,(T))(a,(T,S))(a,(S,S))(a,(a,S))(a,(a,a))對(((a,a),∧,(a)),a)的左推導為：S(T)(T,S)(S,S)((T),S)((T,S),S)((T,S,S),S)((S,S,S),S)(((T),S,S),S)(((T,S),S,S),S)(((S,S),S,S),S)(((a,S),S,S),S)(((a,a),S,S),S)(((a,a),∧,S),S)(((a,a),∧,(T)),S)(((a,a),∧,(S)),S)(((a,a),∧,(a)),S)(((a,a),∧,(a)),a)改寫文法為：S→aS→∧S→(T)T→SNN→,SNN→ε非終結符FIRST集FOLLOW集S{a,∧,(}{#,,,)}T{a,∧,(}{)}N{,,ε}.{)}....對左部為N的產(chǎn)生式可知：FIRST（→,SN）={，}FIRST（→ε）={ε}FOLLOW（N）={)}由于SELECT(N→,SN)∩SELECT(N→ε)={，}∩{)}=所以文法是LL(1)的。預測分析表（PredictingAnalysisTable）a∧(),#S→a→∧→(T)T→SN→SN→SNN→ε→,SN也可由預測分析表中無多重入口判定文法是LL(1)的。對輸入串（a,a）#的分析過程為：棧（STACK）當前輸入符（CUR_CHAR）剩余輸入符（INOUT_STRING）所用產(chǎn)生式（OPERATION）#S#)T(#)T#)NS#)Na#)N#)NS,#)NS#)Na#)N#)#((aaa,,aa))#a,a)#...a,a)#...,a)#...,a)#...,a)#...a)#...a)#...)#...)#...#...#...S→(T).T→SNS→a.N→,SN.S→a.N→ε可見輸入串（a,a）#是文法的句子。

第3題已知文法G[S]：S→MH|aH→LSo|εK→dML|εL→eHfM→K|bLM判斷G是否是LL(1)文法，如果是，構造LL(1)分析表。答案：文法展開為：S→MHS→aH→LSoH→εK→dMLK→εL→eHfM→K8）M→bLM非終結符FIRST集FOLLOW集S{a,d,b,ε,e}{#,o}........M{d,ε,b}....{e,#,o}......H{ε,e}......{#,f,o}......L{e}.........{a,d,b,e,o,#}K{d,ε}......{e,#,o}......對相同左部的產(chǎn)生式可知：SELECT(S→MH)∩SELECT(S→a)={d,b,e，#,o}∩{a}=SELECT(H→LSo)∩SELECT(H→ε)={e}∩{#,f,o}=SELECT(K→dML)∩SELECT(K→ε)=glwzdjt∩{e,#,o}=SELECT(M→K)∩SELECT(M→bLM)={d，e,#,o}∩=所以文法是LL(1)的。預測分析表：aodefb#S→a→MH→MH→MH→MH→MHM→K→K→K→bLM→KH→ε→LSo→ε→εL→eHfK→ε→dML→ε→ε由預測分析表中無多重入口也可判定文法是LL(1)的。

第7題對于一個文法若消除了左遞歸，提取了左公共因子后是否一定為LL(1)文法試對下面文法進行改寫，并對改寫后的文法進行判斷。(１)A→baB|εB→Abb|aA→aABe|aB→Bb|dS→Aa|bA→SBB→ab答案：(１)先改寫文法為：A→baBA→εB→baBbbB→bbB→a再改寫文法為：A→baBA→εB→bNB→aN→aBbbN→bFIRSTFOLLOWA{#}B{b,a}{#,b}N{b,a}{#,b}預測分析表：ab#A→baB→εB→a→bNN→aBbb→b由預測分析表中無多重入口判定文法是LL(1)的。文法：A→aABe|aB→Bb|d提取左公共因子和消除左遞歸后文法變?yōu)椋篈→aNN→ABeN→εB→dN1N1→bN1N1→ε非終結符FIRST集FOLLOW集A{a}...{#,d}Bpxelpyy...{e}..N{a,ε}{#,d}N1{b,ε}{e}..對相同左部的產(chǎn)生式可知：SELECT(N→ABe)∩SELECT(N→ε)={a}∩{#,d}=SELECT(N1→bN1)∩SELECT(N1→ε)=∩{e}=所以文法是LL(1)的。預測分析表（PredictingAnalysisTable）aebd#A→aNB→dN1N1→ε→bN1N→ABe→ε→ε也可由預測分析表中無多重入口判定文法是LL(1)的。文法：S→Aa|bA→SBB→ab第1種改寫：用A的產(chǎn)生式右部代替S的產(chǎn)生式右部的A得：S→SBa|bB→ab消除左遞歸后文法變?yōu)椋篠→bNN→BaN2)N→ε3)B→ab非終結符FIRST集FOLLOW集S...{#}B{a}...{a}N{ε,a}{#}對相同左部的產(chǎn)生式可知：SELECT(N→BaN)∩SELECT(N→ε)={a}∩{#}=所以文法是LL(1)的。預測分析表（PredictingAnalysisTable）ab#S→bNB→abN→BaN→ε也可由預測分析表中無多重入口判定文法是LL(1)的。第2種改寫：用S的產(chǎn)生式右部代替A的產(chǎn)生式右部的S得：S→Aa|bA→AaB|bBB→ab消除左遞歸后文法變?yōu)椋篠→AaS→bA→bBN3)N→aBNN→εB→ab非終結符FIRST集FOLLOW集S...{#}A...{a}B{a}...{a}N{a,ε}{a}對相同左部的產(chǎn)生式可知：SELECT(S→Aa)∩SELECT(S→b)=∩=≠SELECT(N→aBN)∩SELECT(N→ε)={a}∩{a}={a}≠所以文法不是LL(1)的。預測分析表：ab#S→Aa..→b....A→bBNB→ab..N→aBN→ε...也可由預測分析表中含有多重入口判定文法不是LL(1)的。

附加題問題1：已知文法G[A]如下，試用類C或類PASCAL語言寫出其遞歸下降子程序.(主程序不需寫)G[A]:A→[BB→X]{A}X→(a|b){a|b}答案：不妨約定:在進入一個非終結符號相應的子程序前，已讀到一個單詞.word：存放當前讀到的單詞，Getsym()為一子程序，每調用一次，完成讀取一單詞的工作。error()為出錯處理程序.FIRST(A)為終結符A的FIRST集.類C程序如下：voidA(){ifword=='['{Getsym();B();}elseerror();}voidB(){X();ifword==']'{Getsym();while(wordFIRST(A))A();}elseerror();}invoidX(){if(word=='a'||word=='b'){Getsym();while(word=='a'||word=='b')Getsym();}elseerror();}問題2：設有文法G[A]的產(chǎn)生式集為:A→BaC|CbBB→Ac|cC→Bb|b試消除G[A]的左遞歸。答案：提示：不妨以A、B、C排序.先將A代入B中，然后消除B中左遞歸；再將A、B代入C中。再消除C中左遞歸。后結果為:G[A]:A→BaC|CbBB→CbBcB'|cB'B'→aCcB'|εC→cB'bC'|bC'C'→bBcB'bC'|ε問題3：試驗證如下文法G[E]是LL(1)文法:→[F]E′E’→E?ε→aF’F’→aF’?ε其中E,F,E’,F’為非終結符答案： 各非終結符的FIRST集和FOLLOW集如下：FIRST（E）={[} FOLLOW（E）={＃} FIRST（E′）={[，ε}FOLLOW（E′）={＃} FIRST（F）={a} FOLLOW（F）={]} FIRST（F′）={a，ε}FOLLOW（F′）={]}對于E’→E?ε，F(xiàn)IRST(E)∩FIRST(ε)=φFIRST(E)∩FOLLOW（E’）=φ對于F’→aF’?ε，F(xiàn)IRST(aF’)∩FIRST(ε)=φFIRST（aF’）∩FOLLOW（F’）=φ所以,文法G[E]是LL（1）文法。問題4：文法G[E]是LL(1)文法:→[F]E′E’→E?ε→aF’F’→aF’?ε其中E,F,E’,F’為非終結符。對文法G[E]構造遞歸下降分析程序。答案：/*用類C語言寫出G[E]的遞歸子程序，其中yylex()為取下一單詞過程，變量lookahead存放當前單詞。*/intlookahead;voidParseE(){MatchToken(′[′);ParseF();MatchToken(′]′);ParseE’();}voidParseE’(){switch(lookahead){case′[′:ParseE();break;case′#′:break;default:printf("syntaxerror\n")exit(0);}}voidParseF(){MatchToken(′a′);ParseF’();}voidParseF’(){switch(lookahead){case′a′:MatchToken(′a′);ParseF’();break;case′]′:break;default:printf("syntaxerror\n")exit(0);}}voidMatchToken(intexpected){if(lookahead!=expected)答案：答案：.,a)#...a)#...a)#...)#...#...#...#...MoveinMoveinReduce:S→aMoveinMoveinReduce:S→aReduce:T→T,SMoveinReduce:S→(T)Success!對輸入串（a,(a,a)）#的算符優(yōu)先分析過程為：棧（STACK）當前字符（CHAR）剩余輸入串（INPUT_STRING）動作（ACTION）##(#(a#(N#(N,#(N,(#(N,(a#(N,(N#(N,(N#(N,(N,a#(N,(N,N#(N,(N#(N,(N)#(N,N#(N#(N)#N(a,,(a,,a))))))##a,(a,a))#...,(a,a))#...(a,a))#...(a,a))#...a,a))#...,a))#...a))#...a))#...))#...)#...)#...)#...#...#...#...MoveinMoveinReduce:S→aMoveinMoveinMoveinReduce:S→aMoveinMoveinReduce:S→aReduce:T→T,SMoveinReduce:S→(T)Reduce:T→T,SMoveinReduce:S→(T)Success!第2題已知文法G[S]為：S→a|∧|(T)T→T,S|S給出(a,(a,a))和(a,a)的最右推導，和規(guī)范歸約過程。將(1)和題1中的(4)進行比較給出算符優(yōu)先歸約和規(guī)范歸約的區(qū)別。答案：（１）(a,a)的最右推導過程為：S(T)(T,S)(T,a)(S,a)(a,a)（a,(a,a)）的最右推導過程為：S(T)(T,S)(T,(T))(T,(T,S))(T,(T,a))(T,(S,a))(T,(a,a))(S,(a,a))(a,(a,a))(a,(a,a))的規(guī)范歸約過程：步驟棧輸入動作1#(a,(a,a))#移進2#(a,(a,a))#移進3#(a,(a,a))#歸約，Sa4#(S,(a,a))#歸約，LS5#(T,(a,a))#移進6#(T,(a,a))#移進7#(T,(a,a))#移進8#(T,(a,a))#歸約，Sa9#(T,(S,a))#歸約，TS10#(T,(T,a))#移進11#(T,(T,a))#移進12#(T,(T,a))#歸約，Sa13#(T,(T,S))#歸約，TT,S14#(T,(T))#移進15#(T,(T))#歸約，S(T)16#(T,S)#移進17#(T,S)#歸約，TT,S18#(T)#歸約，S(T)19#S#接受(a,a)的規(guī)范歸約過程：步驟棧輸入動作1#(a,a)#移進2#(a,a)#移進3#(a,a)#歸約，Sa4#(S,a)#歸約，TS5#(T,a)#移進6#(T,a)#移進7#(T,a)#歸約，Sa8#(T,S)#歸約，TT,S9#(T)#移進10#(T)#歸約，S(T)11#S#接受(2)算符優(yōu)先文法在歸約過程中只考慮終結符之間的優(yōu)先關系從而確定可歸約串，而與非終結符無關，只需知道把當前可歸約串歸約為某一個非終結符，不必知道該非終結符的名字是什么，因此去掉了單非終結符的歸約。規(guī)范歸約的可歸約串是句柄，并且必須準確寫出可歸約串歸約為哪個非終結符。第３題：有文法G[S]：SVVT|ViTTF|T+FF)V*|(給出(+(i(的規(guī)范推導。指出句型F+Fi(的短語，句柄，素短語。G[S]是否為OPG若是，給出(1)中句子的分析過程。SVSVViTTFT+F(答案：(1)S=>V=>ViT=>ViF=>Vi(=>Ti(=>T+Fi(=>T+(i(=>F+(i(=>(+(i((2)句型F+Fi(的語法樹：短語：F，F(xiàn)+F，(，F(xiàn)+Fi(句柄：F素短語：( F(3)FIRSTVT和LASTVTFIRSTVTLASTVTSi,+,),(i,+,*,(Vi,+,),(i,+,*,(T+,),(+,(,*F),(,*,(算符優(yōu)先關系i+*()#i≯≮≯≮≮≯+≯≯≯≮≮≯*≯≯