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

1、1、正規(guī)文法又稱 DA、0 型文法 B、1 型文法 C、2 型文法 D、3 型文法2、對于無二義性的文法，規(guī)范歸約是 BA.最左推導(dǎo) B.最右推導(dǎo)的逆過程 C 最左歸約的逆過程 D.最右歸約的逆過程。3、掃描器的任務(wù)是從源程序中識別出一個個單詞符號。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、日CD、6、文法 G:E-E+T|TT-T*P|PP 一(E)|i則句型 P+T+i 的句

2、柄和最左素短語分別為 B。A、P+T 和 iB、P 和 P+TC、i 和 P+T+iD、P 和 P7、四元式之間的聯(lián)系是通過 B 實(shí)現(xiàn)的A.指示器 B.臨時變量 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 定義的語言是無限集，則文法必然是 AA、遞歸的日前后文無關(guān)的 C、二義性白 DD、無二義性的11、文法 G 產(chǎn)牛的 D 的全體是該文法描述的語言。A、句型 B、終結(jié)符集 C 非終結(jié)符集 D、句子12、Chomsky 定義

3、的四種形式語言文法中，0 型文法又稱為 A 文法:1 型文法又稱為 C 文法。A.短語文法 B.上下文無關(guān)文法 C.上下文有關(guān)文法 D.正規(guī)文法A.短語文法 B.上下文無關(guān)文法 C.上下文有關(guān)文法 D.正規(guī)文法13、語法分析最常用的兩類方法是自頂向下和自底向,上分析法。14、一個確定的有窮自動機(jī) DFA 是一個 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、正規(guī)文法16、一個文法

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

5、傳地址(2)傳值(3)傳標(biāo)識符(4)得結(jié)果(5)傳名(6)返回值可選項(xiàng)有：A、(1)(2)(4)(5)B、(1)(2)(5)(6)C(2)(3)(6)D、(2)(3)(4)(6)21、下列代碼中 D 不可能是目標(biāo)代碼。A、匯編指令代碼已可重定位指令代碼 C、絕對指令代碼 D、中間代碼22、一張轉(zhuǎn)換圖只包含有限個狀態(tài)，其中有一個被認(rèn)為是初態(tài)，最多只有一個終態(tài)。母_。A.正確 B.不正確23、有限自動機(jī)能識別 CA.上下文無關(guān)文法 B.上下文有關(guān)文法C.正規(guī)文法 D.短語文法。_24、匯編程序是將 B 程序改造成目標(biāo)語言程序的翻譯程序。A 機(jī)器語言 B 匯編語言 C 高級語言 D 低級語言25、L

6、R(k 戌法B 二義性的。A、都是 B、都不是 C、不一定都是26、喬姆斯基方法的 2 型語言是這樣一種語言，其產(chǎn)生式限制為 AA、A 一 B、A-a,AfaBC 一面|)D、一27、局部優(yōu)化是局限于一個 C 范圍內(nèi)的一種優(yōu)化。A.循環(huán) B.函數(shù) C 基本塊 D.整個程序28、目標(biāo)代碼生成時，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問題。A。A.正確 B.不正確29、喬姆斯基方法的 3 型語言是這樣一種語言，其產(chǎn)生式限制為 BAA-BAaAaBC 一用|)D 一30、運(yùn)算符與運(yùn)算對象類型不符屬于 AQA、語法錯誤 B、語義錯誤 C、語用錯誤 D、規(guī)則集合31、詞法分析器的輸入是 B。A、詞法記號 B

7、、源程序 C、語法單位 D、目標(biāo)程序32、在下述的編譯方法中，自底向上的方法有 F,自頂向下的分析方法有 A。簡單優(yōu)先分析算符優(yōu)先分析遞歸下降分析預(yù)測分析技術(shù)LR(K)分析SLR(k)分析LL(k)分析LALR(K)分析A.B.CD.EF.A.B.CD.EF.33、對于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN用動態(tài)貯存分配策略。B。A.正確 B.不正確34、算符優(yōu)先分析法每次都是對 C 進(jìn)行歸約。A 句柄 B 短語 C 最左素短語 D 素短語35、編譯時能進(jìn)行的類型檢查稱為 CQA、錯誤檢查 B、動態(tài)檢查C 靜態(tài)檢查 D、隨機(jī)檢查36、規(guī)范推導(dǎo)的每一步總是用產(chǎn)生式右邊符號串替換句型中 B_位置的非終

8、結(jié)符號A、最左 B、最右 C、最中 D、任意37、語法分析器的輸入是單詞符號流.其輸出是分析樹的某種表示38、每個文法都能改寫為 LL(1)文法。BA.正確 B.不正確39、對于無二義性的文法，規(guī)范推導(dǎo)是 CA 最左推導(dǎo) B 最右推導(dǎo)的逆過程 C 最左歸約的逆過程 D 最右歸約的逆過程。40、描述語言 L=ambn|nm1 的文法為 D。A、Z-AbbA-aA|aB-bB|bB、ZfAB|bA 一 Aa|aB-aBb|bCZ-AbA-aAb|aD、Z-aAbA-Ab|aAb|41、間接三元式表示法的優(yōu)點(diǎn)為一 AA、采用間接碼表，便于優(yōu)化處理 B、節(jié)省存儲空間，不便于表的修改C 便于優(yōu)化處理，節(jié)

9、省存儲空間 D、節(jié)省存儲空間，不便于優(yōu)化處理42、編譯時能進(jìn)行的類型檢查稱為 CA 錯誤檢查 B 動態(tài)檢查 C 靜態(tài)檢查 D 隨機(jī)檢查43、文法 GS:S-xSx|y 所識別的語言是 A。A、xnyxn(n0)B、(xyx)*C、xyxD、x*yx*44、項(xiàng)目 Aa,稱為 B,其中 ACVN,A 不是開始符。A、移進(jìn)項(xiàng)目已歸約項(xiàng)目 C、出錯項(xiàng)目 D、接受項(xiàng)目45、設(shè)有文法 GS:S-S*S|S+S|(S)|a,該文法 A 二義性文法。A、是 B、不是 C、不一定46、高級語言編譯程序常用的語法分析方法中，LL 分析法屬于_B 分析方法。A、自左至右 Ek 自頂向下 C 自底向上 D、自右至左。

10、47、有文法 G:E-E*T|TT-T+i|i 句子 2+5*3+3 按該文法 G 歸約，其值為 BA23B42C30D1748、高級語言編譯程序常用的語法分析方法中，LL 分析法屬于_B 分析方法。A 自左至右 B 自頂向下 C 自底向上 D 自右至左。49、形如 A-a的甑目為 A 項(xiàng)目。A、待約 B、移進(jìn) C、接受 D、規(guī)約50、活動記錄的連接數(shù)據(jù)不包括 AQA、形參單元 B、動態(tài)鏈(老 SP)C、返回地址 D、全局 Display 地址51、高級語言編譯程序常用的語法分析方法中，IALR 分析法屬于_C 分析方法。A、自左至右 B、自上而下 C、自下而上 D、自右至左52、設(shè) a、b、

11、c 是文法的終結(jié)符，且滿足優(yōu)先關(guān)系 a=b 和 b=c,則 D。A.必有 a=cB.必有 c=aC 必有 b=aD 答案 AC 都不一定成立53、詞法分析器的輸出是二。A、詞法記號流 B、源程序 C、語法單位 D、目標(biāo)程序54、對一個基本塊來說，A 基 M 確的。A、只有一個入口語句和一個出口語句 B、有一個入口語句和多個出口語句C 有多個入口語句和一個出口語句 D、有多個入口語句和多個出口語句55、詞法分析所依據(jù)的是 B。A 語義規(guī)則 B 構(gòu)詞規(guī)則 C 語法規(guī)則 D 等價變換規(guī)則56、句型是由 D 推導(dǎo)出的符號串。A、非終結(jié)符 B、終結(jié)符 C、任何符號 D、開始符號57、如果文法 G 是無二

12、義的，則它的任何句子 aA。A、最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹必定相同B最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹可能不同C 最左推導(dǎo)和最右推導(dǎo)必定相同D、可能存在兩個不同的最左推導(dǎo)，但它們對應(yīng)的語法樹相同58、算符優(yōu)先文法與算符優(yōu)先函數(shù)的關(guān)系的描述中正確的是（B）。A、一個算符優(yōu)先文法一定存在優(yōu)先函數(shù)與之對應(yīng)B、一個算符優(yōu)先文法可能存在多個優(yōu)先函數(shù)與之對應(yīng)C 一個算符優(yōu)先文法一定存在多個優(yōu)先函數(shù)與之對應(yīng)D、一個算符優(yōu)先文法一定存在有限對優(yōu)先函數(shù)與之對應(yīng)59、一個句型中稱為句柄的是該句型的最左 DQA 非終結(jié)符 B 短語 C 句子 D 直接短語60、描述一個語言的文法是（B）A、唯一的 B、不唯一的 C、

13、可能唯一，也可能不唯一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、所謂自上而下分析法是指=。65、所謂語法制導(dǎo)翻譯方法是。66、確定的有窮自動機(jī)是一個五元組，通常表示為 M=（S,2,f,s0,Z）。67、規(guī)范歸約中的可歸約串是指包翅;算符優(yōu)先分析中的可歸約串是指疆羞羞贊。68、編譯程序在邏輯上由詞法分析、哧繪搟、語義分析

14、、中間代69、D 不可能是目標(biāo)程序。A、匯編語言模塊 B、可重定位目標(biāo)模塊 C、可執(zhí)行目標(biāo)模塊 D、中間代碼70、如果一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則稱這個文法是二義W。71、一個名字的屬性包括繼承屬性和綜合屬性。72、正規(guī)式的“*讀作星閉包。73、編譯程序在邏輯上由、語義分析、中間代碼生成、代碼優(yōu)化和目標(biāo)代碼生成六部分組成。74、編譯程序的各個階段的工作都涉及到符號表管理和錯誤處理75、文法用來描述語言的語法結(jié)構(gòu)，它由如下 4 個部分組成：文法終結(jié)符集合、文法非終結(jié)符集合、D 和文法開始符號。A 單詞集合日字母數(shù)字串C 文法句子集合 D、文法產(chǎn)生式的集合76、確定的有窮自動機(jī)是一

15、個元組，通常表示為。77、已知文法GE:E-E+T|TTT*F|FFf（E）|id該文法終結(jié)符集合Vk,文法非終 25 符集合VN=，該文法在喬姆斯基（Chomsky）文法分類屬于2文法。78、編譯程序的各個階段的工作都涉及到和。79、假設(shè) G 是一個文法，S 是文法開始符號，如果 S*x,則稱 x 是該文法的一。80、如果一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則稱這個文法是。81、優(yōu)化時，節(jié)省一條指令 MOVR,M,節(jié)省的指令代價為 CA、0B、1C、2D、382、采用 31_語法分析時，必須消除文法的左遞歸。83、在狀態(tài)轉(zhuǎn)換圖中，結(jié)點(diǎn)代表狀態(tài),用圓圈表示。84、若源程序是高級語言編寫的

16、，目標(biāo)程序是機(jī)器語言或匯編一語言的程序，則相應(yīng)的翻譯程序稱為編譯程序。85、常用的兩種動態(tài)存貯分配辦法是棧式分配和堆式分配。86、翻譯方案和語法制導(dǎo)定義不同的是它的語義動作（而不叫語義規(guī)則）放在括號內(nèi)，并且可以插在產(chǎn)生式右部的任何地方87、如果一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則稱這個文法是。88、所謂最左推導(dǎo)是指：。89、上下文無關(guān)文法的可以用四元組表示,其形式為 G=(V,VT,S,P)。90、后綴式 ab+c+d*e-所表達(dá)的式子為(a+b+c)*d-e。91、常用的兩種動態(tài)存貯分配辦法是分配和分配。92、LL(K良法中，第一個L表示從左到右掃描輸入串，第二個L表示產(chǎn)生最左推導(dǎo),

17、K表示在決定語法分析器每步動作時向前看K個輸入。93、一個上下文無關(guān)文法所含四個組成部分是文法終結(jié)符集合文法非終結(jié)符集合開始符號產(chǎn)生式有限集合。94、對于文法 G,僅含終結(jié)符號的句型稱為句子。95、設(shè)有文法GE:E-E+T|ET|FT-T*F|T/F|FF-(E)|i該文法句型E+T*F的句柄是T*F。96、后綴式 ab+c+d*e-所表達(dá)的式子為。97、文法符號的屬性有兩種，一種稱為繼承屬性，另一種稱為綜合屬性，S屬性定義是指僅使用綜合屬性的語法制導(dǎo)定義。98、LR(0 預(yù)目和 LR(1 預(yù)目的區(qū)別在于是否有搜索符。99、緊跟在條件轉(zhuǎn)移語句后面的語句是基本塊的入口語句。100、若二個正規(guī)式所

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

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

20、以有綜合屬性，但不能有繼承屬性。（F）121、所有 LR 分析器的總控程序都是一樣的，只是分析表各有不同。（T）122、因名字都是用標(biāo)識符表示的，故名字與標(biāo)識符沒有區(qū)別（F）123、空符號串的集合=（F）124、非終結(jié)符可以有綜合屬性，但不能有繼承屬性。（F）125、終結(jié)符可以有綜合屬性，也可以有繼承屬性。（F）126、一張轉(zhuǎn)換圖只包含有限個狀態(tài)，其中有一個被認(rèn)為是初態(tài)，最多只有一個終態(tài)。（）127、若一個句型中出現(xiàn)了某一產(chǎn)生式的右部，則此右部一定是該句型的句柄。（F）129、DAG 是一個可帶環(huán)路的有向圖。（F）130、設(shè)有符號串x和y,把y的符號寫在x的符號之后所得的符號串，叫做x與y的連

21、接，記為xy。（T）131、對任何一個編譯程序來說，產(chǎn)生中間代碼是不可缺少的一部分。（F）132、對任何正規(guī)表達(dá)式 e,都存在一個 DFAM,滿足 L（M）=L（e）。（T）133、運(yùn)行時的DISPLAY6的內(nèi)容是什么它的作用是什么答：內(nèi)容：1、過程 R 的現(xiàn)行活動記錄的地址(sp 的現(xiàn)值)2、R 的外層 Q 的最新活動記錄的地址 3、Q 的外層即主程序 P 的活動記錄的地址作用：跟蹤每個外層的最新活動記錄的位置134、何謂局部優(yōu)化、循環(huán)優(yōu)化和全局優(yōu)化優(yōu)化工作在編譯的哪個階段進(jìn)行答：局部優(yōu)化：在基本快內(nèi)的優(yōu)化。循環(huán)優(yōu)化：對循環(huán)中的代碼進(jìn)行優(yōu)化。全局優(yōu)化：整個程序范圍內(nèi)的優(yōu)化。在中間代碼優(yōu)化階段

22、。135、常見的存儲分配策略有幾種它們都適合于什么性質(zhì)的語言答：1、靜態(tài)分配策略適用于無動態(tài)申請內(nèi)存、無可變體積數(shù)組、無遞歸調(diào)用的程序語言(如 Fortran)2、動態(tài)分配策略棧式動態(tài)分配 2.1.1 簡單棧式分配適用于沒有分程序結(jié)構(gòu)、不允許程序嵌套定義但允許過程遞歸調(diào)用、允許過程含可變數(shù)組的語言嵌套過程語言的棧式分配適用于沒有分程序結(jié)構(gòu)、允許程序嵌套定義和過程遞歸調(diào)用、允許過程含可變數(shù)組的語言堆式動態(tài)分配適用于允許程序?yàn)樽兞吭谶\(yùn)行時動態(tài)申請和釋放存儲空間的語言136、下面文法是否是二義文法試說明理由。GS:SSaS答：二義137、已知文法 G(E)EfT|E+TT-F|T*FF-(E)|i(

23、1)給出句型(T*F+i)的最右推導(dǎo)及畫出語法樹；(2)給出句型(T*F+i)的短語、素短語。1)E-E+T-E+-T+i-T*F+I 樹略2)短語：T*F+iT*Fi素短語：T*Fi138、把算術(shù)表達(dá)式(a+b)*(b+c)翻譯成：(a)后綴表示ab+bc+*(b)語法樹圖略(c)有向無環(huán)圖圖略(d)四元式三地址代碼四地址代碼：(+,a,b,t1)(+,b,c,t2)(*,t1,t2,t3)(,t3,-,t4)139、DFA 與 NFA 的區(qū)另 1J答：1、DFA 弧上不允許有出現(xiàn)，NFA 允許2、DFA 中每個狀態(tài) S 和輸入符號 a 最多有一條邊離開 S,NFA 有多條3、NFA 可以有

24、多個初態(tài)，DFA 只有一個140、設(shè)已構(gòu)造出文法 G(S):SS(S)S的 LR 分析表如下狀態(tài)ACTIONGOTO()#S0r2r211S2Acc2r2r233S4S54r2r265r1r16S4S77r1r1假定輸入串為()()，請給出 LR 分析過程(即狀態(tài)，符號，輸入串的變化過程)。步驟狀態(tài)符號輸入串步驟狀態(tài)符號輸入串10()()$201S()()$3012S()()$40123S()()$501235S()()$601S()$7012S()$80123S(S)$901235S(S)$1001S$141、對符號表的基本操作有幾種，分別是什么答：5 類。1、填寫名稱 2、查找名字 3、訪

25、問信息 4、填寫修改信息 5、刪除(或者：4 類。建立、插入、查找、刪除)142、給定代碼段如下，求出按四種不同方式進(jìn)行參數(shù)傳遞后，變量 a 的值procedureP(w,x,y,z);beginy:=y*w;z:=z+x;endbegina:=5;b:=3;P(a+b,a-b,a,a);write(a);end傳值：5傳地址：42得結(jié)果：7傳名：77143、目標(biāo)代碼有哪幾種形式生成目標(biāo)代碼時通常應(yīng)考慮哪幾個問題答：1、匯編語言 2、機(jī)器語言又可分為 a 可立即執(zhí)行的機(jī)器語言 b 可重定位的機(jī)器語言需要考慮：1.、如何使生成的目標(biāo)代碼最短 2、如何分配寄存器的使用144、下面的推導(dǎo) Srmrm

26、AbWrmlbW 中，最后一步用的是 Al,分別指出 LL(1)方法和 LR(1)方法在掃描到此句型的什么位置決定用此產(chǎn)生式(5 分)P79答：LL(1)掃描到l的時候決定用此產(chǎn)生式；LR(1)a描到b的時候決定使用次產(chǎn)生式145、構(gòu)造一個最簡DFA,它接受正規(guī)式ab(a|b)*。給出文法GS:SSaA|AAfAbB|BBfcSd|e(1)證實(shí) AacAbcBaAdbed 是文法 GS的一個句型；(2)請寫出該句型的所有短語、素短語以及句柄。答：1)這里用最右推導(dǎo)表示，省略樹SSaSaBSacScRSacAcRSacAbBcRSacAbeCSacAbBbecHSacAbcSdbedfSacAb

27、cSaAdbecRSacAbcAaAdbecHSacAbcBaAdbedfAacAbcBaAdbed2)短語：AacAbcBaAdbedcAbcBaAdbedAbcBaAdbeAbcBaAdcBaAdBaAeA 素短語：BaAe 句柄：A146、寫出表達(dá)式 a+b*(c-d)對應(yīng)的逆波蘭表示、三元式三地址代碼序列和抽象語法樹。147、什么是活動記錄它主要由哪些內(nèi)容構(gòu)成148、對下列四元式序列生成目標(biāo)代碼(10 分)T=A-BS=C+DW=E-FU=W/TV=U*S其中，V 是基本塊出口的活躍變量，R0 和 R1 是可用寄存器。答 MOVR0,ASUB R0,BMOVR1,AADD R1， DM

28、OVS， R1MOvR1， ESUB R1， FDIVR1， R0MULR1， S149、設(shè)有如下的三地址碼(四元式)序列:ReadNI:=NJ：=2L1：ifIJgotoL2ifI=0gotoL4J：=J+1I:=NgotoL1L3:PrintYESReturnL4：PrintNOReturn(1)、對題中代碼劃分基本塊，并給每個基本塊一個序號(2)、畫出基本塊集合的控制流圖，每個基本塊就用(1)小題中的序號表示。(3)、若有循環(huán)的話，列出構(gòu)成每個循環(huán)的結(jié)點(diǎn)。150、已知文法G(V):VN|N舊EV|V+ENT(1)給出與G(V痔價的LL(1)文法G(V);VNVV-E|EVEEf+E|eN

29、i(2)求文法G(V)的每個非終結(jié)符的FIRST集合和FOLLOW集合；First(V)=iFirst(V)=,First(E)=iFirst(E)=+,First(N)=iFollow(V)=$,+,Follow(V)=$,+,Follow(E)=Follow(E戶Follow(N)=,$,+)(3)構(gòu)造文法G(V)的LL(1汾析表。+i$VV一NVV，V一eVfEV一eV一eEEVEE，E-+EE，一eNNT151、考慮下面的三地址語句序列:b:=1b:=2ifw=xgotoL2e:=bgotoL2L1:gotoL3L2:c:=3b:=4c:=6L3:ifye 則 First(a)FFol

30、low(A)=空集154、寫出語句 a:=b*(-c)+b*(-c)的后綴式、抽象語法樹、DAG 圖、四元式三地址代碼和三元式三地址代碼。155、設(shè)有文法 GA：A-iB*eB 一 SB|sS 一eC|.iC 一 eC|判定該文法是否為 LL(1)文法若是則給出它的 LL(1 汾析表，否則說明理由。(20 分)First(A)=iFirst(B)=,.First(S)=,.First(C)=e,Follow(A)=$Follow(B)=*Follow(S)=*Follow(C)=對產(chǎn)生式 BSB|First(SB)=First(S)=,.First(=所以 First(SB)nFirst(9=

31、空集First(SB)AFollow(B 尸空集對產(chǎn)生式 S 一eC|.iFirst(eC)=First(.i)=.i所以 First(eC)nFirst(.i 尸空集對產(chǎn)生式 CeC|First(eC)eFirst(s)=所以 First(eC)nFirst(。=空集First(eC)nFollow(C 尸空集所以此文法是 LL(1)文法.*ie$AA-iB*eBB 一 SBB 一B 一 SBSS 一.iSeCCC 一|&C 一 eC156、構(gòu)造一個 DFA,它接受匯=0,1上能被 5 整除的二進(jìn)制數(shù)。157、正規(guī)式(0|1)*和(|0)1*)*是否等價，說明理由。158、寫出字母表

32、=a,b上語言 L=w|w 的最后兩個字母是 aa 或 bb的正規(guī)式，并畫出接受該語言的最簡 DFA（a|b）*aa|bb159、文法 G(S 汲其 LR 分析表如下，請給出串 baba$的分析過程。(1)SDbB(2)Dd(3)D 一 e(4)Ba(5)BBba(6)B 一LR 分析表ACTIONGOTObda$SBD0r3s3121acc2s43r24r6S5r665r4r46s7r17S88r5r5（注：答案格式為步驟饃輸入串動作）步驟愎輸入串動作）10baba$按 Be 規(guī)約20D2baba$移進(jìn)30D2b4aba$移進(jìn)40D2b4a5ba$按 B 一 a 規(guī)約50D2b4B6ba$移

33、進(jìn)60D2b4B6b7a$移進(jìn)70D2b4B6b7a8$按 BBba 規(guī)約80D2b4B6$按 SDbB 規(guī)約90S1$接受160、已知文法G(A):A-aABl|aB-Bb|d(1)消除文法中的左遞歸，提取公共左因子，給出與G(A將價的LL(1)t?feG(A);(2)求文法G(A)的每個非終結(jié)符的FIRS球合和FOLLOW集合；(3)構(gòu)造文法G(A)的LL(1汾析表。答：1)A-aAAABl|eB-dBB-bB|e2)First(A尸aFirst(B尸dFirst(A尸a,First(B)=b,Follow(A)=$,dFollow(B)=lFollow(A)=$,dFollow(B)=l3)abld$AA-aAAA-ABlAeAeBB-bBB，B一e161、設(shè)文法G(S):SS+aF|aF|+aFF-*aF|*a(1)消除左遞歸和回溯；(2)計(jì)算每個非終結(jié)符的FIRSTS口FOLLOW(3)構(gòu)造預(yù)測分析表。答1、Sr+aFS|aFSS一+aFS|F7*aFF一F|&2、Fist(S)=