1、5-05.在 SLR (1)分析法的名稱中，S 的含義是 簡(jiǎn)單的、填空題：1-01.編譯程序的工作過程一般可以劃分為詞法分析，語法分析，語義分析，之間代碼生成，代碼優(yōu)化等幾個(gè)基本階段，同時(shí)還會(huì)伴有表格處理 和出錯(cuò)處理.1-02.若源程序是用高級(jí)語言編寫的，目標(biāo)程序是 機(jī)器語言程序或匯編程序，則其翻譯程序稱為編譯程序1-03.編譯方式與解釋方式的根本區(qū)別在于是否生成目標(biāo)代碼.1-04.翻譯程序是這樣一種程序，它能夠?qū)⒂眉渍Z言書寫的程序轉(zhuǎn)換成與其等價(jià)的用乙語言書寫的程序.1-05.對(duì)編譯程序而言，輸入數(shù)據(jù)是源程序，輸出結(jié)果是目標(biāo)程序.1-06.如果編譯程序生成的目標(biāo)程序是機(jī)器代碼程序，則源程序的執(zhí)

2、行分為兩大階段：編譯階段 和 運(yùn)行階段如果編譯程序生成的目標(biāo)程序是匯編語言程序，則源程序的執(zhí)行分為三個(gè)階段：編譯階段，匯編階段和運(yùn)行階段 .1-07.若源程序是用高級(jí)語言編寫的，目標(biāo)程序是機(jī)器語言程序或匯編程序，則其翻譯程序稱為 編譯程序。1-08. 一個(gè)典型的編譯程序中，不僅包括詞法分析、語法分析、中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成等 五個(gè)部分，還應(yīng)包括表格處理和出錯(cuò)處理。其中，詞法分析器用于識(shí)別單詞。1- 09.編譯方式與解釋方式的根本區(qū)別為是否生成目標(biāo)代碼。2- 01.所謂最右推導(dǎo)是指：任何一步ag都是對(duì)a中最右非終結(jié)符進(jìn)行替換的。2-02. 一個(gè)上下文無關(guān)文法所含四個(gè)組成部分是一組終

3、結(jié)符號(hào)、 一組非終結(jié)符號(hào)、一個(gè)開始符號(hào)、一組產(chǎn)生式 。2-03 .產(chǎn)生式是用于定義語法成分的一種書寫規(guī)則。2-04.設(shè) GS是給定文法，則由文法G 所定義的語言 L(G)可描述為：L(G)= X 丨 Sx，x VT*。2-05.設(shè) G 是一個(gè)給定的文法， S 是文法的開始符號(hào)，如果Sx (其中 x V*)，則稱 x 是文法的一個(gè)句型。2- 06.設(shè) G 是一個(gè)給定的文法，S 是文法的開始符號(hào)，如果Sx 俱中 x VT*),則稱 x 是文法的一個(gè)句子。3- 01.掃描器的任務(wù)是從源程序中識(shí)別出一個(gè)個(gè)單詞符號(hào)。4- 01.語法分析最常用的兩類方法是自上而下 和 自下而上分析法。4-02.語法分析的

4、任務(wù)是識(shí)別給定的終極符串是否為給定文法的句子。4-03.遞歸下降法不允許任一非終極符是直接左遞歸的。4-04.自頂向下的語法分析方法的關(guān)鍵是如何選擇候選式 的問題。4-05.遞歸下降分析法是自頂向上分析方法。4- 06.自頂向下的語法分析方法的基本思想是：從文法的開始符號(hào)開始，根據(jù)給定的輸入串并按照文法的產(chǎn)生式一步一步的向下進(jìn)行直接推導(dǎo)，試圖推導(dǎo)出文法的句子，使之與給定的輸入串匹配。5- 01 .自底向上的語法分析方法的基本思想是：從給定的終極符串開始，根據(jù)文法的規(guī)則一步一步的向上進(jìn)行直接歸約，試圖歸約到文法的開始符號(hào) 。5-02.自底向上的語法分析方法的基本思想是：從輸入串入手，利用文法的產(chǎn)

5、生式一步一步地向上進(jìn)行接歸約 ，力求 歸約 到文法的 開始符號(hào)。5-05.在 SLR (1)分析法的名稱中，S 的含義是 簡(jiǎn)單的5-03.簡(jiǎn)單優(yōu)先方法每次歸約當(dāng)前句型的句柄， 算符優(yōu)先方法每次歸約當(dāng)前句型的最左素短語，二者都是不斷移進(jìn)輸入符號(hào)，直到符號(hào)棧頂出現(xiàn)可歸約串 的尾，再向前找到 可歸約串 的頭，然后歸約。5-04.在 LR( 0)分析法的名稱中，L 的含義是，R 的含義是 最左歸約 ，0 的含義是向貌似句柄的符號(hào)串后查看 0 個(gè)輸入符號(hào) 。6-01.所謂屬性文法是一個(gè)屬性文法是一個(gè)三元組：A=( G,V, F), 個(gè)上下文無關(guān)文法G; 個(gè)屬性的有窮集 V 和關(guān)于屬性的斷言或謂詞的有窮集

6、F。每個(gè)斷言與文法的某產(chǎn)生式相聯(lián)。6-02.綜合屬性是用于“自下而上”傳遞信息。6-03.繼承屬性是用于“自上而下”傳遞信息。6- 04.終結(jié)符只有綜合屬性，它們由詞法分析器提供。7- 01.在使用高級(jí)語言編程時(shí)，首先可通過編譯程序發(fā)現(xiàn)源程序的全部A錯(cuò)誤和 B 部分錯(cuò)誤.a.語法 b.語義 c 語用 d.運(yùn)行8- 01.符號(hào)表中的信息欄中登記了每個(gè)名字的屬性和特征等有關(guān)信息，如類型、種屬、所占單元大小、地8- 02. 一個(gè)過程相應(yīng)的 DISPLAY 表的內(nèi)容為 現(xiàn)行活動(dòng)記錄地址和所有外層最新活動(dòng)記錄的地址。9- 01. 一個(gè)過程相應(yīng)的 DISPLAY 表的內(nèi)容為現(xiàn)行活動(dòng)記錄地址和所有外層最新活

7、動(dòng)記錄的地址。9-02.常用的兩種動(dòng)態(tài)存貯分配辦法是棧式動(dòng)態(tài)分配和 堆式動(dòng)態(tài)分配。9- 03.常用的參數(shù)傳遞方式有傳地址，傳值和傳名。10- 01.局部?jī)?yōu)化是局限于一個(gè)基本塊 范圍內(nèi)的一種優(yōu)化。10-02.代碼優(yōu)化的主要目標(biāo)是如何提高目標(biāo)程序的運(yùn)行速度 和如何減少目標(biāo)程序運(yùn)行時(shí)所需的空間二、單選題：1-10. 一個(gè)編譯程序中，不僅包含詞法分析，語法分析，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生 成等五個(gè)部分，還應(yīng)包括qc .其中,b 和代碼優(yōu)化部分不是每個(gè)編譯程序都必需的.詞法分析器用于識(shí)別(3)c，語法分析器則可以發(fā)現(xiàn)源程序中的d .(1) a.模擬執(zhí)行器 b.解釋器 C.表格處理和出錯(cuò)處理d.符

8、號(hào)執(zhí)行器(2) a.語法分析 b.中間代碼生成c.詞法分析 d. 目標(biāo)代碼生成a.字符串 b.語句 c.單詞 d.標(biāo)識(shí)符(4) a.語義錯(cuò)誤 b.語法和語義錯(cuò)誤c.錯(cuò)誤并校正d.語法錯(cuò)誤1-11.程序語言的語言處理程序是一種(1)a .b 是兩類程序語言處理程序，他們的主要區(qū)別在于(3)d.(1) a.系統(tǒng)軟件 b.應(yīng)用軟件 c.實(shí)時(shí)系統(tǒng) d.分布式系統(tǒng)(2) a.高級(jí)語言程序和低級(jí)語言程序b.解釋程序和編譯程序c.編譯程序和操作系統(tǒng) d.系統(tǒng)程序和應(yīng)用程序a.單用戶與多用戶的差別b.對(duì)用戶程序的查錯(cuò)能力c.機(jī)器執(zhí)行效率d.是否生成目標(biāo)代碼1-12.匯編程序是將a 翻譯成 b，編譯程序是將c

9、翻譯成 d .a.匯編語言程序b.機(jī)器語言程序c.高級(jí)語言程序d. a 或者 b e. a 或者 c f. b 或者 c1-13.下面關(guān)于解釋程序的描述正確的是b .(1) 解釋程序的特點(diǎn)是處理程序時(shí)不產(chǎn)生目標(biāo)代碼(2) 解釋程序適用于 COBOL 和 FORTRAN 語言(3) 解釋程序是為打開編譯程序技術(shù)的僵局而開發(fā)的a. (1)(2) b. (1) c. (1)(2)(3) d.(2)(3)1-14.高級(jí)語言的語言處理程序分為解釋程序和編譯程序兩種編譯程序有五個(gè)階段，而解釋程序通常缺少_(1)e 和(1)b.其中， (1)e 的目的是使最后階段產(chǎn)生的目標(biāo)代碼更為高效與編譯系統(tǒng)相比，解釋系

10、統(tǒng)(2)d解釋程序處理語言時(shí)，大多數(shù)采用的是b 方法.a 就是一種典型的解釋型語言.(1) : a.中間代碼生成b目標(biāo)代碼生成 c詞法分析 d語法分析 e代碼優(yōu)化(2) : a比較簡(jiǎn)單，可移植性好，執(zhí)行速度快b. 比較復(fù)雜，可移植性好，執(zhí)行速度快c比較簡(jiǎn)單，可移植性差，執(zhí)行速度慢d. 比較簡(jiǎn)單，可移植性好，執(zhí)行速度慢(3) : a.源程序命令被逐個(gè)直接解釋執(zhí)行b.先將源程序轉(zhuǎn)化為之間代碼，再解釋執(zhí)行c. 先將源程序解釋轉(zhuǎn)化為目標(biāo)程序，在執(zhí)行d.以上方法都可以(4) : a. BASIC b. C c. FORTRAN d. PASCAL1-15.用高級(jí)語言編寫的程序經(jīng)編譯后產(chǎn)生的程序叫b.用不

11、同語言編寫的程序產(chǎn)生b 后，可用g連接在一起生成機(jī)器可執(zhí)行的程序.在機(jī)器中真正執(zhí)行的是e .a.源程序 b.目標(biāo)程序 c.函數(shù) d.過程e.機(jī)器指令代碼 f.模塊 g.連接程序 h.程序庫1-16.要在某一臺(tái)機(jī)器上為某種語言構(gòu)造一個(gè)編譯程序，必須掌握下述三方面的內(nèi)容 :c 丄,_L.a.匯編語言 b.高級(jí)語言 c.源語言 d.目標(biāo)語言e.程序設(shè)計(jì)方法 f.編譯方法 g.測(cè)試方法 h.機(jī)器語言1-17.由于受到具體機(jī)器主存容量的限制，編譯程序幾個(gè)不同階段的工作往往被組合成(1)d，諸階段的工作往往是 (2)d 進(jìn)行的.(1) a.過程 b.程序 c.批量 d.遍a.順序 b.并行 c.成批 d.

12、穿插1-18.編譯程序與具體的機(jī)器a，與具體的語言 a .a.有關(guān) b.無關(guān)1-19.使用解釋程序時(shí)，在程序未執(zhí)行完的情況下，a 重新執(zhí)行已執(zhí)行過的部分.a.也能 b.不可能1-20.編譯過程中，語法分析器的任務(wù)就是b .(1)分析單詞是怎樣構(gòu)成的(2)分析單詞串是如何構(gòu)成語句和說明的(3) 分析語句和說明是如何構(gòu)成程序的(4)分析程序的結(jié)構(gòu)a.b.(3)(4) c. (1) (2)(3) d.(1) (2)(3)(4)1-21.編譯程序是一種常用的b 軟件.a.應(yīng)用 b.系統(tǒng)1-22.編寫一個(gè)計(jì)算機(jī)高級(jí)語言的源程序后，到正式上機(jī)運(yùn)行之前，一般要經(jīng)過b 這幾步.(1)編輯編譯連接運(yùn)行a. (1

13、) (2)(3)(4) b. (1) (2)(3) c. (1) (3) d.(1) (4)1-23.編譯程序必須完成的工作有_a 一.(1)詞法分析(2)語法分析(3)語義分析(4) 代碼生成(5)之間代碼生成(6)代碼優(yōu)化a.b. (1)(2)(3)(4)(5) c. (1)(2)(3)(4)(5)(6)d. (1) (2)(3)(4)(6) e. (1) (2)(3)(5)(6)1-24.用高級(jí)語言書寫的源程序都必須通過編譯，產(chǎn)生目標(biāo)代碼后才能投入運(yùn)行 ”這種說法aa.不正確 b.正確1-25.把匯編語言程序翻譯成機(jī)器可執(zhí)行的目標(biāo)程序的工作是由b 完成的.a.編譯器 b.匯編器 c.解釋

14、器 d.預(yù)處理器1-26.編譯程序生成的目標(biāo)程序b是機(jī)器語言的程序.a. 一定 b.不一定1-30 通常一個(gè)編譯程序中，不僅包含詞法分析，語法分析，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等五個(gè)部分，還應(yīng)包括CA.模擬執(zhí)行器B.解釋器C.表格處理和出錯(cuò)處理D.符號(hào)執(zhí)行器2-07 .文法 G 所描述的語言是 C的集合。A. 文法 G 的字母表 V 中所有符號(hào)組成的符號(hào)串B. 文法 G 的字母表 V 的閉包 V*中的所有符號(hào)串C. 由文法的開始符號(hào)推出的所有終極符串D. 由文法的開始符號(hào)推出的所有符號(hào)串2-08.喬姆斯基(Chomsky)把文法分為四種類型，即 0型、1 型、2 型、3 型。其中 3

15、型文法是BA.短語文法B.正則文法C 上下文有關(guān)文法D.上下文無關(guān)文法2-09.文法 GN= (b, N, B, N, Nb | bB, BbN)，該文法所描述的語言是2-10 . 一個(gè)句型中的最左B稱為該句型的句柄?？蛇x項(xiàng)有：A.短語B.簡(jiǎn)單短語C.素短語D.終結(jié)符號(hào)2-11 .設(shè) G 是一個(gè)給定的文法，S 是文法的開始符號(hào)，如果Sx(其中 x V*),則稱 x 是文法 G 的一個(gè) BA.候選式B.句型C.單詞D.產(chǎn)生式2-12 .一個(gè)上下文無關(guān)文法G 包括四個(gè)組成部分，它們是：一組非終結(jié)符號(hào)，一組終結(jié)符號(hào)，一個(gè)開始符號(hào)，以及一組D。A.句子B.句型C.單詞D.產(chǎn)生式2-13.文法 GE:a

16、. 一定 b.不一定1-28.編譯程序是一種B 。A.匯編程序B.翻譯程序C.解釋程序1-29 .按邏輯上劃分,編譯程序第二步工作是C 。A.語義分析B.詞法分析C.語法分析D.目標(biāo)程序D.代碼優(yōu)化C 。A. L(GN)=biIi0C. L(GN)=b2i+1Ii0B. L(GN)=b2i| i 0D. L(GN)=b2i+1| i 11-27.編譯程序生成的目標(biāo)程序b 是可執(zhí)行的程序TIE+TFIT*Fi aI(E)(X(XA.句柄B.前綴C.活前綴D.LR(0項(xiàng)三、是非題(下列各題，你認(rèn)為正確的，請(qǐng)?jiān)陬}干的括號(hào)內(nèi)打“ /錯(cuò)的打“X”)1-31.計(jì)算機(jī)高級(jí)語言翻譯成低級(jí)語言只有解釋一種方式。

17、(X(X1-34.甲機(jī)上的某編譯程序在乙機(jī)上能直接使用的必要條件是甲機(jī)和乙機(jī)的操作系統(tǒng)功能完全相同。2-15.正則文法其產(chǎn)生式為Aa, ABb, A,B VN,a、b VT。(V)4-09.每個(gè)文法都能改寫為L(zhǎng)L(1)文法。(X1-32.在編譯中進(jìn)行語法檢查的目的是為了發(fā)現(xiàn)程序中所有錯(cuò)誤。(X5-08.算符優(yōu)先關(guān)系表不一定存在對(duì)應(yīng)的優(yōu)先函數(shù)。5-09 .自底而上語法分析方法的主要問題是候選式的選擇。 法是自頂向下語法分析方法。(X(X5-11.簡(jiǎn)單優(yōu)先文法允許任意兩個(gè)產(chǎn)生式具有相同右部。(X5-12.若一個(gè)句型中出現(xiàn)了某產(chǎn)生式的右部，則此右部一定是該句型的句柄。5-13. 一個(gè)句型的句柄一定是

18、文法某產(chǎn)生式的右部。7-02.數(shù)組元素的地址計(jì)算與數(shù)組的存儲(chǔ)方式有關(guān)。8-03 .在程序中標(biāo)識(shí)符的出現(xiàn)僅為使用性的。(X9-04.對(duì)于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN采用動(dòng)態(tài)貯存分配策略。9-05 .在程序中標(biāo)識(shí)符的出現(xiàn)僅為使用性的。四、名詞解釋1-35.掃描遍指編譯程序?qū)υ闯绦蚧蛑虚g代碼程序從頭到尾掃描一次。2-16.短語設(shè) GZ是給定文法,w=xuy V+,為該文法的句型，如果滿足下面兩個(gè)條件該文法句型 E+ F* (E+ T)的簡(jiǎn)單短語是下列符號(hào)串中的B ( E+ T) E+ T F F* (E+ T)可選項(xiàng)有：A)和 B)和C)和D)2- 14 .若一個(gè)文法是遞歸的，則它所產(chǎn)生的語言

19、的句子A。A是無窮多個(gè)B是有窮多個(gè)C是可枚舉的D個(gè)數(shù)是常量3- 02 詞法分析器用于識(shí)別C。A.句子B.句型C.單詞D.產(chǎn)生式4-07 在語法分析處理中，F(xiàn)IRST集合、FOLLOW 集合、SELECTS 合均是B。A.非終極符集B.終極符集C.字母表D.狀態(tài)集4- 08.編譯程序中語法分析器接收以A為單位的輸入。A.單詞B.表達(dá)式C.產(chǎn)生式D.句子5- 06 .在自底向上的語法分析方法中，分析的關(guān)鍵是D。A.尋找句柄B.尋找句型C.消除遞歸D.選擇候選式5-07.在 LR 分析法中，分析棧中存放的狀態(tài)是識(shí)別規(guī)范句型C 的 DFA 狀態(tài)。1Z xUy;2U u;則稱句型 xuy 中的子串 u

20、是句型 xuy 的短語。2-17.簡(jiǎn)單短語設(shè) GZ是給定文法，w=xuy V+,為該文法的句型，如果滿足下面兩個(gè)條件1Z xUy;2U u;則稱句型 xuy 中的子串 u 是句型 xuy 的簡(jiǎn)單短語(或直接短語)。2-18 句柄一個(gè)句型中的最左簡(jiǎn)單短語稱為該句型的句柄。4-11.語法分析一一按文法的產(chǎn)生式識(shí)別輸入的符號(hào)串是否為一個(gè)句子的分析過程。4- 12.選擇符集合 SELECT 給定上下文無關(guān)文法的產(chǎn)生式Aa, A VN, V*,若a則SELECT(Aa)=FIRS)T 其中如果as,貝USELECT(Aa)=FIRST )FOLLOW(A)FIRST(憶表示 FIRST(的非s元素。5-

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

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

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

24、A 的地址，則用 addr (A)作為該結(jié)點(diǎn)的標(biāo)記。通常把葉結(jié)點(diǎn)上作為標(biāo)記的標(biāo)識(shí)符加上下標(biāo) 0，以表示它是該變量的初值。(2) 圖的內(nèi)部結(jié)點(diǎn)(有后繼的結(jié)點(diǎn))以一運(yùn)算符作為標(biāo)記，表示該結(jié)點(diǎn)代表應(yīng)用該運(yùn)算符對(duì)其后繼結(jié)點(diǎn)所 代表的值進(jìn)行運(yùn)算的結(jié)果。(3) 圖中各個(gè)結(jié)點(diǎn)上可能附加一個(gè)或多個(gè)標(biāo)識(shí)符，表示這些變量具有該結(jié)點(diǎn)所代表的值。五、簡(jiǎn)答題：2-19 什么是句子 什么是語言答：設(shè) G 是一個(gè)給定的文法，S 是文法的開始符號(hào)，如果Sx 其中 x VT*),則稱 x 是文法的一個(gè)句子。設(shè) GS 是給定文法，則由文法G 所定義的語言 L(G)可描述為：L(G)=x | Sx,x VT*。2-20.已知文法

25、GE為：T|E+T|E-TF|T*F|T/F1(E)|i1該文法的開始符號(hào)(識(shí)別符號(hào))是什么2請(qǐng)給出該文法的終結(jié)符號(hào)集合VT和非終結(jié)符號(hào)集合 VN。3找出句型 T+T*F+i 的所有短語、簡(jiǎn)單短語和句柄。解：該文法的開始符號(hào)(識(shí)別符號(hào))是E。2該文法的終結(jié)符號(hào)集合VT=+、-、*、/、(、)、 i。非終結(jié)符號(hào)集合 VN=E、 T、F。3句型 T+T*F+I 的短語為 i、T*F、第一個(gè) T、T+T*F+i;簡(jiǎn)單短語為 i、T*F、第一個(gè) T;句柄為第一個(gè) To2-21.已知文法 GS為：4 dABATaA|aBb| &1GS產(chǎn)生的語言是什么2GS能否改寫為等價(jià)的正規(guī)文法解： GS產(chǎn)生的

26、語言是 L(GS)=defbmIn1,m0。GS能改寫為等價(jià)的正規(guī)文法，其改寫后的等價(jià)的正規(guī)文法 GSX為：S J dAAtaA|aB|aBtbB|b2- 22.設(shè)有語言 L(G)=ada | a (a,b)*,aR為 a 之逆，試構(gòu)造產(chǎn)生此語言的上下文無關(guān)文法G。解:根據(jù)題義，可知 aR為 a 之逆的含義就是句子中的符號(hào)a、b 以 d 為中心呈左右對(duì)稱出現(xiàn)；由于 a (a,b)*,所以 a、b 的個(gè)數(shù)可以為零。所以可構(gòu)造產(chǎn)生此語言的上下文無關(guān)文法GS為：STaSa|bSb|d3- 03 .簡(jiǎn)述 DFA 與 NFA 有何區(qū)別答：DFA 與 NFA 的區(qū)別表現(xiàn)為兩個(gè)方面：一是 NFA 可以若干個(gè)

27、開始狀態(tài)，而DFA 僅只一個(gè)開始狀態(tài)。另一方面，DFA 的映象 M 是從 KXE到 K,而 NFA 的映象 M 是從 KXE到 K 的子集，即映象 M 將產(chǎn)生一個(gè) 狀態(tài)集合(可能為空集)，而不是單個(gè)狀態(tài)。3-04.試給出非確定自動(dòng)機(jī)的定義。答：一個(gè)非確定的有窮自動(dòng)機(jī)(NFA) M 是一個(gè)五元組：M= ( K,S,f, S , Z)。其中：1. K 是一個(gè)有窮集，它的每個(gè)元素稱為一個(gè)狀態(tài)；2. 工是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入符號(hào)，所以也稱工為輸入符號(hào)表；3. f 是狀態(tài)轉(zhuǎn)換函數(shù)，是在 KXS*TK 的子集的映射，即，f: KX S*T2K ;表明在某狀態(tài)下對(duì)于某輸入符號(hào)可能有多個(gè)后

28、繼狀態(tài)；4. S( K 是一個(gè)非空初態(tài)集；5. Z( K 是一個(gè)終態(tài)集(可空)。3-05.為正規(guī)式(a|b )*a(a|b)構(gòu)造一個(gè)等價(jià)的確定的有限自動(dòng)機(jī)。解答：確定化，得到DFA+一d+一d3-06.給定下列自動(dòng)機(jī)，將其轉(zhuǎn)換為確定的自動(dòng)機(jī)。注：帶+號(hào)的結(jié)點(diǎn)為初始狀態(tài)；帶一號(hào)的結(jié)點(diǎn)為終止?fàn)顟B(tài)解答：(1)消除&邊，得到注：帶+號(hào)的結(jié)點(diǎn)為初始狀態(tài)；帶一號(hào)的結(jié)點(diǎn)為終止?fàn)顟B(tài)+dCAdEdB +SHNFA:ddddEd+d+ADdSAABCEG+SAAABCEGABCEABCEGBBBCEBCEDGCCDGHDDDGDHEEGHHGHDHDHHH(1)把此自動(dòng)機(jī)轉(zhuǎn)換為確定自動(dòng)機(jī)(2)給出此 DF

29、A 的正則表達(dá)式。DFA。解答：(1):有狀態(tài)矩陣如圖：abab00,1 200121201012-212-21212從而可得 DFA 如圖：a其中：開始狀態(tài)：o終止?fàn)顟B(tài)：2注： 帶+號(hào)的結(jié)點(diǎn)為初始狀態(tài)；帶一號(hào)的結(jié)點(diǎn)為終止?fàn)顟B(tài)3-07.給定下列自動(dòng)機(jī):b1aa02b(2)此 DFA 的正則表達(dá)式為：(aa*bb)(bab)*或ab (bab)*。4-13.消除下列文法 GE 的左遞歸。E-TITT/FIFi ( E)1i解答：消除文法 GE的左遞歸后得到：ETTEET-TEITtFTT/FT FT( E)1i4-14.在 LL分析法中,LL 分別代表什么含義答:第一個(gè) L 代表從左到右的掃描，

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

31、B不能同時(shí)So4-18.什么是文法的左遞歸 答：一個(gè)文法含有下列形式的產(chǎn)生式之一時(shí)：1) ATA3,A VN,共 V*2) ATB3BTAa,A、BVN, a、3V*則稱該文法是左遞歸的。4- 19.遞歸下降法的主要思想是什么答：對(duì)每個(gè)非終結(jié)符按其產(chǎn)生式結(jié)構(gòu)寫出相應(yīng)語法分析子程序。因?yàn)槲姆ㄟf歸相應(yīng)子程序也遞歸，子程序 的結(jié)構(gòu)與產(chǎn)生式結(jié)構(gòu)幾乎一致。所以稱此種方法稱為遞歸子程序法或遞歸下降法。5- 19.自底向上分析法的原理是什么答：在采用自左向右掃描，自底向上分析的前提下，該類分析方法是從輸入符號(hào)串入手，通過反復(fù)查找當(dāng) 前句型的句柄(最左簡(jiǎn)單短語) ，并使用文法的產(chǎn)生式把句柄歸約成相應(yīng)的非終極符

32、來一步步地進(jìn)行 分析的。最終把輸入串歸約成文法的開始符號(hào)，表明分析成功。5-23. 給定文法 GZ：1ZtC S2Ctif E then其中：Z、C S、A、E VN；34 A=E4ETEVAif、then、=、V、 i VT5EtA6Atia)構(gòu)造此文法的 LR(O 項(xiàng)目集規(guī)范族，并給出識(shí)別活前綴的DFA。b)構(gòu)造其 SLR( 1 )分析表。2.Follow(Z)=#Follow(C)=iFollow(S)=#Follow(E)=#,V,thenFollow(A)=,# ,V,then 則可構(gòu)造 SLR( 1)分析表為:ACTIONGOTO0ifthe n=Vi#ZCSEA0S3121OK2

33、S6453S6784r15S96r6r6r6r67S10S118r5r5r59S312810r2G 中加入產(chǎn)生式 0.ZTZ,然后得到新的文法G,再求 G的識(shí)別全部活前綴的DFAIo:ZT.ZI7:CTifE.thenZTC SET E.VACT.if E then|9：STA=.E11:ZTZ.ET.EVAI2：ZTC.SETA4 .A=EAT.iAT.iI10:CTif E then|3：CTif .E thenI11:ETEV.AET.EVAAT.iET.AI12:4 A=E.AT.iETE.VAI4：ZTC SI13:ETEVA.I5:STA.=E|6：ATi.解答：1首先拓廣文法：在14SA|2|12Vii|6iAI11iVEI3I7thenAI101811S61312S113134445-24.設(shè)有文法 GS:STaA ATAb求識(shí)別該文法所有活前綴的DFA。解答：(1).首先拓廣文法：在 G 中加入產(chǎn)生式TS,然后得到新的文法 GTSTaATAbTb.再求 G的識(shí)別全部活前綴的DFA:6-07.語法制導(dǎo)翻譯方法的基本思想是什么答：在語法分析過程中，每當(dāng)使用一條產(chǎn)生式進(jìn)行推導(dǎo)或歸約時(shí)，就執(zhí)行該產(chǎn)生式所對(duì)應(yīng)的語義動(dòng)作進(jìn)行屬性計(jì)算，完成對(duì)輸入符號(hào)串的翻譯。6-08.何謂“語法制導(dǎo)翻譯”答：在語法分析過程中，隨著分析的步步進(jìn)展