編譯原理習(xí)題答案.

1、1、正規(guī)文法又稱 D A、0型文法 B、1型文法 C、2型文法 D、3型文法2、對于無二義性的文法，規(guī)范歸約是 B A. 最左推導(dǎo) B. 最右推導(dǎo)的逆過程 C.最左歸約的逆過程 D.最右歸約的逆過程。3、掃描器的任務(wù)是從 源程序 中識別出一個(gè)個(gè) 單詞符號 。4、程序所需的數(shù)據(jù)空間在程序運(yùn)行前就可確定，稱為 A 管理技術(shù)。A 靜態(tài)存儲 B 動態(tài)存儲 C 棧式存儲 D 堆式存儲5、編譯過程中，語法分析器的任務(wù)是（ B）。分析單詞是怎樣構(gòu)成的分析單詞串是如何構(gòu)成語句和說明的分析語句和說明是如何構(gòu)成程序的分析程序的結(jié)構(gòu)A、 B、 C、 D、6、文法G：EE+T|T TT*P|P P (E)| i則句型

2、P+T+i的句柄和最左素短語分別為 B 。 A、P+T和i B、P和P+T C、i和P+T+i D、P和P 7、四元式之間的聯(lián)系是通過 B 實(shí)現(xiàn)的A.指示器 B.臨時(shí)變量 C.符號表 D.程序變量8、程序語言的單詞符號一般可以分為保留字、標(biāo)識符、常數(shù)、運(yùn)算符、界符 等等。9、下列 B 優(yōu)化方法是針對循環(huán)優(yōu)化進(jìn)行的。A刪除多余運(yùn)算 B刪除歸納變量 C合并已知量 D復(fù)寫傳播10、若文法 G 定義的語言是無限集，則文法必然是 A A、遞歸的 B、前后文無關(guān)的 C、二義性的 D、無二義性的11、文法 G 產(chǎn)生的 D 的全體是該文法描述的語言。A、句型 B、終結(jié)符集 C、非終結(jié)符集 D、句子12、Cho

3、msky 定義的四種形式語言文法中， 0 型文法又稱為 A 文法； 1 型文法又稱為 C 文法。A.短語文法 B.上下文無關(guān)文法 C.上下文有關(guān)文法 D.正規(guī)文法 A.短語文法 B.上下文無關(guān)文法 C.上下文有關(guān)文法 D.正規(guī)文法 13、語法分析最常用的兩類方法是 自頂向下 和 自底向上 分析法。14、一個(gè)確定的有窮自動機(jī)DFA是一個(gè) A 。A 五元組（K，f, S, Z） B 四元組（VN，VT，P，S）C 四元組（K，f，S） D 三元組(VN,VT,P)A、語法 B、語義C、代碼D、運(yùn)行15、 B 不屬于喬姆斯基觀點(diǎn)分類的文法。A、上下文無關(guān)文法 B、算符優(yōu)先文法 C、上下文有關(guān)文法 D

4、、正規(guī)文法16、一個(gè)文法所描述的語言是 A ；描述一個(gè)語言的文法是 B 。A.唯一的 B.不唯一的 C.可能唯一,可能不唯一 A.唯一的 B.不唯一的 C.可能唯一,可能不唯一 17、語法分析是依據(jù)語言的 語法 規(guī)則進(jìn)行的，中間代碼產(chǎn)生是依據(jù)語言的 等價(jià)變換 規(guī)則進(jìn)行的。 18、 B 不屬于喬姆斯基觀點(diǎn)分類的文法。A上下文無關(guān)文法 B算符優(yōu)先文法 C上下文有關(guān)文法 D正規(guī)文法19、過程調(diào)用時(shí)參數(shù)傳遞方式有 A (1)傳地址 (2)傳值 (3)傳標(biāo)識符 (4)得結(jié)果 (5)傳名 (6) 返回值 可選項(xiàng)有：A、(1)(2)(4)(5) B、(1)(2)(5)(6) C、(1)(2)(3) (6)

5、D、(2)(3)(4)(6)20、過程調(diào)用時(shí)參數(shù)傳遞方式有 (1)傳地址 (2)傳值 (3)傳標(biāo)識符 (4)得結(jié)果 (5)傳名 (6) 返回值 可選項(xiàng)有：A、(1)(2)(4)(5) B、(1)(2)(5)(6) C、(1)(2)(3) (6) D、(2)(3)(4)(6)21、下列代碼中 D 不可能是目標(biāo)代碼。 A、匯編指令代碼 B、可重定位指令代碼 C、絕對指令代碼 D、中間代碼22、一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài)，其中有一個(gè)被認(rèn)為是初態(tài)，最多只有一個(gè)終態(tài)。 B 。A.正確 B.不正確23、有限自動機(jī)能識別 C A上下文無關(guān)文法 B上下文有關(guān)文法C正規(guī)文法 D短語文法。 24、匯編程序是將 B

6、 程序改造成目標(biāo)語言程序的翻譯程序。A機(jī)器語言 B匯編語言 C高級語言 D低級語言25、LR(k)文法_B_二義性的。A、都是B、都不是C、不一定都是26、喬姆斯基方法的2型語言是這樣一種語言，其產(chǎn)生式限制為 A A、Aa B、Aa，AaB C、a (| a | | b |) D、a b27、局部優(yōu)化是局限于一個(gè) C 范圍內(nèi)的一種優(yōu)化。A.循環(huán) B.函數(shù) C.基本塊 D.整個(gè)程序28、目標(biāo)代碼生成時(shí)，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問題。 A 。A.正確 B.不正確29、喬姆斯基方法的3型語言是這樣一種語言，其產(chǎn)生式限制為 B A Aa B Aa或AaB C a(| a | | b |) D

7、 a b30、運(yùn)算符與運(yùn)算對象類型不符屬于 A 。A、語法錯(cuò)誤 B、語義錯(cuò)誤 C、語用錯(cuò)誤 D、規(guī)則集合31、詞法分析器的輸入是 B 。A、詞法記號 B、源程序 C、語法單位 D、目標(biāo)程序32、在下述的編譯方法中，自底向上的方法有 F ，自頂向下的分析方法有 A 。簡單優(yōu)先分析 算符優(yōu)先分析 遞歸下降分析 預(yù)測分析技術(shù) LR（K）分析 SLR（k）分析 LL（k）分析 LALR（K）分析 A. B. C. D. E. F. A. B. C. D. E. F. 33、對于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN采用動態(tài)貯存分配策略。 B 。 A.正確 B.不正確34、算符優(yōu)先分析法每次都是對 C 進(jìn)行

8、歸約。A 句柄 B短語 C最左素短語 D素短語35、編譯時(shí)能進(jìn)行的類型檢查稱為 C 。A、錯(cuò)誤檢查 B、動態(tài)檢查C、靜態(tài)檢查 D、隨機(jī)檢查36、規(guī)范推導(dǎo)的每一步總是用產(chǎn)生式右邊符號串替換句型中 B 位置的非終結(jié)符號A、最左 B、最右 C、最中 D、任意37、語法分析器的輸入是 單詞符號流 ，其輸出是 分析樹的某種表示 38、每個(gè)文法都能改寫為LL(1)文法。 B A.正確 B.不正確39、對于無二義性的文法，規(guī)范推導(dǎo)是 C A 最左推導(dǎo) B 最右推導(dǎo)的逆過程 C 最左歸約的逆過程 D 最右歸約的逆過程。40、描述語言 L= ambn | nm1 的文法為 D 。A、ZAbb AaA | a B

9、bB | bB、ZAB | b AAa | aBaBb | bC、ZAb AaAb | aD、ZaAbAAb | aAb | 41、間接三元式表示法的優(yōu)點(diǎn)為 A A、采用間接碼表，便于優(yōu)化處理 B、節(jié)省存儲空間，不便于表的修改C、便于優(yōu)化處理，節(jié)省存儲空間 D、節(jié)省存儲空間，不便于優(yōu)化處理42、編譯時(shí)能進(jìn)行的類型檢查稱為 C A錯(cuò)誤檢查 B動態(tài)檢查 C靜態(tài)檢查 D隨機(jī)檢查43、文法 GS：S xSx | y所識別的語言是 A 。 A、xnyxn(n0) B、(xyx)* C、xyx D、x*yx*44、項(xiàng)目A稱為 B ，其中AVN，A不是開始符。A、移進(jìn)項(xiàng)目 B、歸約項(xiàng)目 C、出錯(cuò)項(xiàng)目 D、接

10、受項(xiàng)目45、設(shè)有文法GS: S- S*S | S+S | (S) | a, 該文法_A_二義性文法。A、 是 B、不是 C、不一定46、高級語言編譯程序常用的語法分析方法中，LL分析法屬于 B 分析方法。A、自左至右 B、自頂向下 C、自底向上 D、自右至左。47、有文法G：EE*T|TTTi|i句子25*33按該文法G歸約，其值為 B A 23 B42 C 30 D 1748、高級語言編譯程序常用的語法分析方法中，LL分析法屬于 B 分析方法。A 自左至右 B 自頂向下 C 自底向上 D自右至左。49、形如AB的項(xiàng)目為 A 項(xiàng)目。 A、待約 B、移進(jìn) C、接受 D、規(guī)約50、活動記錄的連接數(shù)

11、據(jù)不包括 A 。A、形參單元 B、動態(tài)鏈（老SP） C、返回地址 D、全局Display地址51、高級語言編譯程序常用的語法分析方法中，lALR分析法屬于 C 分析方法。A、 自左至右 B、 自上而下 C、 自下而上 D、自右至左52、設(shè)a、b、c是文法的終結(jié)符，且滿足優(yōu)先關(guān)系a=b和b=c，則 D 。A.必有a=c B.必有c=a C 必有b=a D 答案AC都不一定成立53、詞法分析器的輸出是 A 。A、詞法記號流 B、源程序 C、語法單位 D、目標(biāo)程序54、對一個(gè)基本塊來說， A 是正確的。 A、只有一個(gè)入口語句和一個(gè)出口語句 B、有一個(gè)入口語句和多個(gè)出口語句C、有多個(gè)入口語句和一個(gè)出口

12、語句 D、有多個(gè)入口語句和多個(gè)出口語句55、詞法分析所依據(jù)的是 B 。A 語義規(guī)則 B 構(gòu)詞規(guī)則 C 語法規(guī)則 D 等價(jià)變換規(guī)則56、句型是由 D 推導(dǎo)出的符號串。A、非終結(jié)符 B、終結(jié)符 C、任何符號 D、開始符號57、如果文法G是無二義的，則它的任何句子 A 。 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)的語法樹相同58、算符優(yōu)先文法與算符優(yōu)先函數(shù)的關(guān)系的描述中正確的是（B）。A、一個(gè)算符優(yōu)先文法一定存在優(yōu)先函數(shù)與之對應(yīng)B、一個(gè)算符優(yōu)先文法可能存在多個(gè)優(yōu)先函數(shù)與之對應(yīng)C、

13、一個(gè)算符優(yōu)先文法一定存在多個(gè)優(yōu)先函數(shù)與之對應(yīng)D、一個(gè)算符優(yōu)先文法一定存在有限對優(yōu)先函數(shù)與之對應(yīng)59、一個(gè)句型中稱為句柄的是該句型的最左 D 。 A 非終結(jié)符 B 短語 C 句子 D 直接短語60、描述一個(gè)語言的文法是（B ）A、唯一的 B、不唯一的 C、可能唯一，也可能不唯一61、下列 C 優(yōu)化方法不是針對循環(huán)優(yōu)化進(jìn)行的。 A、強(qiáng)度削弱 B、刪除歸納變量 C、刪除多余運(yùn)算 D、代碼外提62、更動一張 A 表很困難。 A 三元式 B 間接三元式 C 四元式 D 三元式和四元式63、棧式存儲分配申請和釋放存儲空間遵守 BC 原則。A、先申請先釋放 B、先申請后釋放 C、后申請先釋放 D、任意64、

14、所謂自上而下分析法是指 。65、所謂語法制導(dǎo)翻譯方法是 。66、確定的有窮自動機(jī)是一個(gè) 五元組 ，通常表示為 M=(S , ,f,s0,Z ) 。67、規(guī)范歸約中的可歸約串是指 句柄 ；算符優(yōu)先分析中的可歸約串是指最左素短語 。68、編譯程序在邏輯上由 詞法分析 、 語法分析 、語義分析、中間代碼生成、代碼優(yōu)化和目標(biāo)代碼生成六部分組成。69、 D 不可能是目標(biāo)程序。 A、匯編語言模塊 B、可重定位目標(biāo)模塊 C、可執(zhí)行目標(biāo)模塊 D、中間代碼70、如果一個(gè)文法存在某個(gè)句子對應(yīng)兩棵不同的語法樹，則稱這個(gè)文法是 二義的 。71、一個(gè)名字的屬性包括 繼承屬性 和 綜合屬性 。72、正規(guī)式的“*”讀作 星

15、閉包 。73、編譯程序在邏輯上由 、 、語義分析、中間代碼生成、代碼優(yōu)化和目標(biāo)代碼生成六部分組成。74、編譯程序的各個(gè)階段的工作都涉及到 符號表管理 和 錯(cuò)誤處理 75、文法用來描述語言的語法結(jié)構(gòu)，它由如下4個(gè)部分組成：文法終結(jié)符集合、文法非終結(jié)符集合、 D 和文法開始符號。A、單詞集合 B、字母數(shù)字串C、文法句子集合 D、文法產(chǎn)生式的集合 76、確定的有窮自動機(jī)是一個(gè) 元組，通常表示為 。 77、已知文法GE： EE + T | T TT * F | F F（E）| id 該文法終結(jié)符集合VT= ， 文法非終結(jié)符集合VN= ，該文法在喬姆斯基（Chomsky）文法分類屬于 2 文法。78、編

16、譯程序的各個(gè)階段的工作都涉及到 和 。79、假設(shè)G是一個(gè)文法，S是文法開始符號，如果S*x，則稱x是該文法的一 。80、如果一個(gè)文法存在某個(gè)句子對應(yīng)兩棵不同的語法樹，則稱這個(gè)文法是 。81、優(yōu)化時(shí)，節(jié)省一條指令MOV Ri，M，節(jié)省的指令代價(jià)為 C A、0 B、1 C、2 D、382、采用 LL(1) 語法分析時(shí)，必須消除文法的左遞歸。83、在狀態(tài)轉(zhuǎn)換圖中，結(jié)點(diǎn)代表 狀態(tài) ，用圓圈表示。84、若源程序是高級語言編寫的，目標(biāo)程序是 機(jī)器語言或匯編 語言的程序，則相應(yīng)的翻譯程序稱為編譯程序。85、常用的兩種動態(tài)存貯分配辦法是 棧式 分配和 堆式 分配。86、翻譯方案和語法制導(dǎo)定義不同的是它的 語義

17、動作 （而不叫語義規(guī)則）放在括號 內(nèi)，并且可以插在產(chǎn)生式 右部 的任何地方87、如果一個(gè)文法存在某個(gè)句子對應(yīng)兩棵不同的語法樹，則稱這個(gè)文法是 。88、所謂最左推導(dǎo)是指： 。89、上下文無關(guān)文法的可以用 四元組 表示，其形式為 G=(VN,VT,S,P) 。90、后綴式 ab+c+d*e- 所表達(dá)的式子為 （a+b+c）*d-e 。91、常用的兩種動態(tài)存貯分配辦法是 分配和 分配。92、LL(K)文法中，第一個(gè)L表示 從左到右掃描輸入串 ，第二個(gè)L表示 產(chǎn)生最左推導(dǎo) ，K表示 在決定語法分析器每步動作時(shí)向前看K個(gè)輸入符 。93、一個(gè)上下文無關(guān)文法所含四個(gè)組成部分是 文法終結(jié)符集合 文法非終結(jié)符集

18、合 開始符號 產(chǎn)生式有限集合 。94、對于文法G，僅含終結(jié)符號的句型稱為 句子 。95、設(shè)有文法GE： EE + T | E T | T TT * F | T/F | F F（E）| i 該文法句型E + T * F 的句柄是 T * F 。96、后綴式 ab+c+d*e- 所表達(dá)的式子為 。97、文法符號的屬性有兩種，一種稱為 繼承 屬性，另一種稱為 綜合 屬性，S屬性定義是指僅使用 綜合 屬性的語法制導(dǎo)定義。98、LR(0)項(xiàng)目和LR(1)項(xiàng)目的區(qū)別在于 是否有搜索符 。99、緊跟在條件轉(zhuǎn)移語句后面的語句是基本塊的 入口 語句。100、若二個(gè)正規(guī)式所表示的 DFA（或正規(guī)集） 相同，則認(rèn)為

19、二者是等價(jià)的。101、僅含終結(jié)符的句型稱為 。102、編譯方式與解析程序的根本區(qū)別在于是否生成目標(biāo)代碼。 ( F )103、規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩個(gè)過程。 ( T )104、一個(gè)上下文無關(guān)文法的開始符號可以是終結(jié)符或非終結(jié)符。 ( F )105、逆波蘭表示法表示表達(dá)式時(shí)無需使用括號。 ( T ) 106、符號表由詞法分析程序建立，由語法分析程序使用。 ( F ) 107、逆波蘭法表示的表達(dá)式亦稱前綴式。 ( F ) 108、代碼生成器的輸入包括中間代碼和符號表中的信息。 ( T )109、孤立地考慮一個(gè)基本塊常常不能確定一個(gè)賦值是否真是無用的。 ( T )110、目標(biāo)代碼生成時(shí)，應(yīng)考慮如

20、何充分利用計(jì)算機(jī)的寄存器的問題。 ( T )111、無左遞歸的文法是LL(1)文法。 ( F )112、一個(gè)句型的直接短語語是唯一的。 ( F )113、正規(guī)文法產(chǎn)生的語言都可以用上下文無關(guān)文法來描述。 (F )114、對任何一個(gè)編譯程序來說，產(chǎn)生中間代碼是不可缺少的一部分。 ( F )115、一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài)，其中有一個(gè)被認(rèn)為是初態(tài)，最多只有一個(gè)終態(tài)。( F )116、一個(gè)上下文無關(guān)文法的開始符號可以是終結(jié)符或非終結(jié)符。 ( F )117、一個(gè)文法所有句子的集合構(gòu)成該文法定義的語言。 ( T )118、優(yōu)化實(shí)質(zhì)上是對代碼進(jìn)行等價(jià)變換，變換后的代碼結(jié)構(gòu)不同但運(yùn)行結(jié)果相同。 ( T )

21、119、算符優(yōu)先分析法是一種規(guī)范歸約分析法。 ( F )120、非終結(jié)符可以有綜合屬性，但不能有繼承屬性。 ( F )121、所有LR分析器的總控程序都是一樣的，只是分析表各有不同。 ( T )122、因名字都是用標(biāo)識符表示的，故名字與標(biāo)識符沒有區(qū)別 (F )123、空符號串的集合=。 ( F )124、非終結(jié)符可以有綜合屬性，但不能有繼承屬性。 ( F )125、終結(jié)符可以有綜合屬性，也可以有繼承屬性。 ( F )126、一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài)，其中有一個(gè)被認(rèn)為是初態(tài)，最多只有一個(gè)終態(tài)。( )127、若一個(gè)句型中出現(xiàn)了某一產(chǎn)生式的右部，則此右部一定是該句型的句柄。 ( F )129、DA

22、G是一個(gè)可帶環(huán)路的有向圖。 ( F )130、設(shè)有符號串x和y，把y的符號寫在x的符號之后所得的符號串，叫做x與y的連接，記為xy。 ( T )131、對任何一個(gè)編譯程序來說，產(chǎn)生中間代碼是不可缺少的一部分。 ( F )132、對任何正規(guī)表達(dá)式e，都存在一個(gè)DFAM，滿足L(M)L(e)。 ( T)133、 運(yùn)行時(shí)的DISPLAY表的內(nèi)容是什么？它的作用是什么？答：內(nèi)容：1、過程R的現(xiàn)行活動記錄的地址（sp的現(xiàn)值）2、R的外層Q的最新活動記錄的地址3、Q的外層即主程序P的活動記錄的地址作用：跟蹤每個(gè)外層的最新活動記錄的位置134、何謂局部優(yōu)化、循環(huán)優(yōu)化和全局優(yōu)化？優(yōu)化工作在編譯的哪個(gè)階段進(jìn)行？

23、答：局部優(yōu)化：在基本快內(nèi)的優(yōu)化。循環(huán)優(yōu)化：對循環(huán)中的代碼進(jìn)行優(yōu)化。全局優(yōu)化：整個(gè)程序范圍內(nèi)的優(yōu)化。 在 中間代碼優(yōu)化階段。135、常見的存儲分配策略有幾種？它們都適合于什么性質(zhì)的語言？答：1、靜態(tài)分配策略 適用于無動態(tài)申請內(nèi)存、無可變體積數(shù)組、無遞歸調(diào)用的程序語言（ 如 Fortran）2、動態(tài)分配策略2.1棧式動態(tài)分配 2.1.1簡單棧式分配 適用于沒有分程序結(jié)構(gòu)、不允許程序嵌套定義但允許過程遞歸調(diào)用、允許過程含可變數(shù)組的語言 2.1.2嵌套過程語言的棧式分配 適用于沒有分程序結(jié)構(gòu)、允許程序嵌套定義和過程遞歸調(diào)用、允許過程含可變數(shù)組的語言2.2堆式動態(tài)分配 適用于允許程序?yàn)樽兞吭谶\(yùn)行時(shí)動態(tài)申

24、請和釋放存儲空間的語言136、下面文法是否是二義文法？試說明理由。 GS： S SaS | e 答：二義137、已知文法G(E) ET|ET TF|T * F F(E)|i (1) 給出句型(T * Fi)的最右推導(dǎo)及畫出語法樹； (2) 給出句型(T * Fi)的短語、素短語。1）EETE+iT+iT*F+I 樹略2）短語：T*F+i T*F i素短語：T*F i138、把算術(shù)表達(dá)式(a+b)*(b+c)翻譯成： (a) 后綴表示 ab+bc+*(b) 語法樹 圖略(c) 有向無環(huán)圖 圖略(d) 四元式三地址代碼四地址代碼：（+, a ，b，t1）（+，b，c，t2）（*，t1，t2，t3）

25、（，t3，-，t4）139、DFA與NFA的區(qū)別？答：1、DFA弧上不允許有出現(xiàn)，NFA允許2、DFA中每個(gè)狀態(tài)S和輸入符號a最多有一條邊離開S，NFA有多條3、NFA可以有多個(gè)初態(tài)，DFA只有一個(gè)140、設(shè)已構(gòu)造出文法G(S)：SS(S)Se的LR分析表如下狀態(tài)ACTIONGOTO()#S0r2r211S2Acc2r2r233S4S54r2r265r1r16S4S77r1r1假定輸入串為( )( )，請給出LR分析過程(即狀態(tài)，符號，輸入串的變化過程)。步驟 狀態(tài) 符號 輸入串步驟狀態(tài)符號輸入串10（）（）$201S（）（）$3012S(）（）$40123S()（）$501235S()（）$

26、601S（）$7012S(）$80123S(S）$901235S(S)$1001S$141、對符號表的基本操作有幾種，分別是什么？ 答：5類。1、填寫名稱2、查找名字3、訪問信息4、填寫修改信息5、刪除（或者：4類。建立、插入、查找、刪除）142、給定代碼段如下，求出按四種不同方式進(jìn)行參數(shù)傳遞后，變量a的值procedure P(w,x,y,z);begin y := y*w; z := z+x;endbegin a := 5; b := 3; P(a+b,a-b,a,a); write(a);end傳值:5傳地址: 42得結(jié)果: 7傳名: 77143、目標(biāo)代碼有哪幾種形式？生成目標(biāo)代碼時(shí)通常

27、應(yīng)考慮哪幾個(gè)問題？答：1、匯編語言2、機(jī)器語言 又可分為a可立即執(zhí)行的機(jī)器語言b可重定位的機(jī)器語言需要考慮：1.、如何使生成的目標(biāo)代碼最短2、如何分配寄存器的使用144、下面的推導(dǎo)S rm rm g A b w rm g l b b w中，最后一步用的是A lb，分別指出LL（1）方法和LR（1）方法在掃描到此句型的什么位置決定用此產(chǎn)生式？(5分) P79答： LL(1)掃描到l的時(shí)候決定用此產(chǎn)生式；LR(1)掃描到b的時(shí)候決定使用次產(chǎn)生式145、構(gòu)造一個(gè)最簡DFA，它接受正規(guī)式ab (a|b)*。給出文法GS：SSaA|A AAbB|B BcSd|e (1)證實(shí)AacAbcBaAdbed是文

28、法GS的一個(gè)句型；(2)請寫出該句型的所有短語、素短語以及句柄。 答：1）這里用最右推導(dǎo)表示，省略樹SSaASaBSacSdSacAdSacAbBdSacAbedSacAbBbedSacAbcSdbedSacAbcSaAdbedSacAbcAaAdbedSacAbcBaAdbed AacAbcBaAdbed2）短語：AacAbcBaAdbed cAbcBaAdbed AbcBaAdbe AbcBaAd cBaAd BaA e A 素短語：BaA e 句柄：A146、寫出表達(dá)式a+b*(c-d)對應(yīng)的逆波蘭表示、三元式三地址代碼序列和抽象語法樹。147、什么是活動記錄？它主要由哪些內(nèi)容構(gòu)成？14

29、8、對下列四元式序列生成目標(biāo)代碼 (10分) T=A-B S=C+D W=E-F U=W/T V=U*S其中，V是基本塊出口的活躍變量，R0和R1是可用寄存器。答 MOV R0 ，A SUB R0 ，B MOV R1 ，A ADD R1 ，D MOV S ，R1 MOv R1 ，ESUB R1 ，F(xiàn)DIV R1 ，R0MUL R1 ，S149、設(shè)有如下的三地址碼(四元式)序列：Read N I=N J=2 L1：if IJ goto L3 L2：I=I-J if IJ goto L2 if I=0 goto L4 J=J+1 I=N goto L1 L3：Print YES Return L4

30、：Print NO Return （1）、對題中代碼劃分基本塊，并給每個(gè)基本塊一個(gè)序號（2）、畫出基本塊集合的控制流圖，每個(gè)基本塊就用（1）小題中的序號表示。（3）、若有循環(huán)的話，列出構(gòu)成每個(gè)循環(huán)的結(jié)點(diǎn)。 150、已知文法G(V)： V N | N EE V | V+E Ni(1)給出與G(V)等價(jià)的LL(1)文法G(V)；V NV V E| E VE E +E| Ni(2)求文法G(V)的每個(gè)非終結(jié)符的FIRST集合和FOLLOW集合；First(V)=i First(V)= , First(E)=i First(E)= + , First(N)=iFollow(V)=$,+, Follow

31、(V)=$,+, Follow(E)= Follow(E)= Follow(N)= , $ , + (3)構(gòu)造文法G(V)的LL(1)分析表。+i$VV NVVV V EV V EE VEEE +EE NNi151、考慮下面的三地址語句序列：b := 1b := 2if w = x goto L2e := bgoto L2L1:goto L3L2:c := 3b := 4c := 6L3:if y 則First()Follow(A)=空集154、寫出語句a:=b*(-c)+b*(-c)的后綴式、抽象語法樹、DAG圖、四元式三地址代碼和三元式三地址代碼。155、設(shè)有文法GA： A iB*e B

32、SB | S eC | . i C eC | 判定該文法是否為LL(1)文法？若是則給出它的LL(1)分析表，否則說明理由。 (20分)First(A)=i First(B)= , , . First(S)= , . First(C)=e, Follow(A)=$ Follow(B)=* Follow(S)=* Follow(C)=對產(chǎn)生式B SB | First(SB)=First(S)= , . First()= 所以First(SB)First()=空集First(SB)Follow(B)=空集對產(chǎn)生式S eC | . iFirst(eC)= First(. i)= . i 所以Firs

33、t(eC)First(. i)=空集對產(chǎn)生式C eC | First(eC) e First()= 所以First(eC)First()=空集First(eC)Follow(C)=空集所以此文法是LL(1)文法.*ie$AA iB*eBB SBB B SBSS . iS eCCC | C eC156、構(gòu)造一個(gè)DFA，它接受=0，1上能被5整除的二進(jìn)制數(shù)。157、正規(guī)式 (0 | 1)* 和 ( (e | 0) 1* )*是否等價(jià)，說明理由。 158、寫出字母表S = a, b上語言L = w | w的最后兩個(gè)字母是aa或bb的正規(guī)式，并畫出接受該語言的最簡DFA。(a|b)*aa|bb159、

34、文法G(S)及其LR分析表如下，請給出串baba$的分析過程。(1) S DbB(2) D d(3) D (4) B a(5) B Bba(6) B LR分析表ACTIONGOTObda$SBD0r3s3121acc2s43r24r6S5r665r4r46s7r17S88r5r5(注：答案格式為 步驟 棧 輸入串 動作) 步驟棧輸入串動作)10baba$按B 規(guī)約20D2baba$移進(jìn)30D2b4aba$移進(jìn)40D2b4a5ba$按B a規(guī)約50D2b4B6ba$移進(jìn)60D2b4B6b7a$移進(jìn)70D2b4B6b7a8$按B Bba規(guī)約80D2b4B6$按S DbB規(guī)約90S1$接受160、已

35、知文法G(A)： A aABl | aB Bb | d(1)消除文法中的左遞歸，提取公共左因子，給出與G(A)等價(jià)的LL(1)文法G(A)；(2)求文法G(A)的每個(gè)非終結(jié)符的FIRST集合和FOLLOW集合；(3)構(gòu)造文法G(A)的LL(1)分析表。答：1）A aA AABl| B dB B bB |2) First(A)=a First(B)=d First(A)=a, First(B)=b, Follow(A)=$,d Follow(B)=l Follow(A)=$,d Follow(B)=l3) abld$AA aAAAABlAABB bBBB 161、設(shè)文法G(S)： SS+aF | aF | +aF F*aF | *a(1) 消除左遞歸和回溯；(2) 計(jì)算每個(gè)非終結(jié)符的FIRST和FOLLOW； (3) 構(gòu)造預(yù)測分析表。答1、S+aFS | aFS S+aFS |F*aFF F|2、Fist(S)=a,+ Fist(S)=+, Fist(F)=* Fist(F)=*, Follow(S)=$ Follow(S)=$ Follow(F)=$,+ Follow(F)=$,+3、+a*$SS+aFSSaFSSS+aFSSFF*aFFF F FF 162、構(gòu)造下面文