編譯原理第1階段練習(xí)題2020年上半年江南大學(xué)考試題庫及答案

1、江南大學(xué)網(wǎng)絡(luò)教育第一階段練習(xí)題考試科目：編譯原理第 章至第 章（總分100分）學(xué)習(xí)中心（教學(xué)點）批次： 層次:專業(yè)： 學(xué)號： 身份證號： 姓名：得分:單選題（共4題，總分值20分，下列選項中有且僅有一個選項符合題目要求, 請在答題卡上正確填涂。）1.若一個文法是遞歸的，則它所產(chǎn)生的語言的句子是（）。（5分）A.無窮多個B.有窮多個C.可枚舉的2 .文法 GA : Afe AaB B-Ab 8-2是（）。（5 分）A. 0型文法B. 1型文法C. 2型文法3 .詞法分析器的輸入是（）。（5分）A.單詞符號串B.源程序C.語法單位D.個數(shù)是常量D. 3型文法D.目標(biāo)程序4. 一個上下文無關(guān)文法 G

2、包括四個組成部分，它們是：一組非終結(jié)符號，一組終結(jié)符號,個開始符號，以及一組（）。（5分）A.句子B.句型C.單詞D.產(chǎn)生式第 3 頁 /共16頁二填空題（共2題，總分值10分）5 .編譯程序的功能可以分解為詞法分析、語法分析、 、中間代碼生成、中間代碼優(yōu) 化、目標(biāo)代碼生成。（5分）6 .微小語言Micro的單詞有下面的幾種： 標(biāo)識符、實常數(shù)、保留字、換行符。（5分）三 簡答題 ( 共 2 題 ，總分值20 分 )7 .給出與正規(guī)式 R= 1(0|1)*101等價的NFA(10分)8 .寫出下面程序經(jīng)詞法分析后的TOKENS示。begin var X:real;var J:integer;re

3、ad(J);J:=J+(J*20);X:=J-1;Write(2*J+X)End ( 10 分)四 綜合計算題( 共 2 題 ，總分值50 分 )9 .已知文法 G(S) Sfa|(T) T S|S寫出句子(a, a), a)的規(guī)范歸約過程及每一步的歸約規(guī)則和句柄。(25分)10 . 已知文法GE 為：E-T|E+T|E-T T fF|T*F|T/F F f(E) |i 該文法的開始符號(識別符號)是什么？ 請給出該文法的終結(jié)符號集合Vt 和非終結(jié)符號集合Vn 。 找出句型T+T*F+i 的所有短語、簡單短語和句柄。( 25 分)一 單選題 （ 共 4 題 ， 總分值 20 分 ， 下列選項中

4、有且僅有一個選項符合題目要求， 請在答題卡上正確填涂。）1 . 答案：A解析過程：2 . 答案：D解析過程：3 . 答案： B解析過程：4 .答案：D解析過程：二填空題（共2題，總分值10分）5 .答案：語義分析解析過程：6 .答案：整常數(shù)，符號詞解析過程：三簡答題（共2題，總分值20分）7.答案：解析過程：i$colon$real$semi$line8.答案：$begin解：$var($id,X)$var($id,J)$colon$integer$semi$line$read$LParend,J)$RParen$semi$line($id,J)$assign($id,J)$plus$Lpar

5、en($id,J)$mult($intC,20)$RParen$semi$line($id,X)$assign($id,J)$subs($intC,1)$semi$line$write$LParen($intC,2)$mult($id,J)$plus($id,X)$RParen$semi$End解析過程:四綜合計算題（共2題，總分值50分）9 .答案：解： 句型 歸約規(guī)則 句柄(a ,a),a)Sa a(S ,a),a)T-S S(T ,a),a)S一 a a(T ,S),a)TS T, S(S) , a) T -S S(T) , a) S - (T) (T)(S, a) T -S S(T ,

6、 a) S 一 a a(T, S) T 一T, S T, S(T) S - (T) (T)S解析過程：10 .答案：解： 該文法的開始符號（識別符號）是 E。i。非終結(jié)符號集合 Vn=E、T、F。 該文法的終結(jié)符號集合Vt=+、-、*、/、句型T+T*F+I的短語為i、T*F、第一個 T、T+T*F+i;簡單短語為i、T*F、第一個T;句柄為第一個To 解析過程:考試科目：編譯原理第 章至第 章（總分100分）學(xué)習(xí)中心（教學(xué)點）批次： 層次:專業(yè)： 學(xué)號： 身份證號： 姓名：得分：單選題（共4題，總分值20分，下列選項中有且僅有一個選項符合題目要求, 請在答題卡上正確填涂。）1.有限狀態(tài)自動機

7、能識別（）。（5分）A.上下文無關(guān)文法B.上下文有關(guān)文法C.正則文法2.文法 GE:E 一 E+T|T,T-T*P|P,P 一（E）|I,則句型P+T+i的短語有（A.i,P+T 3.A.尋找句柄4.在語法分析處理中,A.非終極符集B. pP+T,i,P+T+i在自底向上的語法分析方法中，分析的關(guān)鍵是（C. P+T+i）。（5 分）D.短語文法）。（5 分）D. pP+T,iB.尋找句型C.消除遞歸D.消除公共前綴FIRST 集合、FOLLOW合、SELECT集合者B是（）。（5 分）B.終極符集C.字母表D.狀態(tài)集二填空題（共2題，總分值10分）5 .文法要滿足兩個條件： 和 才可以使用自頂

8、向下的語法分析方法。（5分）6 .是這樣一種動作文法，即動作符只出現(xiàn)于產(chǎn)生式的末尾。（5分）三簡答題（共2題，總分值20分）7 .若有文法GS為：S->Ac|aBA->dfB->be ，請寫出語言 L（GS）的全部元素。 （10分）8 .文法GS為：S 一 VV一 T|ViT第7頁/共16頁T-F| T+FF-)V*I(試給出句型ViFi( 的短語，簡單(直接)短語,句柄。( 10 分)四 綜合計算題( 共 2 題 ，總分值50 分 )9. 寫出表達(dá)式(a b*c)/(a b) d 的逆波蘭表示和三元式序列。( 25 分)10. 下面的文法是不是LL(1) 文法？若是，請構(gòu)造

9、相應(yīng)的LL(1) 分析表。S f aD D - STe | T f bH | H H f d |625 分)第 9 頁 /共16頁一 單選題 （ 共 4 題 ， 總分值 20 分 ， 下列選項中有且僅有一個選項符合題目要求， 請在答題卡上正確填涂。）1. 答案：C解析過程：2. 答案：B解析過程：3. 答案：A解析過程：4. 答案：B解析過程：二 填空題 （ 共 2 題 ，總分值10 分 ）5. 答案：沒有左遞歸, 沒有公共前綴解析過程：6. 答案：尾動作文法解析過程：三簡答題（共2題，總分值20分）7. 答案：解：因為 S=>Ac=>dfcS=>aB=>abe所以 L

10、（GS尸a b c d e f解析過程：8. 答案：解：句型ViFi（的語法樹如下F是句型ViFi（相對于T的短語、簡單短語、句柄（是句型ViFi（相對于F的短語、簡單短語（是句型ViFi（相對于T的短語ViF是句型ViFi（相對于V的短語ViFi（是句型ViFi（相對于V的短語ViFi（是句型ViFi（相對于S的短語解析過程：四綜合計算題（共2題，總分值50分）9. 答案：解：逆波蘭表示：abc* +ab+/d 三元式序列：(1)(*, b, c)(2)(+, a, (1) (+, a, b)(4)(/, (2), (3)(，(4), d)解析過程：10. 答案：解：Predict(S 一

11、aD尸first(aD尸aPredict(Df STe尸first(STe尸aPredict(D一 e 尸follow(D)=#,b,d,ePredict(T一bH)=first(bH尸bPredict"一H)=firs)(Hfollow(T)=d,ePredict(H一d)=first(d)=dPridict(H一e )=follow(H)=e所以該文法是LL文法，LL(1汾析表如下表：a亡bdS1D25333I545H76解析過程:考試科目：編譯原理第 章至第 章（總分100分）學(xué)習(xí)中心（教學(xué)點）批次： 層次:專業(yè)： 學(xué)號： 身份證號： 姓名：得分:單選題（共4題，總分值20分，

12、下列選項中有且僅有一個選項符合題目要求,請在答題卡上正確填涂。）（5分）C.符號表D.程序變量B.運行時間短但占用內(nèi)存空間大D.運行時間短且占用存儲空間?。?分）C.語法檢查D.地址分配（5分）C.刪除多余運算D.代碼外提1 .四元式之間的聯(lián)系是通過（）來實現(xiàn)的。A.指示器B.臨時變量2 .優(yōu)化可生成（）的目標(biāo)代碼。（5分）A.運行時間較短C.占用存儲空間較小3 .在目標(biāo)代碼生成階段，符號表用于（）。A.目標(biāo)代碼生成B.語義檢查4 .下列（）優(yōu)化方法不是針對循環(huán)優(yōu)化進(jìn)行的。A.強度削弱B.刪除歸納變量二填空題（共2題，總分值10分）5 . 優(yōu)化可分為 、 和全局優(yōu)化三種。（5分）6 .語法分析

13、是依據(jù)語言的 規(guī)則進(jìn)行的，中間代碼產(chǎn)生是依據(jù)語言的 規(guī)進(jìn)行的。 （5分）三簡答題（共2題，總分值20分）7 .什么是活動記錄？它主要由哪些內(nèi)容構(gòu)成？（10分）8 .寫出表達(dá)式 A*（B/C-D）+E/F的逆波蘭中間代碼。 （10分）四綜合計算題（共2題，總分值50分）9 .文法GM及其LR分析表如下，請給出對串 dada#的分析過程。狀態(tài)ACTIONGOTOdeaSBV0r3S3121ace234P 3r24r6S5r665r4r4r 6S7rl1S83r5工5GM: 1) S VdB3) V 一 e5) B fBda2) V 一 e4) B fa6) B 一 e（25 分）10 .試寫出算術(shù)

14、表達(dá)式a+b*c-（c*b+a-e）/（b*c+d）優(yōu)化后的四元式序列。（25分）第13頁/共16頁一 單選題 （ 共 4 題 ， 總分值 20 分 ， 下列選項中有且僅有一個選項符合題目要求， 請在答題卡上正確填涂。）1. 答案：B解析過程：2. 答案：D解析過程：3. 答案：D解析過程：4. 答案：C解析過程：二 填空題 ( 共 2 題 ，總分值10 分 )5. 答案：局部優(yōu)化, 循環(huán)優(yōu)化解析過程：6. 答案：語法, 語義解析過程：三 簡答題 ( 共 2 題 ，總分值20 分 )7. 答案： 解： 一個過程的一次執(zhí)行所需信息的管理，是通過稱為活動記錄的連續(xù)存儲塊來實現(xiàn)的?；顒佑涗浀闹饕獌?nèi)容

15、有：(1)臨時變量域存放目標(biāo)程序臨時變量的值；(2)局部數(shù)據(jù)域存放過程本次執(zhí)行時的局部數(shù)據(jù)、簡單變量及數(shù)組內(nèi)情向量等；(3)機器狀態(tài)域保存在調(diào)用過程前有關(guān)機器狀態(tài)的信息，包括各寄存器的當(dāng)前值及返回地址等；(4)存取鏈為訪問其它活動記錄中所存放的非局部數(shù)據(jù)所提供的鏈地址；(5)控制鏈指向主調(diào)過程的活動記錄；(6)實參存放主調(diào)過程為被調(diào)用過程所提供的實參信息；(7)返回值為主調(diào)過程存放被調(diào)過程的返回值解析過程：8. 答案：解：ABC/D-*EF/+解析過程：四 綜合計算題( 共 2 題 ，總分值50 分 )第 15 頁 /共16頁狀態(tài)棧符號棧輸入流動作so4 I 二n口S0S25V便S4SOS2S4#VdS5SOS2S4S5#Vdada#r4SOS2S4S6WdBS7S0S2S4S6S7VdBda#SESOS2S4S6S7SE#VdBdarSSOS2S4S6#VdB=rlSOS11 Jace9. 答案：解：解析過程：10. 答案：解：該表達(dá)式的四元式序列為：(1)(*, b, c, T1)(2)(+, a, T1, T2)(3) (*, c, b, T3)(4) (+