編譯原理試題

1、編譯原理 試題計(jì)算機(jī)學(xué)院 2001級(jí) 班 學(xué)號(hào) 姓名題號(hào) 一 二 三 四 五 六 七 八 九 十 十一十二總分滿分 12 6 8 7 8 8 12 12 7 6 6 8 100得分一 選擇題（12 分）【 】1詞法分析器的輸入是 。A符號(hào)串 B源程序 C語(yǔ)法單位 D目標(biāo)程序【 】2兩個(gè)有窮自動(dòng)機(jī)等價(jià)是指它們的 。A狀態(tài)數(shù)相等 B有向弧數(shù)相等C所識(shí)別的語(yǔ)言相等 D狀態(tài)數(shù)和有向弧數(shù)相等【 】3文法 G：S xSx | y 所識(shí)別的語(yǔ)言是 。Axy*x B(xyx)* Cxx*yxx* Dx*yx*【 】4設(shè)a,b,c 為文法的終結(jié)符， 且有優(yōu)先關(guān)系 a b 和 b c，則 。A必有 a c B必有

2、 c aC必有 b a D選項(xiàng) A、B 和 C 都不一定成立【 】5若狀態(tài) k 含有項(xiàng)目“ A. ”，且僅當(dāng)輸入符號(hào) aFOLLOW(A時(shí)) ，才用規(guī)則“ A ”歸約的語(yǔ)法分析方法是 。AALR分析法 BLR(0) 分析法CLR(1) 分析法 DSLR(1)分析法【 】6生成中間代碼時(shí)所依據(jù)的是 。A語(yǔ)法規(guī)則 B詞法規(guī)則 C語(yǔ)義規(guī)則 D等價(jià)變換規(guī)則【 】7表達(dá)式（ ab）（cd）的逆波蘭表示為 。Aabcd BabcdCabcd Dabcd【 】8基本塊 。A只有一個(gè)入口語(yǔ)句和一個(gè)出口語(yǔ)句 B有一個(gè)入口語(yǔ)句和多個(gè)出口語(yǔ)句C有多個(gè)入口語(yǔ)句和一個(gè)出口語(yǔ)句 D有多個(gè)入口語(yǔ)句和多個(gè)出口語(yǔ)句二 判斷題（

3、6 分。認(rèn)為正確的填 “T”，錯(cuò)的填 “F”）【T 】1同心集的合并有可能產(chǎn)生“歸約 / 歸約”沖突?！綯 】2一個(gè)文法所有句子的集合構(gòu)成該文法定義的語(yǔ)言?！?】3非終結(jié)符可以有綜合屬性，但不能有繼承屬性。【T 】4逆波蘭表示法表示表達(dá)式時(shí)無(wú)需使用括號(hào)。【 】5一個(gè)有窮自動(dòng)機(jī)有且只有一個(gè)終態(tài)。【】6若過(guò)程 p 第 k 次被調(diào)用，則 p 的 DISPLAY 表中就有 k+1 個(gè)元素。三 填空題（8 分）1最常用的兩類語(yǔ)法分析方法是 自頂向下 和 自低向上分析法。2對(duì)于文法 GE ：ET|E+T T F|T*F F PF|P P (E)|i, 句型 T+T*F+i的直接短語(yǔ)為 ，句柄為 。* 且

4、a3在 LR(0) 分析法中，若 , VV 則稱“ A .”為 規(guī)約T項(xiàng)目，稱“ S .a”為 移進(jìn) 項(xiàng)目。4在 PL/0 的目標(biāo)代碼解釋執(zhí)行時(shí)，寄存器 B 總是指向當(dāng)前執(zhí)行過(guò)程活動(dòng)記錄的起始地址 ，而寄存器 T 總是指向 棧頂 。四（7 分）有窮自動(dòng)機(jī) M接受字母表 0,1 上所有滿足下述條件的串：串中至少包含兩個(gè)連續(xù)的 0 或兩個(gè)連續(xù)的 1。請(qǐng)寫(xiě)出與 M等價(jià)的正規(guī)式。五（8 分）構(gòu)造下列文法相應(yīng)的有窮自動(dòng)機(jī)。GS ： S aA | bQA aA | bB | bB bD | aQQ aQ | bD | bD bB | aAE aB | bFF bD | aE | b六（8 分）寫(xiě)一個(gè)文法，

5、使其語(yǔ)言是：L ambman bn | m,n 0 七（12 分）已知文法GA ： A aAB | aB Bb | d（1）構(gòu)造與 GA 等價(jià)的 LL(1) 文法；（2）構(gòu)造 GA 的預(yù)測(cè)分析表。八（12 分）考慮文法GS: S AS | bA SA | a（1）構(gòu)造文法的可歸前綴圖（活前綴的 DFA）；（2）判斷文法是否是 LR(0) 文法，并說(shuō)明理由。九（7 分）將下面程序段翻譯成四元式序列。while A<CB<D doif A=1 then C:=C+1else while A<D doA:=A+2;十（6 分）設(shè)有以下程序段program main;var a,b:

6、integer;procedure p(x,y,z:integer);beginy:=y+1;z:=z+xend ;begina:=2; b:=3; p(a+b,a,a); write(a)end .對(duì)于下列參數(shù)傳遞方式，分別寫(xiě)出執(zhí)行程序后 a 的輸出值。（1）傳名；（2）傳地址。十一（6 分）有一語(yǔ)法制導(dǎo)翻譯如下所示：S bAb print( ”1”) A (B print( ”2”) A a print( ”3”) B Aa) print( ”4”) 若對(duì)輸入序列 b(aa)a)a)b 進(jìn)行自底向上分析，請(qǐng)寫(xiě)出輸出序列。34242421十二（8 分）對(duì) PL/0 語(yǔ)言擴(kuò)充 ELSE 子句:

7、< 條件語(yǔ)句 > := IF <條件> THEN <語(yǔ)句> ELSE <語(yǔ)句> 請(qǐng)?jiān)诳杖碧幪羁?，完成條件語(yǔ)句的編譯算法：switch (SYM) case IFSYM:GetSym() ;CONDITION(SymSetUnion(SymSetNew(THENSYM),FSYS),LEV,TX);if (SYM=THENSYM) GetSym();else Error(16);CX1=CX; GEN(JPC,0,0);STATEMENT(SymSetUnion(SymSetNew(ELSESYM),FSYS),LEV,TX);if ( SYM!=

8、ELSESYM ) CODECX1.A=CX;else CX2=CX; GEN(JMP,0,0);CODECX1.A= cx ( 或者 cx2+1) ;STATEMENT(FSYS,LEV,TX);CODEcx2.A=cx ;break ;CP_sample答案題號(hào) 一 二 三 備 注1 B 自頂向下 自底向上2 C T,T*F , i T3 D 歸約 移進(jìn)4 D 起始地址 棧頂5 D 6 C 7 B8 A四 五 六G： SABa* (00 |11)(0 |1)*(0 |1) A A baAb| Bab aaB SaBb| Z b bbb DQ ba七修改后的文法 GA ：A aA Selec

9、t (A aA)=aA AB| Select (A AB)=a Select(A )=#,dB dB Select(B dB)=dBbB| Select(B bB)=b Select(B )=#Select(A AB) Select(A ) Select(B bB ) Select(B ) GA 為 LL(1) 文法預(yù)測(cè)分析表：a b d #A AaAA AAB A AB BdBB BbB B八（1）可歸前綴圖 （2）因?yàn)榇嬖跊_突，所以不是 LR(0) 文法。I1:S S.I5:A S.AA S.AA .SASA .SAA .aSA .aS .ASAS .ASS .b bS .b SA aaI

10、7:A SA.I0:S .S I2:A a. S A.SabS .AS S .ASaS .bA .SA aA .a A .a Sba bI6:S AS.SA AI4:S A.S A S.AA A .SAS .ASS .b A .aSA .SA S .ASAA .a S .b九100 （J <, A, C, 102 ） 或： 100 if A<C goto 102101 （J , , , 113 ） 101 goto 113102 （J <, B, D, 104 ） 102 if B<D goto 104103 （J , , , 113 ） 103 goto 113104 （J =, A, 1, 106 ） 104 if A=1 goto 106105 （J , , , 108 ） 105 goto 108106 （+, C, 1, C ） 106 C:=C+1107 （J , , , 112 ） 107 goto 112 ( 或 goto 100)108 （J , A, D, 110 ） 108 if A D goto 110109 （J , , , 112 ） 109 goto 112 ( 或 goto 100)110