編譯原理試題

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

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

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

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

5、使其語言是：L ambman bn | m,n 0 七（12 分）已知文法GA ： A aAB | aB Bb | d（1）構造與 GA 等價的 LL(1) 文法；（2）構造 GA 的預測分析表。八（12 分）考慮文法GS: S AS | bA SA | a（1）構造文法的可歸前綴圖（活前綴的 DFA）；（2）判斷文法是否是 LR(0) 文法，并說明理由。九（7 分）將下面程序段翻譯成四元式序列。while A<CB<D doif A=1 then C:=C+1else while A<D doA:=A+2;十（6 分）設有以下程序段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 .對于下列參數(shù)傳遞方式，分別寫出執(zhí)行程序后 a 的輸出值。（1）傳名；（2）傳地址。十一（6 分）有一語法制導翻譯如下所示：S bAb print( ”1”) A (B print( ”2”) A a print( ”3”) B Aa) print( ”4”) 若對輸入序列 b(aa)a)a)b 進行自底向上分析，請寫出輸出序列。34242421十二（8 分）對 PL/0 語言擴充 ELSE 子句:

7、< 條件語句 > := IF <條件> THEN <語句> ELSE <語句> 請在空缺處填空，完成條件語句的編譯算法：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答案題號 一 二 三 備 注1 B 自頂向下 自底向上2 C T,T*F , i T3 D 歸約 移進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) 文法預測分析表：a b d #A AaAA AAB A AB BdBB BbB B八（1）可歸前綴圖 （2）因為存在沖突，所以不是 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