編譯原理練習(xí)題參考答案

一、填空題：1-01.編譯程序的工作過程一般可以劃分為 詞法分析，語法分析，語義分析，之間代碼生成，代碼優(yōu)化等幾個基本階段,同時還會伴有表格處理 和出錯處理.1-02.若源程序是用高級語言編寫的,目標程序是機器語言程序或匯編程序，則其翻譯程序稱為編譯程序.1-03.編譯方式與解釋方式的根本區(qū)別在于 是否生成目標代碼.1-04.翻譯程序是這樣一種程序,它能夠?qū)⒂眉渍Z言書寫的程序 轉(zhuǎn)換成與其等價的用乙語言書寫的程序.1-05.對編譯程序而言，輸入數(shù)據(jù)是源程序，輸出結(jié)果是目標程序.1-06.如果編譯程序生成的目標程序是機器代碼程序 ，則源程序的執(zhí)行分為兩大階段：編譯階段和運行階段.如果編譯程序生成的目標程序是匯編語言程序 ，則源程序的執(zhí)行分為三個階段：編譯階段,_匯編階段和運行階段.1-07.若源程序是用高級語言編寫的，目標程序是機器語言程序或匯編程序 ，則其翻譯程序稱為 編譯程序。1-08.一個典型的編譯程序中，不僅包括詞法分析、語法分析、中間代碼生成、代碼優(yōu)化、目標代碼生成等五個部分，還應(yīng)包括表格處理和出錯處理。其中,詞法分析器用于識別 單詞。1-09.編譯方式與解釋方式的根本區(qū)別為是否生成目標代碼。2-01.所謂最右推導(dǎo)是指： 任何一步a3都是對“中最右非終結(jié)符進行替換的 。2-02.一個上下文無關(guān)文法所含四個組成部分是 一組終結(jié)符號、一組非終結(jié)符號、一個開始符號、一組產(chǎn)生式。2-03.產(chǎn)生式是用于定義 語法成分的一種書寫規(guī)則。2-04.設(shè)G[S]是給定文法，則由文法G所定義的語言L(G)可描述為：L(G)={x*_s x,xeVt}。TOC\o"1-5"\h\z2-05.設(shè)G是一個給定的文法，S是文法的開始符號，如果S x(其中xCV),則稱x是文法的一個句型 。2-06.設(shè)G是一個給定的文法，S是文法的開始符號，如果* 一S x(其中xCVt),則稱x是文法的一個句子。3-01.掃描器的任務(wù)是從源程序中識別出一個個 單詞符號 。4-01.語法分析最常用的兩類方法是 自上而下和自下而上 分析法。4-02.語法分析的任務(wù)是識別給定的終極符串是否為給定文法的句子。4-03.遞歸下降法不允許任一非終極符是直接 左遞歸的。4-04.自頂向下的語法分析方法的關(guān)鍵是 如何選擇候選式 的問題。4-05.遞歸下降分析法是自 頂向上分析方法。4-06.自頂向下的語法分析方法的基本思想是：從文法的 開始符號開始，根據(jù)給定的輸入串并按照文法的產(chǎn)生式一步一步的向下進行直接推導(dǎo)，試圖推導(dǎo)出文法的 句子，使之與給定的輸入串匹配。5-01.自底向上的語法分析方法的基本思想是：從給定的終極符串開始，根據(jù)文法的規(guī)則一步一步的向上進行直接歸約，試圖歸約到文法的 開始符號。5-02.自底向上的語法分析方法的基本思想是：從輸入串入手，利用文法的產(chǎn)生式一步一步地向上進行 直接歸約,力求歸約到文法的開始符號 。

5-03.簡單優(yōu)先方法每次歸約當前句型的 句柄，算符優(yōu)先方法每次歸約當前句型的 最左素短語，二者都是不斷移進輸入符號，直到符號棧頂出現(xiàn) 可歸約串的尾,再向前找到 可歸約串的頭,然后歸約。5-04.在LR(0)分析法的名稱中， L的含義是自左向右的掃描輸入串 ，R的含義是最左歸約，0的含義是向貌似句柄的符號串后查看 0個輸入符號。5-05.在SLR(1)分析法的名稱中，S的含義是簡單的。6-01.所謂屬性文法是一個屬性文法是一個三元組： A= (G V, F), 一個上下文無關(guān)文法 G; 一個屬性的有窮集V和關(guān)于屬性的斷言或謂詞的有窮集 F。每個斷言與文法的某產(chǎn)生式相聯(lián)。6-02.綜合屬性是用于“自下而上”傳遞信息。6-03.繼承屬性是用于“自上而下”傳遞信息。6-04.終結(jié)符只有綜合屬性，它們由詞法分析器提供。7-01.在使用高級語言編程時，首先可通過編譯程序發(fā)現(xiàn)源程序的全部 A錯誤和B部分錯誤.a.語法b.語義c.語用 d.運行8-01.符號表中的信息欄中登記了每個名字的 屬性和特征等有關(guān)信息 ，如類型、種屬、所占單元大小、地址等等。TOC\o"1-5"\h\z8-02.一個過程相應(yīng)的DISPLAY表的內(nèi)容為現(xiàn)行活動記錄地址和所有外層最新活動記錄的地址 。9-01.一個過程相應(yīng)的DISPLAY表的內(nèi)容為現(xiàn)行活動記錄地址和所有外層最新活動記錄的地址 。9-02.常用的兩種動態(tài)存貯分配辦法是 棧式動態(tài)分配和 堆式動態(tài)分配。9-03.常用的參數(shù)傳遞方式有 傳地址，傳值和傳名。10-01.局部優(yōu)化是局限于一個 基本塊范圍內(nèi)的一種優(yōu)化。10-02.代碼優(yōu)化的主要目標是如何提高 目標程序的運行速度 和如何減少目標程序運行時所需的空間 。、單選題：1-10.一個編譯程序中，不僅包含詞法分析，語法分析，中間代碼生成，代碼優(yōu)化，目標代碼生成等五個部分，還應(yīng)包括⑴c.其中，(2)b和代碼優(yōu)化部分不是每個編譯程序都必需的 ^詞法分析器用于識別(3)c,語法分析器則可以發(fā)現(xiàn)源程序中的(4)d.a.模擬執(zhí)行器 b.解釋器c.表格處理和出錯處理 d.符號執(zhí)行器a.語法分析 b.中間代碼生成 c.詞法分析 d.目標代碼生成a.字符串 b.語句 c.單詞 d.標識符a.語義錯誤 b.語法和語義錯誤 c.錯誤并校正 d.語法錯誤1-11.程序語言的語言處理程序是一種 (1)a.(2)b是兩類程序語言處理程序，他們的主要區(qū)別在于(3)d.a.系統(tǒng)軟件b.應(yīng)用軟件 c.實時系統(tǒng) d.分布式系統(tǒng)a.高級語言程序和低級語言程序 b.解釋程序和編譯程序c.編譯程序和操作系統(tǒng) d.系統(tǒng)程序和應(yīng)用程序a.單用戶與多用戶的差別 b.對用戶程序的查錯能力c.機器執(zhí)行效率 d.是否生成目標代碼1-12.匯編程序是將a翻譯成b,編譯程序是將c翻譯成d.c. 高級語言程序f.b或者cc. 高級語言程序f.b或者cd.a或者be.a或者c1-13.下面關(guān)于解釋程序的描述正確的是 b.(1)解釋程序的特點是處理程序時不產(chǎn)生目標代碼解釋程序適用于COBO次口FORTRAN語言(3)解釋程序是為打開編譯程序技術(shù)的僵局而開發(fā)的(1)(2) b.(1) c.(1)(2)(3) d.(2)(3)1-14.高級語言的語言處理程序分為解釋程序和編譯程序兩種 .編譯程序有五個階段，而解釋程序通常缺少⑴e和(1)b.其中,(1)e 的目的是使最后階段產(chǎn)生的目標代碼更為高效 ^與編譯系統(tǒng)相比，解釋系統(tǒng) (2)d. 解釋程序處理語言時，大多數(shù)采用的是 (3)b方法.(4)a就是一種典型的解釋型語言.(1):a. 中間代碼生成 b.目標代碼生成 c.詞法分析 d.語法分析 e.代碼優(yōu)化(2):a. 比較簡單，可移植性好，執(zhí)行速度快比較復(fù)雜，可移植性好，執(zhí)行速度快比較簡單，可移植性差，執(zhí)行速度慢比較簡單，可移植性好，執(zhí)行速度慢(3):a. 源程序命令被逐個直接解釋執(zhí)行 b.先將源程序轉(zhuǎn)化為之間代碼，再解釋執(zhí)行c.先將源程序解釋轉(zhuǎn)化為目標程序 ，在執(zhí)行d.以上方法都可以:a.BASICb.Cc.FORTRANd.PASCAL1-15.用高級語言編寫的程序經(jīng)編譯后產(chǎn)生的程序叫 b.用不同語言編寫的程序產(chǎn)生 b后，可用_g_連接在一起生成機器可執(zhí)行的程序 .在機器中真正執(zhí)行的是 e.a.源程序 b.目標程序 c.函數(shù) d.過程e.機器指令代碼 f.模塊 g.連接程序 h.程序庫1-16.要在某一臺機器上為某種語言構(gòu)造一個編譯程序 ，必須掌握下述三方面的內(nèi)容 ：c,d,：La.匯編語言 b.高級語言c.源語言 d.目標語言e.程序設(shè)計方法 f.編譯方法 g.測試方法h.機器語言1-17.由于受到具體機器主存容量的限制 ，編譯程序幾個不同階段的工作往往被組合成 ⑴d,諸階段的工作往往是 (2)d 進行的.⑴a. 過程 b.程序 c.批量 d.遍a. 順序 b.并行 c.成批 d.穿插1-18.編譯程序與具體的機器 a,與具體的語言a.a.有關(guān)b.無關(guān)1-19.使用解釋程序時，在程序未執(zhí)行完的情況下， a重新執(zhí)行已執(zhí)行過的部分.a.也能 b.不可能1-20.編譯過程中，語法分析器的任務(wù)就是 b.(1)分析單詞是怎樣構(gòu)成的 (2) 分析單詞串是如何構(gòu)成語句和說明的(3)分析語句和說明是如何構(gòu)成程序的 (4)分析程序的結(jié)構(gòu)a.(2)(3) b.(2)(3)(4) c.(1)(2)(3) d.(1)(2)(3)(4)1-21.編譯程序是一種常用的b軟件.應(yīng)用 b.系統(tǒng)1-22.編寫一個計算機高級語言的源程序后 ，到正式上機運行之前，一般要經(jīng)過 b這幾步.

⑴編輯(2)編譯(3)連接(4)運行a.(1)(2)(3)(4)(1)(2)(3)c.(1)(3) a.(1)(2)(3)(4)1-23.編譯程序必須完成的工作有 a(1)詞法分析(4) (1)詞法分析(4) 代碼生成(2)語法分析(5)之間代碼生成(3)語義分析(6)代碼優(yōu)化a.(1)(2)(3)(4)d.a.(1)(2)(3)(4)d.(1)(2)(3)(4)(6)b.(1)(2)(3)(4)(5)e.(1)(2)(3)(5)(6)c.(1)(2)(3)(4)(5)(6)1-24.“用高級語言書寫的源程序都必須通過編譯1-24.“用高級語言書寫的源程序都必須通過編譯，產(chǎn)生目標代碼后才能投入運行”這種說法a.不正確b.正確1-25.把匯編語言程序翻譯成機器可執(zhí)行的目標程序的工作是由 b完成的.a.編譯器b.匯編器c.解釋器 d.預(yù)處理器1-26.編譯程序生成的目標程序b是機器語言的程序.a. 一定 b.不一定1-27.編譯程序生成的目標程序b是可執(zhí)行的程序.a. 一定 b.不一定1-28.編譯程序是一種B。A.匯編程序 B. 翻譯程序 C. 解釋程序 D. 目標程序1-29.按邏輯上劃分，編譯程序第二步工作是 C。A.語義分析 B. 詞法分析 C. 語法分析 D. 代碼優(yōu)化1-30.通常一個編譯程序中，不僅包含詞法分析，語法分析，中間代碼生成，代碼優(yōu)化，目標代碼生成等五個部分，還應(yīng)包括C。A.模擬執(zhí)行器 B.解釋器C.表格處理和出錯處理 D.符號執(zhí)行器2-07.文法G所描述的語言是C的集合。A.文法G的字母表V中所有符號組成的符號串,■.、....一*...........B.又法G的字母表V的閉包V中的所有符號串C.由文法的開始符號推出的所有終極符串D.由文法的開始符號推出的所有符號串2-08.喬姆斯基(Chomsky)把文法分為四種類型， 即0型、1型、2型、3型。其中3型文法是BA.短語文法 B.正則文法C. 上下文有關(guān)文法 D. 上下文無關(guān)文法2-09.文法G[N]=(2-09.文法G[N]=(,{N,B},CC。L(G[N])={bii>0}C.L(G[N])={b 2i+1 i>0}2-10.一個句型中的最左 BL(G[N])={b 2ii>0}D.L(G[N]尸{b 2i+1 i>1}稱為該句型的句柄?？蛇x項有:A.短語A.短語B.簡單短語 C.素短語D. 終結(jié)符號2-11 .設(shè)2-11 .設(shè)G是一個給定S的文法，S是文法的開始符號x(其中xCV),則稱x是文法G的一個B。A.候選式A.候選式B.句型C.單詞D.產(chǎn)生式2-12.一個上下文無關(guān)文法G2-12.一個上下文無關(guān)文法號，以及一組DA.句子B.句型C.單詞D.產(chǎn)生式2-13.文法G[E]:E-TIE+TT-FIT*FF一aI（E）該文法句型E+F*（E+T）的簡單短語是下列符號串中的 B。①（E+T） ②E+T ③F④F*（E+T）可選項有：A）①和③B）②和③C）③和④D）③2-14.若一個文法是遞歸的，則它所產(chǎn)生的語言的句子A。A.是無窮多個B.是有窮多個C.是可枚舉的 D.個數(shù)是常量3-02.詞法分析器用于識別 C。A.句子B.句型C.單詞D.產(chǎn)生式4-07.在語法分析處理中，F(xiàn)IRST集合、FOLLO僚合、SELECT^合均是 B。A.非終極符集 B. 終極符集 C.字母表D.狀態(tài)集4-08.編譯程序中語法分析器接收以 A為單位的輸入。A.單詞B.表達式C.產(chǎn)生式D.句子5-06.在自底向上的語法分析方法中，分析的關(guān)鍵是D。A.尋找句柄 B. 尋找句型 C.消除遞歸D. 選擇候選式5-07.在LR分析法中，分析棧中存放的》危態(tài)是識別規(guī)范句型 C的DFA狀態(tài)。A.句柄B. 前綴C.活前綴D.LR（0）項目TOC\o"1-5"\h\z三、是非題（下列各題，你認為正確的，請在題干的括號內(nèi)打“ ，”，錯的打“X”。 ）(X)(X)1-31.計算機高級語言翻譯成低級語言只有解釋一種方式。(X)(X)1-32.在編譯中進行語法檢查的目的是為了發(fā)現(xiàn)程序中所有錯誤。1-34.甲機上的某編譯程序在乙機上能直接使用的必要條件是甲機和乙機的操作系統(tǒng)功能完全相同。 （X）2-15.正則文法其產(chǎn)生式為Aa,ABb,A,BCVn,a、bCW。 （，）4-09.每個文法都能改寫為LL（1）文法。 （X）4-10.遞歸下降法允許任一非終極符是直接左遞歸的。 （，）5-08.算符優(yōu)先關(guān)系表不一定存在對應(yīng)的優(yōu)先函數(shù)。 （，）5-09.自底而上語法分析方法的主要問題是候選式的選擇。 （X）法是自頂向下語法分析方法。 （X）5-11.簡單優(yōu)先文法允許任意兩個產(chǎn)生式具有相同右部。 （X）5-12.若一個句型中出現(xiàn)了某產(chǎn)生式的右部，則此右部一定是該句型的句柄。 （X）5-13.一個句型的句柄一定是文法某產(chǎn)生式的右部。 （，）7-02.數(shù)組元素的地址計算與數(shù)組的存儲方式有關(guān)。 （，）8-03.在程序中標識符的出現(xiàn)僅為使用性的。 （X）

(X)(X)9-04.對于數(shù)據(jù)空間的存貯分配， FORTRA(X)(X)9-05.在程序中標識符的出現(xiàn)僅為使用性的。四、名詞解釋1-35.掃描遍指編譯程序?qū)υ闯绦蚧蛑虚g代碼程序從頭到尾掃描一次。2-16.短語一一設(shè)G[Z]是給定文法,w=xuyEV+,為該文法的句型,如果滿足下面兩個條件：①Z xUy;②U u;則稱句型xuy中的子串u是句型xuy的短語。2-17.簡單短語一一設(shè)G[Z]是給定文法，w=xuy€V+,為該文法的句型，如果滿足下面兩個條件：①Z xUy;②Uu;則稱句型xuy中的子串u是句型xuy的簡單短語(或直接短語)。2-18.句柄———個句型中的最左簡單短語稱為該句型的句柄。4-11.語法分析--按文法的產(chǎn)生式識別輸入的符號串是否為一個句子的分析過程。4-12.選擇符集合SELECT—給定上下文無關(guān)文法的產(chǎn)生式 Za,ACVn,aCV*,若a e,貝USELECT(A>a尸F(xiàn)IRST(a),其中如果a ￡,貝USELECT(A>a尸F(xiàn)IRST(a s)UFOLLOW(A)FIRST(a￡)表示FIRST(a)的非｛￡｝元素。5-14.活前綴——若S'=R =R aAco a3co是文法G'中的一個規(guī)范推導(dǎo)，G'是G的拓廣文法，符號串丫是a3的前綴，則稱丫是G的，也是G'的一個活前綴。其中S′為文法開始符號?；颍嚎蓺w前綴的任意首部。5-15.簡歸前綴一一是指規(guī)范句型的一個前綴，這種前綴不含句柄之后的任何符號。(0)項目一一把產(chǎn)生式右部某位置上標有圓點的產(chǎn)生式稱為相應(yīng)文法的一個 LR(0)項目。5-17.最左素短語一一設(shè)有文法 G[S],其句型的素短語是一個短語 ，它至少包含一個終結(jié)符，并除自身外不包含其它素短語，最左邊的素短語稱最左素短語。6-05.語義規(guī)則一一對于文法的每個產(chǎn)生式都配備了一組屬性的計算規(guī)則，稱為語義規(guī)則。6-06.翻譯方案一一將屬性文法中的語義規(guī)則用花括號 ｛｝括起來，插在產(chǎn)生式右部的合適地方，指明語義規(guī)則的計算次序，陳述一些細節(jié)，得到一種語義動作與語法分析交錯的表示方法，以表述語義動作在語法分析過程中的執(zhí)行時刻，稱之為翻譯方案。7-03.后綴式一一一種把運算量(操作數(shù))寫在前面把算符寫在后面(后綴)的表示法。即一個表達式E的后綴形式可以如下定義：(1)如果弱一個變量或常量，則E的后綴式是E自身。(2)如果弱EiopE2形式的表達式，這里op是任何二元操作符，則E的后綴式為Ei'E2'op,這里E1'和E2'分別為E1和E2的后綴式。(3)如果弱(E1)形式的表達式，則E1的后綴式就是E的后綴式。答：一個過程的活動指的是該過程的一次執(zhí)行。 就是說，每次執(zhí)行一個過程體，產(chǎn)生該過程體的一個活動。9-07.活動記錄答：為了管理過程在一次執(zhí)行中所需要的信息，使用一個連續(xù)的存儲塊，這樣一個連續(xù)的存儲塊稱為活動記錄。9-08.活動的生存期答：指的是從執(zhí)行某過程體第一步操作到最后一步操作之間的操作序，包括執(zhí)行過程時調(diào)用其它過程花費的時間。10-06.基本塊的 DAG。答：一個基本塊的 DA提一種其結(jié)點帶有下述標記或附加信息的 DAG圖的葉結(jié)點(沒有后繼的結(jié)點)以一標識符(變量名)或常數(shù)作為標記，表示該結(jié)點代表該變量或常數(shù)的值。如果葉結(jié)點用來代表某變量 A的地址，則用addr(A)作為該結(jié)點的標記。通常把葉結(jié)點上作為標記的標識符加上下標 0，以表示它是該變量的初值。圖的內(nèi)部結(jié)點(有后繼的結(jié)點)以一運算符作為標記，表示該結(jié)點代表應(yīng)用該運算符對其后繼結(jié)點所代表的值進行運算的結(jié)果。圖中各個結(jié)點上可能附加一個或多個標識符，表示這些變量具有該結(jié)點所代表的值。五、簡答題：2-19什么是句子？什么是語言 ?答：設(shè)G是一個給定的文法，S是文法的開始符號，如果S x(其中xCVT),則稱x是文法的一個句子。設(shè)G[S]是給定文法，則由文法G所定義的語言L(G)可描述為：L(G)={x

*S x,x€Vt}2-20.已知文法G[E]為：E-T|E+T|E-TT-F|T*F|T/FF-(E)|i①該文法的開始符號(識別符號)是什么？②請給出該文法的終結(jié)符號集合 VT和非終結(jié)符號集合 VN。③找出句型T+T*F+i的所有短語、簡單短語和句柄。解：①該文法的開始符號(識別符號)是E。②該文法的終結(jié)符號集合 VT={+、-、*、/、(、)、i}。非終結(jié)符號集合 VN={E、T、F}。③句型T+T*F+I的短語為i、T*F、第一個T、T+T*F+i;簡單短語為i、T*F、第一個 T;句柄為第一個 T。2-21.已知文法G[S]為：SfdABAfaA|aBfBb|￡G[S]產(chǎn)生的語言是什么？G[S]能否改寫為等價的正規(guī)文法？解：①G[S]產(chǎn)生的語言是L(G[S]尸{danbmn>1,m>0}o

②G[S]能改寫為等價的正規(guī)文法,其改寫后的等價的正規(guī)文法 G[S']為：S/一dAA 一aA|aB|aB 一bB|b2-22.設(shè)有語言L(G尸｛adaR|aC(a,b)*,aR為a之逆｝，試構(gòu)造產(chǎn)生此語言的上下文無關(guān)文法 G解：根據(jù)題義，可知aR為a之逆的含義就是句子中的符號 a、b以d為中心呈左右對稱出現(xiàn)；由于aC(a,b)*,所以a、b的個數(shù)可以為零。所以可構(gòu)造產(chǎn)生此語言的上下文無關(guān)文法 G[S]為：S-aSa|bSb|d3-03.簡述DFA與NFA有何區(qū)別？答：DFA與NFA的區(qū)別表現(xiàn)為兩個方面：一是NFA可以若干個開始狀態(tài)， 而DFA僅只一個開始狀態(tài)。另一方面，DFA的映象M是從KX匯到K,而NFA的映象M是從KX匯到K的子集，即映象M將產(chǎn)生一個狀態(tài)集合(可能為空集)，而不是單個狀態(tài)。3-04.試給出非確定自動機的定義。答：一個非確定的有窮自動機(NFAM是一個五元組：M=(K,2,f,S,Z)。其中：K是一個有窮集，它的每個元素稱為一個狀態(tài)；2是一個有窮字母表，它的每個元素稱為一個輸入符號，所以也稱2為輸入符號表；f是狀態(tài)轉(zhuǎn)換函數(shù)，是在 KX2*一K的子集的映射，即，f:KX2*一2K;表明在某狀態(tài)下對于某輸入符號可能有多個后繼狀態(tài)；S(K是一一個非空初態(tài)集；Z(K是一一個終態(tài)集(可空)。3-05.為正規(guī)式(a|b)*a(a|b)構(gòu)造一個等價的確定的有限自動機。解答：a，bQD一a―0a，bQD一a―0二^?3-06.給定卜列自動機，將其轉(zhuǎn)換為確定的自動機。+4JBLdstar-飛d解答：⑴消除e邊，得到NFA注：帶十號的結(jié)點為初始狀態(tài)；帶一號的結(jié)點為終止狀態(tài)移:帶十號的結(jié)點為初始狀態(tài)；帶一號的結(jié)點為終止狀態(tài)E)-(Gyd-^^Hl)十- d?十- d?SA十- d?十- d?SAABCEG+[SA][A][A][BCE][G]ABCE[A][BCE][G]BB[BCE][BCE][DG]CCD[G][H]DD[DG][DH]EEG[H][H]GH[DH][DH]HH(2)確定化，得到DFA注：帶十號的結(jié)點為初始狀態(tài)；帶一號的結(jié)點為終止狀態(tài)3-07.給定下列自動機:其中：開始狀態(tài)：0終止狀態(tài)：2(2)給出此DFA的正則表達式。解答：(1)：有狀態(tài)矩陣如圖：abTOC\o"1-5"\h\z00,1 2~1 2001201012-21 2-2 001201012-21 2從而可得DFA如圖:a極小化后:a極小化后:ab)ab)*或a*b(bab)*。(2)此DFA的正則表達式為： (aa*bb)(b4-13.消除下列文法G[E]的左遞歸。E一E-TITT-T/FIFF-(E)?i解答：消除文法G[E]的左遞歸后得到：EfTE'E'--TE'I￡T^FT「一/FT'I￡F-(E)?i4-14.在LL(1)分析法中，LL分別代表什么含義？答：第一個L代表從左到右的寸3描，第二個 L代表每次進行最左推導(dǎo)。4-15.自頂向下分析思想是什么？答：從開始符出發(fā)導(dǎo)出句型并一個符號一個符號地與給定終結(jié)符串進行匹配。如果全部匹配成功，則表示開始符號可推導(dǎo)出給定的終結(jié)符串。因此判定給定終結(jié)符號串是正確句子。4-16.自頂向下的缺點是什么？答：在推導(dǎo)過程中，如果對文法不做限制。那么產(chǎn)生式的選擇成為無根據(jù)的，只好一一去試所有可能的產(chǎn)生式，直至成功為止。這種方法的致命弱點是不斷地回溯，大大影響速度。(1)文法的定義是什么？答：一個上下文無關(guān)文法是LL(1)文法的充分必要條件是每個非終結(jié)符 A的兩個不同產(chǎn)生式，A-a,A-3;滿足SELECT(A一a)ASELECT(A一3尸①。其中，a、3不能同時4-18.什么是文法的左遞歸？答：一個文法含有下列形式的產(chǎn)生式之一時：1)A-A3,ACvn3eV*2)A-B3,BfAa,A、BCVN,a、3CV*則稱該文法是左遞歸的。4-19.遞歸下降法的主要思想是什么？

答：對每個非終結(jié)符按其產(chǎn)生式結(jié)構(gòu)寫出相應(yīng)語法分析子程序。因為文法遞歸相應(yīng)子程序也遞歸，子程序的結(jié)構(gòu)與產(chǎn)生式結(jié)構(gòu)幾乎一致。所以稱此種方法稱為遞歸子程序法或遞歸下降法。5-19.自底向上分析法的原理是什么？答：在采用自左向右掃描，自底向上分析的前提下，該類分析方法是從輸入符號串入手，通過反復(fù)查找當前句型的句柄(最左簡單短語)，并使用文法的產(chǎn)生式把句柄歸約成相應(yīng)的非終極符來一步步地進行分析的。最終把輸入串歸約成文法的開始符號，表明分析成功。5-23.給定文法5-23.給定文法G[Z]:1.ZfCSOifEthenS^A=E—EVAOifEthenS^A=E—EVA其中：Z、CS、A、ECVN；if、then、=、V、iCVta)構(gòu)造此文法的LR(0)項目集規(guī)范族，并給出識別活前綴的 DFAb)構(gòu)造其SLR(1)分析表。解答：1.首先拓廣文法：在解答：1.首先拓廣文法：在綴的DFAG中加入產(chǎn)生式0.Z'-Z,然后得到新的文法G',再求G'的識別全部活前I0：Z'一.ZZ一.CS8.ifEthenI1：Z'一Z.12：Z-C.SSf.A=E2.i13：Cfif.EthenE一.EVAE一.A2.iI4：Z-CS.I5:SfA.=E6:Afi..Follow(Z)={#}Follow(C)={i}Follow(S)={#}Follow(E)={#,V,then}Follow(A)={=,#,V,then}則可構(gòu)造SLR(1)分析表為：ACTIONGOTO0ifthen=Vi#ZCSEA0S3121OK

2S453S784r15S96「6r6「6r67SoS118「5「5r59S12810「211S1312S11r313「4「4r45-24.設(shè)有文法G[S]:SfaA2AbZb求識別該文法所有活前綴的 DFA解答：.首先拓廣文法：在G中加入產(chǎn)生式’一S,然后得到新的文法G''一S一aA一Ab一b.再求G的識別全部活前綴的 DFA6-07.語法制導(dǎo)翻譯方法的基本思想是什么 ？答：在語法分析過程中，每當使用一條產(chǎn)生式進行推導(dǎo)或歸約時，就執(zhí)