網(wǎng)絡(luò)學(xué)院編譯原理平時(shí)作業(yè)

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

2、STS0|S21, |S1|=2k (k>0 ), |S2|=2k(k 為)。且S是0,1上的串，含有奇數(shù)個(gè) 0和奇數(shù)個(gè)1。S是0,1上的串，含有偶數(shù)個(gè)0和偶數(shù)個(gè)1。考慮有一個(gè)自動(dòng)機(jī)M接受S1,那么自動(dòng)機(jī) M如下：01|10aqu00|11精選資料，歡迎下載和L(M"等價(jià)的正規(guī)表達(dá)式，即 S1為：(0 11)|(01|10)(00|11) *(01|10) *(01|10)(00|11) *類(lèi)似的考慮有一個(gè)自動(dòng)機(jī) M接受S2,那么自動(dòng)機(jī) M如下:和L(M2)等價(jià)的正規(guī)表達(dá)式，即 S2為：(00|11)|(01|10)(00|11)*(01|10)*因此，S為：(00|11)|(

3、01|10)(00|11)*(01|10)*(01|10)(00|11)*0|(00|11)|(01|10)(00|11)*(01|10)*1(6)不包含子串011的由0和1組成的符號(hào)串的全體。* * *答：1 |1 0(叩0)(1| 9 由0和1組成的符號(hào)串，把它看成二進(jìn)制數(shù)，能被3整除的符號(hào)串的全體 答：假設(shè)w的自動(dòng)機(jī)如下：13 (q0, 0) =q13 (q0, 1) =q03 (q1, 0) =q23 (q1, 1) =q03 (q2, 0) =q23 (q2, 1) =q0狀議轉(zhuǎn)換圖101 01 01對(duì)應(yīng)的正規(guī)表達(dá)式：(1(01 0)1|0)2給出接受下列在字母表0,1上的語(yǔ)言的DF

4、A(1) 所有以00結(jié)束的符號(hào)串的集合。(2) 所有具有3個(gè)0的符號(hào)串的集合。答：(1) DFA M=(0 , 1, q。, q1, q?, q。，q 2, ®其中3定義如下：(2)正則表達(dá)式：1DFAM=(0, 1 , q0, q1, q2, qs , q°, q 3,其中3定義如下：3 (q0,0)=q13(q0,1)=q03 (q1,0)=q23g,1)=qi3 (q2,0)=qs3(q2,1)=q23 (qs,1)=q33下面是用正規(guī)式表示的變量聲明:( int | float ) id (, id )* ; 請(qǐng)改用上下文無(wú)關(guān)文法表示，也就是寫(xiě)一個(gè)上下文無(wú)關(guān)文法，它

5、和該正規(guī)式等價(jià)。 答：D TL；Tint | floatLL, 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 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

7、 matched-stmt other則上面給出的 if-then-else 文法仍是二義性的。5證明下面文法是SLR文法，并構(gòu)造其SLR分析表EfE+T|TTfTF|FFfF*|a|b答： 該文法的拓廣文法 G' 為(o) E'f E(1) EfE+T(2) Ef T(3) TfTF(4) Tf F(5) FfF*(6) Ff a(7) Ffb其LR(0)項(xiàng)目集規(guī)范族和goto函數(shù)(識(shí)別活前綴的DFA)如下：10 = E' f-E,E f-E+T, E f-T,T fTF, T fF,F fF*,Ffa, F fb11 = E' fE , EfE +TI2 =

8、 E fT , TfT F, F f F*, F f a, F f bI3 = TfF , F fF * I4 = F fa I5 = F fb I6 = EfE+ T, Tf TF, Tf F,F f F*,F f a, Ff b I7 =T fTF , F fF * I8 = F fF* I9 = E fE+T, T fT F, F f F*, F f a, F f b3求 FOLLOW集：FOLLOW(E)= , $ FOLLOW(T)=+ , $ , a, bFOLLOW(F)=+ ,$ , a, b, *構(gòu)造的SLR分析表如下：狀態(tài)actiongoto+ab$ETF0S4S51231

9、S6acc2衛(wèi)S4 1SSP r273SB4r444rGrGrGrGr6517r7r7r?了6S4S5937r3SBr3r3r33r5r5r5r5P r59r1別S517顯然，此分析表無(wú)多重定義入口，所以此文法是SLR文法。6為下面的文法構(gòu)造LALR分析表E E+T|TT (E)|a(1) S EE TT a答：其拓廣文法G':(0) S' S E E+T T (E)0 = S'S-, $, S -»E, $, E E+T, $/+, E -T, $/+, T (E), $/+, T1 = S'-s；$ I2 = S E ； $, EE +T, $/+

10、 I3 = ET ； $/+4 = T(E), $/+, EE+T, )/+, E-T, )/+,T (E), )/+, Ta, )/+5 = Ta , $/+ I6 - E E+ T, $/+, T(E), $/+, T a, $/+7 = T(E ), $/+, EE +T, )/+ I8 = ET , )/+9 = T(E), )/+, EE+T, )/+, E-T, )/+, T(E), )/+, Ta, )/+構(gòu)造其LR(1)項(xiàng)目集規(guī)范族和goto函數(shù)(識(shí)別活前綴的DFA)如下:a, $/+10 = T-a ;)/+ I11 = E E+T , $/+ I12 :=T -(E) ,

11、$/+13 = E-E+ T, )/+, T-(E), )/+, T- a)/+I14 = T - (E ), )/+, E-E +T, )/+15 = E-E+T , )/+ I16 = T -(E) ；)/+a合并同心的LR(1)項(xiàng)目集，得到LALR的項(xiàng)目集和轉(zhuǎn)移函數(shù)如下：I 0 = S 'V,$, SE,$, E»E+T, $/+, E»T,$/+, T (E), $/+, T»a,$/+Ii = S' -S ; $ I 2 = S E ； $, E E +T, $/+ I 3,8 = E T , $/+/)14.9 = T - ( E),

12、$/+/), E - E+T, )/+, E - T, )/+, T - (E), )/+, T - a, )/+15.10 = T - a ； $/+/) I 6,13 = E - E+ T, $/+/), T - (E), $/+/), T - a, $/+/)17,14 = T-(E ), $/+/), E-E +T, )/+ I11,15 = E-E+T； $/+/)I 12,16 = T - (E), $/+/)LALR分析表如下:STATEactiongotoA4()$8ET035,10S4.9123.61acc2S6.13r133r3r3r343S5.10S407,145,10r

13、5r5r5気MS5.10Sd.311(157.14S6.13S12.1611,15r2r2r212.16r447 (1)通過(guò)構(gòu)造識(shí)別活前綴的DFA和構(gòu)造分析表，來(lái)證明文法 E E + id | id是SLR文法。 答：先給出接受該文法活前綴的DFA如下：再構(gòu)造SLR分析表如下:狀態(tài)動(dòng)作轉(zhuǎn)移id+$E0s211s3acc2r2r23S44r1r 1表中沒(méi)有多重定義的條目，因此該文法是SLR(1)的。(2)下面左右兩個(gè)文法都和(1)的文法等價(jià)E E + M id | idEM E + id | idMM請(qǐng)指出其中有幾個(gè)文法不是LR(1)文法，并給出它們不是LR(1)文法的理由 答:只有文法E M

14、E + id | idM不是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 TLTint | realLid RR , id R |答：先計(jì)算FIRST和FOLLOWFIRST(D) = FIRST(T) = i nt,realFIRST(L) = idFIRST(R) = ,4FOLLOW(D) = FOLLOW(L) = $FOLLOW(T) = idFOLLOW(R) = $LL(1)分析表如下：intrealidJ$

15、DD -> TLD -> TLTT -> intT -> realLL -> id RRR -> ,id RR -> £9下面的文法產(chǎn)生的表達(dá)式是對(duì)整型和實(shí)型常數(shù)應(yīng)用算符+形成的。當(dāng)兩個(gè)整數(shù)相加時(shí)，結(jié)果仍為整數(shù)，否則就是實(shí)數(shù)。E E+T|TT num num num(a) 給出一個(gè)語(yǔ)法制導(dǎo)定義以確定每個(gè)子表達(dá)式的類(lèi)型。in ttoreal(b) 擴(kuò)充(a)中的語(yǔ)法制導(dǎo)定義把表達(dá)式翻譯成前綴形式， 并且決定類(lèi)型。使用一元算符 把整型值轉(zhuǎn)換成相等的實(shí)型值，以使得前綴形式中的 +的兩個(gè)操作對(duì)象是同類(lèi)型的。答：(a):產(chǎn)生式語(yǔ)義規(guī)則E E1+TIF

16、(E1.type=in teger) and (T.type=in teger) THENE.type:=in tegerELSEE.type:=realE TE.type:=T.typeT num.numT.type:=realT numT.type:=in teger(b)：產(chǎn)生式語(yǔ)義規(guī)則E E1+TIF (E1.type=in teger) and (T.type=in teger) THEN BEGINE.type:=in tegerPrint(+',E1.val,T.val)ENDELSE BEGINE.type:=realIF E1.type=i nteger THENBe

17、gi nE1.type:=realE1.val:=i nttoreal(E1.val)EndIF T.type:=i nteger THENBegi nT.type:=realT.val:=in ttoreal(T.val)EndPrint(+',E1.val,T.val)ENDE TE.type:=T.typeE.val:=T.valT num.numT.type:=realT.val:= num.nu mlexvalT numT.type:=in tegerT.val:= nu mlexval10假設(shè)說(shuō)明是由下列文法產(chǎn)生的：X id LL ,id L|:TT integer | r

18、eal(a) 建立一個(gè)翻譯模式，把每一個(gè)標(biāo)識(shí)符的類(lèi)型加入到符號(hào)表中(b) 從(a)中的翻譯模式構(gòu)造一個(gè)預(yù)翻譯程序 答：產(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 in tegerT.type:=i ntegerT realT.type:=real(b):Procedure D;beginIf lookahead=id the nBegi nMatch(id);D.type=L;addtype(id

19、.e ntry,D.type) endelseerrorendFunction L: DataType;BeginIf lookahead=', 'thenBeginMatch( ');If lookahead=id the nbeginmatch(id);L.Type=L; addtype(id.e ntry,L.type); return(L.type)endElseerrorEndElse if lookahead=' thenBeginMatch( )；L.Type=T;return(L.Type)endelseerrorEndFunction T: D

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

21、eger答：EE1 *E2if E1.sign= E2.sign then E.sign := POS else E.sign := NEG E+E1 E. sign := E1. sign EE1 if E1.sign= POS then E.sign := NEG else E.sign := POSE 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。（不得修改文法。）SL . R | LLL B | BRB R | BB0 |

22、 1答：SL . RS.val:= L.val + R.valSLS.val:= L.valLL1 BL.val :=L 1. val2 + B.valLBL.val:= B.valRB R1R.val:= (R1. val + B.val )/2RBR.val:= B.val /2B0B.val:= 0B. val := 113 試問(wèn)下面的程序?qū)⒂性鯓拥妮敵?？分別假定：(a) 傳值調(diào)用(call-by-value )；(b) 弓丨用調(diào)用(call-by-referenee)；(c) 復(fù)制恢復(fù)(copy-restore )；(d) 傳名調(diào)用(call-by-name )。program mai

23、n(input,output )；procedure p ( x,y,z )；beginy：= y +1;z := z + x;end；begina：= 2；b:= 3;p(ab,a,a) ；print aend.答： 1) 傳地址：所謂傳地址是指把實(shí)在參數(shù)的地址傳遞給相應(yīng)的形式參數(shù)。在過(guò)程段中每 個(gè)形式參數(shù)都有一對(duì)應(yīng)的單元，稱為形式單元。形式單元將用來(lái)存放相應(yīng)的實(shí)在參數(shù)的地址。 當(dāng)調(diào)用一個(gè)過(guò)程時(shí)，調(diào)用段必須領(lǐng)先把實(shí)在參數(shù)的地址傳遞到一個(gè)為被調(diào)用段可以拿得到的 地方。當(dāng)程序控制轉(zhuǎn)入被調(diào)用段之后，被調(diào)用段首先把實(shí)參地址捎進(jìn)自己相應(yīng)的形式單元中， 過(guò)程體對(duì)形式參數(shù)的任何弓用 1 或賦值都被處理成對(duì)

24、形式單元的間接訪問(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è)單元的直接訪 問(wèn)。但在過(guò)程工作完畢返回前必須把第 2 個(gè)單元的內(nèi)容行放到第 1 個(gè)單元所指的那個(gè)實(shí)參單 元之中。3) 傳值：所謂傳值，是一種簡(jiǎn)單的參數(shù)傳遞方法。調(diào)用段把實(shí)在參數(shù)的值計(jì)算出來(lái)并 存放在一個(gè)被調(diào)用段可以拿得到的地方。被調(diào)用段開(kāi)

25、始丁作時(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第二次被激活時(shí)的運(yùn)行棧，控制鏈和訪問(wèn)鏈。說(shuō)明在c中如何訪 問(wèn)變量X。program env ；p

26、rocedure a ； var x:i nteger ； procedure b ； procedure c ；begin x:=2 ； b end; procedure c beg in c end; procedure bbegin b end； procedure abeg in a end. ma in答:envcontrol linkcontrol linkcontrol link access linkaccess linkacontrol linkc"'control linkbcaccess linkaccess linkaccess linkxbcontr

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

28、of i, j, f, e = %o, %o, %o, %o n", &i, &j, &f, &e);printf( "Address of i1, j1, f1, el = %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(i nt), sizeof( Ion

29、g), sizeof(float), sizeof(double);mai n()short i, j; float f, e;func(i, j, f, e);運(yùn)行結(jié)果是：Address of i, j, f, e = 35777772536, 35777772542, 35777772544, 35777772554Address of i1, j1, f1, el = 35777772426, 35777772424, 35777772420, 35777772414 Sizes of short, i nt, Io ng, float, double = 2, 4, 4, 4, 8，請(qǐng)

30、問(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ù)形式參數(shù)所聲明的類(lèi)型，決定是否要將實(shí)在參數(shù)向低級(jí)別類(lèi)型轉(zhuǎn)換。因此被調(diào)用函數(shù)把實(shí)在參數(shù)的低位字在本例中，long類(lèi)型數(shù)據(jù)占4個(gè)字節(jié)，而

31、short類(lèi)型數(shù)據(jù)只占2個(gè)字節(jié)。節(jié)的內(nèi)容當(dāng)成是自己所需的數(shù)據(jù)，見(jiàn)圖5.2long低地址放高位咼地址 放低位shortdoublefloat圖5.3圖5.2長(zhǎng)整型和短整型SUNX作站來(lái)說(shuō)，低地址存放整型數(shù)據(jù)的高位。注意，對(duì)于對(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é)作為自5.3。己所需的數(shù)據(jù)，因?yàn)閐ouble后面4個(gè)字節(jié)的內(nèi)容都是為了增加精度用的，見(jiàn)圖這樣在main函數(shù)中依次將參數(shù)提升后反序進(jìn)棧，大小分別為8, 8, 4, 4。在func函數(shù)中，按形式參數(shù)的類(lèi)型，雙精度型和浮點(diǎn)型見(jiàn)圖把這些存儲(chǔ)單元的一部分看成是形式參數(shù)的存儲(chǔ)單元, 它們的

32、類(lèi)型大小不一致了。5.4。從這個(gè)圖不難理解為什么形式參數(shù)的地址間隔和在main函數(shù)中參數(shù)壓棧時(shí)的觀點(diǎn)棧的增 長(zhǎng)方向f，8個(gè)字節(jié)4個(gè)字節(jié)，起始地址e, 8個(gè)字節(jié)i，4個(gè)字節(jié) j，4個(gè)字節(jié)在func函數(shù)中存取形式參數(shù)時(shí)的觀點(diǎn)> 2個(gè)字節(jié)，起始地址2個(gè)字節(jié)，起始地址4個(gè)字節(jié)，起始地址35777772536357777725423577777254435777772554char、short、float等）另行分配在局部數(shù)據(jù)圖5.4參數(shù)在棧中的情況 注意，現(xiàn)在的編譯器將需要進(jìn)行類(lèi)型轉(zhuǎn)換的形式參數(shù)（類(lèi)型是精選資料，歡迎下載區(qū)，當(dāng)控制進(jìn)入被調(diào)用過(guò)程時(shí)，首先將調(diào)用過(guò)程壓棧的需要進(jìn)行類(lèi)型轉(zhuǎn)換的實(shí)在參數(shù)取

33、出，把它們存入所分配的局 部數(shù)據(jù)區(qū)存儲(chǔ)單元，并同時(shí)完成必要的數(shù)據(jù)類(lèi)型的轉(zhuǎn)換。在這種情況下，不會(huì)出現(xiàn)本題所碰到的現(xiàn)象。X86機(jī)器，數(shù)據(jù)的高另外，在SPARC工作站上，整型數(shù)據(jù)的高位存放在低地址，而低位存放在高地址。如果是int和long的大小一樣)。低位不是按這樣的次序存放，那也不會(huì)出現(xiàn)本題所碰到的現(xiàn)象。 下面是某個(gè)編譯器的類(lèi)型提升函數(shù)，供讀者理解用(備注:Type promote(Type ty)switch(ty->op)case ENUM:return in ttype;case INT:if (ty->size < in ttype->size) return i

34、n ttype;break;case UNSIGNED:if (ty->size < in ttype->size) return in ttype;break;case FLOAT:if (ty->size < doubletype->size) retur n doubletype;return ty;16試把下列C語(yǔ)言程序的可執(zhí)行語(yǔ)句翻譯為(a) 一棵語(yǔ)法樹(shù)，(b) 后綴式，(c) 三地址代碼。mai n() int i;int a10;while (i<=10)精選資料，歡迎下載ai=0;(b) 后綴式為：i 10<= a i 0 = w

35、hile從理論上可以說(shuō)while(i<=10) ai=O;的后綴式如上面表示。但若這樣表示，在執(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)向 <本語(yǔ) 句始址>。(c) 三地址代碼序列為：100 if i <= 10 got 102101 goto 106102 t1:=4*i103 t2:=a104 t2t1:=0105 goto 100

36、10617 Pascal 語(yǔ)言中，語(yǔ)句：for v ：= initial to final do stmt與下列代碼序列有相同含義begi nt1:=i nitial;t2:=fi nal;if t1<=t2 then beginv:=t1;stmtwhile v<>t2 do beg inv : =succ (v)；stmtendendend(a) 試考慮下述Pascal程序program forloop(i nput, output);var i,initial,final: integer;beg inread(i nitial, fin al);for i:= ini

37、tial to final dowrite(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 := finalif t1 > t2 goto S.next v := t1 stmt.code S.beg

38、in:if v > t2 goto S.next v := succ(v) stmt.code goto S.begin語(yǔ)法制導(dǎo)定義如下：產(chǎn)生式 動(dòng)作 S tfor E do S1 S.begin := newlabel S.first := newtemp S.last := newtemp S.curr:= newtempS.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“

39、: ”) |gen(“if ”S.curr“>”S.Last“goto ”S.next) |S1.code|gen(S.curr := succ(S.curr) |gen(“goto”S.begin) E tv:=initial to final E.init := initial.placeE.final := final.place18對(duì)于下面C語(yǔ)言文件s.cf1（int x）long x;x = 1;f2（int x）long x;x = 1; 某編譯器編譯時(shí)報(bào)錯(cuò)如下：s.c: In functionf1 ':s.c:3: warning: declaration ofx&

40、#39;shadows a parameter請(qǐng)回答，對(duì)函數(shù) f2 為什么沒(méi)有類(lèi)似的警告錯(cuò)誤。 答：對(duì)于函數(shù) f1 ，局部變量 x 聲明的作用域是整個(gè)函數(shù)體，導(dǎo)致在函數(shù)體中不可能訪問(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ǔ)言，其中所有的變量都是整型（不需要顯式聲明），并且僅包含賦值語(yǔ)句、讀語(yǔ) 句和寫(xiě)語(yǔ)句。下面的產(chǎn)生式定義了該語(yǔ)言的語(yǔ)法（其中 lit表示整型常量；0P的產(chǎn)生式?jīng)]有給出, 因?yàn)樗拖旅嬗懻摰膯?wèn)題無(wú)關(guān)）。ProgramStmtListStmtE

41、xpStmtListStmt StmtList | Stmtid := Exp; | read ( id ); | write ( Exp );id | lit| Exp 0P Exp我們把不影響 write 語(yǔ)句輸出值的賦值（包括通過(guò) read 語(yǔ)句來(lái)賦值）稱為無(wú)用賦值，寫(xiě)一個(gè)語(yǔ) 法指導(dǎo)定義， 它確定一個(gè)程序中出現(xiàn)過(guò)賦予無(wú)用值的變量集合 （不需要知道無(wú)用賦值的位置） 和沒(méi)有置初值的變量集合(不影響 write 語(yǔ)句輸出值的未置初值變量不在考慮之中)。非終結(jié)符 StmtList 和 Stmt 用下面 3 個(gè)屬性(你根據(jù)需要來(lái)定義其它文法符號(hào)的屬性)：(1)uses_in ：在本語(yǔ)句表或語(yǔ)句入口

42、點(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 StmtListStmtList.uses_out:= ;Program.useless := StmtList.useless;Program.no_initial := StmtList.uses_in;StmtLi

43、stStmt StmtList 1 StmtList 1.uses_out := StmtList.uses_out;Stmt.uses_out := StmtList1.uses_in;StmtList.uses_in := Stmt.uses_inStmtList.useless := StmtList1.uselessStmt.useless;StmtListStmt Stmt.uses_out := StmlList.uses_out;StmlList.uses_in := Stmt.uses_in;StmtList.useless := Stmt.uselessStmtid := E

44、xp; Stmt.useless := if id .lexeme Stmt.uses_out then else id .lexeme;Stmt.uses_in := if id .lexeme Stmt.uses_outthen (Stmt.uses_out-id.lexeme)Exp.useselseStmt.uses_outStmtread ( id ); Stmt.useless:=ifid .lexemeStmt.uses_outthenelse id .lexemeStmt.uses_in := Stmt.usesout- id.lexemeStmtwrite ( Exp );S

45、tmt.useless :=, Stmt.usesin := Stmt.uses_outExp.usesExpidExp.uses:= id .lexemeExplitExp.uses:=ExpExp 1OP Exp 2 Exp.uses:= Exp 1.usesExp 2.uses20 為下列 C 程序生成目標(biāo)代碼 main()int i;int a10;while(i<=10) ai=0;答：21 試構(gòu)造下面的程序的流圖，并找出其中所有回邊及循環(huán) read Px := 1c := P * Pif c < 100 goto L1B := P * Px := x + 1B := B

46、 + x write x haltL1: B:= 10x := x + 2B := B + x write B if B < 100 goto L2 haltL2: x := x + 1goto L1回邊: 循環(huán)|答：程序的流圖如下22試求出如下四元式程序中的循環(huán)并進(jìn)行循環(huán)優(yōu)化.I := 1read J, KL: A := K * IB := J * IC := A * Bwrite CI := I + 1if I < 100 goto L halt9.4(1)中，其中有三個(gè)基本塊B1，B2，B3,有答：把本題的三地址代碼劃分成基本塊并畫(huà)出其程序流圖顯示在圖 一條回邊B2 ->

47、; B2，相應(yīng)的循環(huán)是B2。I > 1 read 二 KT.: A K - TE ;二 J * C -* Bwrilu I T + Ii£ I < 100 goto Lhalt圖g 4 cr程序毓囹B2中A和B都是I的歸納變量。優(yōu)(1) 代碼外提：由于循環(huán)中沒(méi)有不變運(yùn)算，故不做此項(xiàng)優(yōu)化(2)強(qiáng)度削弱:化結(jié)果顯示在圖9.4(2)中。halt§9.4(2)經(jīng)理度削弱后的額圏(3)刪除歸納變量：變換循環(huán)控制條件，刪除歸納變量I后的流圖顯示在圖9.4(3)中圖9.4（3）刪除歸綱變量的程序流圖23考慮下面的三地址語(yǔ)句序列：b := 1b := 2if w <= x

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

49、)L3:if y <= z goto L4(5)goto L5(6)L4:g := g + 1h := 8goto L1(7)L5:h := 9(8)(3)結(jié)點(diǎn)5、7和3構(gòu)成一個(gè)循環(huán)，其中5是入口結(jié)點(diǎn)b := 224對(duì)下面的程序片段作出其程序流圖并計(jì)算：(1) 各基本塊的到達(dá)_定值集INB；(2) 各基本塊中各變量引用點(diǎn)的ud鏈；(3) 各基本塊出口的活躍變量集 V_OUTB；(4) 各基本塊中變量定值點(diǎn)的du鏈。I := 1J := 0L1: J := J + Iread Iif I < 100 goto L2write JhaltL2 : I := I * I圖g”柱序流逼 -定值集INB。公式為：INB = U OUTPP PB答：本題程序的程序流圖如圖 9.6(1)所示。(1)計(jì)算各基本塊的到達(dá)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 d 3, d 4 00110000 d 1, d 2, d6 11000100 d 6 00000100 d 1, d 4 10010000B 00