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

1、編譯原理平時(shí)作業(yè)1對(duì)于下列語(yǔ)言分別寫(xiě)出它們的正規(guī)表達(dá)式。(1)英文字母組成的所有符號(hào)用，要求符號(hào)用中順序包含五個(gè)元音。 答：令Letter表示除這五個(gè)元音外的其它字母。(letter) A(letter) E(letter) I(letter) O(letter) U(letter)(2)英文字母組成的所有符號(hào)用，要求符號(hào)用中的字母依照詞典順序排列。 答：A*B*.Z*(3) 2 =0,1上的含偶數(shù)個(gè)1的所有用。答：(0|10*1)*(4) 2 =0,1上的含奇數(shù)個(gè)1的所有申。答：(0|10*1)*1(5)具有偶數(shù)個(gè)0和奇數(shù)個(gè)1的有0和1組成的符號(hào)用的全體。答：設(shè)S是符合要求的串，|S|=2k

2、+1 (k分0。則 Sf s 1。|&1, |S1|=2k (k>0) , |S2|=2k (k且S1是0,1上的串，含有奇數(shù)個(gè) 0和奇數(shù)個(gè)1。0和偶數(shù)個(gè)1。那么自動(dòng)機(jī)Mi如下:S2是0,1上的串，含有偶數(shù)個(gè) 考慮有一個(gè)自動(dòng)機(jī) Mi接受Si,011000|11ai|io00|11和L(M 1)等價(jià)的正規(guī)表達(dá)式，即* *Si為:*(00|11)|(01|10)(00|11) (01|10) (01|10)(00|11)類(lèi)似的考慮有一個(gè)自動(dòng)機(jī)M2接受S2,那么自動(dòng)機(jī) M2如下:和L(M 2)等價(jià)的正規(guī)表達(dá)式，即 (00|11)|(01|10)(00|11)*(01|10) 因此，S為

3、：(00|11)|(01|10)(00|11)*(01|10)(00|11)|(01|10)(00|11)*(01|10)S2為:(01|10)(00|11)*0|1(6)不包含子用011的由0和1組成的符號(hào)用的全體。答: 答:1 |1 0(0|10) (1| £)由0和1組成的符號(hào)用，把它看成二進(jìn)制數(shù)，能被3整除的符號(hào)用的全體。 假設(shè)w的自動(dòng)機(jī)如下：對(duì)應(yīng)的正規(guī)表達(dá)式：(1(01*0)1|0)*2給出接受下列在字母表0,1上的語(yǔ)言的DFA 所有以00結(jié)束的符號(hào)用的集合。DFA M=(0 , 1, qo, qi, q2 , q。, q 2 , 8)其中8定義如下：狀態(tài)轉(zhuǎn)換圖(2)所有具

4、有3個(gè)0的符號(hào)用的集合 正則表達(dá)式:1*01*01*01*8 (q0,0)=q18 (q0,1)=q08 (q1，0)=q28 (q1，1)=q08 (q2,0)=q26 (q2,1)=q0DFA M=(0 , 1, q0, q1, q2, q3, q0，q 3, 8)其中8定義如下:S (q0,0)=q18 (q1，0)=q28 (q2,0)=q36 (q3,1)=q38 (q0, 1) =q08 (q1，1) 二q18 (q2, 1) =q2狀態(tài)轉(zhuǎn)換圖3下面是用正規(guī)式表示的變量聲明：(int | float ) id (, id )* ;請(qǐng)改用上下文無(wú)關(guān)文法表示，也就是寫(xiě)一個(gè)上下文無(wú)關(guān)文法

5、，它和該正規(guī)式等價(jià)。 答：D - T L ;T. int | floatL .，L, id | id4試分析下面給出的if-then-else 語(yǔ)句的文法，它的提出原本是為了矯正dangling-else (懸而未決的-else)文法的二義性：stmt f if expr then stmt|matched-stmtmatched- stmt f if expr then matched -stmt else stmt|other試說(shuō)明此文法仍然是二義性的。答： 考慮句子 if e then if e then other else if e then other else other它具有如

6、下所示的兩種分析樹(shù) 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 stmtmatched-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 oth

7、er if matched-stmt other則上面給出的if-then-else文法仍是二義性的。5證明下面文法是SLR(1)文法，并構(gòu)造其SLR分析表。E- E+T|TTf TF|FF-F*|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)項(xiàng)目集規(guī)范族和goto函數(shù)(識(shí)別活前綴的DFA)如下：Io= E'一 E, E 一 E+T, E 一 T, T 一 TF, T 一FF- -a, -F F*- bI1 = E'-

8、E , E 一E +TI2 = E 一 T , T 一 T F, F 一 F*, F一 a,F一 bI3 = T一 F , F 一 F斗4 = F - a I5 = F 一b I6 = E - E+- T,TTFTf FF F*,F aFb I7= T - TF -，F(xiàn)-F- * I8 =F 一 F* I9 = E 一 E+T , T 一 T F, F 一 F*, F 一 a, F 一 b求 FOLLOW!: FOLLOW(E尸什，$ FOLLOW(T)= + , $ , a, bFOLLOW(F尸+ , $ , a, b, *構(gòu)造的SLR分析表如下：狀態(tài)actiongoto+.ab*ETF0

9、S4S517311S6acc2r?1S4S5r廠(chǎng)73kAS8r4r4r44r6r6r6r6r65r7r7r7r7r76S4S5937出SBr3r3r38r55r5r5r59r1S495n7顯然，此分析表無(wú)多重定義入口，所以此文法是SLR文法。6為下面的文法構(gòu)造LALR(1)分析表SfEE- E+T|TT- (E)|a答：其拓廣文法G':(0) S' 一 S (1) S 一 E(2) E E+T(3) E一 T(4) T- (E) (5) T- a構(gòu)造其LR(1)項(xiàng)目集規(guī)范族和goto函數(shù)(識(shí)別活前綴的DFA)如下：|0= S S, $, SE, $, EE+T, $/+1 E

10、(守 $/+T, $/+,- a, $/+Ii = S，- S , $ I2 = S - E -，$, E - E +T, $/+3= E -T ,$/+I4 = T -( E), $/+, E- E+T, )/+, E T - - TE)/+/+, T - a, )/+15 = T - a , $/+ 16 = E - E+ T, $/+, T -(E), $/+, T - a, $/+17 = T -(E ), $/+, E- E +T, )/+8 = E - T)/+19 = T -( E), )/+, E - E+T,)/+, E - T,)/+, T -(E), )/+, T - a

11、,)/+110 = T- a -，)/+ I11 = E- E+T -，$/+Ii2 = T -(E) , $/+Ii3 = E-E+T, )/+, T-(E), )/+, T T14 aT+L (E ),)/+, E -E +T, )/+115 = E - E+Tj )/+116 = T -(E) , )/+合并同心的LR 項(xiàng)目集，得到LALR的項(xiàng)目集和轉(zhuǎn)移函數(shù)如下：|0 = S S, $, SE, $, EE+T, $/+, ET, $/+, T - (E), $/+, TIi = S '- S , $ 2 = S -E -，$, E -E +T, $/+8= E -T , $/+

12、/)I4,9 = T -( E), $/+/), E- E+T, )/+, E T (3)阿,丁一 a, )/+15,10 = T -a , $/+/)I6,13 = E-E+ T, $/+/), T -(E), $/+/), T - a, $/+/)I7,14 = T -(E ), $/+/), E- E - +TI )/+5= E - E+，$/+/)I 12,16 = T -(E). , $/+/)LALR分析表如下:STATEactiongotoA+()$sET0S5,10P S4,9123#1acc2S6,13r138r3r3r34,9S5.10S4.97J43.85,10r5r5r

13、56,13S5J0%. 9111157,14S6.13S12.1611,15r2r2r212316r4r4r47 (1)通過(guò)構(gòu)造識(shí)別活前綴的DFA和構(gòu)造分析表，來(lái)證明文法 E t E + id | id 是SLR(1)文法。答：先給出接受該文法活前綴的DFA如下：再構(gòu)造SLR分析表如下:狀態(tài)動(dòng)作轉(zhuǎn)移id+$E0s211s3acc2r2r23s44riri表中沒(méi)有多重定義的條目，因此該文法是SLR(1)的。(2)下面左右兩個(gè)文法都和(1)的文法等價(jià)E > E + M id | idE > M E + id | idM M ；請(qǐng)指出其中有幾個(gè)文法不是LR(1)文法，并給出它們不是LR(

14、1)文法的理由。答：只有文法E > M E + id | idM r ；：不是LR(1)文法。因?yàn)閷?duì)于句子id+id+id來(lái)說(shuō)，分析器在面臨第一個(gè)id時(shí)需要做的空歸約次數(shù)和句子中+id的個(gè)數(shù)一樣多，而此時(shí)句子中+id的個(gè)數(shù)是未知的。8 根據(jù)自上而下的語(yǔ)法分析方法，構(gòu)造下面文法的 LL (1)分析表。D > TLT int | realL ) id RR > , id R | ；答：先計(jì)算 FIRST和FOLLOWFIRST(D) = FIRST(T) = int,realFIRST(L) = idFIRST(R) = , eFOLLOW(D) = FOLLOW(L) = $F

15、OLLOW(T) = idFOLLOW(R) = $LL(1)分析表如下：intrealid,$DD -> TLD -> TLTT -> intT -> realLL -> idRRR -> ,idRR -> &9下面的文法產(chǎn)生的表達(dá)式是對(duì)整型和實(shí)型常數(shù)應(yīng)用算符 +形成的。當(dāng)兩個(gè)整數(shù) 相加時(shí)，結(jié)果仍為整數(shù)，否則就是實(shí)數(shù)。E- E+T|TTf num.num|num(a)給出一個(gè)語(yǔ)法制導(dǎo)定義以確定每個(gè)子表達(dá)式的類(lèi)型。(b)擴(kuò)充(a)中的語(yǔ)法制導(dǎo)定義把表達(dá)式翻譯成前綴形式，并且決定類(lèi)型。使用一元算符inttoreal把整型值轉(zhuǎn)換成相等的實(shí)型值，以使

16、得前綴形式中的 +的 兩個(gè)操作對(duì)象是同類(lèi)型的。(a)：產(chǎn)生式語(yǔ)義規(guī)則E E1+TIF (E1.type=integer) and (T.type=integer) THENE.type:=integerELSEE.type:=realE TE.type:=T.typeT num.numT.type:=realT numT.type:=integer(b)：產(chǎn)生式語(yǔ)義規(guī)則E E1+TIF (E1.type=integer) and (T.type=integer) THENBEGINE.type:=integerPrint( +',E1.val,T.val)ENDELSE BEGINE.

17、type:=realIF E1.type=integer THENBeginE1.type:=realE1.val:=inttoreal(E1.val)EndIF T.type:=integer THENBeginT.type:=realT.val:=inttoreal(T.val)EndPrint( +',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假設(shè)說(shuō)明是由下列文法產(chǎn)生的:A

18、 id LL-,id L|:TTf integer |real(a)建立一個(gè)翻譯模式，把每一個(gè)標(biāo)識(shí)符的類(lèi)型加入到符號(hào)表中(b)從(a)中的翻譯模式構(gòu)造一個(gè)預(yù)翻譯程序。答：(a)：產(chǎn)生式翻譯模式D idLD.Type:=L.Typeaddtype(id.entry, D.type)L ,idL1L.Type:=L1.Typeaddtype(id.entry, L.type)L :TL.type:=T.typeT integerT.type:=integerT realT.type:=real(b)：Procedure D;beginIf lookahead=id thenBeginMatch(i

19、d);D.type=L;addtype(id.entry,D.type) endelseerrorendFunction L: DataType;BeginIf lookahead= ',' thenBeginMatch( ,");If lookahead=id thenbeginmatch(id);L.Type=L;addtype(id.entry,L.type); return(L.type)endElseerrorEndElse if lookahead= 'thenBeginMatch( :")；L.Type=T;return(L.Type)

20、 endelseerrorEndFunction T: DataType;BeginIf lookahead=integer thenBeginMatch(integer);return(integer) endelse If lookahead=real thenBeginMatch(real);return(real) endelseerrorend11為下面的算術(shù)表達(dá)式文法寫(xiě)一個(gè)語(yǔ)法制導(dǎo)的翻譯方案，它將每個(gè)子表達(dá)式E的符號(hào)（即值大于零還是小于零）記錄在屬性 E.sign中（屬性值分別用POS或 NEG表示）。你可以假定所有的整數(shù)都不為零，這樣就不用擔(dān)心零的符號(hào)。Et E *E | +E

21、| -E | unsigned_integerErEi *E2if Ei.sign= E2.sign then E.sign := POS elseE.sign := NEG Er +E1 E.sign := E1.sign E-Ei if E1.sign= POS thenE.sign := NEG else E.sign := POSEt unsigned_integer E.sign := POS12為下面文法寫(xiě)一個(gè)語(yǔ)法制導(dǎo)的定義，用 S的綜合屬性val給出下面文法中S 產(chǎn)生的二進(jìn)制數(shù)的值。例如，輸入101.101時(shí)，S. val := 5.625。（不得修改文法。）S > L .

22、 R | LL > L B | BR > B R | BB > 0 | 1S. val := L. val + R. valS ，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試問(wèn)下面的程序?qū)⒂性鯓拥妮敵?？分別假定：(a)傳值調(diào)用(call-by-value)；(b)弓I用調(diào)用(

23、call-by-reference);(c)復(fù)制恢復(fù)(copy-restore ;(d)傳名調(diào)用(call-by-name)。program main(input,output)；procedurep (x,y,z)；beginy： =y+1;z： =z + x；end;begina： =2；b: = 3;p(a+ b,a,a)；print aend.答：1) .傳地址：所謂傳地址是指把實(shí)在參數(shù)的地址傳遞給相應(yīng)的形式參數(shù)。在過(guò)程段中每個(gè)形式參數(shù)都有一對(duì)應(yīng)的單元，稱(chēng)為形式單元。形式單元將用來(lái)存放相應(yīng)的實(shí)在參 數(shù)的地址。當(dāng)調(diào)用一個(gè)過(guò)程時(shí)，調(diào)用段必須領(lǐng)先把實(shí)在參數(shù)的地址傳遞到一個(gè)為被調(diào)用段可 以拿得

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

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

26、第二次被激活時(shí)的運(yùn)行棧，控制鏈和訪(fǎng)問(wèn)鏈 說(shuō)明在c中如何訪(fǎng)問(wèn)變量X。program env ；procedure a ；var x:integer ；procedure b ;procedure c ;begin x:=2 ； b end; procedure cbegin c end; procedure bbegin b end; procedure abegin a end. main答：envS control link access - link 二a二八control linkjaccess link/control link access - linknzzzzj control

27、link aaccess link/control link 匚. access link.V c ) control link/二 access .Jink.二二二二1J說(shuō)明：c中沿著存取鏈向前走兩步，到過(guò)程 a的活動(dòng)記錄中就可以訪(fǎng)問(wèn)到變量 X。15下面給出一個(gè) C語(yǔ)言程序及其在 SPARC/SUN工作站上經(jīng)某編譯器編譯后 的運(yùn)行結(jié)果。從運(yùn)行結(jié)果看，函數(shù) func中4個(gè)局部變量i1, j1, f1, el的地址問(wèn) 隔和它們類(lèi)型的大小是一致的，而4個(gè)形式參數(shù)i, j, f, e的地址間隔和它們的類(lèi) 型的大小不一致，試分析不一致的原因。注意，輸出的數(shù)據(jù)是八進(jìn)制的。func (i, j, f, e

28、)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, doubl

29、e = %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);運(yùn)行結(jié)果是：Address of i, j, f, e = 35777772536, 35777772542, 35777772544, 35777772554 Address of i1, j1, f1, el = 35777772426, 35777772424, 35777772420, 35

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

31、式參數(shù)所聲明的類(lèi)型，決定是否要將實(shí)在參數(shù)向低級(jí)別類(lèi)型轉(zhuǎn)換。在本例中，10ng類(lèi)型數(shù)據(jù)占4個(gè)字節(jié)，而short類(lèi)型數(shù)據(jù)只占2個(gè)字節(jié)。因此被調(diào)用函數(shù)把實(shí)在參數(shù)的低位字節(jié)的內(nèi)容當(dāng)成是自己所需的數(shù)據(jù)，見(jiàn)圖5.2低地址放高位longshorttWj地址 放低位圖5.2長(zhǎng)整型和短整型注意，對(duì)于SUN工作站來(lái)說(shuō)，低地址存放整型數(shù)據(jù)的高位。對(duì)于實(shí)型來(lái)說(shuō)。double類(lèi)型是8個(gè)字節(jié)，而float類(lèi)型4個(gè)字節(jié)。被調(diào)用函數(shù)把實(shí)在參 數(shù)的前4個(gè)字節(jié)作為自己所需的數(shù)據(jù)，因?yàn)?double后面4個(gè)字節(jié)的內(nèi)容都是為了增加精度 用的，見(jiàn)圖5.3。doublefloat圖5.3雙精度型和浮點(diǎn)型這樣在main函數(shù)中依次將參數(shù)提升

32、后反序進(jìn)棧，大小分別為8, 8, 4, 4。在func函數(shù)中,按形式參數(shù)的類(lèi)型，把這些存儲(chǔ)單元的一部分看成是形式參數(shù)的存儲(chǔ)單元，見(jiàn)圖5.4。從這個(gè)圖不難理解為什么形式參數(shù)的地址間隔和它們的類(lèi)型大小不一致了。注意，現(xiàn)在的編譯器將需要進(jìn)行類(lèi)型轉(zhuǎn)換的形式參數(shù)（類(lèi)型是char、short、float等）另行分配在局部數(shù)據(jù)區(qū)，當(dāng)控制進(jìn)入被調(diào)用過(guò)程時(shí)， 首先將調(diào)用過(guò)程壓棧的需要進(jìn)行類(lèi)型轉(zhuǎn)換的實(shí)在參數(shù)取出，把它們存入所分配的局部數(shù)據(jù)區(qū)存儲(chǔ)單元，并同時(shí)完成必要的數(shù)據(jù)類(lèi)型的轉(zhuǎn)換。在這種情況下，不會(huì)出現(xiàn)本題所碰到的現(xiàn)象。另外，在SPARC工作站上，整型數(shù)據(jù)的高位存放在低地址，而低位存放在高地址。如棧的增 長(zhǎng)方向在

33、main函數(shù)中參數(shù)壓棧時(shí)的觀(guān)點(diǎn)在func四數(shù)中存取形 式參數(shù)時(shí)的觀(guān)點(diǎn)i, 4個(gè)字節(jié)2 2個(gè)字節(jié)，起始地址 35777772536j, 4個(gè)字節(jié)”>2個(gè)字節(jié)，起始地址 35777772542 a 4個(gè)字節(jié)，起始地址 35777772544_ 1f, 8個(gè)字節(jié)*e, 8個(gè)字節(jié) 4個(gè)字節(jié)，起始地址 35777772554圖5.4參數(shù)在棧中的情況果是X86機(jī)器，數(shù)據(jù)的高低位不是按這樣的次序存放，那也不會(huì)出現(xiàn)本題所碰到的現(xiàn)象。下面是某個(gè)編譯器的類(lèi)型提升函數(shù)，供讀者理解用（備注： int和long的大小一樣）。Type promote(Type ty)switch(ty->op)case EN

34、UM: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語(yǔ)言程序的可執(zhí)行語(yǔ)句翻譯為 （a）一棵語(yǔ)法樹(shù)，(b)后綴式，(c)三地址代碼。main() int i

35、;int a10;while (i<=10)ai=0；(b)后綴式為：i 10<= a i 0 = while從理論上可以說(shuō) while(i<=10) ai=0;的后綴式如上面表示。但若這樣表示，在執(zhí)行 while操 作時(shí)，賦值語(yǔ)句已經(jīng)執(zhí)行，這顯然與語(yǔ)義不符，因此改為：i 10 <=<下一個(gè)語(yǔ)句開(kāi)始地址 >BM a i 0 =< 本語(yǔ)句地址 > BRL其中BM操作為當(dāng)表達(dá)式為假時(shí)轉(zhuǎn)向<下一個(gè)語(yǔ)句開(kāi)始地址>,BRL是一個(gè)一目運(yùn)算，無(wú)條件轉(zhuǎn)向V本語(yǔ)句始址>。(c)三地址代碼序列為：100 if i <= 10 got 1021

36、01 goto 106102 t1:=4*i103 t2:=a104 t2t1:=0105 goto 10010617 Pascal 語(yǔ)言中，語(yǔ)句：for v : = initial to final do stmt與下列代碼序列有相同含義begint1:=initial;t2:=final;if t1<=t2 then beginv:=t1;stmtwhile v<>t2 do begin:=succ (v);stmtend end end(a) 試考慮下述Pascal 程序program forloop(input, output);var i,initial,final

37、: integer;beginread(initial, final);for i:= initial to final do write(i) end對(duì)于 initial=MAXINT-5 和 final= MAXINT ，問(wèn)此程序?qū)⒆鲂┦裁?？其中MAXINT為目標(biāo)機(jī)器允許的最大整數(shù)。(b) 試構(gòu)造一個(gè)翻譯pascal 的 for 語(yǔ)句為三地址代碼的語(yǔ)法制導(dǎo)定義。答：( a) 程序?qū)@示如下六個(gè)整數(shù)：MAXINT -5 MAXINT-4 MAXINT-3 MAXINT-2 MAXINT-1 MAXINT(b)為簡(jiǎn)單起見(jiàn)，for語(yǔ)句的三地址代碼如下：t1 := initial t2 := fi

38、nalif 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語(yǔ)法制導(dǎo)定義如下：產(chǎn)生式 動(dòng)作 Sf for E do S1 S.begin := newlabel S.first := newtemp S.la st := newtemp S.curr:= newtemp S.code:=gen(S.first “ := ”E.init) |gen(S.last “ := ” E.final) |gen( “ Sif.fi”rs

39、t “ >” S.last “ goto S” .next) |gen(S.curr “ := ”S.first) |gen(S.begin “ : ”) |gen( “” iSf .curr “ >” S.Last “ goto ”S.next) |S1.code |gen(S.curr := succ(S.curr) |gen( " goto " S.begin) E - v:=initial to final E.init := initial.place E.final := final.place18 對(duì)于下面C 語(yǔ)言文件s.cf1(int x) lo

40、ng x;x = 1; f2(int x) long x;x = 1;某編譯器編譯時(shí)報(bào)錯(cuò)如下：s.c: In function f1 :s.c:3: warning: declaration of X' shadows a parameter請(qǐng)回答，對(duì)函數(shù)f2為什么沒(méi)有類(lèi)似的警告錯(cuò)誤。答：對(duì)于函數(shù)f1 ,局部變量x聲明的作用域是整個(gè)函數(shù)體，導(dǎo)致在函數(shù)體中不可能訪(fǎng)問(wèn)形式參數(shù)X。由于這是一個(gè)合法的 C語(yǔ)言函數(shù)，因此編譯器給出警告錯(cuò)誤。對(duì)于函數(shù)f2 ,由于局部變量 x的作用域只是函數(shù)體的一部分，不會(huì)出現(xiàn)上述問(wèn)題，因而編 譯器不報(bào)錯(cuò)。19考慮一個(gè)簡(jiǎn)單語(yǔ)言，其中所有的變量都是整型（不需要顯式聲明

41、），并且僅包含賦值語(yǔ)句、讀語(yǔ)句和寫(xiě)語(yǔ)句。下面的產(chǎn)生式定義了該語(yǔ)言的語(yǔ)法（其中 lit表示整型常量；OP的產(chǎn)生式?jīng)]有給出，因?yàn)樗拖旅嬗懻摰膯?wèn)題無(wú)關(guān)）。Program > StmtListStmtList Stmt StmtList | StmtStmt id := Exp; | read Qd ）; | write （ Exp ）;Exp > id | lit | Exp OP Exp我們把不影響write語(yǔ)句輸出值的賦值（包括通過(guò)read語(yǔ)句來(lái)賦值）稱(chēng)為無(wú) 用賦值，寫(xiě)一個(gè)語(yǔ)法指導(dǎo)定義，它確定一個(gè)程序中出現(xiàn)過(guò)賦予無(wú)用值的變量集合（不需要知道無(wú)用賦值的位置）和沒(méi)有置初值的變量集合（不

42、影響write語(yǔ)句輸出值的未置初值變量不在考慮之中）。非終結(jié)符StmtList和Stmt用下面3個(gè)屬性（你根據(jù)需要來(lái)定義其它文法符號(hào) 的屬性）：（1） uses_in：在本語(yǔ)句表或語(yǔ)句入口點(diǎn)的引用變量集合，它們的值影響在 該程序點(diǎn)后的輸出。（2） uses_out在本語(yǔ)句表或語(yǔ)句出口點(diǎn)的引用變量集合，它們的值影響在 該程序點(diǎn)后的輸出。（3） useless本語(yǔ)句表或語(yǔ)句中出現(xiàn)的無(wú)用賦值變量集合。答：Exp的屬性u(píng)ses表示它引用的變量集合。 Program的useless和no_initial分別表示程序 的無(wú)用賦值變量集合和未置初值變量集合。Program t StmtList StmtLi

43、st.uses_out:=0;Program.useless := StmtList.useless;Program.no_initial := StmtList.uses_in;StmtList t Stmt StmtList 1 StmtListi.uses_out := StmtList.uses_out;Stmt.uses_out := StmtList i.uses_in;StmtList.uses_in := Stmt.uses_inStmtList.useless := StmtList i.useless 一 Stmt.useless;StmtList StmtStmt.use

44、s_out := StmlList.uses_out;StmlList.uses_in := Stmt.uses_in;StmtList.useless := Stmt.uselessStmtrid := Exp;Stmt.useless :=if id.lexeme S Stmt.uses_out then 0 elseid.lexeme;Stmt.uses_in := if id.lexeme Stmt.uses_outthen (Stmt.uses_out id.lexeme) oExp.uses else Stmt.uses_outStmtread (id );Stmt.useless

45、:=if id.lexeme S Stmt.uses_out then 0 elseid.lexeme;Stmt.uses_in := Stmt.uses_out - id.lexemeStmt write ( Exp );Stmt.useless := Stmt.uses_in := Stmt.uses_out 2 Exp.usesExp r idExp.uses:= id.lexemeExp . litExp.uses:=*'Exp . Expi OP Exp2 Exp.uses:= Expi.usesExp2.uses20為下列C程序生成目標(biāo)代碼 main()int i;int

46、a10;while(i<=10)ai=0；21試構(gòu)造下面的程序的流圖，并找出其中所有回邊及循環(huán) read Px := 1c := P * P if c < 100 goto L1B := P * x := x + 1B := B + x write x haltL1: B:= 10 x := x + 2 B := B + x write B if B < 100 goto L2 haltL2: x := x + 1 goto L1 答：程序的流圖如下22試求出如下四元式程序中的循環(huán)并進(jìn)行循環(huán)優(yōu)化.I := 1read J, KL: A := K * IB := J * IC

47、:= A * Bwrite CI := I + 1if I < 100 goto Lhalt答：把本題的三地址代碼劃分成基本塊并畫(huà)出其程序流圖顯示在圖9.4(1)中，其中有三個(gè)基本塊B1, B2, B3,有一條回邊 B2 -> B2 ,相應(yīng)的循環(huán)是B2。read J, K圖9. 4(1)程序流圖(2)強(qiáng)度削弱：B2中A和B(1)代碼外提：由于循環(huán)中沒(méi)有不變運(yùn)算，故不做此項(xiàng)優(yōu)化 都是I的歸納變量。優(yōu)化結(jié)果顯示在圖9.4(2)中。圖±4(二殳強(qiáng)度由弱后的流圖I后的流圖顯示在圖 9.4(3)中(3)刪除歸納變量：變換循環(huán)控制條件，刪除歸納變量圖9. 4(外刪除歸納巧足的程序流回

48、23考慮下面的三地址語(yǔ)句序列：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)在該代碼中用水平的橫線(xiàn)將代碼分成基本塊，并給每個(gè)基本塊一個(gè)序 號(hào)。(2)畫(huà)出該代碼的控制流圖，每個(gè)基本塊就用(1)的序號(hào)表示。(3)若有循環(huán)的話(huà)，列出構(gòu)成每個(gè)循環(huán)的結(jié)點(diǎn)。答：(1)b := 1b := 2if w <= x goto L2(1)e := bgoto

49、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 L1L5: h := 9(8)(2)(3)結(jié)點(diǎn)5、7和3構(gòu)成一個(gè)循環(huán)，其中 5是入口結(jié)點(diǎn)。24對(duì)下面的程序片段作出其程序流圖并計(jì)算：(1)各基本塊的到達(dá)_定值集INB;(2)各基本塊中各變量引用點(diǎn)的ud鏈；(3)各基本塊出口的活躍變量集 V_OUTB;(4)各基本塊中變量定值點(diǎn)的du標(biāo)。I := 1J := 0II : J := J + Iread Iif I < 100 goto L

50、2write J haltL2 : I := I * I答：本題程序的程序流圖如圖9.6(1)所示。II 1J := 1圖g.6(D程序法圖(1)計(jì)算各基本塊的到達(dá)-定值集INB。公式為:INB = U OUTPPC PBOUTB = 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 ()0110100R d 3, d 4 00110000 d 1, d 2, d6 -1000100B d 6 00000100 d 1,

51、 d 410010000 00000000 00000000求各基本塊到達(dá)-定值的初值及各遍的執(zhí)行結(jié)果顯示在表9.6(2)中。表 9.6(2)“本塊初值A(chǔ)遍后第二遍后第三遍后NBOUTBINBOUTBINBOUTBINBOUTBB0000000011000000000000001100000000000000110000000000000011000000B20000000000110000110001000011000011100100001100001110010000110000Bb0000000000000100001100000010010000110000001001000011000000100100B00000000000000000011000000110