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

1、精品文庫 平時作業(yè) 1對于下列語言分別寫出它們的正規(guī)表達式。 (1) 英文字母組成的所有符號串，要求符號串中順序包含五個元音。 答:令Letter表示除這五個元音外的其它字母。 (letter) A(letter) E(letter) l(letter) O(letter) U(letter) (2) 英文字母組成的所有符號串，要求符號串中的字母依照詞典順序排列。 答：A*b*.Z* 工=0,1上的含偶數(shù)個1的所有串。 答：(0|10*1)* 藝=0,1上的含奇數(shù)個1的所有串。 答：(0|10*1)*1 (5)具有偶數(shù)個0和奇數(shù)個1的有0和1組成的符號串的全體。 答：設(shè)S是符合要求的串，|S|

2、=2k+1 (k 駅。 則 Sts 10|S21，|S1|=2k (k0 )，|3|=2k (k 且S1是0,1上的串，含有奇數(shù)個0和奇數(shù)個1。 S2是0,1上的串，含有偶數(shù)個0和偶數(shù)個1。 考慮有一個自動機 M1接受S1，那么自動機 M1如下： 00111 和L(M 1)等價的正規(guī)表達式，即 Si為： (00|11)|(01|10)(00|11)*(01|10)*(01|10)(00|11)* 類似的考慮有一個自動機 M2接受S2,那么自動機 M2如下: 00111 和L(M 2)等價的正規(guī)表達式，即 S2為： (00|11)|(01|10)(00|11)*(01|10)* 因此，S為： (

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

4、2, 3) 其中5定義如下： 5 (qo, 0) =qi 5 (qo, =qo 5(qi, 0) =q2 5 (qi, =qo q3, qo, qi, q2, DFA M=(0 , 1 , qo, 5) 其中5定義如下: 5 (qo, =qi 5 (qo, =qo 5 (qi, =q2 5 (qi, =qi 5 (q2, 5 (q2, =q3 =q2 3下面是用正規(guī)式表示的變量聲明： (int | float ) id (, id )* ; 請改用上下文無關(guān)文法表示，也就是寫一個上下文無關(guān)文法，它和該正規(guī)式等價。 答：DT TL； T T int | float L T L, id | id

5、4試分析下面給出的if-the n-else語句的文法，它的提出原本是為了矯正dan gli ng-else (懸而未 歡迎下載2 精品文庫 決的-else)文法的二義性： stmt 7 if expr then stmt |matched-stmt matched- stmt 7 if expr the n matched -stmt else stmt |other 試說明此文法仍然是二義性的。 答：考慮句子if e then if e then other else if e then other else others具有如下所示的兩種分析樹stmt expr the n e if s

6、tmt if matched-stmt expr the n matched-stmt e other if esle stmt matched-stmt expr the n matched-stmt e other esle stmt matched-stmt other stmt matched-stmt if expr the n matched-stmt e if esle stmt esle stmt matched-stmt expr the n e stmt other expr the n matched-stmt e other if matched-stmt other

7、則上面給出的if-then-else文法仍是二義性的。 5證明下面文法是SLR(1)文法，并構(gòu)造其SLR分析表。 E7 E+T|T T7 TF|F F7 F*|a|b 答:該文法的拓廣文法 G為 其LR(0)項目集規(guī)范族和goto函數(shù)(識別活前綴的DFA)如下: 10 = E 11 = E I3 = T I6 = E I9 = E E, E E+T, E T, T TF, T 7 7 E , E 7 E +TI2 = E 7 F , F 7 F *4 = F 7 E+ T, T 7 E+T，T TF, T 7 T F, F -F7- 7,FF7 b 7 T , T 7 T F, F 7. F*

8、, F 7. a, F 7. b 7 a I5 = F 7 b 7. F, F 7. F*, F 77 =(TF 7TFb , F 7 F I8*= F 7 F* 7 F*, F 7 a, F 7 b (0) E 7 E (1) E 7 e+t E 7 T (3) T 7 TF T 7 F (5) F 7 F* F 7 a (7) F 7 b 歡迎下載8 b b b 求 FOLLOW 集: FOLLOW(F)= + , 構(gòu)造的SLR分析表如下: FOLLOW(E)= + , $ FOLLOW(T)= + , $ , a, b $ , a, b, * 狀態(tài) action goto + 4 a b

9、 $ E T F 0 S4 35 1 2 3 1 36 acc 2 r2 S4 S5 7 3 4 S8 r4 r4 4 4 陽 re r6 r6 re 5 r7 r7 r7 r7 r7 6 S4 S5 g 3 7 r3 S6 r3 r3 r3 8 r5 5 r5 r5 r5 9 r1 S4 S5 r1 7 顯然，此分析表無多重定義入口，所以此文法是 SLR文法。 6為下面的文法構(gòu)造LALR(1)分析表 Sf E Ef E+T|T Tf (E)|a G： 答:其拓廣文法 (0) S f E+T (4) T 構(gòu)造其LR(1)項目集規(guī)范族和 Io= S f S, $, S Ii = S f S，$

10、I2= S f E，$, E I4 = T f ( E), $/+, E I5= T f a , $/+ I6 = E I7 = T I9 = T Iio = T Ii3 = E Ii5 = E f (E) goto函數(shù)(識別活前綴的 DFA)如下： f E, $, E f E+T, $/+T f (Ef$/+TT$f； a, $/+ f E +T, $/+= E f T , $/+ f E+T, )/+, E T f TE/+/+, T f a, )/+ f E+ T, $/+, T f (E), $/+, T f a, $/+ f (E ), $/+, Ef E +T, )/+I8 = E

11、 f T , )/+ f ( E), )/+, Ef E+T, )/+, Ef T, )/+, T f (E), )/+, T f a , )/+ I11= E f E+，$/+ l12 = T f (E) , $/+ f E+ T, )/+, Tf (E), )/+, T f 14 =aT+f (E ),)/+, E f E+T , )/+ I16 = T f (E) ,)/+ f a, )/+ f E +T, )/+ T 16 12 10 112 11J3 110 19 T 石 V_ EK riE a 合并同心的LR(1)項目集，得到LALR的項目集和轉(zhuǎn)移函數(shù)如下： |0= S 7. S,

12、 $, S7. E, $, E7. E+T, $/+, E 7. T, $/+, T I1 = S 7 S，, $2 = S 7 E，, $, E7 E，+T, $/+8= E 7 T , $/+/) 14.9 = T 7 ( E), $/+/), E 7. E+T, )/+, E T 77 (E),)y/+j, T 7. a, )/+ 15.10 = T l7,14 = T I 12,16 = T S, $, S E, $, E S，$2 = S 7 E，$, E r E), $/+/), E 7 E+T, )/+, E T 亠(E),)/+l，T 7 a , $/+/) I6,i3 = E

13、 7 E+ T, $/+/), T(E), $/+/), T 7 (E ), $/+/), E 7 E +TI 1/+5= E 7 e+T , $/+/) 7 (E) , $/+/) 7. (E), $/+, T a, $/+/) a, $/+ LALR分析表如下: 0 廠 T廠、 r IU 1 3 J-一4 111, 15 + 12 S T 10 13,0 I屍10 14,9 17,14 STATE action goto A + ( ) $ s E T 0 S5J0 S4.9 1 2 3.8 1 acc 2 56.13 r1 3,8 r3 r3 3 43 35J0 34.9 7J4 3.8

14、 5,10 r5 5 r5 6,13 S5J0 54.9 11,15 7,14 36,13 312JG 11,15 2 2 r2 12JS 4 4 r4 E T E + id | id 是 SLR(1)文法。 7(1)通過構(gòu)造識別活前綴的DFA和構(gòu)造分析表，來證明文法 答:先給出接受該文法活前綴的 DFA如下： 再構(gòu)造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 T E + M id | idE t M E +

15、 id | id M T sM T 名 請指出其中有幾個文法不是LR(1)文法，并給出它們不是LR(1)文法的理由。 答:只有文法 E T M E + id | id 精品文庫 M T E 不是LR(1)文法。因為對于句子 id+id + id來說，分析器在面臨第一個id時需要做的空歸約次數(shù)和句子中+ id的 個數(shù)一樣多，而此時句子中+ id的個數(shù)是未知的。 D T T T L T R T 8根據(jù)自上而下的語法分析方法，構(gòu)造下面文法的LL (1)分析表。 TL int | real id R ,id R | 答：先計算FIRST和FOLLOW FIRST(D) = FIRST(T) = i n

16、t,real FIRST(L) = id FIRST(R) = , 門 FOLLOW(D) = FOLLOW(L) = $ FOLLOW(T) = id FOLLOW(R) = $ LL(1)分析表如下： int real id $ D D - TL D - TL T T - int T - real L L - idR R R - ,idR R - 9下面的文法產(chǎn)生的表達式是對整型和實型常數(shù)應(yīng)用算符 +形成的。當(dāng)兩個整數(shù)相加時，結(jié)果仍為整 數(shù)，否則就是實數(shù)。 E E+T|T T num.num|num (a) 給出一個語法制導(dǎo)定義以確定每個子表達式的類型。 歡迎下載 11 (b)擴充(a)中

17、的語法制導(dǎo)定義把表達式翻譯成前綴形式，并且決定類型。使用一元算符inttoreal 把整型值轉(zhuǎn)換成相等的實型值，以使得前綴形式中的+的兩個操作對象是同類型的。 答: (a): 產(chǎn)生式 語義規(guī)則 E E1+T IF (E1.t yp e=i nteger) and (T.t yp e=i nteger) THEN E.t ype:=in teger ELSE E.t yp e:=real E T E.ty pe:=T.t ype T num.num T.t yp e:=real T num T.t ype:=in teger (b): 產(chǎn)生式 語義規(guī)則 E E1+T IF (E1.t ype=i

18、n teger) and (T.t ype=in teger) THEN BEGIN E.t ype:=in teger Print( +,E1.val,T.val) END ELSE BEGIN E.t yp e:=real IF E1.t yp e=i nteger THEN Begi n E1.t yp e:=real E1.val:=i nttoreal(E1.val) End IF T.ty pe:=i nteger THEN Begi n T.t yp e:=real T.val:=in ttoreal(T.val) End Print( +,E1.val,T.val) END T

19、 num.num E.typ e:=T.t ype E.val:=T.val T.t yp e:=real T.val:= num.num .lexval T num T.t ype:=in teger T.val:= num .lexval 10假設(shè)說明是由下列文法產(chǎn)生的： X id L L ,id L|:T T integer |real (a) 建立一個翻譯模式，把每一個標(biāo)識符的類型加入到符號表中。 (b) 從(a)中的翻譯模式構(gòu)造一個預(yù)翻譯程序。 答： 歡迎下載 精品文庫 : 產(chǎn)生式 翻譯模式 D id L D.Ty pe:=L.Ty pe addtype( id.entry, D.t

20、ype) L ,id L1 L.T yp e:=L1.Ty pe addtype( id.entry, L.type) L:T L.t yp e:=T.t ype T integer T.ty pe:=i nteger T real T.t yp e:=real (b): P rocedure D; begin If lookahead=id the n Begi n Match(id); D.typ e=L; addt yp e(id.e ntryQ.t ype) end else error end Function L: DataT ype; Begin If lookahead=the

21、n Begin Match( )； If lookahead=id the n begin match(id); L.T yp e=L; addt yp e(id.e ntry,L.t yp e); return(L.t ype) end Else error End Else if lookahead= the n Begin Match(: L.T yp e=T; return(L.T ype) end else error 歡迎下載29 End Function T: DataT ype; Begin If lookahead=in teger the n Begi n Match(i

22、nteger); return (i nteger) end else If lookahead=real the n Beg in Match(real); return(real) end else error end 11為下面的算術(shù)表達式文法寫一個語法制導(dǎo)的翻譯方案， 它將每個子表達式E的符號（即值大于零 還是小于零）記錄在屬性E.sign中（屬性值分別用POS或NEG表示）。你可以假定所有的整數(shù)都不 為零，這樣就不用擔(dān)心零的符且 Et E *E | +E | -E | unsigned_integer 答： Et Et Et Et Ei *E2 if Ei.sign= E2.sign

23、 then E.sign := POS elseE.sign := NEG +Ei E.sign := E1.sign -E1 if E1 .sign= POS then E.sign := NEG elseE.sign := POS un sig ned_in teger E.sig n := P OS 12為下面文法寫一個語法制導(dǎo)的定義，用S的綜合屬性val給出下面文法中S產(chǎn)生的二進制數(shù)的值。 例如，輸入101.101時， S. val := 5.625。（不得修改文法。） 答: S T L . R | L L T L B | B R T B R | B B T 0 | 1 S T L .

24、 R S T L L T L1 B L T B R T B R1 R T B B T 0 B T 1 S. val := L. val + R. val S. val := L. val L. val := L1. val x2 + B. val L. val := B. val R. val := (R1. val + B. val)/2 R. val := B. val/2 B. val := 0 B. val := 1 傳值調(diào)用(call-by-value)； 引用調(diào)用(call-by-refere nee)； 復(fù)制恢復(fù)(copy-restore)； 傳名調(diào)用(call-by-name)

25、。 13試問下面的程序?qū)⒂性鯓拥妮敵?？分別假定： (a) (b) (c) (d) p rogram main (i npu t,out pu t)； procedurep (x,y,z)； begin y：= y+ 1； z:= z+x ； end; begin a：= 2； b:= 3； p(a+ b,a,a)； print a end. 答：1).傳地址：所謂傳地址是指把實在參數(shù)的地址傳遞給相應(yīng)的形式參數(shù)。在過程段中每 當(dāng)調(diào)用段工作完畢返 個形式參數(shù)都有一對應(yīng)的單元，稱為形式單元。形式單元將用來存放相應(yīng)的實在參數(shù)的地址。 當(dāng)調(diào)用一個過程時，調(diào)用段必須領(lǐng)先把實在參數(shù)的地址傳遞到一個為被調(diào)用段

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

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

28、ascal程序畫出過程c第二次被激活時的運行棧，控制鏈和訪問鏈。說明在c中如何訪 問變量X。 Program env ； procedure a ； var x:i nteger； procedure b ; procedure c ; begin x:=2 ； b end; procedure c beg in c end; p rocedure b begin b end； procedure a beg in a end. ma in 答: env control link access link a co ntFol li nk access li nk x b con trol li

29、 nk H H access link con trol li nk access link H _ I control link - II- - ：T-1I|-III- access link l= -_-_ - rfa JI fl 11 -J I k control link c access link 說明：c中沿著存取鏈向前走兩步，到過程 a的活動記錄中就可以訪問到變量x。 15下面給出一個C語言程序及其在 SP ARC/SUN工作站上經(jīng)某編譯器編譯后的運行結(jié)果。從運行 結(jié)果看，函數(shù)func中4個局部變量i1, j1, f1, e1的地址間隔和它們類型的大小是一致的，而4個形 式參數(shù)i

30、, j, f, e的地址間隔和它們的類型的大小不一致，試分析不一致的原因。注意，輸出的數(shù)據(jù)是 八進制的。 func (i, j, f, e) short i, j; float f, e; short i1, j1; float f1, e1; prin tf( Address of i, j, f, e = %o, %o, %o, %o n, prin tf( Address of i1, j1, f1, e1 = %o, %o, %o, %o n, prin tf( Sizes of short, i nt, Io ng, float, double = %d, %d, %d, %d, %

31、d n, sizeof(short), sizeof(i nt), sizeof( Ion g), sizeof(float), sizeof(double); mai n() short i, j; float f, e; fun c(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 o

32、f short, i nt, Io ng, float, double = 2, 4, 4, 4, 8 請問為什么？ 答: c語言編譯器是不做實在參數(shù)和形式參數(shù)的個數(shù)和類型是否一致的檢查的，由程序員自己保證它們的一致性。 但是對于形式參數(shù)和實在參數(shù)是不同的整型（如一個是short型，另一個是long型），或者是不同的實型，編譯器 則試圖保證目標(biāo)代碼運行時能得到正確的結(jié)果，條件是，當(dāng)需要高級別類型數(shù)據(jù)向低級別類型數(shù)據(jù)轉(zhuǎn)換時，不出現(xiàn) 溢出。這樣，C編譯器作的約定是，當(dāng)整型或?qū)嵭蛿?shù)據(jù)作為實在參數(shù)時，分別將它們提升到long和double類型的 數(shù)據(jù)傳遞到被調(diào)用函數(shù)。被調(diào)用函數(shù)根據(jù)形式參數(shù)所聲明的類型

33、，決定是否要將實在參數(shù)向低級別類型轉(zhuǎn)換。 因此被調(diào)用函數(shù)把實在參數(shù)的低位字 在本例中，long類型數(shù)據(jù)占4個字節(jié)，而short類型數(shù)據(jù)只占2個字節(jié)。 節(jié)的內(nèi)容當(dāng)成是自己所需的數(shù)據(jù)，見圖5.2 long 低地址 放高位 高地址 放低位 short 圖5.2長整型和短整型 SUN工作站來說，低地址存放整型數(shù)據(jù)的高位。 注意，對于 對于實型來說。double類型是8個字節(jié)，而float類型be個字節(jié)。被調(diào)用函數(shù)把實在參數(shù)的前4個字節(jié)作為自己 所需的數(shù)據(jù)，因為 double后面4 個字節(jié)的內(nèi)容都是為了增加精度用的.見圖 這樣在 main函數(shù)中依次將參數(shù)i提升 數(shù)壓棧時的觀點 f，8個字節(jié) 把這些存儲單

34、元的一部分看成是形式參數(shù)的存儲單元， 它們的類型大小不一致向。e，8個字節(jié)S 大小分別為 5.3。 8, 8, 4, 4。在funcc函數(shù)中存取形式參數(shù)的類型, 式參數(shù)時的觀點 j，4個字節(jié) 5.4。 2個字節(jié)，起始地址 2個字節(jié)，起始地址 、4個字節(jié)，起始地址 35777772536 35777772542 35777772544 參數(shù) 間隔和 圖5.4參數(shù)在棧中的情況 注意，現(xiàn)在的編譯器將需要進行類型轉(zhuǎn)換的形式參數(shù)（類型是Char、short、float等）另行分配在局部數(shù)據(jù)區(qū), 當(dāng)控制進入被調(diào)用過程時，首先將調(diào)用過程壓棧的需要進行類型轉(zhuǎn)換的實在參數(shù)取出，把它們存入所分配的局部數(shù) 據(jù)區(qū)存儲

35、單元，并同時完成必要的數(shù)據(jù)類型的轉(zhuǎn)換。在這種情況下， 另外，在SPARC工作站上，整型數(shù)據(jù)的高位存放在低地址， 高低位不是按這樣的次序存放，那也不會出現(xiàn)本題所碰到的現(xiàn)象。 下面是某個編譯器的類型提升函數(shù)，供讀者理解用（備注： Type pro mote（T ype ty） 不會出現(xiàn)本題所碰到的現(xiàn)象。 而低位存放在高地址。如果是 int和long的大小一樣）。 X86機器，數(shù)據(jù)的 switch(ty-op) case ENUM: return inttype; case INT: if (ty-size size) return inttype; break; case UNSIGNED: if

36、 (ty-size size) return inttype; break; case FLOAT: if (ty-size size) retur n doublet ype; return ty; 16試把下列C語言程序的可執(zhí)行語句翻譯為 (a) 棵語法樹， (b) 后綴式， (C)三地址代碼。 mai n() int i; int a10; while (i=10) ai=0; 后綴式為：i 10= a i 0 = while (b) 從理論上可以說while(iv=10) ai=O; 值語句已經(jīng)執(zhí)行，這顯然與語義不符， i 10 =下一個語句開始地址BM a i 0 = 本語句地址 B

37、RL 的后綴式如上面表示。但若這樣表示，在執(zhí)行 因此改為： while操作時，賦 其中BM操作為當(dāng)表達式為假時轉(zhuǎn)向 下一個語句開始地址，BRL是一個一目運算，無條件轉(zhuǎn)向 本語句始址。 (C)三地址代碼序列為: 100 if i = 10 got 102 101 goto 106 102 t1:=4*i 103 t2:=a 104 t2t1:=0 105 goto 100 106 17 Pascal語言中，語句：for v 與下列代碼序列有相同含義 begi n t1:=i nitial;t2:=fi nal; if t1=t2 then begin v:=t1; stmt while vt2

38、do beg in v : =succ( v)； stmt end end end : =in itial to final do stmt (a) 試考慮下述Pascal程序 p rogram forloop (i nput, out pu t); var i,i nitialfi nal: in teger; beg in read(i nitial, fin al); for i:= in itial to final do write(i) end 對于 initial=MAXINT-5 和 final= 大整數(shù)。 (b) 試構(gòu)造一個翻譯pascal的for 答： (a) 程序?qū)@示如

39、下六個整數(shù)：MAXINT -5 MAXINT -4 MAXINT -3 MAXINT -2 MAXINT -1 MAXINT (b) 為簡單起見，for語句的三地址代碼如下： t1 := in itial t2 := final if t1 t2 goto S.n ext v := t1 stmt.code S.begi n: if v t2 goto S.n ext v := succ(v) stmt.code goto S.begi n 語法制導(dǎo)定義如下： 產(chǎn)生式動作 S for S.code:=ge n( S.first |gen(S.begin“ ： ” MAXINT問此程序?qū)⒆鲂┦裁?/p>

40、？其中 MAXINT為目標(biāo)機器允許的最 語句為三地址代碼的語法制導(dǎo)定義。 E do S1 S.begin := newlabel S.first := “ :=” E.init) |gen(S.last“ := ” )|ge n(“if ” S.curr “” S.Last newtemp S.last := newtemp S.curr:= newtemp E.fi nal) |ge n(“if ” S.first “ firSt)ast “goto ” S.next) |S1.code |gen(S.curr := succ(S.curr) | E v:=in itial to final

41、 E.i nit := in itial. place E.final := fin al. place 18對于下面C語言文件S.C f1(i nt X) long X； X = 1; f2(i nt X) long X； X = 1; 某編譯器編譯時報錯如下： S.C： In function f1: s.c:3: warning: declaratio n of X shadows a p arameter 請回答，對函數(shù)f2為什么沒有類似的警告錯誤。 答： X。 對于函數(shù)f1，局部變量X聲明的作用域是整個函數(shù)體，導(dǎo)致在函數(shù)體中不可能訪問形式參數(shù) 由于這是一個合法的C語言函數(shù)，因此編譯器

42、給出警告錯誤。 對于函數(shù)f2,由于局部變量X的作用域只是函數(shù)體的一部分，不會出現(xiàn)上述問題，因而編譯器不 報錯。 19考慮一個簡單語言，其中所有的變量都是整型(不需要顯式聲明)，并且僅包含賦值語句、讀語 句和寫語句。下面的產(chǎn)生式定義了該語言的語法(其中 lit表示整型常量；0P的產(chǎn)生式?jīng)]有給出，因 為它和下面討論的冋題無關(guān))。 P rogram- StmtList Stmt T Exp T StmtList T Stmt StmtList | Stmt id := Exp; I read (d ); | write ( Exp ); id | lit | Exp OP Exp 我們把不影響wri

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

44、屬性uses表示它引用的變量集合。Program的useless和no_initial分別表示程序的無用賦值變量集合和 StmtList.uses_out:= 0; Program.useless := StmtList.useless; P rogram. no_i nitial := StmtList.usesn; StmtList T Stmt StmtList 1 StmtList 1.uses_out := StmtList.uses_out; Stmt.uses_out := StmtList 1.uses_i n; StmtList.uses_in := Stmt.uses_in

45、 StmtList.useless := StmtList uselessStmt.useless; 未置初值變量集合。 P rogram T StmtList StmtList T Stmt Stmt.uses_out := StmlList.uses_out; StmlList.uses_in := Stmt.uses_i n; StmtList.useless := Stmt.useless Stmt id := Exp; Stmt.useless :=if id .lexeme cStmt.uses_out then。else id .lexeme; Stmt.uses in := i

46、f id.lexemeStmt.uses out Stmt read (id ); Stmt Exp T id Exp T lit Exp T Expi OP Exp2 write ( Exp ); then (Stmt.uses_out - idexeme2Exp.uses else Stmt.uses_out Stmt.useless:=if id .lexeme Stmt.uses_out then。eIsC idexeme; Stmt.uses_in := Stmt.uses_out -idexeme Stmt.useless := 0, Stmt.uses_ in := Stmt.u

47、ses_out . Exp. uses Exp.uses:= id .lexeme Exp. uses:= 0 Exp. uses:= Exp i.usesExp 2.uses 20為下列C程序生成目標(biāo)代碼。 mai n() int i; int a10; while(i=10) ai=0; 答： 21試構(gòu)造下面的程序的流圖，并找出其中所有回邊及循環(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 w

48、rite 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，相應(yīng)的循環(huán)是B2。 耳 B 圖9. 4(1)程序流圖 J I ：= 1 read L K (1)代碼外提：由于循環(huán)中沒有不變運算，故不做此項優(yōu)化 化結(jié)果顯示在圖9.4(2)中。 (2)強度削弱：B2中A和B都是I的歸納變量。優(yōu) 巧：二 K * I 壬：二 J *

49、I L: A := 3j B ：= 3? C := A * B write C I := I + 1 S : - Sj + K :二 Sg + J if I 100 goto L halt 圖9.4(2)經(jīng)弓gj度削弱后的就圖 (3)刪除歸納變量：變換循環(huán)控制條件，刪除歸納變量I后的流圖顯示在圖 9.4(3)中 y halt 圖9.4(3)刪除歸納變量的程序流圖 23考慮下面的三地址語句序列： b := 1 b := 2 if w = x goto L2 e := b goto L2 L1: goto L3 L2: c := 3 b := 4 c := 6 L3: if y = z goto

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

51、L5: h := 9 (3)結(jié)點5、7和3構(gòu)成一個循環(huán)，其中5是入口結(jié)點。 (2) (5) (6) 24對下面的程序片段作出其程序流圖并計算: （1） （2） （3） （4） 各基本塊的到達_定值集INB； 各基本塊中各變量引用點的ud鏈； 各基本塊出口的活躍變量集 V_OUTB； 各基本塊中變量定值點的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）所示。 4 7 3 圖9. 5程序流圖 (1)計算各基本塊的到達-定值集INB。公

52、式為： INB = U OUTP PP B OUTB = GENB U ( INB - KILLB) GENB和KILLB由程序流圖直接求出，顯示在表9.6(1)中。 表 9.6(1) 基本塊 GENB 位向量 KILLB 位向量 B d 1, d 2 11000000 d 3, d 4, d6 ( 0110100 B d 3, d 4 00110000 d 1, d 2, d6 1 1000100 B d 6 00000100 d 1, d 4 10010000 B 00000000 00000000 求各基本塊到達-定值的初值及各遍的執(zhí)行結(jié)果顯示在表9.6(2)中。 表 9.6(2) 基本

53、塊 初值 第一遍后 第二遍后 第三遍后 NB OUTB NB OUTB INB OUTB INB OUTB B 00000000 11000000 00000000 11000000 00000000 11000000 00000000 11000000 00000000 00110000 11000100 00110000 11100100 00110000 11100100 00110000 B 00000000 00000100 0011000000100100 00110000 00100100 00110000 00100100 00000000 00000000 001100000

54、0110000 00110000 00110000 00110000 00110000 (2)求各基本塊中各變量引用點的ud鏈： (簡稱 假設(shè)在程序中某點 U引用了變量a,則把能到達U的a的所有定值點，稱為 a在引用點u的引用-定值鏈 ud鏈)?？梢岳玫竭_-定值信息來計算各個變量在任何引用點的ud鏈。 由圖9.6(1)的程序流圖可知，I的引用點是d3、d5和d6, J的引用點是d3和d8。 引用點 B2中I和J的引用點d3前面沒有對I和J的定值點，其ud鏈在INB2= d 1, d 2, d 3, d 6 中，所以I在 d3的ud鏈?zhǔn)?d 1, d 6 ； J在引用點d3的ud鏈?zhǔn)?d 2, d 3 。 在B2中I的引用點d5前面有I的定值點d4,且在d4定值后到達d5,所以I在引用點d5的ud鏈?zhǔn)?d 4 。 B3中I的引用點d6前面沒有I的定值點，其ud鏈?zhǔn)荌NB 3中I的所有定值點，所以是d 4 。 B4中 J的引用點d8前面