編譯原理平時作業(yè)-答案

1、平時作業(yè)1 對于下列語言分別寫出它們的正規(guī)表達式。 (1) 英文字母組成的所有符號串，要求符號串中順序包含五個元音。答： 令Letter表示除這五個元音外的其它字母。  (letter)*A(letter)*E(letter)*I(letter)*O(letter)*U(letter)*(2) 英文字母組成的所有符號串，要求符號串中的字母依照詞典順序排列。 答： A*B*.Z*(3) =0,1上的含偶數個1的所有串。答： (0|10*1)*(4) =0,1上的含奇數個1的所有串。答：(0|10*1)*1(5)

2、60;具有偶數個0和奇數個1的有0和1組成的符號串的全體。答：設S是符合要求的串，|S|=2k+1 (k0）。則 SS10|S21，|S1|=2k (k>0），|S2|=2k (k0）。且S1是0,1上的串，含有奇數個0和奇數個1。 S2是0,1上的串，含有偶數個0和偶數個1?？紤]有一個自動機M1接受S1，那么自動機M1如下：和L(M1)等價的正規(guī)表達式，即S1為：(00|11)|(01|10)(00|11)*(01|10)*(01|10)(00|11)*類似的考慮有一個自動機M2接受S2，那么自動機M2如下：和L(M2)等價的正規(guī)表達式，即S2為：(00|11)|(01|10

3、)(00|11)*(01|10)*因此，S為：(00|11)|(01|10)(00|11)*(01|10)*(01|10)(00|11)*0|(00|11)|(01|10)(00|11)*(01|10)*1(6) 不包含子串011的由0和1組成的符號串的全體。答：1*|1*0(0|10)*(1|)(7) 由0和1組成的符號串,把它看成二進制數，能被3整除的符號串的全體。答： 假設w的自動機如下：對應的正規(guī)表達式：(1(01*0)1|0)*2 給出接受下列在字母表0,1上的語言的DFA。(1) 所有以00結束的符號串的集合。(2) 所有具有3個0的符號串的

4、集合。答：(1) DFA M=(0，1，q0，q1，q2，q0，q2，)其中定義如下:（q0，0）=q1     （q0，1）=q0（q1，0）=q2     （q1，1）=q0（q2，0）=q2     （q2，1）=q0(2)正則表達式: 1*01*01*01* DFA M=(0，1，q0，q1，q2，q3，q0，q3，)其中定義如下:（q0，0）=q1     （q0，1）=q0（q1，0）=q2 &

5、#160;   （q1，1）=q1（q2，0）=q3     （q2，1）=q2（q3，1）=q3     3 下面是用正規(guī)式表示的變量聲明：( int | float ) id (, id )* ;請改用上下文無關文法表示，也就是寫一個上下文無關文法，它和該正規(guī)式等價。答：D ® T L ; T ® int | floatL ® L, id | id4 試分析下面給出的if-then-else語句的文法，它的提出原本是為了矯正dangling-else (懸而未決

6、的-else)文法的二義性：stmt if expr then stmt |matched-stmt matched-stmt if expr then matched-stmt else stmt |other 試說明此文法仍然是二義性的。 答：考慮句子if e then if e then other else if e then other else other 它具有如下所示的兩種分析樹 stmt expr then e if stmt if matched-stmt expr then matched-stmt e other if esle stmt matched-stmt ex

7、pr then matched-stmt e other esle stmt matched-stmt other stmt matched-stmt if expr then matched-stmt e if esle stmt esle stmt matched-stmt expr then e stmt other expr then matched-stmt e other if matched-stmt other 則上面給出的if-then-else文法仍是二義性的。5 證明下面文法是SLR(1)文法，并構造其SLR分析表。EE+T|T TTF|F FF*|a|b 答：該文法的拓

8、廣文法G'為 (0) E' E(1) E E+T(2) E T(3) T TF(4) T F(5) F F*(6) F a(7) F b其LR(0)項目集規(guī)范族和goto函數(識別活前綴的DFA)如下:I0 = E'·E, E·E+T, E·T, T·TF, T·F, F·F*,        F·a, F·b I1 = E'E·, EE·+TI2 = ET·, TT

9、3;F, F·F*, F·a, F·bI3 = TF·, FF·* I4 = Fa· I5 = Fb· I6 = EE+·T, T·TF, T·F, F·F*, F·a, F·b I7 = TTF·, FF·* I8 = FF*·I9 = EE+T·, TT·F, F·F*, F·a, F·b求FOLLOW集：    FOLLOW(E)=,

10、60;   FOLLOW(T)=, , a, bFOLLOW(F)=, , a, b, *構造的SLR分析表如下： 顯然，此分析表無多重定義入口，所以此文法是SLR文法。6 為下面的文法構造LALR(1)分析表SE EE+T|TT(E)|a答：其拓廣文法G'： (0) S' S(1) S E(2) E E+T(3) E T(4) T (E)(5) T a構造其LR(1)項目集規(guī)范族和goto函數(識別活前綴的DFA)如下: I0 = S·S, $, S·E, $, E·E+T, $/+, E·T, $/+,&

11、#160;T·(E), $/+, T·a, $/+ I1 = SS·, $ I2 = SE·, $, EE·+T, $/+ I3 = ET·, $/+I4 = T(·E), $/+, E·E+T, )/+, E·T, )/+,  T·(E), )/+, T·a, )/+ I5 = Ta·, $/+ I6 = EE+·T, $/+, T·(E), $/+, T·a, $/+I7 = T(E·), $/+, EE·+T,

12、 )/+ I8 = ET·, )/+I9 = T(·E), )/+, E·E+T, )/+, E·T, )/+, T·(E), )/+, T·a, )/+I10 = Ta·, )/+ I11 = EE+T·, $/+ I12 = T(E)·, $/+I13 = EE+·T, )/+, T·(E), )/+, T·a, )/+ I14 = T(E·), )/+, EE·+T, )/+I15 = EE+T·, )/+ I16 = T(E)·

13、, )/+合并同心的LR(1)項目集，得到LALR的項目集和轉移函數如下： I0 = S·S, $, S·E, $, E·E+T, $/+, E·T, $/+, T··(E), $/+, T·a, $/+I1 = SS·, $ I2 = SE·, $, EE·+T, $/+ I3,8 = ET·, $/+/)I4,9 = T(·E), $/+/), E·E+T, )/+, E·T, )/+,  T·(E), )/+, T·a,

14、 )/+I5,10 = Ta·, $/+/) I6,13 = EE+·T, $/+/), T·(E), $/+/), T·a, $/+/)I7,14 = T(E·), $/+/), EE·+T, )/+ I11,15 = EE+T·, $/+/) I12,16 = T(E) ·, $/+/)LALR分析表如下：7 （1）通過構造識別活前綴的DFA和構造分析表，來證明文法E ® E + id | id是SLR(1)文法。答：先給出接受該文法活前綴的DFA如下：E¢ ®·EE &

15、#174;·E + idE ®·idI0E¢ ® E·E ® E·+ idI1E ® id·I2Eid+E ® E +·idI3E ® E + id·I4id再構造SLR分析表如下：狀態(tài) 動作轉移 id + $ E 0 s2 1 1 s3 acc 2 r2 r2 3 s4 4 r1 r1 表中沒有多重定義的條目，因此該文法是SLR(1)的。（2）下面左右兩個文法都和（1）的文法等價E ® E + M id | idE ® M E + i

16、d | idM ® eM ® e請指出其中有幾個文法不是LR(1)文法，并給出它們不是LR(1)文法的理由。答：只有文法E ® M E + id | idM ® e不是LR(1)文法。因為對于句子id+id+id來說，分析器在面臨第一個id時需要做的空歸約次數和句子中+id的個數一樣多，而此時句子中+id的個數是未知的。8根據自上而下的語法分析方法，構造下面文法的LL（1）分析表。D ® TLT ® int | realL ® id RR ® , id R | e答：先計算FIRST和FOLLOWFIRST(D)

17、= FIRST(T) = int,realFIRST(L) = id FIRST(R) = ,FOLLOW(D) = FOLLOW(L) = $FOLLOW(T) = idFOLLOW(R) = $LL(1)分析表如下：intrealid,$DD -> TLD -> TLTT -> intT -> realLL -> idRRR -> ,idRR -> 9 下面的文法產生的表達式是對整型和實型常數應用算符+形成的。當兩個整數相加時，結果仍為整數，否則就是實數。        

18、0;EE+T|T         Tnum.num|num     （a）給出一個語法制導定義以確定每個子表達式的類型。     （b）擴充（a）中的語法制導定義把表達式翻譯成前綴形式，并且決定類型。使用一元算符inttoreal把整型值轉換成相等的實型值，以使得前綴形式中的+的兩個操作對象是同類型的。答： (a):產生式語義規(guī)則EàE1+TIF (E1.type=integer) and (T.type=integer) T

19、HEN E.type:=integerELSE E.type:=realEàTE.type:=T.typeTànum.numT.type:=realTànumT.type:=integer(b):產生式語義規(guī)則EàE1+TIF (E1.type=integer) and (T.type=integer) THEN BEGIN E.type:=integer Print(+,E1.val,T.val) ENDELSE BEGIN E.type:=real IF E1.type=integer THEN Begin E1.type:=realE1.val:=

20、inttoreal(E1.val) End IF T.type:=integer THEN Begin T.type:=real T.val:=inttoreal(T.val) End Print(+,E1.val,T.val)ENDEàTE.type:=T.typeE.val:=T.valTànum.numT.type:=realT.val:=num.num.lexvalTànumT.type:=integerT.val:=num.lexval10 假設說明是由下列文法產生的：        

21、Did L        L,id L|:T        Tinteger |real    （a）建立一個翻譯模式，把每一個標識符的類型加入到符號表中。    （b）從（a）中的翻譯模式構造一個預翻譯程序。 答： (a)：產生式翻譯模式Dàid LD.Type:=L.Typeaddtype(id.entry, D.type)Là,id L1L.Type:=L1.Typeaddtype

22、(id.entry, L.type)Là:TL.type:=T.typeTàintegerT.type:=integerTàrealT.type:=real(b)：Procedure D;beginIf lookahead=id then BeginMatch(id);D.type=L;addtype(id.entry,D.type) endelse errorendFunction L: DataType;BeginIf lookahead=, then Begin Match(,); If lookahead=id then begin match(id);L

23、.Type=L; addtype(id.entry,L.type); return(L.type) end Else error EndElse if lookahead=: thenBeginMatch(:);L.Type=T;return(L.Type)endelse errorEndFunction T: DataType;BeginIf lookahead=integer thenBeginMatch(integer);return(integer)endelse If lookahead=real thenBeginMatch(real);return(real)endelse er

24、rorend11為下面的算術表達式文法寫一個語法制導的翻譯方案，它將每個子表達式E的符號（即值大于零還是小于零）記錄在屬性E.sign中（屬性值分別用POS或NEG表示）。你可以假定所有的整數都不為零，這樣就不用擔心零的符號。E ® E *E | +E | -E | unsigned_integer答：E ® E1 *E2if E1.sign= E2.sign then E.sign := POS else E.sign := NEG E ® +E1 E.sign := E1.sign E ® -E1 if E1.sign= POS then E.sig

25、n := NEG else E.sign := POSE ® unsigned_integer E.sign := POS12為下面文法寫一個語法制導的定義，用S的綜合屬性val給出下面文法中S產生的二進制數的值。例如，輸入101.101時，S. val := 5.625。（不得修改文法。）S ® L . R | LL ® L B | BR ® B R | BB ® 0 | 1答：S ® L . RS. val := L. val + R. val S ® LS. val := L. valL ® L1 BL. v

26、al := L1. val ´2 + B. valL ® BL. val := B. valR ® B R1R. val := (R1. val + B. val)/2R ® BR. val := B. val/2B ® 0B. val := 0B ® 1B. val := 113 試問下面的程序將有怎樣的輸出？分別假定：    （a）傳值調用（call-by-value）；    （b）引用調用（call-by-reference）；    （

27、c）復制恢復（copy-restore）；    （d）傳名調用（call-by-name）。     program main(input,output）；        procedure p（x,y,z）；           begin              

28、;y：y1；              z：zx；           end；        begin            a：2；         &#

29、160;  b：3；            p(ab,a,a)；            print a        end.答：1)傳地址：所謂傳地址是指把實在參數的地址傳遞給相應的形式參數。在過程段中每個形式參數都有一對應的單元，稱為形式單元。形式單元將用來存放相應的實在參數的地址。當調用一個過程時，調用段必須領先

30、把實在參數的地址傳遞到一個為被調用段可以拿得到的地方。當程序控制轉入被調用段之后，被調用段首先把實參地址捎進自己相應的形式單元中，過程體對形式參數的任何引用1或賦值都被處理成對形式單元的間接訪問。當調用段工作完畢返回時，形式單元(它們都是指示器)所指的實在參數單元就持有所指望的值。 2)傳結果：和“傳地址”相似(但不等價)的另一種參數傳遞力法是所謂“傳結果”。這種方法的實質是，每個形式參數對應有兩個申元，第1個單元存放實參的地址，第2個單元存放實參的值。在過程體中對形參的任何引用或賦值都看成是對它的第2個單元的直接訪問。但在過程工作完畢返回前必須把第2個單元的內容行放到第1個單元所指的那個實參

31、單元之中。 3)傳值：所謂傳值，是一種簡單的參數傳遞方法。調用段把實在參數的值計算出來并存放在一個被調用段可以拿得到的地方。被調用段開始丁作時，首先把這些值抄入形式中元中，然后就好像使用局部名一樣使用這些形式單元。如果實在參數不為指示器，那末，在被調用段中無法改變實參的值。 4)傳名：所謂傳名，是一種特殊的形實參數結合方式。解釋“傳名”參數的意義：過程調用的作用相當于把被調用段的過程體抄到調用出現(xiàn)的地方，但把其中任一出現(xiàn)的形式參數都替換成相應的實在參數(文字替換)。它與采用“傳地址”或“傳值”的方式所產生的結果均不相同。 (a)2； (b)8； (c)7； (d)9。14 對以下的Pascal

32、程序畫出過程c第二次被激活時的運行棧，控制鏈和訪問鏈。說明在c中如何訪問變量x。program env；      procedure a；        var x:integer；        procedure b；          procedure c；    &#

33、160;       begin x:=2；b end；procedure c          begin c end；procedure b        begin b end；procedure a       begin a end. main  答： envcontrol linkacc

34、ess linkacontrol linkaccess linkx bcontrol linkaccess link ccontrol linkaccess link bcontrol linkaccess link caccess linkcontrol link說明：c中沿著存取鏈向前走兩步，到過程a的活動記錄中就可以訪問到變量x。15 下面給出一個 C 語言程序及其在 SPARC/SUN 工作站上經某編譯器編譯后的運行結果。從運行結果看，函數 func中 4個局部變量 i1, j1, f1, e1的地址間隔和它們類型的大小是一致的，而 4個形式參數 i, j, f, e的地址間隔和它們的

35、類型的大小不一致，試分析不一致的原因。注意，輸出的數據是八進制的。 func (i, j, f, e) short i, j; float f, e; short i1, j1; float f1, e1; printf( "Address of i, j, f, e = %o, %o, %o, %o n", &i, &j, &f, &e); printf( "Address of i1, j1, f1, e1 = %o, %o, %o, %o n", &i1, &j1, &f1, &e1)

36、; printf( "Sizes of short, int, long, float, double = %d, %d, %d, %d, %d n", sizeof(short), sizeof(int), sizeof(long), sizeof(float), sizeof(double) ); main() short i, j; float f, e; func(i, j, f, e); 運行結果是： Address of i, j, f, e = 35777772536, 35777772542, 35777772544, 35777772554 Address

37、 of i1, j1, f1, e1 = 35777772426, 35777772424, 35777772420, 35777772414 Sizes of short, int, long, float, double = 2, 4, 4, 4, 8，請問為什么？答：C語言編譯器是不做實在參數和形式參數的個數和類型是否一致的檢查的，由程序員自己保證它們的一致性。但是對于形式參數和實在參數是不同的整型（如一個是short型，另一個是long型），或者是不同的實型，編譯器則試圖保證目標代碼運行時能得到正確的結果，條件是，當需要高級別類型數據向低級別類型數據轉換時，不出現(xiàn)溢出。這樣，C編譯器作

38、的約定是，當整型或實型數據作為實在參數時，分別將它們提升到long和double類型的數據傳遞到被調用函數。被調用函數根據形式參數所聲明的類型，決定是否要將實在參數向低級別類型轉換。低地址放高位高地址放低位shortlong圖5.2 長整型和短整型在本例中，long類型數據占4個字節(jié)，而short類型數據只占2個字節(jié)。因此被調用函數把實在參數的低位字節(jié)的內容當成是自己所需的數據，見圖5.2注意，對于SUN工作站來說，低地址存放整型數據的高位。floatdoublee圖5.3 雙精度型和浮點型對于實型來說。double類型是8個字節(jié)，而float類型4個字節(jié)。被調用函數把實在參數的前4個字節(jié)作為

39、自己所需的數據，因為double后面4個字節(jié)的內容都是為了增加精度用的，見圖5.3。e，8個字節(jié)在main函數中參數壓棧時的觀點在func函數中存取形式參數時的觀點4個字節(jié)，起始地址357777725544個字節(jié)，起始地址357777725442個字節(jié)，起始地址357777725422個字節(jié)，起始地址35777772536f，8個字節(jié)j，4個字節(jié)i，4個字節(jié)棧的增長方向圖5.4 參數在棧中的情況這樣在main函數中依次將參數提升后反序進棧，大小分別為8, 8, 4, 4。在func函數中，按形式參數的類型，把這些存儲單元的一部分看成是形式參數的存儲單元，見圖5.4。從這個圖不難理解為什么形式參

40、數的地址間隔和它們的類型大小不一致了。注意，現(xiàn)在的編譯器將需要進行類型轉換的形式參數（類型是char、short、float等）另行分配在局部數據區(qū)，當控制進入被調用過程時，首先將調用過程壓棧的需要進行類型轉換的實在參數取出，把它們存入所分配的局部數據區(qū)存儲單元，并同時完成必要的數據類型的轉換。在這種情況下，不會出現(xiàn)本題所碰到的現(xiàn)象。另外，在SPARC工作站上，整型數據的高位存放在低地址，而低位存放在高地址。如果是X86機器，數據的高低位不是按這樣的次序存放，那也不會出現(xiàn)本題所碰到的現(xiàn)象。下面是某個編譯器的類型提升函數，供讀者理解用（備注：int和long的大小一樣）。Type promote

41、(Type ty)switch(ty->op)case ENUM:return inttype;case INT:if (ty->size < inttype->size)return inttype;break;case UNSIGNED:if (ty->size < inttype->size)return inttype;break;case FLOAT:if (ty->size < doubletype->size)return doubletype;return ty;16 試把下列C語言程序的可執(zhí)行語句翻譯為(a)一棵語法

42、樹， (b)后綴式， (c)三地址代碼。main() int i; int a10; while (i<=10) ai=0;while答：(a).一棵語法樹賦值表達式布爾表達式表達式表達式數組元素表達式<=下標表達式110a01(b) 后綴式為： i 10<= a i 0 = while從理論上可以說while(i<=10) ai=0; 的后綴式如上面表示。但若這樣表示，在執(zhí)行while操作時，賦值語句已經執(zhí)行，這顯然與語義不符，因此改為：i 10 <=< 下一個語句開始地址>BM a i 0 =< 本語句地址 > BRL其中BM操作為當表

43、達式為假時轉向<下一個語句開始地址>，BRL是一個一目運算，無條件轉向<本語句始址>。(c) 三地址代碼序列為：100 if i <= 10 got 102101 goto 106102 t1:=4*i103 t2:=a104 t2t1:=0105 goto 10010617Pascal語言中，語句： for v：initial to final do stmt 與下列代碼序列有相同含義begin t1:=initial;t2:=final; if t1<=t2 then begin v:=t1; stmt while v<>t2 do begi

44、n v：=succ（v)； stmt end endend (a)試考慮下述Pascal程序program forloop(input, output); var i,initial,final: integer; begin read(initial, final); for i:= initial to final do write(i) end對于initial=MAXINT-5和final= MAXINT，問此程序將做些什么？其中MAXINT為目標機器允許的最大整數。(b)試構造一個翻譯pascal的for語句為三地址代碼的語法制導定義。 答：（a）程序將顯示如下六個整數： MAXIN

45、T -5 MAXINT -4 MAXINT -3 MAXINT -2 MAXINT -1 MAXINT （b）為簡單起見，for語句的三地址代碼如下： t1 := initial t2 := final if t1 > t2 goto S.next v := t1 stmt.code S.begin: if v > t2 goto S.next v := succ(v) stmt.code goto S.begin 語法制導定義如下： 產生式 動作 Sfor E do S1 S.begin := newlabel S.first := newtemp S.last := newte

46、mp S.curr:= newtemp S.code:=gen(S.first “:=” E.init) |gen(S.last “:=” E.final) |gen(“if” S.first “>” S.last “goto” S.next) |gen(S.curr “:=” S.first) |gen(S.begin “:” ) |gen(“if ” S.curr “>” S.Last “goto” S.next) |S1.code |gen(S.curr := succ(S.curr) |gen(“goto” S.begin) Ev:=initial to final E.i

47、nit := initial.place E.final := final.place18對于下面C語言文件s.c f1(int x)long x;x = 1;f2(int x)long x;x = 1;某編譯器編譯時報錯如下：s.c: In function f1:s.c:3: warning: declaration of x shadows a parameter請回答，對函數f2為什么沒有類似的警告錯誤。答：對于函數f1，局部變量x聲明的作用域是整個函數體，導致在函數體中不可能訪問形式參數x。由于這是一個合法的C語言函數，因此編譯器給出警告錯誤。對于函數f2，由于局部變量x的作用域只是

48、函數體的一部分，不會出現(xiàn)上述問題，因而編譯器不報錯。19考慮一個簡單語言，其中所有的變量都是整型（不需要顯式聲明），并且僅包含賦值語句、讀語句和寫語句。下面的產生式定義了該語言的語法（其中l(wèi)it表示整型常量；OP的產生式沒有給出，因為它和下面討論的問題無關）。Program®StmtListStmtList ®Stmt StmtList | StmtStmt®id := Exp; | read (id ); | write ( Exp ); Exp®id | lit | Exp OP Exp我們把不影響write語句輸出值的賦值（包括通過read語句來賦

49、值）稱為無用賦值，寫一個語法指導定義，它確定一個程序中出現(xiàn)過賦予無用值的變量集合（不需要知道無用賦值的位置）和沒有置初值的變量集合（不影響write語句輸出值的未置初值變量不在考慮之中）。非終結符StmtList和Stmt用下面3個屬性（你根據需要來定義其它文法符號的屬性）：（1）uses_in：在本語句表或語句入口點的引用變量集合，它們的值影響在該程序點后的輸出。（2）uses_out：在本語句表或語句出口點的引用變量集合，它們的值影響在該程序點后的輸出。（3）useless：本語句表或語句中出現(xiàn)的無用賦值變量集合。答：Exp的屬性uses表示它引用的變量集合。Program的useless

50、和no_initial分別表示程序的無用賦值變量集合和未置初值變量集合。Program® StmtList StmtList.uses_out:=Æ Program.useless := StmtList.useless;Program.no_initial := StmtList.uses_in;StmtList ® Stmt StmtList1 StmtList1.uses_out := StmtList.uses_out;Stmt.uses_out := StmtList1.uses_in;StmtList.uses_in := Stmt.uses_inSt

51、mtList.useless := StmtList1.useless È Stmt.useless;StmtList® StmtStmt.uses_out := StmlList.uses_out;StmlList.uses_in := Stmt.uses_in;StmtList.useless := Stmt.uselessStmt ®id := Exp; Stmt.useless :=if id.lexemeÎStmt.uses_out then Æ elseid.lexeme; Stmt.uses_in := if id.lexeme&

52、#206;Stmt.uses_out then (Stmt.uses_outid.lexeme)ÈExp.uses else Stmt.uses_outStmt ®read (id ); Stmt.useless:=if id.lexemeÎStmt.uses_out then Æ elseid.lexeme;Stmt.uses_in := Stmt.uses_out id.lexemeStmt ®write ( Exp );Stmt.useless := Æ, Stmt.uses_in := Stmt.uses_out È

53、 Exp.usesExp® idExp.uses:= id.lexemeExp® litExp.uses:= ÆExp® Exp1 OP Exp2Exp.uses:= Exp1.uses È Exp2.uses20 為下列C程序生成目標代碼。    main()                    int

54、i;            int a10;            while(i<=10)                 ai=0;     

55、0;    答：21 試構造下面的程序的流圖，并找出其中所有回邊及循環(huán)。          read P          x := 1          c := P * P          if c &l

56、t; 100 goto L1          B := P * P          x := x + 1          B := B + x          write x     

57、;     halt      L1: B:= 10          x := x + 2          B := B + x          write B      &

58、#160;   if B < 100 goto L2          halt      L2: x := x + 1          goto L1 答：程序的流圖如下22 試求出如下四元式程序中的循環(huán)并進行循環(huán)優(yōu)化. I := 1 read J, K L: A := K * I B := J * I C := A * B write

59、C I := I + 1 if I < 100 goto L halt答：把本題的三地址代碼劃分成基本塊并畫出其程序流圖顯示在圖9.4(1)中，其中有三個基本塊B1，B2，B3，有一條回邊B2 -> B2，相應的循環(huán)是B2。 （1）代碼外提：由于循環(huán)中沒有不變運算，故不做此項優(yōu)化 （2）強度削弱：B2中A和B都是I的歸納變量。優(yōu)化結果顯示在圖9.4(2)中。 （3）刪除歸納變量：變換循環(huán)控制條件，刪除歸納變量I后的流圖顯示在圖9.4(3)中 23 考慮下面的三地址語句序列：b := 1b := 2if w <= x goto L2e := bgoto L2L1:goto L3

60、L2:c := 3b := 4c := 6L3:if y <= z goto L4goto L5L4:g := g + 1h := 8goto L1L5:h := 9（1）在該代碼中用水平的橫線將代碼分成基本塊，并給每個基本塊一個序號。（2）畫出該代碼的控制流圖，每個基本塊就用（1）的序號表示。（3）若有循環(huán)的話，列出構成每個循環(huán)的結點。答：（1） （2）14237865b := 1b := 2if w <= x goto L2（1）e := bgoto L2（2）L1:goto L3（3）L2:c := 3b := 4c := 6（4）L3:if y <= z goto L

61、4（5）goto L5（6）L4:g := g + 1h := 8goto L1（7）L5:h := 9（8）（3） 結點5、7和3構成一個循環(huán)，其中5是入口結點。24 對下面的程序片段作出其程序流圖并計算：（1）各基本塊的到達_定值集INB；（2）各基本塊中各變量引用點的ud鏈；（3）各基本塊出口的活躍變量集V_OUTB；（4）各基本塊中變量定值點的du鏈。            I := 1       

62、0;    J := 0        L1: J := J + I            read I            if I < 100 goto L2         &

63、#160;  write J            halt        L2 : I := I * I答：本題程序的程序流圖如圖9.6(1)所示。 （1）計算各基本塊的到達-定值集INB。公式為：                 INB  = OUTP                        PPB