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

1、平時(shí)作業(yè)1 對(duì)于以下語言分別寫出它們的正規(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)=0,1上的含偶數(shù)個(gè)1的所有串。答：(0|10*1)*(4)=0,1上的含奇數(shù)個(gè)1的所有串。答：(0|10*1)*1(5)具有偶數(shù)個(gè)0和奇數(shù)個(gè)1的有0和1組成的符號(hào)串的全體。答：設(shè)S是符合要求的串，|S|=2k+1 (k0。

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

3、1)*0|(00|11)|(01|10)(00|11)*(01|10)*1(6)不包含子串011的由0和1組成的符號(hào)串的全體。答：1*|1*0(0|10)*(1|)(7)由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上的語言的DFA。(1)所有以00結(jié)束的符號(hào)串的集合。(2)所有具有3個(gè)0的符號(hào)串的集合。答：(1) DFAM=(0，1，q0，q1，q2，q0，q2，)其中定義如下:q0，0=q1 q0，1=q0q1，0=q2 q1，1=q0q2，0=q2 q2，1=q0(2)

4、正那么表達(dá)式: 1*01*01*01* DFAM=(0，1，q0，q1，q2，q3，q0，q3，)其中定義如下:q0，0=q1 q0，1=q0q1，0=q2 q1，1=q1q2，0=q3 q2，1=q2q3，1=q3 3 下面是用正規(guī)式表示的變量聲明：( int | float ) id (, id )* ;請(qǐng)改用上下文無關(guān)文法表示，也就是寫一個(gè)上下文無關(guān)文法，它和該正規(guī)式等價(jià)。答：D T L ; T int | floatL L, id | id4 試分析下面給出的if-then-else語句的文法，它的提出原本是為了矯正dangling-else (懸而未決的-else)文法的二義性：st

5、mt 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-

6、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)文法，并構(gòu)造其SLR分析表。EE+T|T TTF|F FF*|a|b 答：該文法的拓廣文法G為 (0) E E(1

7、) E E+T(2) E T(3) T TF(4) T F(5) F F*(6) F a(7) F b其LR(0)工程集標(biāo)準(zhǔn)族和goto函數(shù)(識(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

8、)=, , a, bFOLLOW(F)=, , a, b, *構(gòu)造的SLR分析表如下： 顯然，此分析表無多重定義入口，所以此文法是SLR文法。6 為下面的文法構(gòu)造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構(gòu)造其LR(1)工程集標(biāo)準(zhǔn)族和goto函數(shù)(識(shí)別活前綴的DFA)如下: I0 = SS, $, SE, $, EE+T, $/+, ET, $/+,T(E), $/+, Ta, $/+ I1 = SS, $ I2 = SE, $, EE+T, $/+ I3 = ET, $/+

9、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, )/

10、+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(

11、E), $/+/), EE+T, )/+ I11,15 = EE+T, $/+/) I12,16 = T(E) , $/+/)LALR分析表如下：7 1通過構(gòu)造識(shí)別活前綴的DFA和構(gòu)造分析表，來證明文法E E + id | id是SLR(1)文法。答：先給出接受該文法活前綴的DFA如下：E EE E + idE idI0E EE E+ idI1E idI2Eid+E E +idI3E E + idI4id再構(gòu)造SLR分析表如下：狀態(tài) 動(dòng)作轉(zhuǎn)移 id + $ E 0 s2 1 1 s3 acc 2 r2 r2 3 s4 4 r1 r1 表中沒有多重定義的條目，因此該文法是SLR(1)的。2下面左

12、右兩個(gè)文法都和1的文法等價(jià)E E + M id | idE M E + id | idM eM e請(qǐng)指出其中有幾個(gè)文法不是LR(1)文法，并給出它們不是LR(1)文法的理由。答：只有文法E M E + id | idM e不是LR(1)文法。因?yàn)閷?duì)于句子id+id+id來說，分析器在面臨第一個(gè)id時(shí)需要做的空歸約次數(shù)和句子中+id的個(gè)數(shù)一樣多，而此時(shí)句子中+id的個(gè)數(shù)是未知的。8根據(jù)自上而下的語法分析方法，構(gòu)造下面文法的LL1分析表。D TLT int | realL id RR , id R | e答：先計(jì)算FIRST和FOLLOWFIRST(D) = FIRST(T) = int,real

13、FIRST(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)生的表達(dá)式是對(duì)整型和實(shí)型常數(shù)應(yīng)用算符+形成的。當(dāng)兩個(gè)整數(shù)相加時(shí)，結(jié)果仍為整數(shù)，否那么就是實(shí)數(shù)。 EE+T|T Tnum.num|num a給出一個(gè)語法制導(dǎo)定義以確定每個(gè)子表達(dá)式的類型。 b擴(kuò)充a中的語法制導(dǎo)定義把表達(dá)式翻譯成前綴形式，并且決定類型。使用一元算符inttoreal把整型

14、值轉(zhuǎn)換成相等的實(shí)型值，以使得前綴形式中的+的兩個(gè)操作對(duì)象是同類型的。答： (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) ENDE

15、LSE 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 假

16、設(shè)說明是由以下文法產(chǎn)生的： Did L L,id L|:T Tinteger |real a建立一個(gè)翻譯模式，把每一個(gè)標(biāo)識(shí)符的類型參加到符號(hào)表中。 b從a中的翻譯模式構(gòu)造一個(gè)預(yù)翻譯程序。 答： (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 Be

17、ginMatch(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

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

19、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為下面文法寫一個(gè)語法制導(dǎo)的定義，用S的綜合屬性val給出下面文法中S產(chǎn)生的二進(jìn)制數(shù)的值。例如，輸入101.101時(shí)，S. val := 5.625。不得修改文法。S L . R | LL L B | BR B R |

20、 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復(fù)制恢復(fù)copy-restore； d傳名調(diào)用call-by

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

22、式單元的間接訪問。當(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í)參的值。在過程體中對(duì)形參的任何引用或賦值都看成是對(duì)它的第2個(gè)單元的直接訪問。但在過程工作完畢返回前必須把第2個(gè)單元的內(nèi)容行放到第1個(gè)單元所指的那個(gè)實(shí)參單元之中。 3)傳值：所謂傳值，是一種簡(jiǎn)單的參數(shù)傳遞方法。調(diào)用段把實(shí)在參數(shù)的值計(jì)算出來并存放在一個(gè)被調(diào)用段可以拿得到的地方。被調(diào)用段開始丁作時(shí)，首先把這些值抄入形式中元中，然后就好似

23、使用局部名一樣使用這些形式單元。如果實(shí)在參數(shù)不為指示器，那末，在被調(diào)用段中無法改變實(shí)參的值。 4)傳名：所謂傳名，是一種特殊的形實(shí)參數(shù)結(jié)合方式。解釋“傳名參數(shù)的意義：過程調(diào)用的作用相當(dāng)于把被調(diào)用段的過程體抄到調(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程序畫出過程c第二次被激活時(shí)的運(yùn)行棧，控制鏈和訪問鏈。說明在c中如何訪問變量x。program env； procedure a； var x:integer； procedure b；

24、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的活動(dòng)記錄中就可以訪問到變量x。15

25、下面給出一個(gè) C 語言程序及其在 SPARC/SUN 工作站上經(jīng)某編譯器編譯后的運(yùn)行結(jié)果。從運(yùn)行結(jié)果看，函數(shù) func中 4個(gè)局部變量 i1, j1, f1, e1的地址間隔和它們類型的大小是一致的，而 4個(gè)形式參數(shù) i, j, f, e的地址間隔和它們的類型的大小不一致，試分析不一致的原因。注意，輸出的數(shù)據(jù)是八進(jìn)制的。 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); p

26、rintf( 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); 運(yùn)行結(jié)果是： Address of i, j, f, e

27、= 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，請(qǐng)問為什么？答：C語言編譯器是不做實(shí)在參數(shù)和形式參數(shù)的個(gè)數(shù)和類型是否一致的檢查的，由程序員自己保證它們的一致性。但是對(duì)于形式參數(shù)和實(shí)在參數(shù)是不同的整型如一個(gè)是short型，另一個(gè)是long型，或者是不同的實(shí)型，編譯器那么試

28、圖保證目標(biāo)代碼運(yùn)行時(shí)能得到正確的結(jié)果，條件是，當(dāng)需要高級(jí)別類型數(shù)據(jù)向低級(jí)別類型數(shù)據(jù)轉(zhuǎn)換時(shí)，不出現(xiàn)溢出。這樣，C編譯器作的約定是，當(dāng)整型或?qū)嵭蛿?shù)據(jù)作為實(shí)在參數(shù)時(shí)，分別將它們提升到long和double類型的數(shù)據(jù)傳遞到被調(diào)用函數(shù)。被調(diào)用函數(shù)根據(jù)形式參數(shù)所聲明的類型，決定是否要將實(shí)在參數(shù)向低級(jí)別類型轉(zhuǎn)換。低地址放高位高地址放低位shortlong圖5.2 長(zhǎng)整型和短整型在本例中，long類型數(shù)據(jù)占4個(gè)字節(jié)，而short類型數(shù)據(jù)只占2個(gè)字節(jié)。因此被調(diào)用函數(shù)把實(shí)在參數(shù)的低位字節(jié)的內(nèi)容當(dāng)成是自己所需的數(shù)據(jù)，見圖5.2注意，對(duì)于SUN工作站來說，低地址存放整型數(shù)據(jù)的高位。floatdoublee圖5.3 雙

29、精度型和浮點(diǎn)型對(duì)于實(shí)型來說。double類型是8個(gè)字節(jié)，而float類型4個(gè)字節(jié)。被調(diào)用函數(shù)把實(shí)在參數(shù)的前4個(gè)字節(jié)作為自己所需的數(shù)據(jù)，因?yàn)閐ouble后面4個(gè)字節(jié)的內(nèi)容都是為了增加精度用的，見圖5.3。e，8個(gè)字節(jié)在main函數(shù)中參數(shù)壓棧時(shí)的觀點(diǎn)在func函數(shù)中存取形式參數(shù)時(shí)的觀點(diǎn)4個(gè)字節(jié)，起始地址357777725544個(gè)字節(jié)，起始地址357777725442個(gè)字節(jié)，起始地址357777725422個(gè)字節(jié)，起始地址35777772536f，8個(gè)字節(jié)j，4個(gè)字節(jié)i，4個(gè)字節(jié)棧的增長(zhǎng)方向圖5.4 參數(shù)在棧中的情況這樣在main函數(shù)中依次將參數(shù)提升后反序進(jìn)棧，大小分別為8, 8, 4, 4。在fu

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

31、的現(xiàn)象。下面是某個(gè)編譯器的類型提升函數(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)三

32、地址代碼。main() int i; int a10; while (i=10) ai=0;while答：(a).一棵語法樹賦值表達(dá)式布爾表達(dá)式表達(dá)式表達(dá)式數(shù)組元素表達(dá)式=下標(biāo)表達(dá)式110a01(b) 后綴式為： i 10= a i 0 = while從理論上可以說while(i=10) ai=0; 的后綴式如上面表示。但假設(shè)這樣表示，在執(zhí)行while操作時(shí)，賦值語句已經(jīng)執(zhí)行，這顯然與語義不符，因此改為：i 10 =BM a i 0 = BRL其中BM操作為當(dāng)表達(dá)式為假時(shí)轉(zhuǎn)向，BRL是一個(gè)一目運(yùn)算，無條件轉(zhuǎn)向。(c) 三地址代碼序列為：100 if i = 10 got 102101 goto

33、 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：=succv)； stmt end endend (a)試考慮下述Pascal程序program forloop(input, output); var i,initial,final: integer; begin

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

35、next v := t1 stmt.code S.begin: if v t2 goto S.next v := succ(v) stmt.code goto S.begin 語法制導(dǎo)定義如下： 產(chǎn)生式 動(dòng)作 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

36、 “:= 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.place文檔來自于網(wǎng)絡(luò)搜索18對(duì)于下面C語言文件s.c f1(int x)long x;x = 1;f2(int x)long x;x = 1;某編譯器編譯時(shí)報(bào)錯(cuò)如下：s.c: In function f1:s.c:3

37、: warning: declaration of x shadows a parameter請(qǐng)答復(fù)，對(duì)函數(shù)f2為什么沒有類似的警告錯(cuò)誤。答：對(duì)于函數(shù)f1，局部變量x聲明的作用域是整個(gè)函數(shù)體，導(dǎo)致在函數(shù)體中不可能訪問形式參數(shù)x。由于這是一個(gè)合法的C語言函數(shù)，因此編譯器給出警告錯(cuò)誤。對(duì)于函數(shù)f2，由于局部變量x的作用域只是函數(shù)體的一局部，不會(huì)出現(xiàn)上述問題，因而編譯器不報(bào)錯(cuò)。19考慮一個(gè)簡(jiǎn)單語言，其中所有的變量都是整型不需要顯式聲明，并且僅包含賦值語句、讀語句和寫語句。下面的產(chǎn)生式定義了該語言的語法其中l(wèi)it表示整型常量；OP的產(chǎn)生式?jīng)]有給出，因?yàn)樗拖旅嬗懻摰膯栴}無關(guān)。ProgramStmtLi

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

39、序點(diǎn)后的輸出。2uses_out：在本語句表或語句出口點(diǎn)的引用變量集合，它們的值影響在該程序點(diǎn)后的輸出。3useless：本語句表或語句中出現(xiàn)的無用賦值變量集合。答：Exp的屬性u(píng)ses表示它引用的變量集合。Program的useless和no_initial分別表示程序的無用賦值變量集合和未置初值變量集合。Program StmtList StmtList.uses_out:=; Program.useless := StmtList.useless;Program.no_initial := StmtList.uses_in;StmtList Stmt StmtList1 StmtList

40、1.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.

41、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_

42、in := Stmt.uses_out Exp.usesExp idExp.uses:= id.lexemeExp litExp.uses:= Exp Exp1 OP Exp2Exp.uses:= Exp1.uses Exp2.uses20 為以下C程序生成目標(biāo)代碼。main()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:= 1

43、0 x := x + 2 B := B + x write B if B 100 goto L2 halt L2: x := x + 1 goto L1 答：程序的流圖如下22 試求出如下四元式程序中的循環(huán)并進(jì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。 1代碼外提：由于循環(huán)中沒有不變運(yùn)算，故不做此項(xiàng)優(yōu)化 2強(qiáng)度削弱：B2中A和B都是I的歸納變量。優(yōu)化結(jié)果顯示在圖9.4(2)中。 3刪除歸納變量：變換循環(huán)控制條件，刪除歸納變量I后的流圖顯示在圖9.

44、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 := 91在該代碼中用水平的橫線將代碼分成根本塊，并給每個(gè)根本塊一個(gè)序號(hào)。2畫出該代碼的控制流圖，每個(gè)根本塊就用1的序號(hào)表示。3假設(shè)有循環(huán)的話，列出構(gòu)成每個(gè)循環(huán)的結(jié)點(diǎn)。答：1 214237865b := 1b := 2if w = x goto L21e := bgoto L22L1:goto L

45、33L2:c := 3b := 4c := 64L3:if y = z goto L45goto L56L4:g := g + 1h := 8goto L17L5:h := 98（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鏈。 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計(jì)算各根本塊的到達(dá)-定值集INB。公式為： INB = OUTP PPB OUTB