北京理工大學計算機科學與技術類《編譯原理與設計》試卷B(2018.06)

1、0課程編號： COM07017北京理工大學 20172018 學年第二學期計算機科學與技術類編譯原理與設計試卷 B (2018.06)班級 學號 姓名 成績題號 一 二 三 四 五 六 七 八 九 總分成績* 注意：各題均必須答在試卷上，書寫不下可以寫在試卷背面。一判斷題 （ 10 分）在下面答題表中填上 “ 或”“。 ”題號 1 2 3 4 5 6 7 8 9 10答案1. 通常情況下 C 語言程序是編譯執(zhí)行的， Python 語言程序是解釋執(zhí)行的。2. 對集合 A，有 A+=AA* ，所以對任意集合 A, 一定有 A+ A*。3. DISPLAY 表用來記錄每層過程的最新活動記錄地址，它的

2、大小在運行時確定。4. 文法若存在左公因子， 則在自上而下語法分析過程中會因為無匹配操作而出現(xiàn)死 循環(huán)。5. 二義文法一定不是上下文有關文法。6. 句柄是最長活前綴的一個后綴。7. 單詞的屬性字一般應該包括單詞類別和單詞的內碼。8. LR 分析過程中使用的分析棧分為兩部分：狀態(tài)棧和符號棧。9. DFA M 的狀態(tài)表表示如下圖，則該 DFA 可以接受符號串 0100110000111。00 0 11 1 1 12 3010語法制導翻譯方法只能用來產生中間代碼，不能用來生成目標代碼。1二、單項選擇題 ( 在下面答題表中填上答案 ) （10 分）題號 1 2 3 4 5 6 7 8 9 10答案1如

3、下圖所示，循環(huán)不變運算“ j=4”不能提到循環(huán)外面的原因在于【 】A） j 所在的結點不是循環(huán)的所有出口結點的必經結點；B） j 在 L 中其它地方被定值；C）循環(huán)中所有 j 的引用點不是只有循環(huán)中 j 的定值才能到達；D） j 在離開 L 后不再是活躍的；j=1B0 k=3B1i=u+v+jB2 m=8u=u+1if uv goto B3j=4if v=20 goto B2B3B4 m=k2 Yacc 實現(xiàn)用到的算法是（ ）A) 子集法 B) 正規(guī)式轉為 NFAC) 劃分法 D) LALR(1) 項目集規(guī)范簇構造3第十章 PL/0 編譯程序的語法分析程序用的語法分析方法為【 】A)LR 分析

4、法 B)算符優(yōu)先分析法 C)LL(1) 分析表4基本塊優(yōu)化中 不能完成的優(yōu)化工作是【 】A) 刪除公共子表達式 B)常量合并 C)刪除無用賦值5引入中間代碼的目的不包括【 】D)遞歸下降分析法D)運算強度削弱6數(shù)據(jù)流方程 ?(? = ? ?(?(?) 用來計算的數(shù)據(jù)流信息為 【 】。A) 方便生成目標代碼 B)便于優(yōu)化 C) 減少對主存容量的要求 D)便于移植 ?(?) (?(?)?(?)?(?)A ）到達定值 B）活躍變量 C）可用表達式 D）以上都不是27在語句 Z=X*Y-H 中，定義性出現(xiàn)的變量是【 】A)Z B)X C)Y D)H8設有文法 S SS*|SS+|a，則下面的符號串是該

5、文法的句子的是【 】A)aa+0* B)aa+aa*+a C)aa+aaa*+ D) aS+a*9設有 C 語言程序段如下：While(i=j)m=0;printf( “m=%dn”,m);i+;則經過詞法分析后可以識別的單詞個數(shù)是【 】A)20 B)21 C)22 D)2310如下圖所示的程序控制流圖中有【 】個循環(huán)60 1 2 3 4 58 7A)1 B)2 C)3 D)4三填空題 （23 分）1. 設有字母表 = a,b上的語言 L(G)= aibj|1 j i 2j ，描述該語言的上下文無關文法【2. 字符串 的長度為 n，則字符串【 】個。的前綴有【】個，字符串】。的子串有3 EQN

6、的編譯器是用 C 語言編寫的將 EQN文本轉化為格式化的 TROFF文本，用 T 型圖 描述怎么借助 PDP 11 機器上運行的 C語言編譯器得到 PDP 11機器上可運行的 EQN的編譯器【 】。4. 設有文法 GA：A a|(R) T A， T|A R T根據(jù)上述文法填寫如下的算符優(yōu)先關系表：a ( ) ， #，3】。 】。5. 設有文法 GA：A BCc|eDB B |bcD C DaB|ca D |dD根據(jù)上述文法填寫如下 LL(1) 分析表的內容：a b c d #D6. 設有文法：S aSDe|a D Db|b與該文法等價的 LL(1) 文法為【7. 下表為右圖所示流圖的到達定值信

7、息， 則變量 d在 d4點的 ud鏈為【in(B1)out(B1) 1(b),2(c)in(B2) 1(b),2(c),3(a),4(d),5(d),6(c),7(e)out(B2) 1(b),2(c),3(a),4(d),6(c),7(e)B1B2d4： d=d-cd3： a=b+cB3B5B4B68. a+b*( c+d)*( e+f) 的逆波蘭式為【9. 設有文法 GA：A AB+|B B BC*|C C C |a該文法的句型 BBC*+ 的直接短語是【句柄是【 】。10. C 語言程序段：J=1；B=(5 * J - 2)+J ；優(yōu)化后的四元式代碼為【的優(yōu)化技術是【】?！?，素短語是【

8、】，】；使用】。4四 . 解答題設 DFA M 的狀態(tài)圖如下，給出a b0 b 1 a（ 8 分）M 所識別語言的正規(guī)式表示 (要求給出求解的過程 )a,ba 2 b 3五 . 解答題用子集法將下面的最小化過程） 。（ 9 分）NFA 確定化，用劃分法將確定化的 DFA 最小化（要求給出確定化和2a a0 1 43a,b5六 . 解答題設有下列文法 GS ： S S(S)| 1.將下圖的識別該文法0： SS1： SSS， # S(S)| ，SS ， # S (S)，7： S S(S) ，(12 分）|LR(1) 項目有效活前綴的 DFA 補充完整。(b2： S S( S)，S S(S)| ，6

9、： S S(S )，S S (S)，SS4： S S(S) ，)3： S S(S )，S S (S)，(5： S S( S)，S S(S) ，2.根據(jù)上面的state0123DFA ，填寫該文法的如下部分ACTION( )6LR(1)分析表。#GOTOS1state七 解答題 （12 分）設有文法：S S S|S S|S S| S|0 |11.證明文法為二義性文法。|2.原則上二義文法不能使用 LR 分析， 但是根據(jù)一定的約定原則， 構造出無二義性的 LR分析表， 就可以應用于該文法的分析。 設構造出的該文法的無二義性的 LR 分析表如下：ACTION GOTO01234567891011S5

10、r5r6S5r1S5S5S6r5r6S6r1r2S6S7r5r6S7r1r2r3S2S2r5r6S2S2S2r4r1r2r30S3S3r5r6S3S3S3r4r1r2r31S4S4r5r6S4S4S4r4r1r2r3#accr5r6r4r1r2r3S1891011根據(jù)上述 LR 分析表，給出句子 0 1 1 0 0 1 的 LR 分析過程的前 11 步。7步驟 狀態(tài)棧0 0符號棧#待掃描符號串 分析動作0 1 1 0 0 1#123456789103.畫出句子 0 1 1 0 0 1 的語法分析樹。8八解答題 （10 分）有下列 C 語言程序段 :int j;int sum = 0;for(i

11、nt i = 2; i = i) goto L2;if(i % j = 0) goto L1;j+;L1:sum+;L2:;將該程序段對應的四元式形式的中間代碼填入下表中；注意：A) 無條件轉移操作符用“ j”表示，條件成立轉移的操作符用“ jT”表示，條件不成立轉 移的操作符用“ jF ”表示；B)語句標號的地址使用四元式序列的序號表示 ，序號用，表示。序號 四元式代碼 四元式代碼1 142 153 164 175 186 197 208 219 2210 2311 2412 2513 269九 . 解答題 （6 分）對如下的 x86 匯編代碼片段，劃分基本塊（基本塊劃分直接標記在源代碼中） ，并給出程序流圖。movL1:movcmp jleL2:movidiv test je L3 inc cmp jl L2L3:inccmp jl L1ecx, 2esi, 2ecx, esiL3