東南大學(xué)歷年編譯原理試卷2.doc

東南大學(xué)歷年編譯原理試卷2%repeat_0 match=/data/option% %=title% %=count%票 %=percent%_repeat_0% 試題編號(hào):553試題名稱:編譯原理一:由文法G1構(gòu)造LR(1)部分分析表:1.列出4個(gè)項(xiàng)目集I0,I1,I2,I3;(如下圖)2.填寫LR(1)分析表的狀態(tài)0,1,2的action和goto表的內(nèi)容.(如下圖)G1: (0) ST (1) TT(T) (2) T I0:ST,# T I1: ( I2: T I3: - - - action goto 狀態(tài) ( ) # T 0 1 2. . .二:已知文法G2,請(qǐng)用類pascal語(yǔ)言寫出它的遞歸下降分析程序.G2: AB BX|BA XXa|Xb|a|b三:已知文法G3,要求:1.寫出各非終極符的首終極符集合和尾終極符集合;2.填寫opt表: + * i # + * i # G3: EE+T|T|T TT*F|F FpF|P pi四:請(qǐng)寫出產(chǎn)生下列語(yǔ)言的文法.1. L1=aibj|ij=12. L2=1|10,1*&1中包含0,1個(gè)數(shù)相等的任意串3. L3=2|2a,b*&2中a之后必定跟b4. L4=3+3|30,1*五:簡(jiǎn)要回答問(wèn)題.1.對(duì)編譯程序而言,模塊,遍,子程序這三個(gè)概念的主要區(qū)別?2.靜態(tài)存儲(chǔ)分配與動(dòng)態(tài)存儲(chǔ)分配的主要區(qū)別?3.何謂自適應(yīng)線性表?六:翻譯如下布爾表達(dá)式成四元式序列,結(jié)果留待填的真假鏈的四元式序號(hào).試題編號(hào):553試題名稱:編譯原理一:按算法構(gòu)造文法G1:S#M#M(L|aLM,a)的算符優(yōu)先矩陣.(即填寫下列矩陣) a , ( ) # a , ( ) # 二:將下列cfg文法修改成正規(guī)文法.SABAM|N|PBaB|aMbM|bNcN|cPP|三:已知文法G2:(1) SS(2) SAAA(3) S1A(4) S01.列出LR(0)項(xiàng)目集族;2.構(gòu)造SLR分析表;3.試給處語(yǔ)句01100#的LR分析過(guò)程.四:1.構(gòu)造由下列三型文法G3所對(duì)應(yīng)的FA.2.將構(gòu)造的FA確定化和最小化.3.寫出該DFA所識(shí)別的語(yǔ)言.G3: SaA|bS|dC AdE CaD|bC|b DbE|b EaD|bE|b五:設(shè)有源語(yǔ)句AI+1,J+2:=ABK+2,51.列出計(jì)算兩個(gè)數(shù)組的下標(biāo)地址(按行存放)AI+1,J+2的地址D1=?BK+2的地址D2=?2.按語(yǔ)法制導(dǎo)翻譯該語(yǔ)句成四元式序列.(設(shè)數(shù)組首地址分別為a,b;數(shù)組按行存放,每個(gè)元素占一字編址.數(shù)組說(shuō)明:A:array1.10,-5.5,B:array-5.5)六:求文法G4:ABCc|gDBBbcDE|CDab|caDdD|EgAf|c的各非終結(jié)符的隨符集.七:1.簡(jiǎn)述由基本塊尋找循環(huán)結(jié)點(diǎn)的算法.2.對(duì)于如下一段程序,若參數(shù)傳遞分別采用:(a)傳名 (b)傳結(jié)果 (c)傳地址試問(wèn)程序執(zhí)行結(jié)果,Y值是什么?proc Q(B,C)begin B:=B+2; B:=B*Cend;beginY:=2;Q(Y,2*Y);print(Y)end;3.文法G5:EPE|PPP*Q|QQQ+R|RR(E)|aa整常數(shù)試給出下列表達(dá)式計(jì)值結(jié)果(語(yǔ)法制導(dǎo)).3+2*52*2+32+(223)*2+3試題編號(hào):553試題名稱:編譯原理一:1.試寫一正規(guī)文法,使其定義的語(yǔ)言是不以0打頭的偶整數(shù)集合.其中數(shù)字可以用簡(jiǎn)名表示,比如10|2|4|6|8,并把1看作是終結(jié)符.2.試寫一上下文無(wú)關(guān)文法,它能產(chǎn)生下列語(yǔ)言:L=|a,b*,且中a的個(gè)數(shù)是b的兩倍,例如aab等二:請(qǐng)寫出由下列文法所確定的語(yǔ)言.1. G1: S10S01 SaA AbA Aa2. G2: SaSS Sa三:已知NFA的狀態(tài)轉(zhuǎn)換圖如下,試對(duì)它確定化并化簡(jiǎn),并寫出該FA接受的語(yǔ)言.b aSA d c a b bCDEb b ba bT 四:已知文法G4:SSSASSbASAAa1.試求closure(SS,#)和GO(closure(SS,#),S)2.文法是LR(1)嗎?為什么?五:試將下面語(yǔ)句按語(yǔ)法制導(dǎo)翻譯成四元式序列.while (ac) and (bd) doif a=1 then c:=c+1else while aM goto (19)(3) J:=1(4) if JN goto (17)(5) T1:=I*N(6) T2:=T1+J(7) T3:=addr(A)-C(8) T4:=I*2(9) T5:=J+2(10) T6:=T4*N(11) T7:=T6+T5(12) T8:=addr(A)-C(13) T9:=T8T7(14) T3T2:=T9(15) J:=J+1(16) goto (4)(17) I:=I+1(18) go