廣工編譯原理(精選題集+必考大題

1、編譯原理期末試題(二)1、描述由正規(guī)式b*(abb*)*(a| )定義的語言，并畫出接受該語言的最簡(jiǎn)DFA。2、證明文法 E E + id | id是SLR(1)文法。3、下面是表達(dá)式和賦值語句的文法，其中 and的類型是bool bool bool , +的類型是 int int int,=的類型是int int bool ,:=要求id和E的類型都是int或者都是bool。 為該文法寫一個(gè)語法制導(dǎo)定義或翻譯方案，它完成類型檢查。S id := EE E and E | E + E | E = E |id6、描述由正規(guī)式 b a(bb a) b定義的語言，并畫出接受該語言的最簡(jiǎn)DFA。7、下

2、面的文法產(chǎn)生代表正二進(jìn)制數(shù)的0和1的串集：B B 0 | B 1 | 1下面的翻譯方案計(jì)算這種正二進(jìn)制數(shù)的十進(jìn)制值：B B 0 B.val := B1.val 2 | B 1 B.val := B1.val 2 +1|1 B.val := 1 請(qǐng)消除該基礎(chǔ)文法的左遞歸，再重寫一個(gè)翻譯方案，它仍然計(jì)算這種正二進(jìn)制數(shù)的十進(jìn) 制值。編譯原理試卷二答案1、由正規(guī)式b*(abb*)*(a|)定義的語言是字母表a, b上不含子串a(chǎn)a的所有串的集合。最簡(jiǎn)DFA如下：start2、先給出接受該文法活前綴的DFA如下:word范文I0和I3都只有移進(jìn)項(xiàng)目，肯定不會(huì)引起沖突；I2和I4都無移進(jìn)項(xiàng)目并僅含一個(gè)歸約項(xiàng)

3、目，也肯定不會(huì)引起沖突；在Ii中，E的后繼符號(hào)只有$,同第2個(gè)項(xiàng)目的展望符號(hào)“ + ”不一樣,因此Ii也肯定不會(huì)引起沖突。由此可以斷定該文法是SLR(1)的。3、語法制導(dǎo)定義如下。S id := E S.type := if (id .type = bool and E.type = bool) or (id .type = int and E.type = int) then type_ok else type_error EEi and E2 E.type := if E1.type = bool and B.type = bool then bool elsetype_error EEi

4、 +E2E.type:=if Ei .type = int andE.type = intthenint else type_error EEi =E2E.type:=if E1.type = int andE.type = intthenbool else type_error EidE.type:=lookup(id.entry) 6、正規(guī)式b a(bb a) b體現(xiàn)的特點(diǎn)是，每個(gè) a的左邊都有若干b,除非a是第一個(gè)字母。該正規(guī)式定義的語言是： 至少含一個(gè)a,但不含子串a(chǎn)a的所有a和b的串集。最簡(jiǎn)DFA如下:7、消除左遞歸后的文法:B 1 BB 0 B | 1 B | 相應(yīng)的翻譯方案如下：

5、B 1 B .i := 1 B B.val := B .valB 0 B 1.i := B .i 2 B 1 B.val := B1.val|1 B 1.i := B .i 2 +1 B 1 B .val := B 1.val| B .val := B .i編譯原理期末試題(三)1、從優(yōu)化的范圍的角度，優(yōu)化可以分哪兩類？對(duì)循環(huán)的優(yōu)化可以有哪三種?答：從優(yōu)化的范圍的角度，優(yōu)化可以分為局部?jī)?yōu)化和全局優(yōu)化兩類；對(duì)循環(huán)的優(yōu)化有三種：循環(huán)不變表達(dá)式外提、歸納變量刪除與計(jì)算強(qiáng)度削減。2、寫出表達(dá)式a=b*c+b*d對(duì)應(yīng)的逆波蘭式、四元式序列和三元式序列答：逆波蘭式： abc*bd*+:=四元式序列:三元式

6、序列：OP ARG1 ARG2(*, b, c,功(* b, c )(*, b, d,t2)(* b, d )(+, t1, t2, t3)(k，t3,/, a)(+(1),(2)(尸(3), a)3、對(duì)于文法G(S):S bMbM (L |aLMa)答.1) S bMb b(Lb b(Ma)b2) 短語：Ma), (Ma), b(Ma)b直接短語：Ma)句柄：Ma)三、 設(shè)有字母表a, b上的正規(guī)式R=(ab|a)*解：(1)(2)將(1)所得的非確定有限自動(dòng)機(jī)確定化£ab-011312+3(3)對(duì)(2)得到的DFA化簡(jiǎn)，合并狀態(tài)0和2為狀態(tài)2:(4)令狀態(tài)1和2分別對(duì)應(yīng)非終結(jié)符B

7、和AG: A一aB|a|e ; B-aB|bA|a|b| e ;可化簡(jiǎn)為：G: AaB| e ;B- aB|bA| £四、 設(shè)將文法G改寫成等價(jià)的LL(1墳法，并構(gòu)造預(yù)測(cè)分析表。G: S-S*aT|aT|*aT； T一 +aT|+a解：消除左遞歸后的文法 G': S-aTS'|*aTS'S' 一*aTS' | £T-+aT|+a提取左公因子得文法G'':S-aTS |*aTS'S'一*aTS | &T-+aT'一 T|eSelectaTS' )=aSelect(A *aTS

8、9; )=*Select(A aTS' )n Select(Sf *aTS')=Select(S' 一*aTS' )=*Select(S' - e)=Follow(s ' )=#Select(S' 一*aTS' )n Select(S 一 0二Selecg +aT，)=十Select"' fT尸F(xiàn)irst(T) =+Select(下 一 0=Follow(T' )=*,#Select"' fT) n Select(丁 £)=所以該文法是LL文法。預(yù)測(cè)分析表：*+a#S一*aTS

9、'一 aTSS，一*aTS'£T一+aT'£一 T£6設(shè)文法G為:S- A; ABA| £ aB|b解：(1)拓廣文法 G，:(0) S' 6 (1) S->A (2) A-BA(3) A一44) AaB (5)Bfb ; FIRST(A)=化 a, b; FIRST(B) = a, b構(gòu)造的DFA如下:出a I b IB- aS, a I b I- lb 1*116：IT：10S'6工劃Si及 £at*ba, ft M>3 tCO*b, |b|胡Ca->b*a,性 1MLA"

10、*，京IEb->-*b, E I b I #2CB-> *b. a I b I項(xiàng)目集規(guī)范族看出，不存在沖突動(dòng)作。，該文法是 LR(1墳法。(2) LR(1汾析表如下:狀態(tài)ActionGotoB/sAB0S4弱r31*31acc2rl3SiSir36S4S4國(guó)75rar5r56r27rlrl輸入用abab的分析過程為:步驟狀態(tài)棧符號(hào)技當(dāng)甫宇將剩余字符出動(dòng)作0磊ab&bu移進(jìn)(2)04rfa.balrf移進(jìn)045ijaba舊的B->b(4)047標(biāo)bB3bff歸的B4aE03圮abu移進(jìn)034鋁ELb壯移造0315典的B->b0317鋁oB#也打B->nB(9

11、)心3哪歸妁A-> e'10：0336ifBBA#典約ATBA(11)036SBA歸例A4EA(12)02"A白約SA0比件acc五、給定文法GS:S-aA|bQ; A-aA|bB|b; B-bD|aQ ; Q-aQ|bD|b ; D-bB|aA ;Ef aB|bFF-bD|aE|b構(gòu)造相應(yīng)的最小的DFA用子集法將NFA確定化:解：先構(gòu)造其NFA:Sa Ab QAABZccQQ cDZBZ r7QADDZAB r)D QA B n將 S、A、Q、BZ、DZ、D、B 重新命名,因?yàn)?、4中含有z,所以它們?yōu)榻K態(tài)。令巳=(0,1,2,5,6 , 3,4)用 b進(jìn)行分割：P1

12、= ( 0,5, 6 , 1,2 , 3,4)再用 b進(jìn)行分割：P2= ( 0 , 5, 6 , 1,2 , 3,4)再用 a、b 進(jìn)行分割，仍不變。再令0為 A, 1,2為8, 3, 4為C, 5, 6為D。最小化為右上圖。編譯原理期末試題（四）一、簡(jiǎn)述編譯程序的工作過程。 （10）詞法分析語法分析語義分析代碼優(yōu)化目標(biāo)代碼生成Li=an bn | n>1三、給出下面語言的相應(yīng)文法：(15)L2=anbm+nam| n > 1, m > 0G1 aAb |ab-ABA - aAb | abB -bBa| £四、對(duì)下面的文法 G:S 一 a | b | (T)T-T,

13、 S | S(1)消去文法的左遞歸，得到等價(jià)的文法G2;(2)判斷文法G2是否LL (1)文法，如果是，給出其預(yù)測(cè)分析表。(15)G2:Sf a | b | (T) T- ST' 一，S 丁 | £G2是LL (1)文法。ab()#SSf aSf bS一(T)TT- ST'T- ST'T- ST'T，一 g 一，S五、設(shè)有文法GA:AfBCc | gDBB bCDE | £Cf DaB | caD-dD | £gAf | c(1)計(jì)算該文法的每一個(gè)非終結(jié)符的FIRST集和FOLLOW集;(2)試判斷該文法是否為 LL (1)文法。(

14、15)FIRSTFOLLOWABA,b,c,d,g bA,c,dCA,c,dC,d,gDDA,b,c,gEC,g是LL （1）文法。七、有定義二進(jìn)制整數(shù)的文法如下：L 一 LB | BB -0 | 1(15)構(gòu)造一個(gè)翻譯模式，計(jì)算該二進(jìn)制數(shù)的值（十進(jìn)制的值） 引入L、B的綜合屬性val,翻譯模式為：S 一 Lprint（L.val）L 一LiBL.val= Li.val*2+B.valL -BL.val= B.valB 0B.val=0B 1B.val=1編譯原理期末試題（五）有窮自動(dòng)機(jī)M接受字母表 =0,1上所有滿足下述條件的串：每個(gè) 1都有0直接跟在右邊。構(gòu)造一個(gè)最小的 DFA M及和M等

15、價(jià)的正規(guī)式。四證明正規(guī)式（ab）*a與正規(guī)式a（ba）*等價(jià)（用構(gòu)造他們的最小的 DFA方法）【答案：四正規(guī)式Cahj .山對(duì)應(yīng)的麗良加圖.j文兩個(gè)TF機(jī)式最線都可得到最商的DFA如圖所示.所以這兩個(gè)正就式等。Q五 寫一個(gè)文法，使其語言是:L = InOmlmOn | m,n>0 五文法 G: S -1S0 | AA - 0A1 | £六對(duì)文法GSS aSb | PP f bPc | bQcQ f Qa | a(1)它是否是算符優(yōu)先文法？請(qǐng)構(gòu)造算符優(yōu)先關(guān)系表(2)文法GS消除左遞歸、提取左公因子后是否是LL (1)文法？請(qǐng)證實(shí)。1.求出 GS的 FIRSTVT集和 LASTVT

16、集:FIERSTVT (S) =a,bFIERSTVT(P尸bFIERSTVT(Q尸a構(gòu)造優(yōu)先關(guān)系表為：LASTBVT (S) =b,cLASTBVT (P) =cLASTBVT (Q) =aword范文abca< ><>b< >c>>由于在優(yōu)先關(guān)系中同時(shí)出現(xiàn)了a<a和a>a以及b<b和b>b ,所以該文法不是算符優(yōu)先文法。2.消除左遞歸和提取左公因子后的文法為:S faSb|PP 一 bP'P' -Pc |QcQ 一 aQ'Q' fQ ' | £求具有相同左部的兩個(gè)產(chǎn)生式

17、的Select集的交集:Select(SfSb) PSelect(S-P) = a CFirst(P) = a qb= Select(P' -Pc)rSelect(P; -Qc) = First(P) CFirst(Q.b £a= Select(Q，少)PSelect(Q' 一) = a PFollow(Q) = a qc=所以修改后的文法是LL (1)文法。七已知文法G為：(0) S' f S(1) S - aAd(2) S bAc(3) S - aec(4) S - bed(5) A e試構(gòu)造它的LR (1)項(xiàng)目集、可歸前綴圖和 LR (1)分析表 1【答

18、案：1構(gòu)造LR(1)分析表如下:狀態(tài)actiongotoabcde#SA0S2S311ac2S5c3S74S85S9r56S107r5S118r19r310r211r4八已知源程序如下:prod:=0;i:=1;while i w 20 dobeginprod:=prod+ai*bi; i:=i+1end;試按語法制導(dǎo)翻譯法將源程序翻譯成四元式序列(設(shè)A是數(shù)組a的起始地址,數(shù)組b的起始地址；機(jī)器按字節(jié)編址，每個(gè)數(shù)組元素占四個(gè)字節(jié))?！敬鸢福骸緼四元式序列100 prodc: =0101 1:-1102 If i<20 goto 104103 goto 114-104105 T2:=A-4

19、106 T3:=T2Tl107 7 4 I* I-108 T5：=B-4109 T6:=T5T4110 T7;=I3*I6 1111 prod.: >rsd.+T 7112113 got。 102114對(duì)PL/0語言的while語句 while 條件B DO 語句S 的編譯程序, 請(qǐng)?jiān)诳杖碧幪羁?，完成該語句的編譯算法：switch (SYM) case WHILESYM:CX1=CX;GetSym();CONDITION(SymSetAdd(DOSYM,FSYS),LEV,TX);CX2=CX ;GEN(JPC,0,0);if (SYM=DOSYM)GetSym() ;else Erro

20、r(18);STATEMENT(FSYS,LEV,TX);GEN(JMP,0,CX1);CODECX2.A=CX ;break;編譯原理期末試題(六)一、回答下列問題：(30分)1 .什么是S-屬性文法？什么是L-屬性文法？它們之間有什么關(guān)系?解答：S-屬性文法是只含有綜合屬性的屬性文法。(2分)S-屬性文法是L-屬性文法的特例。(2分)3 .劃分程序的基本塊時(shí)，確定基本塊的入口語句的條件是什么？解答：(1)程序第一個(gè)語句，或(2)能由條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句轉(zhuǎn)移到的語句，或(3)緊跟在條件轉(zhuǎn)移語句后面的語句。4 . (6分)運(yùn)行時(shí)的DISPLAY表的內(nèi)容是什么？它的作用是什么？答：DIS

21、PLAY表是嵌套層次顯示表。每當(dāng)進(jìn)入一個(gè)過程后，在建立它的活動(dòng)記錄 區(qū)的同時(shí)建立一張嵌套層次顯示表 diaplay.假定現(xiàn)在進(jìn)入的過程層次為i,則它的 diaplay表含有i+1個(gè)單元，自頂向下每個(gè)單元依次存放著現(xiàn)行層、直接外層、 直至最外層(主程序，0層)等每層過程的最新活動(dòng)記錄的起始地址。通過DISPLAY 表可以訪問其外層過程的變量。二、設(shè)=0, 1上的正規(guī)集S由倒數(shù)第二個(gè)字符為1的所有字符串組成，請(qǐng)給出該字集對(duì)應(yīng)的正規(guī)式，并構(gòu)造一個(gè)識(shí)別該正規(guī)集的DFA。（8分）答：構(gòu)造相應(yīng)的正規(guī)式：（0|1）*1（0|1）（3分）NFA: （2 分）1100確定化：（3分）II 0110,1,21,2

22、1,2,31,21,21,2,31,2,31,2,41,2,3,41,2,41,21,2,31,2,3,41,2,41,2,3,4Zl(E )、寫一個(gè)文法使其語言為 L(G)= anbmambn | m,n >10 (6分)答：文法G(S):SaSb | BBbBa | ba四、對(duì)于文法G(E): (8分)E T|E+TT F|T*FF (E)|i1 .寫出句型(T*F+i)的最右推導(dǎo)并畫出語法樹。2 .寫出上述句型的短語，直接短語、句柄和素短語E + TT FT*F1 .(4 分)E T F (E) (E+T)(E+F)word范文(E+i) (T+i)(T*F+i)2 . （4 分）

23、短語：（T*F+i）, T*F+i, T*F, i直接短語：T*F, i句柄：T*F素短語：T*F, i六、設(shè)某語百的do-while語句的語法形式為（9分）S do S（1） While E其語義解釋為：針對(duì)自下而上的語法分析器，按如下要求構(gòu)造該語句的翻譯模式:（1）寫出適合語法制導(dǎo)翻譯的產(chǎn)生式；（2）寫出每個(gè)產(chǎn)生式對(duì)應(yīng)的語義動(dòng)作。答：（1）.適合語法制導(dǎo)翻譯的文法（3分）G（S）:R doU R S WhileSUE(2) . (6 分)R do R.QUAD:=NXQ U R S While U.QUAD尸R.QUAD;BACKPATCH(S.CHAIN, NXQ) S U E BACK

24、PATCH(E.TC, U.QUAD);S.CHAINkE.FC 答案二：(1) S do Mi S While M2 EM &(3 分)(2) M £ M.QUAD := NXQ (6 分)S do Mi S While M2 EBACKPATCH(S).CHAIN, M2.QUAD);BACKPATCH(E.TC, MQUAD); S.CHAIN:=E. FC七、(8分)將語句if (A<X)(B>0) then while C>0 do C:=C+D翻譯成四元式。(8分)答：100 (j<, A, X, 102)101 (j, -, -, 109

25、)102 (j>, B, 0, 104)103 (j, -, -, 109)104 (j>, C, 0, 106)105 (j, -, -, 109)106 (+, C, D, T1)107 (k，T1, -, C)108 (j, -, -, 104)109(控制結(jié)構(gòu)3分，其他5分)八、(10分)設(shè)有基本塊如下：T1:=S+RT2:= 3T3:= 12/T2T4:=S/RA:=T1-T4T5:=S+RB:=T5T6:=T5*T3B:=T6(1)畫出DAG圖；設(shè)A,B是出基本塊后的活躍變量，請(qǐng)給出優(yōu)化后的四元式序列word范文答：(1) DAG如右圖:n8T6,Bn3 T1n6T4n

26、2(2)四元式序列：(4分)T1:=S+RT4:=S/RA:=T1-T4B:=T1*4九、(9分)設(shè)已構(gòu)造出文法G(S):(1) S BB(2) B aB(3) B b的LR分析表如下狀態(tài)ACTIONGOTOab#SB0s3s4121acc2s6s753s3s484r3r35ri6s6s797r38r2r29r2假定輸入用為abab,請(qǐng)給出LR分析過程（即按照步驟給出狀態(tài)，符號(hào)，輸入申 的變化過程）。步驟狀態(tài)符號(hào)輸入用00#abab#103#abab#2034#abab#3038#aBab#402#Bab#5026#Bab#60267#Bab#70269#BaB#8025#BB#901#S#

27、acc編譯原理期末試題（八）1. （10分）處于/*和*/之間的用構(gòu)成注解，注解中間沒有 7。畫出接受這種注 解的DFA的狀態(tài)轉(zhuǎn)換圖。2. 為語言L = ambn | 0 m 2n（即a的個(gè)數(shù)不超過b的個(gè)數(shù)的兩倍） 寫一個(gè)LR （1）文法，不準(zhǔn)超過6個(gè)產(chǎn)生式。（若超過6個(gè)產(chǎn)生式，不給分。若 所寫文法不是LR （1）文法，最多給5分。）3. （10分）構(gòu)造下面文法的LL （1）分析表。D TLT int | realL id RR , id R |4. （15分）就下面文法S （ L） | a L L S | S?給出一個(gè)語法制導(dǎo)定義，它輸出配對(duì)括號(hào)的個(gè)數(shù)。?給出一個(gè)翻譯方案，它輸出每個(gè) a的嵌

28、套深度。如句子（a, （a, a），第一小題的輸出是2,第二小題的輸出是1 2 2startLR (1)文法LR (1)文法二義文法S AB | aABbS ABS AASb|A aaAb |A aaAb | ab |A a |B Bb |B Bb |intrealid,$DD TLD TLTT intT realLL id RRR,id R RS Sprint(S.num)S (L)S.num := L.num +1S aS.num := 0LLi,SL.num := L1.num + S.numL SL.num := S.num2.3.4.S S.depth := 0 SS L.depth

29、 := S.depth +1 (L)S a print(S.depth)LLi.depth := L.depth L 1, S.depth := L.depth SL S.depth := L.depth S5. ti := initialt2 := finalif t1 > t2goto Liv := tiL2 stmtif v = 12 goto Liv := v + 1goto L2Li:編譯原理期末大題1 .設(shè)有如下文法 G (S),試消除其左遞歸。G ( S) : S- >Ac|cA>Bb|bB>Sa|a解：S- abcS|bcS |cS: S' ab

30、cS |2 .試構(gòu)造與下面G (S)等價(jià)的無左遞歸的文法。G (S): S->Sa|Nb|cN>Sd|Ne|f解：Sf fN bScS； SaS|dN bS , N'f eN 3 .設(shè)有文法G(S):5 >aBc|bABA>aAb|b8 >b| £求各產(chǎn)生式的FIRST集,FOLLOW(AW口 FOLLOW(B)以及各產(chǎn)生式的SELECT構(gòu)造LL(1加析表，并分析符號(hào)用baabbb是否是。解：(1) FIRST(aBc尸a,FIRST(bAB)=b FIRST(aAb)=a, A-b: FIRST(內(nèi) b)=b, B-b: FIRST(b) =

31、b, FIRST()=§FOLLOW(A)=b, #, FOOLOW(B尸c, #SELECT(SaBc尸a, SELECTSbAB) =b, SELECT(Z aAb)=a, SELECT(A> b)=b, SELECT(B>b)=b, SELECT(B> )=c, #因此，所得的LL(1汾析表如表A-4所小。(2)分析符號(hào)用baabbb成功，baabbb是該文法的句子，如圖 A-16所示步驟符號(hào)棧輸入串所用的產(chǎn)生式1#Sbaabbb#S bAB2#BAbbaabbb#3#BAaabbb#AaAb4#BbAaaabbb#5#BbAabbb#AaAb6#BbbAaa

32、bbb#7#BbbAbbb#Ab8#Bbbbbbb#9#Bbbbb#10#Bbb#11#B#B£12#成功圖A-16 識(shí)別用baabbb的過程5.已知文法G(S*S- >a|(T)T- >T,S|S給出句子(a,a),a珀最左推導(dǎo)并畫出語法樹；給出句型(T,a,(T)所有的短語、直接短語、素短語、最左素短語、句柄和活前綴。解：(1 ) 最左 推導(dǎo)： S (T)(T,S)(S,S)(a,S) (a,(T) (a,(T,S) (a,(S,S) (a,(a, S) (a,(a,a)語法樹：如圖A-16所示。aaT , SS I a圖 A-16(a,(a,a)B 語法樹(2)句型

33、(T, a, (T)的短語、直接短語、素短語、最左素短語、句柄、活前綴及語法樹(圖A-17)短語:a | T,a | (T) | T , a , (T) | (T , a , (T)直接短語：a | (T)素短語：a | (T)最左素短語：a句柄：a活前綴:II ( II (T II (T，II (T，a( T )T , SXTX /'T , S ( T )Ia圖A-17(T,a,(T)勺語法樹4.設(shè)文法G (S)為：S > a | a A bA > 1 A 0 | £求L R ( 0 )項(xiàng)目集族;構(gòu)造文法G (E)的S > b | b B aB>1

34、B 0 | £構(gòu)造識(shí)別文法G (E)的DFA;SLR( 1 )的分析表；分析句子a 110 0 b的識(shí)別過程。解：(1)、(2) LR(0項(xiàng)目集族和識(shí)別活前綴的 DFA,如圖A-19所示。圖 A-19LR(0)Ii： S' S -(I0： S'SaAbbBa12： S a S aAbA 1A0S bBaB 1B0項(xiàng)目集族和DFA、構(gòu)造下列正則表達(dá)式的確定性的有限狀態(tài)自動(dòng)機(jī)。(12%aba(a|b)*aba、證明下面文法是SLR(1立法，并構(gòu)造其SLR分析表。(15%<E> <E> + <T> | <T> <T>

35、; <T> <F> | <F><F> <F>*|a | b答：分析表如下所示：狀態(tài)T項(xiàng)目集輸入符號(hào)下一狀態(tài)*<E'>-> <E> !<E>1<E> /<E>+<T><E>1<E> /<T><T>20<T> <T><F><T>2<T> <F><F>3<F> /<F>*<F>3<F&

36、gt; /aa4<F> /bb51*<E'>-><E> , _L±Accept*<E> /<E> +<T>+6*<E> /<T> ,±/+#2*<T> <T> <F><F>72<F> /<F>*<F>7<F> /aa4<F> /bb53*<T> <F> >±/+/a/b#4*<F> /<F> *8

37、4*<F> /a ,#65*<F> /b ,#7*<E> /<E>+ <T><T>9<T> <T><F><T>96<T> <F><F>3<F> /<F>*<F>3<F> /aa4<F> /bb57*<T> <T><F> ±/+/a/b#3*<F> /<F> *88*<F> /<F>* ,#

38、5*<E> -><E>+<T> ±/+#1*<T> -xT> <F><F>79<F> -) <F>*<F>7<F> -4aa4<F> -fbb5四、寫出下列表達(dá)式的三地址形式的中間表示。(16%(1) 5+6 (a + b);(2) A ( B (C D);(3 )for j:=1 to 10 do aj + j:=0;(4 )if x > y then x:=10 else x:= x + y;答：100:101:102: 100:1

39、01:102:103:104:105:106:107: 100:t1:=a+b t2:=6*t1 t3:=5+t2if A goto 102 goto Tif B goto 104 goto Fif C goto T goto 106if D goto T goto F j:=1101: if j>10 goto NEXT102: i:=j+j103: ai:=0104: goto 101 100: if x>y goto 102105: goto 104106: x:=10107: goto 105108: x:=x+y109:五、條件語句可形式定義為：（20%）<S>

40、; IF <E> THEN <S>1 ELSE <S>2其中<E>帶有屬性1 . <E>.type 值為boolean” 表示<E>是布爾類型2 . <E>.true和<E>.false 值為<E>中真和假的尚待回填的出口的鏈?zhǔn)字羔槜l件語句的語義可描述為：t:=e;3 f not_ t then goto L1;<S>1；goto L2;L1: <S>2；L2:其中e為<E>的值。試用句法制導(dǎo)翻譯的方法寫出符合上述要求的條件語句的翻譯方案答：條件語句的

41、屬性翻譯文法為：< if1> if<E>CheckBool(<E>.type);TLT:=NewTL;GEN(LABEL,TLT);Backpatch(<E>.true,TLT);<if1>.false:=<E>.false;_ 1< if2><if1> then <S><if2>.TL:=NewTL;GEN(BR, <if2>.TL);TLF:=NewTL;GEN(LABEL,TLF);Backpatch(<E>.false,TLF);< S&

42、gt; <if2> else <S>GEN(LABEL,<if2>.TL);六、對(duì)如下程序框架，若采用以過程為單位、二級(jí)存儲(chǔ)區(qū)的存儲(chǔ)分配方法試寫出當(dāng)程序流到達(dá)L時(shí),整個(gè)運(yùn)行棧的內(nèi)容.(15%)procedure mainprocedure q(x,y : int)beginZ:real;array Bx.y of real;beginD,E: real;array C1.600 of int;end;beginarray A1.x of real;beginE,F : int;L:end;end;end;qbeginr,s : int;array T10.4

43、00 of real;call q(1,200);end;/main要求用圖的形式詳細(xì)列出調(diào)用記錄中各個(gè)項(xiàng)的分布情況。答：調(diào)用記錄中各項(xiàng)的分布情況如圖6.29所示：棧 增 長(zhǎng) 方 向數(shù)組A數(shù)組BE,F分程序4的stp4數(shù)組A1的信息向量分程序3的stp3Z,數(shù)組B的信息向量分程序1的stpiq過程的stp形實(shí)參數(shù)通訊區(qū)x,y,1,200調(diào)用點(diǎn)的機(jī)器狀態(tài)Old SP區(qū)頭地址表數(shù)組T 數(shù)組T的信息向量r,s分程序的stpmain過程的stp 形實(shí)參數(shù)通訊區(qū)調(diào)用點(diǎn)的機(jī)器狀態(tài)Old SP區(qū)頭地址表七、設(shè)基本塊 由如下語句構(gòu)成：（10%）T0: =3.14;Ti：=2*To；T2:=R+r;A:=T*T2；B:=A;T3：=2*To；T4:=R+r;T5：=T3*T4；T6：=R-r ；B：=T596;a）試給出基本塊 的DAG。b）根據(jù)DAG重寫基本塊。c）若 所在的程序中只有A和B在 后將要被引用，試寫出優(yōu)化后的基本塊答：1）基本塊 的DAG如圖7