編譯原理練習題參考答案

1、、填空題：1-01.編譯程序的工作過程一般可以劃分為詞法分析，語法分析，語義分析，之間代碼生成，代碼優(yōu)化等幾個基本階段,同時還會伴有表格處理和出錯處理.1-02.若源程序是用高級語言編寫的,目標程序是機器語言程序或匯編程序，則其翻譯程序稱為編譯程序.1-03.編譯方式與解釋方式的根本區(qū)別在于是否生成目標代碼.1-04.翻譯程序是這樣一種程序,它能夠將用甲語言書寫的程序轉換成與其等價的用乙語言書寫的程序.1-05.對編譯程序而言，輸入數(shù)據(jù)是源程序，輸出結果是目標程序.1-06.如果編譯程序生成的目標程序是機器代碼程序，則源程序的執(zhí)行分為兩大階段：編譯階段和運行階段.如果編譯程序生成的目標程序是匯

2、編語言程序，則源程序的執(zhí)行分為三個階段：編譯階段,_匯編階段和運行階段.1-07.若源程序是用高級語言編寫的，目標程序是機器語言程序或匯編程序，則其翻譯程序稱為編譯程序。1-08.一個典型的編譯程序中，不僅包括詞法分析、語法分析、中間代碼生成、代碼優(yōu)化、目標代碼生成等五個部分，還應包括表格處理和出錯處理。其中,詞法分析器用于識別單詞。1-09.編譯方式與解釋方式的根本區(qū)別為是否生成目標代碼。2-01.所謂最右推導是指：任何一步 a3 都是對 a 中最右非終結符進行替換的。2-02.一個上下文無關文法所含四個組成部分是一組終結符號、一組非終結符號、一個開始符號、一組產(chǎn)生式2-03.產(chǎn)生式是用于定

3、義語法成分的一種書寫規(guī)則。2-04.設 GS是給定文法，則由文法 G 所定義的語言 L(G)可描述為：L(G)=x*_Sx,xeVT。2-05.設 G 是一個給定的文法，S 是文法的開始符號，如果 Sx*一(其中 xCV),則稱 x 是文法的一個句型。2-06.設 G 是一個給定的文法，S 是文法的開始符號，如果Sx(其中XCVT),則稱 x 是文法的一個句子。3-01.掃描器的任務是從源程序中識別出一個個單詞符號。4-01.語法分析最常用的兩類方法是自上而下和自下而上分析法。4-02.語法分析的任務是識別給定的終極符串是否為給定文法的句子。4-03.遞歸下降法不允許任一非終極符是直接左遞歸的

4、。4-04.自頂向下的語法分析方法的關鍵是如何選擇候選式的問題。4-05.遞歸下降分析法是自頂向上分析方法。4-06.自頂向下的語法分析方法的基本思想是：從文法的開始符號開始，根據(jù)給定的輸入串并按照文法的產(chǎn)生式一步一步的向下進行直接推導，試圖推導出文法的句子，使之與給定的輸入串匹配。5-01.自底向上的語法分析方法的基本思想是：從給定的終極符串開始，根據(jù)文法的規(guī)則一步一步的向上進行直接歸約，試圖歸約到文法的開始符號。5-02.自底向上的語法分析方法的基本思想是：從輸入串入手，利用文法的產(chǎn)生式一步一步地向上進行直接歸約,力求歸約到文法的開始符號。5-03.簡單優(yōu)先方法每次歸約當前句型的句柄，算符

5、優(yōu)先方法每次歸約當前句型的最左素短語，二者都是不斷移進輸入符號，直到符號棧頂出現(xiàn)可歸約串的尾,再向前找到可歸約串的頭,然后歸約。5-04.在 LR(0)分析法的名稱中，L 的含義是自左向右的掃描輸入串，R 的含義是最左歸約，0 的含義是向貌似句柄的符號串后查看 0 個輸入符號。5-05.在 SLR(1)分析法的名稱中，S 的含義是簡單的。6-01.所謂屬性文法是一個屬性文法是一個三元組：A=(GV,F),一個上下文無關文法 G;一個屬性的有窮集 V 和關于屬性的斷言或謂詞的有窮集 F。每個斷言與文法的某產(chǎn)生式相聯(lián)。6-02.綜合屬性是用于“自下而上”傳遞信息。6-03.繼承屬性是用于“自上而下

6、”傳遞信息。6-04.終結符只有綜合屬性，它們由詞法分析器提供。7-01.在使用高級語言編程時，首先可通過編譯程序發(fā)現(xiàn)源程序的全部 A 錯誤和 B 部分錯誤.a.語法 b.語義 c.語用 d.運行8-01.符號表中的信息欄中登記了每個名字的屬性和特征等有關信息，如類型、種屬、所占單元大小、地址等等。8-02.一個過程相應的 DISPLAY 表的內容為現(xiàn)行活動記錄地址和所有外層最新活動記錄的地址。9-01.一個過程相應的 DISPLAY 表的內容為現(xiàn)行活動記錄地址和所有外層最新活動記錄的地址。9-02.常用的兩種動態(tài)存貯分配辦法是棧式動態(tài)分配和堆式動態(tài)分配。9-03.常用的參數(shù)傳遞方式有傳地址，

7、傳值和傳名。10-01.局部優(yōu)化是局限于一個基本塊范圍內的一種優(yōu)化。10-02.代碼優(yōu)化的主要目標是如何提高目標程序的運行速度和如何減少目標程序運行時所需的空間。、單選題：1-10.一個編譯程序中，不僅包含詞法分析，語法分析，中間代碼生成，代碼優(yōu)化，目標代碼生成等五個部分，還應包括c.其中，(2)b 和代碼優(yōu)化部分不是每個編譯程序都必需的詞法分析器用于識別(3)c,語法分析器則可以發(fā)現(xiàn)源程序中的(4)d.(1)a.模擬執(zhí)行器 b.解釋器 c.表格處理和出錯處理 d.符號執(zhí)行器(2)a.語法分析 b.中間代碼生成 c.詞法分析 d.目標代碼生成(3)a.字符串 b.語句 c.單詞 d.標識符(4

8、)a.語義錯誤 b.語法和語義錯誤 c.錯誤并校正 d.語法錯誤1-11.程序語言的語言處理程序是一種(1)a.(2)b 是兩類程序語言處理程序，他們的主要區(qū)別在于(3)d.(1)a.系統(tǒng)軟件 b.應用軟件 c.實時系統(tǒng) d.分布式系統(tǒng)(2)a.高級語言程序和低級語言程序 b.解釋程序和編譯程序c.編譯程序和操作系統(tǒng) d.系統(tǒng)程序和應用程序(3)a.單用戶與多用戶的差別 b.對用戶程序的查錯能力c.機器執(zhí)行效率 d.是否生成目標代碼1-12.匯編程序是將 a 翻譯成 b,編譯程序是將 c 翻譯成 d.a.匯編語言程序 b.機器語言程序d.a 或者 be.a 或者 c1-13.下面關于解釋程序的

9、描述正確的是 b.(1)解釋程序的特點是處理程序時不產(chǎn)生目標代碼(2)解釋程序適用于 COBO 次口 FORTRAN 語言(3)解釋程序是為打開編譯程序技術的僵局而開發(fā)的a. (1)(2)b.(1)c.(1)(2)(3)d.(2)(3)1-14.高級語言的語言處理程序分為解釋程序和編譯程序兩種.編譯程序有五個階段，而解釋程序通常缺少(1)e 和(1)b.其中,(1)e 的目的是使最后階段產(chǎn)生的目標代碼更為高效與編譯系統(tǒng)相比，解釋系統(tǒng)(2)d.解釋程序處理語言時，大多數(shù)采用的是(3)b 方法.(4)a 就是一種典型的解釋型語言.(1):a.中間代碼生成 b.目標代碼生成 c.詞法分析 d.語法分

10、析 e.代碼優(yōu)化(2):a.比較簡單，可移植性好，執(zhí)行速度快b. 比較復雜，可移植性好，執(zhí)行速度快c. 比較簡單，可移植性差，執(zhí)行速度慢d. 比較簡單，可移植性好，執(zhí)行速度慢(3):a.源程序命令被逐個直接解釋執(zhí)行 b.先將源程序轉化為之間代碼，再解釋執(zhí)行c.先將源程序解釋轉化為目標程序，在執(zhí)行 d.以上方法都可以(4) :a.BASICb.Cc.FORTRANd.PASCAL1-15.用高級語言編寫的程序經(jīng)編譯后產(chǎn)生的程序叫 b.用不同語言編寫的程序產(chǎn)生 b 后，可用_g_連接在一起生成機器可執(zhí)行的程序.在機器中真正執(zhí)行的是 e.a.源程序 b.目標程序 c.函數(shù) d.過程e.機器指令代碼

11、f.模塊 g.連接程序 h.程序庫1-16.要在某一臺機器上為某種語言構造一個編譯程序，必須掌握下述三方面的內容：c,d,JLa.匯編語言 b.高級語言 c.源語言 d.目標語言e.程序設計方法 f.編譯方法 g.測試方法 h.機器語言1-17.由于受到具體機器主存容量的限制，編譯程序幾個不同階段的工作往往被組合成d,諸階段的工作往往是(2)d 進行的.a.過程 b.程序 c.批量 d.遍(5) a.順序 b.并行 c.成批 d.穿插1-18.編譯程序與具體的機器 a,與具體的語言 a.a.有關 b.無關1-19.使用解釋程序時，在程序未執(zhí)行完的情況下，a 重新執(zhí)行已執(zhí)行過的部分.a.也能 b

12、.不可能1-20.編譯過程中，語法分析器的任務就是 b.(1)分析單詞是怎樣構成的(2)分析單詞串是如何構成語句和說明的(3)分析語句和說明是如何構成程序的(4)分析程序的結構a.(2)(3)b.(2)(3)(4)c.(1)(2)(3)d.(1)(2)(3)(4)c.高級語言程序f.b 或者 c1-21.編譯程序是一種常用的 b 軟件.a.應用 b.系統(tǒng)1-22.編寫一個計算機高級語言的源程序后，到正式上機運行之前，一般要經(jīng)過 b 這幾步.編輯(2)編譯(3)連接(4)運行b.(1)(2)(3)c.(1)(3)d.(1)(4)1-23.編譯程序必須完成的工作有 aa.不正確 b.正確1-25.

13、把匯編語言程序翻譯成機器可執(zhí)行的目標程序的工作是由 b 完成的.a.編譯器 b.匯編器 c.解釋器 d.預處理器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)化，目標代碼生成等五個部分，還應包括 C。A.模擬執(zhí)行器 B.解釋器 C

14、.表格處理和出錯處理 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.上下文有關文法 D.上下文無關文法可選項有:(1)詞法分析(4)代碼生成(2)語法分析(5)之間代碼生成(3)語義分析(6)代碼優(yōu)化a.(1)(2)(3)(4)d.(1)(2)

15、(3)(4)(6)b.(1)(2)(3)(4)(5)e.(1)(2)(3)(5)(6)c.(1)(2)(3)(4)(5)(6)1-24.“用高級語言書寫的源程序都必須通過編譯，產(chǎn)生目標代碼后才能投入運行”這種說法2-09.文法 GN=(b,N,B,N,Nfb|bB,B-bN),該文法所描述的語言是C。A. L(GN)=bii0C.L(GN)=b2i+1i02-10.一個句型中的最左 BB. L(GN)=b2ii0D.L(GN)=b2i+1i1稱為該句型的句柄。A.短語 B.簡單短語 C.素短語 D.終結符號2-11.設 G 是一個給定S的文法，S 是文法的開始符號x(其中 xCV),則稱 x

16、是文法 G 的一個 BcA.候選式 B.句型 C.單詞 D.產(chǎn)生式2-12.一個上下文無關文法 G 包括四個組成部分，它們是：一組非終結符號，一組終結符號，一個開始符號，以及一組 DA.句子 B.句型 C.單詞 D.產(chǎn)生式2-13.文法 GE:E-TIE+TT-FIT*FF 一 aI（E）該文法句型 E+F*（E+T）的簡單短語是下列符號串中的 B。（E+T）E+TFF*（E+T）可選項有：A）和B）和C）和D）2-14.若一個文法是遞歸的，則它所產(chǎn)生的語言的句子 A。A.是無窮多個 B.是有窮多個 C.是可枚舉的 D.個數(shù)是常量3-02.詞法分析器用于識別 C。A.句子 B.句型 C.單詞

17、D.產(chǎn)生式4-07.在語法分析處理中，F(xiàn)IRST 集合、FOLLO 僚合、SELEC 磔合均是 B。A.非終極符集 B.終極符集 C.字母表 D.狀態(tài)集4-08.編譯程序中語法分析器接收以 A 為單位的輸入。A.單詞 B.表達式 C.產(chǎn)生式 D.句子5-06.在自底向上的語法分析方法中，分析的關鍵是 D。A.尋找句柄 B.尋找句型 C.消除遞歸 D.選擇候選式5-07.在 LR 分析法中，分析棧中存放的危態(tài)是識別規(guī)范句型 C 的 DFA 狀態(tài)。A.句柄 B.前綴 C.活前綴 D.LR（0）項目三、是非題（下列各題，你認為正確的，請在題干的括號內打“，”，錯的打“X”。）1-31.計算機高級語言

18、翻譯成低級語言只有解釋一種方式。（X）1-32.在編譯中進行語法檢查的目的是為了發(fā)現(xiàn)程序中所有錯誤。（X）1-34.甲機上的某編譯程序在乙機上能直接使用的必要條件是甲機和乙機的操作系統(tǒng)功能完全相同。（X）2-15.正則文法其產(chǎn)生式為 Aa,ABb,A,BVN,a、bCW。（，）4-09.每個文法都能改寫為 LL（1）文法。（X）4-10.遞歸下降法允許任一非終極符是直接左遞歸的。（，）5-08.算符優(yōu)先關系表不一定存在對應的優(yōu)先函數(shù)。（，）5-09.自底而上語法分析方法的主要問題是候選式的選擇。（X）5-10.LR 法是自頂向下語法分析方法。（X）5-11.簡單優(yōu)先文法允許任意兩個產(chǎn)生式具有相

19、同右部。（X）5-12.若一個句型中出現(xiàn)了某產(chǎn)生式的右部，則此右部一定是該句型的句柄。（X）5-13.一個句型的句柄一定是文法某產(chǎn)生式的右部。（，）7-02.數(shù)組元素的地址計算與數(shù)組的存儲方式有關。（，）8-03.在程序中標識符的出現(xiàn)僅為使用性的。（X）9-04,對于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRA 咪用動態(tài)貯存分配策略。9-05.在程序中標識符的出現(xiàn)僅為使用性的。四、名詞解釋1-35,掃描遍指編譯程序對源程序或中間代碼程序從頭到尾掃描一次。2-16,短語一一設 GZ是給定文法，w=xuyCV+,為該文法的句型，如果滿足下面兩個條件：ZxUy;Uu;則稱句型 xuy 中的子串 u 是句型 xu

20、y 的短語。2-17,簡單短語一一設 GZ是給定文法，w=xuyV+,為該文法的句型，如果滿足下面兩個條件：ZxUy;Uu;則稱句型 xuy 中的子串 u 是句型 xuy 的簡單短語(或直接短語)。2-18,短柄個句型中的最左簡單短語稱為該句型的句柄。4-11.語法分析-按文法的產(chǎn)生式識別輸入的符號串是否為一個句子的分析過程。4-12.選擇符集合 SELECT給定上下文無關文法的產(chǎn)生式 Za,ACVN,aCV*,若ae,貝 USELECT(Aa)=FIRST(a),其中如果a,貝 USELECT(Aa)=FIRST(as)UFOLLOW(A)FIRST(as)表示 FIRST(a)的非元素。5

21、-14,活前綴若 S=R=RaAcoa3co 是文法 G中的一個規(guī)范推導，G是 G 的拓廣文法，符號串丫是 a3 的前綴，則稱丫是 G 的，也是 G的一個活前綴。其中 S為文法開始符號?；颍嚎蓺w前綴的任意首部。5-15,可歸前綴一一是指規(guī)范句型的一個前綴，這種前綴不含句柄之后的任何符號。5-16.LR(0)項目一一把產(chǎn)生式右部某位置上標有圓點的產(chǎn)生式稱為相應文法的一個 LR(0)項目。5-17.最左素短語一一設有文法 GS,其句型的素短語是一個短語，它至少包含一個終結符，并除自身外不包含其它素短語，最左邊的素短語稱最左素短語。6-05.語義規(guī)則一一對于文法的每個產(chǎn)生式都配備了一組屬性的計算規(guī)則

22、，稱為語義規(guī)則。6-06.翻譯方案一一將屬性文法中的語義規(guī)則用花括號括起來，插在產(chǎn)生式右部的合適地方，指明語義規(guī)則的計算次序，陳述一些細節(jié)，得到一種語義動作與語法分析交錯的表示方法，以表述語義動作在語法分析過程中的執(zhí)行時刻，稱之為翻譯方案。7-03,后綴式一一一種把運算量(操作數(shù))寫在前面把算符寫在后面(后綴)的表示法。即一個表達式 E 的后綴形式可以如下定義：(1)如果弱一個變量或常量，則 E 的后綴式是 E 自身。(2)如果弱 E1opE2 形式的表達式，這里 op 是任何二元操作符，則 E 的后綴式為曰日 op,這里日和 E/分別為E1 和 E2 的后綴式。(3)如果弱(曰)形式的表達式

23、，則 E1 的后綴式就是 E 的后綴式。答：一個過程的活動指的是該過程的一次執(zhí)行。就是說，每次執(zhí)行一個過程體，產(chǎn)生該過程體的一個活動。9-07.活動記錄(X)(X)答：為了管理過程在一次執(zhí)行中所需要的信息，使用一個連續(xù)的存儲塊，這樣一個連續(xù)的存儲塊稱為活動記錄。9-08.活動的生存期答：指的是從執(zhí)行某過程體第一步操作到最后一步操作之間的操作序，包括執(zhí)行過程時調用其它過程花費的時間。10-06.基本塊的 DAG答：一個基本塊的 DA 提一種其結點帶有下述標記或附加信息的 DAG（1）圖的葉結點（沒有后繼的結點）以一標識符（變量名）或常數(shù)作為標記，表示該結點代表該變量或常數(shù)的值。如果葉結點用來代表

24、某變量 A 的地址，則用 addr（A）作為該結點的標記。通常把葉結點上作為標記的標識符加上下標 0,以表示它是該變量的初值。（2）圖的內部結點（有后繼的結點）以一運算符作為標記，表示該結點代表應用該運算符對其后繼結點所代表的值進行運算的結果。（3）圖中各個結點上可能附加一個或多個標識符，表示這些變量具有該結點所代表的值。五、簡答題：2-19 什么是句子？什么是語言？答：設 G 是一個給定的文法，S 是文法的開始符號，如果Sx（其中 xCVT）,則稱 x 是又法的一個句子。設 GS是給定文法，則由文法 G 所定義的語言 L（G）可描述為：L（G）=x*Sx,xeVT。2-20.已知文法 GE為

25、：E 一 T|E+T|E-TT-F|T*F|T/FF-（E）|i該文法的開始符號（識別符號）是什么？請給出該文法的終結符號集合 VT和非終結符號集合。找出句型 T+T*F+i 的所有短語、簡單短語和句柄。解：該文法的開始符號（識別符號）是 E。該文法的終結符號集合 VT=+、-、*、/、（、）、i。非終結符號集合=E、T、F。句型 T+T*F+I 的短語為 i、T*F、第一個 T、T+T*F+i;簡單短語為 i、T*F、第一個 T;句柄為第一個 To2-21.已知文法 GS為:S-dABA 一 aA|aB-Bb|GS產(chǎn)生的語言是什么？GS能否改寫為等價的正規(guī)文法？解：GS產(chǎn)生的語言是 L（GS

26、）=danbmn1,m0oGS能改寫為等價的正規(guī)文法,其改寫后的等價的正規(guī)文法 GS為：S/一 dAA 一 aA|aB|aB 一 bB|b2-22.設有語言 L(G)=adaR|aC(a,b)*,aR為 a 之逆，試構造產(chǎn)生此語言的上下文無關文法 G解：根據(jù)題義，可知 aR為 a 之逆的含義就是句子中的符號 a、b 以 d 為中心呈左右對稱出現(xiàn)；由于 aC(a,b)*,所以 a、b 的個數(shù)可以為零。所以可構造產(chǎn)生此語言的上下文無關文法 GS為：S-aSa|bSb|d3-03.簡述 DFA 與 NFA 有何區(qū)別？答：DFA 與 NFA 的區(qū)別表現(xiàn)為兩個方面：一是 NFA 可以若干個開始狀態(tài)，而

27、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)。其中：1. K 是一個有窮集，它的每個元素稱為一個狀態(tài)；2. 2 是一個有窮字母表，它的每個元素稱為一個輸入符號，所以也稱 2 為輸入符號表；3. f 是狀態(tài)轉換函數(shù)，是在 KX2*一 K 的子集的映射，即，f:KX2*一 2K;表明在某狀態(tài)下對于某輸入符號可能有多個后繼狀態(tài)；4. S(K

28、是一一個非空初態(tài)集；5. Z(K 是一一個終態(tài)集(可空)。3-05.為正規(guī)式(a|b)*a(a|b)構造一個等價的確定的有限自動機。解答：aQo)b3-06.給定卜列自動機，將其轉換為確定的自動機。+3id-siaHSSgj-KGd解答：(1)消除 e 邊，得到 NFA.d12E(GW：注：帶十號的結點為初始狀態(tài)；帶一號的結點為終止狀態(tài)敵:帶十號的結點為初始狀態(tài)；帶一號的結點為終止狀態(tài)一(2)確定化，得到 DFA十-d十-dSAABCEG+SAAABCEGABCEABCEGBBBCEBCEDGCCDGHDDDGDHEEGHHGHDHDHHH注：帶十號的結點為初始狀態(tài)；帶一號的結點為終止狀態(tài)3-

29、07.給定下列自動機:把此自動機轉換為確定自動機其中：開始狀態(tài)：0終止狀態(tài)：2DFA(2)解答:給出此 DFA 的正則表達式。(1):有狀態(tài)矩陣如圖:01-20,1ab222a001-21b012012122從而可得 DFA 如圖:a(2)此 DFA 的正則表達式為：(aa*bb)(bab)*或 a*b(bab)*。4-13.消除下列文法 GE的左遞歸。E 一 E-TITT-T/FIFFf(E)Ii解答：消除文法 GE的左遞歸后得到：EfTEE-TEITfFTT一/FTIFf(E)Ii4-14.在 LL(1)分析法中,LL 分別代表什么含義？答：第一個 L 代表從左到右的寸 3 描，第二個 L

30、 代表每次進行最左推導。4-15.自頂向下分析思想是什么？答：從開始符出發(fā)導出句型并一個符號一個符號地與給定終結符串進行匹配。如果全部匹配成功，則表示開始符號可推導出給定的終結符串。因此判定給定終結符號串是正確句子。4-16.自頂向下的缺點是什么？答：在推導過程中，如果對文法不做限制。那么產(chǎn)生式的選擇成為無根據(jù)的，只好一一去試所有可能的產(chǎn)生式，直至成功為止。這種方法的致命弱點是不斷地回溯，大大影響速度。4-17.LL(1)文法的定義是什么？答：一個上下文無關文法是 LL(1)文法的充分必要條件是每個非終結符 A 的兩個不同產(chǎn)生式，A-a,A-3;滿足 SELECT(A 一 a)ASELECT(

31、A 一 3 尸。其中，a、3 不能同時 4-18.什么是文法的左遞歸？答：一個文法含有下列形式的產(chǎn)生式之一時：1)A-A3,ACVN3eV*2)A-B3,BfAa,A、BCVN,a、3CV*則稱該文法是左遞歸的。4-19.遞歸下降法的主要思想是什么？答：對每個非終結符按其產(chǎn)生式結構寫出相應語法分析子程序。因為文法遞歸相應子程序也遞歸，子程序的結構與產(chǎn)生式結構幾乎一致。所以稱此種方法稱為遞歸子程序法或遞歸下降法。5-19.自底向上分析法的原理是什么?答：在采用自左向右掃描，自底向上分析的前提下，該類分析方法是從輸入符號串入手，通過反復查找當前句型的句柄(最左簡單短語)，并使用文法的產(chǎn)生式把句柄歸

32、約成相應的非終極符來一步步地進行分析的。最終把輸入串歸約成文法的開始符號，表明分析成功。2.Follow(Z)=#Follow(C)=iFollow(S)=#Follow(E)=#,V,thenFollow(A)=,#,V,then則可構造 SLR(1)分析表為:ACTIONGOTO0ifthen=Vi#ZCSEA0S3125-23.給定文法 GZ:1.2.3.4.Z-CSCfifEthenSfA=EEfEVA其中：Z、if、C、S、A、ECVN；then、V、5.6.EfAAfia)構造此文法的 LR(0)項目集規(guī)范族，并給出識別活前綴的DFAb)構造其 SLR(1)分析表。解答：1.首先拓

33、廣文法：在G 中加入產(chǎn)生式 0.Z-Z,然后得到新的文法G ,再求 G的識別全部活前綴的DFA10：I7：CfifE.thenI1:I2：Zf.CSCf.ifEthenZ-Z.ZfC.SI9：EfE.VASfA=.EEf.EVAEf.AI3：S.A=EAf.iCfif.EthenI10：III:Af.iC 一 ifEthen.E-EV.AI4Ef.EVAEf.AI12:Af.iSA=E.Af.iZ-CS.SfA.=EA-i.I13:EfE.VAE-EVA.1OK2S6453&784r15S966r66r67SOS11855r59&12810211&1312S11r31344r45-24.設有文法 GS:S 一 aAAfAbAfb解答:(1).首先拓廣文法：在 G 中加入產(chǎn)生式 0.S-S,然后得到新的文法 G:0.S一 S1.SfaA2 .AfAb3 .A-b(2).再求 G 的識別全部活前綴的 DFA6-07.語法制導翻譯方法的基本思想是什么答：在語法分析過程中，每當使用一條產(chǎn)生式進行推導或歸約時，就執(zhí)行該產(chǎn)生式所對應的語義動作進行屬性計算，完成對輸入符號串的翻譯。6-08.何謂“語法制導翻譯”？答：在語法分析過程中，隨著分析的步步