編譯原測驗題(共8頁)

1、第1-2章測試題一、選擇題1 文法 G 產(chǎn)生(chnshng)的_的全體是該文法描述的語言。dA句型(j xn) B 終結(jié)符集 C非終結(jié)符集 D 句子(j zi)2 若文法 G 定義的語言是無限集，則文法必然是 _。 aA遞歸的 B前后文無關(guān)的 C二義性的 D 無二義性的3 一個文法所描述的語言是_。aA 唯一的 B 不唯一的 C可能唯一，好可能不唯一 D都不對4_是兩類程序語言處理程序。 bA 高級語言程序和低級語言程序 B 解釋程序和編譯程序 C 編譯程序和操作系統(tǒng) D 系統(tǒng)程序和應(yīng)用程序 5. 一個上下文無關(guān)文法 G 包括四個組成部分，它們是：一組非終結(jié)符號，一組終結(jié)符號，一個開始符號，

2、以及一組 _。 dA句子 B句型C 單詞 D 產(chǎn)生式二、解答題1何謂編譯程序？2.一個典型的編譯程序通常由哪些部分組成？各部分的主要功能是什么？三、推導(dǎo)題1.已知文法G(E) ET|ET TF|T *F F(E)|i 和句型(T +F)*i+T (1)畫出句型的語法樹； (2)給出句型的全部短語、簡單短語和句柄。2.設(shè)有文法G：S SS | S*S | i |（S）（1）對于輸入串i+i*i給出一個最左推導(dǎo)；（2）該文法是否是二義性文法？請證明你的結(jié)論。第3章測試題一、選擇題1詞法(cf)分析器用于識別_。CA 字符串 B語句(yj) C 單詞(dnc)D標(biāo)識符2詞法分析器的輸出結(jié)果是_。CA

3、單詞的種別編碼 B單詞在符號表中的位置 C單詞的種別編碼和自身值 D 單詞自身值3詞法分析所用的文法為_。DA0型文法B1型文法 C2型文 D3型文法二、解答題1構(gòu)造正規(guī)式 1(0|1)*101 相應(yīng)的DFA。1構(gòu)造正規(guī)式 1(0|1)*101 相應(yīng)的DFA。解：先構(gòu)造NFA： 確定化： 重新命名，令A(yù)B為B、AC為C、ABY為D得： 所以，可得DFA為： 2已知 NFA=（ x,y,z,0,1,M,x,z ），其中：M(x,0)=z,M(y,0)=x,y,M(z,0)=x,z,M(x,1)=x, M(y,1)= ,M(z,1)=y, 構(gòu)造相應(yīng)的DFA并最小化。NFA圖: 下表由子集法將NFA

4、轉(zhuǎn)換為DFA： 下面將該DFA最小化： (1) 首先將它的狀態(tài)集分成兩個子集：P1=A,D,E,P2=B,C,F (2) 區(qū)分P2:由于F(F,1)=F(C,1)=E,F(F,0)=F并且F(C,0)=C,所以F，C等價。由于F(B,0)=F(C,0)=C, F(B,1)=D,F(C,1)=E,而D，E不等價（見下步），從而B與C，F(xiàn)可以區(qū)分。有P21=C,F,P22=B。 (3) 區(qū)分P1:由于A，E輸入0到終態(tài)，而D輸入0不到終態(tài)，所以D與A，E可以區(qū)分，有P11=A,E,P12=D。 (4) 由于F(A,0)=B,F(E,0)=F,而B，F(xiàn)不等價，所以A，E可以區(qū)分。 (5) 綜上所述，

5、DFA可以區(qū)分為P=A，B，D，E，C，F(xiàn)。所以最小化的DFA如下： 第4章測試題一、選擇題1在語法分析處理(chl)中， FIRST 集合、 FOLLOW 集合、 SELECT 集合均是_。BA.非終結(jié)符集 B終結(jié)符集 C字母表 D.狀態(tài)(zhungti)集 2 在自頂向下的語法分析方法(fngf)中，分析的關(guān)鍵是_。DA.尋找句柄 B.尋找句型 C. 消除遞歸 D.選擇候選式 3.語法分析器用于識別_。BA字符串 B語句 C單詞D標(biāo)識符4語法分析所用的文法為_。CA0型文法B1型文法 C2型文 D3型文法5在規(guī)范歸約中，用_來刻畫可歸約串。BA直接短語 B句柄 C最左素短語 D素短語 二、

6、解答題1設(shè)文法G(S)： S(L) | a S | a LL，S | S (1) 消除左遞歸和回溯； (2) 計算每個非終結(jié)符的first、follow和select集，判斷是否為LL（1） 文法。解：(1) S(L)|aS SS| LSL LSL| (2) FIRST)S)(，aFOLLOW(S)#，) FIRST(S)，a, FOLLOW(S)#，) FIRST(L)(，aFOLLOW(L) ) FIRST(L)，F(xiàn)OLLOW(L )FIRST)S)(，aFOLLOW(S)#，) FIRST(S)，a, FOLLOW(S)#，) FIRST(L)(，aFOLLOW(L) ) FIRST(L

7、)，F(xiàn)OLLOW(L )SELECT （S(L)）=( SELECT （SaS ）=a SELECT （SS）=(，a SELECT （S）=#，) SELECT (LSL)= (，a SELECT (L)= )因為(yn wi)SELECT （S(L)）=( 和SELECT （SaS ）=a的交集(jioj)為空集；SELECT （SS）=(，a 和SELECT （S）=#，) 的交集(jioj)為空集；SELECT (LSL)= (，a SELECT (L)= ) 的交集為空集。因此是LL（1）文法。自底向上語法分析測驗題一、填空題（每空2分，共20分）1語法分析最常用的兩類方法是_ _

8、和_ _ 分析法。自頂向下、自底向上2語法分析器的輸入是_ _其輸出是_ _。單詞、語法單位3.一個LR分析器包括三部分：一個總控程序、 和 。分析表、分析棧4.簡單優(yōu)先分析歸約和LR分析法歸約的是 ，算符優(yōu)先分析法歸約的是 。 句柄、最左素短語5.LR分析表包括action表和 表，一般會把兩張表合并成一張表。ACTION表包含的動作有移進、 接受和報錯四種。goto表、歸約二、計算題（每題40分，共80分）1.構(gòu)造算符文法GH：HH;M|M Md|aHb的算符優(yōu)先關(guān)系。由Md和Ma得：FIRSTVT(M)=d,a； 由H-H;得：FIRSTVT(H)=； 由HM得：FIRSTVT(M) c

9、FIRSTVT(H)，即FIRSTVT(H)=;,d,a 由Md和Mb得：LASTVT(M)=d,b； 由H-，；m得：LASTVT(H)=； 由HM得：LASTVT（M）cLASTVT(H），即LASTVT(H)=;,d,b 對文法開始符H,有#H#存在，即有=，#,也即；，#d. #, b#。 對形如Pab，或PaQb，有a=b，由Ma|b得：a=b； 對形如PaR，而bFIRSTVT(R)，有ab。 由H；M得：；FIRSTVT(M)，即：d，：a 由MaH得：aFIRSTVT(H)，即：a；，a;，即：；，d；，b； 由MHb得：LASTVT(H)b，即：；b，db，bb；2已知文法為

10、： S-a|(T) T-T,S|S 構(gòu)造它的 LR(0)分析表。 （LR（1）分析法自己從書上找例題復(fù)習(xí)）解：加入非終結(jié)符S，方法的增廣文法為： S-S S-a S- S-(T) T-T,S T-S 下面構(gòu)造(guzo)它的LR(0)項目集規(guī)范族為： 從上表(shn bio)可看出,不存在移進-歸約沖突以及歸約歸約沖突，該文法是LR(0)文法。 從而有下面的LR(0)分析表： 第7-10章測試題班級(bnj) 學(xué)號 姓名(xngmng) 成績(chngj) 一、填空題1.常用的參數(shù)傳遞方式有 ， 和 。傳地址，傳值和傳名2.局部優(yōu)化是 在范圍內(nèi)進行的一種優(yōu)化。基本塊3一個名字的屬性包括 和_

11、_。類型、作用域二、選擇題1程序所需的數(shù)據(jù)空間在程序運行前就可確定，稱為_管理技術(shù)。CA.動態(tài)存儲 B.棧式存儲 C.靜態(tài)存儲 D.堆式存儲2編譯程序絕大多數(shù)時間花在_上。DA.出錯處理 B.詞法分析 C.目標(biāo)代碼生成 D.管理表格3. 優(yōu)化可生成 的目標(biāo)代碼。DA 運行時間較短 B 占用存儲空間較小C 運行時間短但占用內(nèi)存空間大 D運行時間短且占用存儲空間小4下列 優(yōu)化方法不是針對循環(huán)優(yōu)化進行的。CA.強度削弱 B刪除歸納變量 C刪除多余運算 D 代碼外提二、語法制導(dǎo)翻譯1 Whilea0 b0do Begin x：x1； if a0 then a：a1 End； 翻譯成四元(s yun)式序列。 (1) (j，a，0，5) (2) (j，3) (3) (j，b，0，5) (4) (j，12) (5) (，1，T1) (6) (：，T1，) (7) (j，a，0，9) (8) (j，1)