編譯原理期末試卷(含答案)

1、編譯原理試題計算機學(xué)院2001級 班 學(xué)號 姓名 題號一二三四五六七八九十十一十二總分滿分126878812127668100得分一 選擇題（12分）【 】1詞法分析器的輸入是 。A符號串 B源程序 C語法單位 D目標(biāo)程序【 】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設(shè)a,b,c為文法的終結(jié)符，且有優(yōu)先關(guān)系aºb和bºc，則 。A必有aºc B必有cºa C必有bº

2、a D選項A、B和C都不一定成立【 】5若狀態(tài)k含有項目“A.”，且僅當(dāng)輸入符號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有多個入口語句和多個出口語句二 判斷題（6分。認為正確的填“T”，錯的填“F”）【T

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

4、目，稱“S ®a.a”為移進 項目。4在PL/0的目標(biāo)代碼解釋執(zhí)行時，寄存器B總是指向當(dāng)前執(zhí)行過程活動記錄的起始地址 ，而寄存器T總是指向棧頂 。四（7分）有窮自動機M接受字母表S0,1上所有滿足下述條件的串：串中至少包含兩個連續(xù)的0或兩個連續(xù)的1。請寫出與M等價的正規(guī)式。五（8分）構(gòu)造下列文法相應(yīng)的有窮自動機。GS：S aA | bQ A aA | bB | b B bD | aQ Q aQ | bD | b D bB | aA E aB | bF F bD | aE | b 六（8分）寫一個文法，使其語言是：L ambmanbn | m,n0 七（12分）已知文法GA：A aAB

5、 | a B Bb | d（1）構(gòu)造與GA等價的LL(1)文法；（2）構(gòu)造GA的預(yù)測分析表。八（12分）考慮文法 GS: S AS | b A SA | a（1）構(gòu)造文法的可歸前綴圖（活前綴的DFA）；（2）判斷文法是否是LR(0)文法，并說明理由。九（7分）將下面程序段翻譯成四元式序列。whileA<CB<Ddoif A=1 then C:=C+1 else while A<D do A:=A+2;十（6分）設(shè)有以下程序段program main;var a,b:integer;procedure p(x,y,z:integer); begin y:=y+1; z:=z+x

6、 end;begin a:=2; b:=3; p(a+b,a,a); write(a)end.對于下列參數(shù)傳遞方式，分別寫出執(zhí)行程序后a的輸出值。（1）傳名；（2）傳地址。十一（6分）有一語法制導(dǎo)翻譯如下所示：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子句: <條件語句> := IF <條件> THEN <語句> ELSE <語句> 請在空

7、缺處填空，完成條件語句的編譯算法：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!=ELSESYM ) CODECX1.A=CX;else CX2=CX; GEN(JMP,0,0); CODECX1.A= cx (或

8、者cx2+1) ; STATEMENT(FSYS,LEV,TX); CODEcx2.A=cx ;break; CP_sample答案題號一二三備 注1B自頂向下 自底向上2CT,T*F , i T3D歸約 移進4D起始地址 棧頂5D6C7B8AZSABDQabaabbbbbbaa四 五 六G：SAB AaAb| BaBb|七修改后的文法GA ： AaA Select (AaA)=a AAB|Select (AAB)=a Select(A)=#,d BdB Select(BdB)=dBbB|Select(BbB)=b Select(B)=#Select(AAB) Select(A)FSelect

9、(BbB) Select(B)F GA為LL(1)文法預(yù)測分析表： abd#AAaAAAABAABBdBBBbBB八（1）可歸前綴圖 （2）因為存在沖突，所以不是LR(0)文法。九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 AD goto 110109（J, , , 112） 109 goto 112 (或goto 100)110（+，