編譯原測(cè)驗(yàn)題(共8頁(yè))

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

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

3、單詞的種別編碼 B單詞在符號(hào)表中的位置 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)集分成兩個(gè)子集：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等價(jià)。由于F(B,0)=F(C,0)=C, F(B,1)=D,F(C,1)=E,而D，E不等價(jià)（見(jiàn)下步），從而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)不等價(jià)，所以A，E可以區(qū)分。 (5) 綜上所述，

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

6、解答題1設(shè)文法G(S)： S(L) | a S | a LL，S | S (1) 消除左遞歸和回溯； (2) 計(jì)算每個(gè)非終結(jié)符的first、follow和select集，判斷是否為L(zhǎng)L（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)= )因?yàn)?yn wi)SELECT （S(L)）=( 和SELECT （SaS ）=a的交集(jioj)為空集；SELECT （SS）=(，a 和SELECT （S）=#，) 的交集(jioj)為空集；SELECT (LSL)= (，a SELECT (L)= ) 的交集為空集。因此是LL（1）文法。自底向上語(yǔ)法分析測(cè)驗(yàn)題一、填空題（每空2分，共20分）1語(yǔ)法分析最常用的兩類方法是_ _

8、和_ _ 分析法。自頂向下、自底向上2語(yǔ)法分析器的輸入是_ _其輸出是_ _。單詞、語(yǔ)法單位3.一個(gè)LR分析器包括三部分：一個(gè)總控程序、 和 。分析表、分析棧4.簡(jiǎn)單優(yōu)先分析歸約和LR分析法歸約的是 ，算符優(yōu)先分析法歸約的是 。 句柄、最左素短語(yǔ)5.LR分析表包括action表和 表，一般會(huì)把兩張表合并成一張表。ACTION表包含的動(dòng)作有移進(jìn)、 接受和報(bào)錯(cuò)四種。goto表、歸約二、計(jì)算題（每題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 對(duì)文法開始符H,有#H#存在，即有=，#,也即；，#d. #, b#。 對(duì)形如Pab，或PaQb，有a=b，由Ma|b得：a=b； 對(duì)形如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)項(xiàng)目集規(guī)范族為： 從上表(shn bio)可看出,不存在移進(jìn)-歸約沖突以及歸約歸約沖突，該文法是LR(0)文法。 從而有下面的LR(0)分析表： 第7-10章測(cè)試題班級(jí)(bnj) 學(xué)號(hào) 姓名(xngmng) 成績(jī)(chngj) 一、填空題1.常用的參數(shù)傳遞方式有 ， 和 。傳地址，傳值和傳名2.局部?jī)?yōu)化是 在范圍內(nèi)進(jìn)行的一種優(yōu)化?；緣K3一個(gè)名字的屬性包括 和_

11、_。類型、作用域二、選擇題1程序所需的數(shù)據(jù)空間在程序運(yùn)行前就可確定，稱為_管理技術(shù)。CA.動(dòng)態(tài)存儲(chǔ) B.棧式存儲(chǔ) C.靜態(tài)存儲(chǔ) D.堆式存儲(chǔ)2編譯程序絕大多數(shù)時(shí)間花在_上。DA.出錯(cuò)處理 B.詞法分析 C.目標(biāo)代碼生成 D.管理表格3. 優(yōu)化可生成 的目標(biāo)代碼。DA 運(yùn)行時(shí)間較短 B 占用存儲(chǔ)空間較小C 運(yùn)行時(shí)間短但占用內(nèi)存空間大 D運(yùn)行時(shí)間短且占用存儲(chǔ)空間小4下列 優(yōu)化方法不是針對(duì)循環(huán)優(yōu)化進(jìn)行的。CA.強(qiáng)度削弱 B刪除歸納變量 C刪除多余運(yùn)算 D 代碼外提二、語(yǔ)法制導(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)