1、11、編譯程序各階段都涉及A、詞法分析 B、表格管理C、語法分析D、語義分析2、 下列哪個程序不是編譯程序的組成部分？ _。A、詞法分析程序B、代碼讀入程序C、代碼生成程序D、語法分析程序3、 編譯程序各階段的工作往往是 _進行的。A、順序B、并行C 成批D、穿插4、 詞法分析所依據(jù)的是 _。A、語義規(guī)則B 構(gòu)詞規(guī)則C 語法規(guī)則D、等價變換規(guī)則5、 編譯程序的語法分析器可以發(fā)現(xiàn)源程序中的 _。A、語義錯誤B、語法和語義錯誤6、高級語言源程序經(jīng)編譯后產(chǎn)生的程序是A、源程序B、目標程序1、掃描器的任務是從源程序中識別出一個個單詞符號。2、高級語言源程序有兩種執(zhí)行方式，即解釋和編譯。判斷：高級語言編

2、寫的源程序都必須通過編譯，產(chǎn)生目標代碼后才能運行。 多遍掃描的編譯程序的多遍是指多次重復讀源程序。高級語言程序到低級語言程序的轉(zhuǎn)換是基于語義的等價變換。編譯程序中錯誤處理的任務是對檢查出的錯誤進行修改。目標程序一定是機器語言程序。連接裝配程序可把經(jīng)編譯程序產(chǎn)生的目標程序變成可執(zhí)行的機器語言程序。簡答題：1、請指出下列錯誤信息可能是編譯的哪個階段報告的？1else 沒有匹配的 if ；2數(shù)組下標越界；3使用的函數(shù)沒有定義；4在數(shù)中出現(xiàn)了非數(shù)字信息。答：語法分析階段 語義分析與中間代碼生成階段語義分析與中間代碼生成階段詞法分析階段2、何謂源程序、中間代碼和目標代碼？它們?nèi)咧g有何種關(guān)系？答：所謂

3、源程序是指用某種高級語言編寫的程序，它是編譯程序的加工對象。目標程序 是指低級語言（機器語言或匯編語言）編寫的程序，它是編譯程序的加工結(jié)果。中間代 碼是其結(jié)構(gòu)介于源程序和目標程序之間的一種機內(nèi)表示形式，它是編譯程序產(chǎn)生的中間臨時結(jié)果。它們?nèi)咧g的關(guān)系是等價關(guān)系，即結(jié)構(gòu)不同，但語義相同。1、 文法 G: S- xSx|y 所識另 U 的語言是 _。A、xyxB、(xyx) *C xnyxn(n 0)D、x*yx*2、 設有文法 GS=(S,B,b,S- b|bB,B-bS,S)該文法所描述的語言是 _。i2i2i+12iA、L(GS)=b|i 0B、L(GS)=b |i 0 C、L(GS)=b

4、 |i 0 D、L(GS)=b | 13、 給定文法 A bA|cc，下面的符號串中為該文法句子的是。C 錯誤并校正D、語法錯誤。C、函數(shù)D、過程21cc bcbc bcbcc bccbcc bbbcc可選項有：A、BC、D、4、描述語言 L=ambn|n m 1的文法為_ 。A、 Z-AbbA- aA|aB-bB|bB、 A- ABbA- Aa|aB-aBb|bC、 Z-AbA- aAb|aD、 乙 aAbA- Ab|aAb|1、 假定 G 是一個文法，S 是它的開始符號。如果S=a，則稱a是一個句型，僅包含的 句型稱為句子。2、設有文法 GS:S- bBB- cC B cCeC- dS S

5、- aB，則VN=_,VT=_。判斷一個上下文無關(guān)文法的開始符號可以是終結(jié)符或非終結(jié)符。1 型文法對規(guī)則的限制比 2 型文法對規(guī)則的限制要多一些。簡答題：1、令文法 G 為：N D|NDD 0|1|2|3|4|5|6|7|8|9(1)文法 G 定義語言是什么？給出句子 0127 的最左推導和最右推導。答：(1)G 的語言是任意的數(shù)字串：L(G)=qa2.an|ai 0,1,2,9(2)最左推導：N=ND=NDD=NDDD=DDDD=0DDD=01DD=012D=0127 最右推導：N=ND=N7=ND7=N27=ND27=N127=D127=01272、證明下述文法是一個二義性文法：S iSe

6、S|iS|i句子 iiiei 的語法樹如下圖所示。詞法分析:1、 如果兩個文法產(chǎn)生的語言相同，則稱這兩個文法是等價的。Sii32、 確定的有限自動機 DFA 是不確定的有限自動機 NFA 的一個特例。3、 兩個等價的正規(guī)式所表示的正規(guī)集相同，高級語言的詞法結(jié)構(gòu)一般可以用正規(guī)文法來實 現(xiàn)。4、 一張符號表的每一項(或稱入口)包含兩大欄，即名字欄和信息欄。5、 符號表的查找和整理技術(shù)通常有線性查找、二叉樹和雜湊技術(shù)。6、 設刀=a,b，試寫一正規(guī)式，其表示的正規(guī)集為“不以 a 開頭，但以 aa 結(jié)尾的字符串集 合”。正規(guī)式為：b(a|b)*aa1、 詞法分析器的輸入是_ 。A、單詞符號串B、源程序

7、C 語法單位D、目標程序2、 _ 不是 NFA 的成分。A、有窮字母表B、唯一的初始狀態(tài)C 終止狀態(tài)集合D、有限狀態(tài)集合3、 在詞法分析階段不能識別的是 _。A、標識符B、運算符C 四元式D、常數(shù)4、 對編譯程序所用到的符號表，涉及的操作不包括 _ 。A、填寫或更新信息欄內(nèi)容B、填入新名C、給定名字，訪問它的有關(guān)信息D、輸出 token 字序列判斷：1、 有限自動機只有一個初態(tài)。2、 對任一個正規(guī)式 r,都存在一個 NFA M,使得 L(M)=L(r)。簡答題：1、 設刀=0,1，試寫一正規(guī)式，其表示的正規(guī)集為：“含有子串 010 的所有串”。答：正規(guī)式為： 1)*o1o(1)*2、 在實現(xiàn)編

8、譯程序時，常將詞法分析程序從語法分析中獨立出來，這樣做有什么好處？ 答：將詞法分析程序從語法分析中獨立出來，這樣做有以下好處：建立高級語言時能獨立地研究詞法與語法兩方面的特性。2詞法規(guī)則簡單，因此可建立特別適用于這種文法的有效分析技術(shù)，也容易實現(xiàn)詞法分 析程序生成自動化。3可以就同一個語言為每種不同的機器編寫一個詞法分析程序，只編寫一個共同的語法分析程序，這時只要每一個詞法分析程序產(chǎn)生相同的符號內(nèi)部表示形式供該語法分析程 序使用即可。綜合題：1、設0,1上的正規(guī)集 S 由倒數(shù)第二個字符為 1 的所有字符串組成，請給出該字集對應 的正規(guī)式，并構(gòu)造一個識別該正規(guī)集的DFA構(gòu)造相應的正規(guī)式：(0|1

9、)*1(0|1)NFA:4確定化:5I10打0,1,21,21,2,31,21,2廠1,2,31,2,31,2,41,2,3,41,2,41,2:1,2,3123,41,2,41,2,3,41、 編譯過程中，語法分析器的任務是 _。分析單詞是怎樣構(gòu)成的分析單詞串是如何構(gòu)成語句和說明的分析語句和說明是如何構(gòu)成程序的分析程序的結(jié)構(gòu)A、B、C、 D2、 在通常的語法分析方法中，特別適用于表達式的分析。A、算符優(yōu)先分析法B LR 分析法C、遞歸下降分析法D、LL（ 1）分析法3、 一個_ 指明了在分析過程中的某時刻所能看到的產(chǎn)生是多大一部分。A、活前綴B、前綴C、項目D、項目集判斷1、 每個文法都能改

10、寫成 LL（ 1）文法。2、 一個 LL（ 1 ）文法一定是無二義的。3、 每一個算符優(yōu)先文法，必定能找到一組優(yōu)先函數(shù)與之對應。4、 欲構(gòu)造行之有效的自上而下分析器，則只需消除左遞歸。5、 所有 LR 分析器的總控程序都是一樣的，只是分析表各有不同。6、 若 B 為非終結(jié)符，則 Aa.B3為移進項目。1、 語法分析最常用的兩類方法是自上而下和自下而上分析法。2、 語法分析器的輸入是單詞符號串，其輸出是語法單位。3、 一個文法 G,若它的預測分析表 M 不含多重定義入口，則 G 是 LL （1）文法。4、 LL （1）文法中，第一個 L 表示從左到右掃描輸入串，第二個L 表示最左推導。5、應用算

11、符優(yōu)先分析技術(shù)分析句型時，每步被直接規(guī)約的是最左素短語，而應用 技術(shù)時，每步被直接規(guī)約的是句柄。6、 活前綴是指規(guī)范句型的一個前綴，這種前綴不含句柄之后的任何符號。LR 分析6簡答題:71、對于文法 G (S): S(L) |as|a L L,S|S畫出句型(S,(a)的語法樹給出句型(S,(a)的短語、直接短語、句柄和素短語。follow(S)=#,follow(T)=1文法不含左遞歸2每個產(chǎn)生式的候選首符集兩兩不想交3. first(T Qfo)ow(T)=所以該文法是 LL(1)文法。綜合題：1、對下面的文法 G: E TE E +E|dT FT T T|F PF F*FdP (E)|a

12、|b|A(1) 計算這個文法的每個非終結(jié)符的FIRST 和 FOLLOW(2) 證明這個文法是 LL(1)的。(3 )構(gòu)造它的預測分析表。語義分析和中間代碼生成:1、 語義分析和中間代碼生成時所依據(jù)的是 _。A、語法規(guī)則B、詞法規(guī)則C、語義規(guī)則D、等價變換規(guī)則短語：S a、(a)、S,(a)(S,(a)直接短語：a,S句 柄：S素短語：a2、考慮以卜文法G：Sa|A|(T)TT,S|S(1)消去 G 的左遞歸(2)經(jīng)改寫后的文法是否是LL(1)的？答：消左遞歸：Sa|A|(T)T STfisrt(S)=a,A,(first(T)=a,A,(T,ST dfirst(T )=,follow(T )

13、=)82、 終結(jié)符具有屬性。A、傳遞B、繼承C、抽象 D、綜合3、 后綴式 ab+cd+/可用表達式_來表示。A、a+b/c+d B (a+b)/(c+d)C、a+b/(c+d) D、a+b+c/d4、 語法制導的翻譯程序能同時進行和語義分析。A、詞法分析B、語法分析C、優(yōu)化D、目標代碼生成5、 四元式之間的聯(lián)系是通過 _實現(xiàn)的。A、指示器B、臨時變量C、符號表D、程序變量1、語法制導的翻譯是基于屬性文法的，屬性有兩類，即綜合屬性和繼承屬性。2、在語法樹中，一個結(jié)點的綜合屬性的值由其子結(jié)點的屬性確定，而繼承屬性則由該結(jié)點 的父結(jié)點或兄弟結(jié)點的某些屬性確定。3、語義分析階段所生成的與源程序等價的

14、中間表示形式可以有逆波蘭表示、三元式表示和 四元式表示等。4、生成中間代碼主要是為了使目標代碼的優(yōu)化容易實現(xiàn)。簡答題：1、給出下列表達式的逆波蘭式:(1) -a+b*(-c+d)(2) a+b*(c-d)/e-f答: (1)a-bc-d+*+(2)abcd-*e/+f-2、給出-(a+b)*(c+d)-(a+b+c)的三元式和四元式。(其中單目運算一用表示)1(+,a,b)(+,a,b,T1)2(,1,_)(,T1,_,T2)3(+,c,d)(+,c,d,T3)4(*,2,3)(*,T2,T3,T4)5(+,a,b)(+,a,b,T5)6(+,c,5)(+,T5,c,T6)7(-,4,6)(-

15、,T4,T6,T7)優(yōu)化：1、 下列_優(yōu)化方法不是針對循環(huán)優(yōu)化進行的。A、強度削弱B、刪除歸納變量C、刪除公共子表達式2、 對于一個基本塊來說，正確的說法是 _。A、只有一個入口語句和一個出口語句B、有一個入口語句和多個出口語句C、有多個入口語句和一個出口語句D、只有多個入口語句和多個出口語句判斷：數(shù)組元素的地址計算與數(shù)組的存儲方式有關(guān)。 循環(huán)中的不變運算都可以提到循環(huán)外。根據(jù)優(yōu)化設計到的程序范圍，優(yōu)化可分為局部優(yōu)化、循環(huán)優(yōu)化和全局優(yōu)化三個不同的級別。 局部優(yōu)D、代碼外提9化是在基本塊范圍內(nèi)進行的一種優(yōu)化。在優(yōu)化中，可把循環(huán)中的不變運算提到循環(huán)外去，這種方法稱為代碼外提。簡答題1、已知三地址代

16、碼序列為：(1)i:=1(2) i:=i+1j：=110j:=j+1(5) k:=i mod j(6) if kz0 goto (4)if i 工 j goto (10)(8)write I(9)writeln(10) if i C goto L2B:=B+1goto L1L2:write Ahalt2、試構(gòu)造以下基本塊(1)T0(2)T1(3)T2(4)A:(5) B：G 的 DAG=3.14=2*T0=R+r=T1*T2=A(6) T3： =2*T0(7)T4 : =R+r(8T5 : =T3+T4(9)T6 : =R-r(10) B : =T5*T63.14B11已知如下翻譯模式，用回填

17、法給出ab or cd and ef 的四元式序列，要求給出簡單過程。文法及其翻譯模式如下：(1)ETEiand M E2backpatch(Ei.truelist,M.quad);E.truelist:= E2.truelist)E.falselist:=merge(E1.falselist,E2.falselist )(2) ETE1or M E2backpatch(E1.falselist,M.quad);E.truelist:=merge(E1.truelist,E2.truelist)E.falselist:=E2.falselistE1Tid1relop id2E.truelist

18、:= makelist( nextquad);E.falselist:=makelist( nextquad+1);Emit( j relop.op ,id1.place , id2.place , OEmit( j,-.-,0 )MT M.quad:=n extquad四兀式序列為：100(j , a, b, 0)101(j ,- ,102102(j ,c , d,104)103(j ,- ,0)104(j ,e, f,0)105(j ,一 ,0)E.t=1OO,1O4ae c d12有文法 G（ S）：STA|BATaAb|cBtaBb |d試構(gòu)造此方法的 LR（ 0）項目集規(guī)范族。1）將文法 G 拓廣為文法 GS-SA-cS-AB-aBbS-BB-dA-aAb2）列出 LR（ 0）的所有項目：1S-?S 5. A-?aAb 9. A-?c13. B- ?aBb 17.B- ?dS-S? 6. A-a?Ab10. A-c ?14. B-a ?Bb 18 B-d?S-? A 7. A-aA?b 11. S- ?B15. B-aB ?bS-A? 8.A-aAb? 12.S-B?16 B-aBb?3）用CLOSURE!、法構(gòu)造文法 G 的 LR （ 0）項目集規(guī)范族：I0: S -?S ,