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

平時作業(yè)1 對于下列語言分別寫出它們的正規(guī)表達式。 (1)英文字母組成的所有符號串，要求符號串中順序包含五個元音。答：令Letter表示除這五個元音外的其它字母。(letter)*A(letter)*E(letter)*I(letter)*O(letter)*U(letter)*(2)英文字母組成的所有符號串，要求符號串中的字母依照詞典順序排列。 答： A*B*.Z*(3)=0,1上的含偶數(shù)個1的所有串。答：(0|10*1)*(4)=0,1上的含奇數(shù)個1的所有串。答：(0|10*1)*1(5)具有偶數(shù)個0和奇數(shù)個1的有0和1組成的符號串的全體。答：設S是符合要求的串，|S|=2k+1 (k0）。則 SS10|S21，|S1|=2k (k0），|S2|=2k (k0）。且S1是0,1上的串，含有奇數(shù)個0和奇數(shù)個1。S2是0,1上的串，含有偶數(shù)個0和偶數(shù)個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)(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組成的符號串,把它看成二進制數(shù)，能被3整除的符號串的全體。答： 假設w的自動機如下：對應的正規(guī)表達式：(1(01*0)1|0)*2 給出接受下列在字母表0,1上的語言的DFA。(1)所有以00結(jié)束的符號串的集合。(2)所有具有3個0的符號串的集合。答：(1) DFAM=(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* DFAM=(0，1，q0，q1，q2，q3，q0，q3，)其中定義如下:（q0，0）=q1 （q0，1）=q0（q1，0）=q2 （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 (懸而未決的-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 expr 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 答：該文法的拓廣文法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函數(shù)(識別活前綴的DFA)如下:I0 = EE, EE+T, ET, TTF, TF, FF*,Fa, Fb I1 = EE, EE+TI2 = ET, TTF, FF*, Fa, FbI3 = TF, FF* I4 = Fa I5 = Fb I6 = EE+T, TTF, TF, FF*, Fa, Fb I7 = TTF, FF* I8 = FF*I9 = EE+T, TTF, FF*, Fa, Fb求FOLLOW集：FOLLOW(E)=, 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函數(shù)(識別活前綴的DFA)如下: I0 = SS, $, SE, $, EE+T, $/+, ET, $/+,T(E), $/+, Ta, $/+ I1 = SS, $ I2 = SE, $, EE+T, $/+ I3 = ET, $/+I4 = T(E), $/+, EE+T, )/+, ET, )/+, T(E), )/+, Ta, )/+ I5 = Ta, $/+ I6 = EE+T, $/+, T(E), $/+, Ta, $/+I7 = T(E), $/+, EE+T, )/+ I8 = ET, )/+I9 = T(E), )/+, EE+T, )/+, ET, )/+, T(E), )/+, Ta, )/+I10 = Ta, )/+ I11 = EE+T, $/+ I12 = T(E), $/+I13 = EE+T, )/+, T(E), )/+, Ta, )/+ I14 = T(E), )/+, EE+T, )/+I15 = EE+T, )/+ I16 = T(E), )/+合并同心的LR(1)項目集，得到LALR的項目集和轉(zhuǎn)移函數(shù)如下： I0 = SS, $, SE, $, EE+T, $/+, ET, $/+, T(E), $/+, Ta, $/+I1 = SS, $ I2 = SE, $, EE+T, $/+ I3,8 = ET, $/+/)I4,9 = T(E), $/+/), EE+T, )/+, ET, )/+, T(E), )/+, Ta, )/+I5,10 = Ta, $/+/) I6,13 = EE+T, $/+/), T(E), $/+/), Ta, $/+/)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 E + idE idI0E EE E+ idI1E idI2Eid+E E +idI3E E + idI4id再構造SLR分析表如下：狀態(tài) 動作轉(zhuǎn)移 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 + id | idM eM e請指出其中有幾個文法不是LR(1)文法，并給出它們不是LR(1)文法的理由。答：只有文法E M E + id | idM e不是LR(1)文法。因為對于句子id+id+id來說，分析器在面臨第一個id時需要做的空歸約次數(shù)和句子中+id的個數(shù)一樣多，而此時句子中+id的個數(shù)是未知的。8根據(jù)自上而下的語法分析方法，構造下面文法的LL（1）分析表。D TLT int | realL id RR , id R | e答：先計算FIRST和FOLLOWFIRST(D) = 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 下面的文法產(chǎn)生的表達式是對整型和實型常數(shù)應用算符+形成的。當兩個整數(shù)相加時，結(jié)果仍為整數(shù)，否則就是實數(shù)。 EE+T|T Tnum.num|num （a）給出一個語法制導定義以確定每個子表達式的類型。 （b）擴充（a）中的語法制導定義把表達式翻譯成前綴形式，并且決定類型。使用一元算符inttoreal把整型值轉(zhuǎn)換成相等的實型值，以使得前綴形式中的+的兩個操作對象是同類型的。答： (a):產(chǎn)生式語義規(guī)則EE1+TIF (E1.type=integer) and (T.type=integer) THEN E.type:=integerELSE E.type:=realETE.type:=T.typeTnum.numT.type:=realTnumT.type:=integer(b):產(chǎn)生式語義規(guī)則EE1+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:=inttoreal(E1.val) End IF T.type:=integer THEN Begin T.type:=real T.val:=inttoreal(T.val) End Print(+,E1.val,T.val)ENDETE.type:=T.typeE.val:=T.valTnum.numT.type:=realT.val:=num.num.lexvalTnumT.type:=integerT.val:=num.lexval10 假設說明是由下列文法產(chǎn)生的： Did L L,id L|:T Tinteger |real （a）建立一個翻譯模式，把每一個標識符的類型加入到符號表中。 （b）從（a）中的翻譯模式構造一個預翻譯程序。 答： (a)：產(chǎn)生式翻譯模式Did LD.Type:=L.Typeaddtype(id.entry, D.type)L,id L1L.Type:=L1.Typeaddtype(id.entry, L.type)L:TL.type:=T.typeTintegerT.type:=integerTrealT.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.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 errorend11為下面的算術表達式文法寫一個語法制導的翻譯方案，它將每個子表達式E的符號（即值大于零還是小于零）記錄在屬性E.sign中（屬性值分別用POS或NEG表示）。你可以假定所有的整數(shù)都不為零，這樣就不用擔心零的符號。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.sign := NEG else E.sign := POSE unsigned_integer E.sign := POS12為下面文法寫一個語法制導的定義，用S的綜合屬性val給出下面文法中S產(chǎn)生的二進制數(shù)的值。例如，輸入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. val := 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 試問下面的程序?qū)⒂性鯓拥妮敵?？分別假定： （a）傳值調(diào)用（call-by-value）； （b）引用調(diào)用（call-by-reference）； （c）復制恢復（copy-restore）； （d）傳名調(diào)用（call-by-name）。 program main(input,output）； procedure p（x,y,z）； begin y：y1； z：zx； end； begin a：2； b：3； p(ab,a,a)； print a end.答：1)傳地址：所謂傳地址是指把實在參數(shù)的地址傳遞給相應的形式參數(shù)。在過程段中每個形式參數(shù)都有一對應的單元，稱為形式單元。形式單元將用來存放相應的實在參數(shù)的地址。當調(diào)用一個過程時，調(diào)用段必須領先把實在參數(shù)的地址傳遞到一個為被調(diào)用段可以拿得到的地方。當程序控制轉(zhuǎn)入被調(diào)用段之后，被調(diào)用段首先把實參地址捎進自己相應的形式單元中，過程體對形式參數(shù)的任何引用1或賦值都被處理成對形式單元的間接訪問。當調(diào)用段工作完畢返回時，形式單元(它們都是指示器)所指的實在參數(shù)單元就持有所指望的值。 2)傳結(jié)果：和“傳地址”相似(但不等價)的另一種參數(shù)傳遞力法是所謂“傳結(jié)果”。這種方法的實質(zhì)是，每個形式參數(shù)對應有兩個申元，第1個單元存放實參的地址，第2個單元存放實參的值。在過程體中對形參的任何引用或賦值都看成是對它的第2個單元的直接訪問。但在過程工作完畢返回前必須把第2個單元的內(nèi)容行放到第1個單元所指的那個實參單元之中。 3)傳值：所謂傳值，是一種簡單的參數(shù)傳遞方法。調(diào)用段把實在參數(shù)的值計算出來并存放在一個被調(diào)用段可以拿得到的地方。被調(diào)用段開始丁作時，首先把這些值抄入形式中元中，然后就好像使用局部名一樣使用這些形式單元。如果實在參數(shù)不為指示器，那末，在被調(diào)用段中無法改變實參的值。 4)傳名：所謂傳名，是一種特殊的形實參數(shù)結(jié)合方式。解釋“傳名”參數(shù)的意義：過程調(diào)用的作用相當于把被調(diào)用段的過程體抄到調(diào)用出現(xiàn)的地方，但把其中任一出現(xiàn)的形式參數(shù)都替換成相應的實在參數(shù)(文字替換)。它與采用“傳地址”或“傳值”的方式所產(chǎn)生的結(jié)果均不相同。 (a)2； (b)8； (c)7； (d)9。14 對以下的Pascal程序畫出過程c第二次被激活時的運行棧，控制鏈和訪問鏈。說明在c中如何訪問變量x。program env； procedure a； var x:integer； procedure b； procedure c； begin x:=2；b end；procedure c begin c end；procedure b begin b end；procedure a begin a end. main答： envcontrol linkaccess linkacontrol linkaccess linkx bcontrol linkaccess link ccontrol linkaccess link bcontrol linkaccess link caccess linkcontrol link說明：c中沿著存取鏈向前走兩步，到過程a的活動記錄中就可以訪問到變量x。15 下面給出一個 C 語言程序及其在 SPARC/SUN 工作站上經(jīng)某編譯器編譯后的運行結(jié)果。從運行結(jié)果看，函數(shù) func中 4個局部變量 i1, j1, f1, e1的地址間隔和它們類型的大小是一致的，而 4個形式參數(shù) i, j, f, e的地址間隔和它們的類型的大小不一致，試分析不一致的原因。注意，輸出的數(shù)據(jù)是八進制的。 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); 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); 運行結(jié)果是： Address of i, j, f, e = 35777772536, 35777772542, 35777772544, 35777772554 Address of i1, j1, f1, e1 = 35777772426, 35777772424, 35777772420, 35777772414 Sizes of short, int, long, float, double = 2, 4, 4, 4, 8，請問為什么？答：C語言編譯器是不做實在參數(shù)和形式參數(shù)的個數(shù)和類型是否一致的檢查的，由程序員自己保證它們的一致性。但是對于形式參數(shù)和實在參數(shù)是不同的整型（如一個是short型，另一個是long型），或者是不同的實型，編譯器則試圖保證目標代碼運行時能得到正確的結(jié)果，條件是，當需要高級別類型數(shù)據(jù)向低級別類型數(shù)據(jù)轉(zhuǎn)換時，不出現(xiàn)溢出。這樣，C編譯器作的約定是，當整型或?qū)嵭蛿?shù)據(jù)作為實在參數(shù)時，分別將它們提升到long和double類型的數(shù)據(jù)傳遞到被調(diào)用函數(shù)。被調(diào)用函數(shù)根據(jù)形式參數(shù)所聲明的類型，決定是否要將實在參數(shù)向低級別類型轉(zhuǎn)換。低地址放高位高地址放低位shortlong圖5.2 長整型和短整型在本例中，long類型數(shù)據(jù)占4個字節(jié)，而short類型數(shù)據(jù)只占2個字節(jié)。因此被調(diào)用函數(shù)把實在參數(shù)的低位字節(jié)的內(nèi)容當成是自己所需的數(shù)據(jù)，見圖5.2注意，對于SUN工作站來說，低地址存放整型數(shù)據(jù)的高位。floatdoublee圖5.3 雙精度型和浮點型對于實型來說。double類型是8個字節(jié)，而float類型4個字節(jié)。被調(diào)用函數(shù)把實在參數(shù)的前4個字節(jié)作為自己所需的數(shù)據(jù)，因為double后面4個字節(jié)的內(nèi)容都是為了增加精度用的，見圖5.3。e，8個字節(jié)在main函數(shù)中參數(shù)壓棧時的觀點在func函數(shù)中存取形式參數(shù)時的觀點4個字節(jié)，起始地址357777725544個字節(jié)，起始地址357777725442個字節(jié)，起始地址357777725422個字節(jié)，起始地址35777772536f，8個字節(jié)j，4個字節(jié)i，4個字節(jié)棧的增長方向圖5.4 參數(shù)在棧中的情況這樣在main函數(shù)中依次將參數(shù)提升后反序進棧，大小分別為8, 8, 4, 4。在func函數(shù)中，按形式參數(shù)的類型，把這些存儲單元的一部分看成是形式參數(shù)的存儲單元，見圖5.4。從這個圖不難理解為什么形式參數(shù)的地址間隔和它們的類型大小不一致了。注意，現(xiàn)在的編譯器將需要進行類型轉(zhuǎn)換的形式參數(shù)（類型是char、short、float等）另行分配在局部數(shù)據(jù)區(qū)，當控制進入被調(diào)用過程時，首先將調(diào)用過程壓棧的需要進行類型轉(zhuǎn)換的實在參數(shù)取出，把它們存入所分配的局部數(shù)據(jù)區(qū)存儲單元，并同時完成必要的數(shù)據(jù)類型的轉(zhuǎn)換。在這種情況下，不會出現(xiàn)本題所碰到的現(xiàn)象。另外，在SPARC工作站上，整型數(shù)據(jù)的高位存放在低地址，而低位存放在高地址。如果是X86機器，數(shù)據(jù)的高低位不是按這樣的次序存放，那也不會出現(xiàn)本題所碰到的現(xiàn)象。下面是某個編譯器的類型提升函數(shù)，供讀者理解用（備注：int和long的大小一樣）。Type promote(Type ty)switch(ty-op)case ENUM:return inttype;case INT:if (ty-size size)return inttype;break;case UNSIGNED:if (ty-size size)return inttype;break;case FLOAT:if (ty-size size)return doubletype;return ty;16 試把下列C語言程序的可執(zhí)行語句翻譯為(a)一棵語法樹， (b)后綴式， (c)三地址代碼。main() int i; int a10; while (i=10) ai=0;while答：(a).一棵語法樹賦值表達式布爾表達式表達式表達式數(shù)組元素表達式=下標表達式110a01(b) 后綴式為： i 10= a i 0 = while從理論上可以說while(i=10) ai=0; 的后綴式如上面表示。但若這樣表示，在執(zhí)行while操作時，賦值語句已經(jīng)執(zhí)行，這顯然與語義不符，因此改為：i 10 =BM a i 0 = BRL其中BM操作為當表達式為假時轉(zhuǎn)向，BRL是一個一目運算，無條件轉(zhuǎn)向。(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 vt2 do begin 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，問此程序?qū)⒆鲂┦裁?？其中MAXINT為目標機器允許的最大整數(shù)。(b)試構造一個翻譯pascal的for語句為三地址代碼的語法制導定義。 答：（a）程序?qū)@示如下六個整數(shù)： MAXINT -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 語法制導定義如下： 產(chǎn)生式 動作 Sfor E do S1 S.begin := newlabel S.first := newtemp S.last := newtemp 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.init := 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請回答，對函數(shù)f2為什么沒有類似的警告錯誤。答：對于函數(shù)f1，局部變量x聲明的作用域是整個函數(shù)體，導致在函數(shù)體中不可能訪問形式參數(shù)x。由于這是一個合法的C語言函數(shù)，因此編譯器給出警告錯誤。對于函數(shù)f2，由于局部變量x的作用域只是函數(shù)體的一部分，不會出現(xiàn)上述問題，因而編譯器不報錯。19考慮一個簡單語言，其中所有的變量都是整型（不需要顯式聲明），并且僅包含賦值語句、讀語句和寫語句。下面的產(chǎn)生式定義了該語言的語法（其中l(wèi)it表示整型常量；OP的產(chǎn)生式?jīng)]有給出，因為它和下面討論的問題無關）。ProgramStmtListStmtList Stmt StmtList | StmtStmtid := Exp; | read (id ); | write ( Exp ); Expid | lit | Exp OP Exp我們把不影響write語句輸出值的賦值（包括通過read語句來賦值）稱為無用賦值，寫一個語法指導定義，它確定一個程序中出現(xiàn)過賦予無用值的變量集合（不需要知道無用賦值的位置）和沒有置初值的變量集合（不影響write語句輸出值的未置初值變量不在考慮之中）。非終結(jié)符StmtList和Stmt用下面3個屬性（你根據(jù)需要來定義其它文法符號的屬性）：（1）uses_in：在本語句表或語句入口點的引用變量集合，它們的值影響在該程序點后的輸出。（2）uses_out：在本語句表或語句出口點的引用變量集合，它們的值影響在該程序點后的輸出。（3）useless：本語句表或語句中出現(xiàn)的無用賦值變量集合。答：Exp的屬性uses表示它引用的變量集合。Program的useless和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_inStmtList.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.lexemeStmt.uses_out then elseid.lexeme; Stmt.uses_in := if id.lexemeStmt.uses_out then (Stmt.uses_outid.lexeme)Exp.uses else Stmt.uses_outStmt read (id ); Stmt.useless:=if id.lexemeStmt.uses_out then elseid.lexeme;Stmt.uses_in := Stmt.uses_out id.lexemeStmt write ( Exp );Stmt.useless := , Stmt.uses_in := Stmt.uses_out Exp.usesExp idExp.uses:= id.lexemeExp litExp.uses:= Exp Exp1 OP Exp2Exp.uses:= Exp1.uses Exp2.uses20 為下列C程序生成目標代碼。main()int i;int a10;while(i=10) ai=0; 答：21 試構造下面的程序的流圖，并找出其中所有回邊及循環(huán)。 read P x := 1 c := P * P if c 100 goto L1 B := P * P x := x + 1 B := B + x write x halt L1: B:= 10 x := x + 2 B := B + x write B 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 C I := I + 1 if I B2，相應的循環(huán)是B2。 （1）代碼外提：由于循環(huán)中沒有不變運算，故不做此項優(yōu)化 （2）強度削弱：B2中A和B都是I的歸納變量。優(yōu)化結(jié)果顯示在圖9.4(2)中。 （3）刪除歸納變量：變換循環(huán)控制條件，刪除歸納變量I后的流圖顯示在圖9.4(3)中 23 考慮下面的三地址語句序列：b := 1b := 2if w = x goto L2e := bgoto L2L1:goto L3L2: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)的結(jié)點。答：（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 L4（5）goto L5（6）L4:g := g + 1h := 8goto L1（7）L5:h := 9（8）（3） 結(jié)點5、7和3構成一個循環(huán)，其中5是入口結(jié)點。24 對下面的程序片段作出其程序流圖并計算：（1）各基本塊的到達_定值集INB；（2）各基本塊中各變量引用點的ud鏈；（3）各基本塊出口的活躍變量集V_OUTB；（4）各基本塊中變量定值點的du鏈。 I := 1 J := 0 L1: J := J + I read I if I 100 goto L2 write J halt L2 : I := I * I答：本題程序的程序流圖如圖9.6(1)所示。 （1）計算各基本塊的到達-定值集INB。公式為： INB = OUTP PPB OUTB = GENB (