編譯原理平時(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)

2、60;具有偶數(shù)個(gè)0和奇數(shù)個(gè)1的有0和1組成的符號(hào)串的全體。答：設(shè)S是符合要求的串，|S|=2k+1 (k0）。則 SS10|S21，|S1|=2k (k>0），|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

3、)(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組成的符號(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)串的

4、集合。答：(1) DFA M=(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)正則表達(dá)式: 1*01*01*01* DFA M=(0，1，q0，q1，q2，q3，q0，q3，)其中定義如下:（q0，0）=q1     （q0，1）=q0（q1，0）=q2 &

5、#160;   （q1，1）=q1（q2，0）=q3     （q2，1）=q2（q3，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 (懸而未決

6、的-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 ex

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

8、廣文法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)如下:I0 = E'·E, E·E+T, E·T, T·TF, T·F, F·F*,        F·a, F·b I1 = E'E·, EE·+TI2 = ET·, TT

9、3;F, F·F*, F·a, F·bI3 = TF·, FF·* I4 = Fa· I5 = Fb· I6 = EE+·T, T·TF, T·F, F·F*, F·a, F·b I7 = TTF·, FF·* I8 = FF*·I9 = EE+T·, TT·F, F·F*, F·a, F·b求FOLLOW集：    FOLLOW(E)=,

10、60;   FOLLOW(T)=, , 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)項(xiàng)目集規(guī)范族和goto函數(shù)(識(shí)別活前綴的DFA)如下: I0 = S·S, $, S·E, $, E·E+T, $/+, E·T, $/+,&

11、#160;T·(E), $/+, T·a, $/+ I1 = SS·, $ I2 = SE·, $, EE·+T, $/+ I3 = ET·, $/+I4 = T(·E), $/+, E·E+T, )/+, E·T, )/+,  T·(E), )/+, T·a, )/+ I5 = Ta·, $/+ I6 = EE+·T, $/+, T·(E), $/+, T·a, $/+I7 = T(E·), $/+, EE·+T,

12、 )/+ I8 = ET·, )/+I9 = T(·E), )/+, E·E+T, )/+, E·T, )/+, T·(E), )/+, T·a, )/+I10 = Ta·, )/+ I11 = EE+T·, $/+ I12 = T(E)·, $/+I13 = EE+·T, )/+, T·(E), )/+, T·a, )/+ I14 = T(E·), )/+, EE·+T, )/+I15 = EE+T·, )/+ I16 = T(E)·

13、, )/+合并同心的LR(1)項(xiàng)目集，得到LALR的項(xiàng)目集和轉(zhuǎn)移函數(shù)如下： I0 = S·S, $, S·E, $, E·E+T, $/+, E·T, $/+, T··(E), $/+, T·a, $/+I1 = SS·, $ I2 = SE·, $, EE·+T, $/+ I3,8 = ET·, $/+/)I4,9 = T(·E), $/+/), E·E+T, )/+, E·T, )/+,  T·(E), )/+, T·a,

14、 )/+I5,10 = Ta·, $/+/) I6,13 = EE+·T, $/+/), T·(E), $/+/), T·a, $/+/)I7,14 = T(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 &

15、#174;·E + idE ®·idI0E¢ ® E·E ® E·+ idI1E ® id·I2Eid+E ® E +·idI3E ® E + id·I4id再構(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）下面左右兩個(gè)文法都和（1）的文法等價(jià)E ® E + M id | idE ® M E + i

16、d | 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)造下面文法的LL（1）分析表。D ® TLT ® int | realL ® id RR ® , id R | e答：先計(jì)算FIRST和FOLLOWFIRST(D)

17、= 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)生的表達(dá)式是對(duì)整型和實(shí)型常數(shù)應(yīng)用算符+形成的。當(dāng)兩個(gè)整數(shù)相加時(shí)，結(jié)果仍為整數(shù)，否則就是實(shí)數(shù)。        

18、0;EE+T|T         Tnum.num|num     （a）給出一個(gè)語法制導(dǎo)定義以確定每個(gè)子表達(dá)式的類型。     （b）擴(kuò)充（a）中的語法制導(dǎo)定義把表達(dá)式翻譯成前綴形式，并且決定類型。使用一元算符inttoreal把整型值轉(zhuǎn)換成相等的實(shí)型值，以使得前綴形式中的+的兩個(gè)操作對(duì)象是同類型的。答： (a):產(chǎn)生式語義規(guī)則EàE1+TIF (E1.type=integer) and (T.type=integer) T

19、HEN E.type:=integerELSE E.type:=realEàTE.type:=T.typeTànum.numT.type:=realTànumT.type:=integer(b):產(chǎn)生式語義規(guī)則EàE1+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:=

20、inttoreal(E1.val) End IF T.type:=integer THEN Begin T.type:=real T.val:=inttoreal(T.val) End Print(+,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è)說明是由下列文法產(chǎn)生的：        

21、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)生式翻譯模式Dàid LD.Type:=L.Typeaddtype(id.entry, D.type)Là,id L1L.Type:=L1.Typeaddtype

22、(id.entry, L.type)Là:TL.type:=T.typeTàintegerT.type:=integerTàrealT.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

23、.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 er

24、rorend11為下面的算術(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_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.sig

25、n := 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 | BB ® 0 | 1答：S ® L . RS. val := L. val + R. val S ® LS. val := L. valL ® L1 BL. v

26、al := 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ū)⒂性鯓拥妮敵觯糠謩e假定：    （a）傳值調(diào)用（call-by-value）；    （b）引用調(diào)用（call-by-reference）；    （

27、c）復(fù)制恢復(fù)（copy-restore）；    （d）傳名調(diào)用（call-by-name）。     program main(input,output）；        procedure p（x,y,z）；           begin              

28、;y：y1；              z：zx；           end；        begin            a：2；         &#

29、160;  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)先

30、把實(shí)在參數(shù)的地址傳遞到一個(gè)為被調(diào)用段可以拿得到的地方。當(dāng)程序控制轉(zhuǎn)入被調(diào)用段之后，被調(diào)用段首先把實(shí)參地址捎進(jìn)自己相應(yīng)的形式單元中，過程體對(duì)形式參數(shù)的任何引用1或賦值都被處理成對(duì)形式單元的間接訪問。當(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í)參

31、單元之中。 3)傳值：所謂傳值，是一種簡(jiǎn)單的參數(shù)傳遞方法。調(diào)用段把實(shí)在參數(shù)的值計(jì)算出來并存放在一個(gè)被調(diào)用段可以拿得到的地方。被調(diào)用段開始丁作時(shí)，首先把這些值抄入形式中元中，然后就好像使用局部名一樣使用這些形式單元。如果實(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

32、程序畫出過程c第二次被激活時(shí)的運(yùn)行棧，控制鏈和訪問鏈。說明在c中如何訪問變量x。program env；      procedure a；        var x:integer；        procedure b；          procedure c；    &#

33、160;       begin x:=2；b end；procedure c          begin c end；procedure b        begin b end；procedure a       begin a end. main  答： envcontrol linkacc

34、ess linkacontrol linkaccess linkx bcontrol linkaccess link ccontrol linkaccess link bcontrol linkaccess link caccess linkcontrol link說明：c中沿著存取鏈向前走兩步，到過程a的活動(dòng)記錄中就可以訪問到變量x。15 下面給出一個(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的地址間隔和它們的

35、類型的大小不一致，試分析不一致的原因。注意，輸出的數(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); printf( "Address of i1, j1, f1, e1 = %o, %o, %o, %o n", &i1, &j1, &f1, &e1)

36、; 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 = 35777772536, 35777772542, 35777772544, 35777772554 Address

37、 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í)型，編譯器則試圖保證目標(biāo)代碼運(yùn)行時(shí)能得到正確的結(jié)果，條件是，當(dāng)需要高級(jí)別類型數(shù)據(jù)向低級(jí)別類型數(shù)據(jù)轉(zhuǎn)換時(shí)，不出現(xiàn)溢出。這樣，C編譯器作

38、的約定是，當(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 雙精度型和浮點(diǎn)型對(duì)于實(shí)型來說。double類型是8個(gè)字節(jié)，而float類型4個(gè)字節(jié)。被調(diào)用函數(shù)把實(shí)在參數(shù)的前4個(gè)字節(jié)作為

39、自己所需的數(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。在func函數(shù)中，按形式參數(shù)的類型，把這些存儲(chǔ)單元的一部分看成是形式參數(shù)的存儲(chǔ)單元，見圖5.4。從這個(gè)圖不難理解為什么形式參

40、數(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)本題所碰到的現(xiàn)象。下面是某個(gè)編譯器的類型提升函數(shù)，供讀者理解用（備注：int和long的大小一樣）。Type promote

41、(Type ty)switch(ty->op)case ENUM: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語言程序的可執(zhí)行語句翻譯為(a)一棵語法

42、樹， (b)后綴式， (c)三地址代碼。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; 的后綴式如上面表示。但若這樣表示，在執(zhí)行while操作時(shí)，賦值語句已經(jīng)執(zhí)行，這顯然與語義不符，因此改為：i 10 <=< 下一個(gè)語句開始地址>BM a i 0 =< 本語句地址 > BRL其中BM操作為當(dāng)表

43、達(dá)式為假時(shí)轉(zhuǎn)向<下一個(gè)語句開始地址>，BRL是一個(gè)一目運(yùn)算，無條件轉(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 v<>t2 do begi

44、n 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對(duì)于initial=MAXINT-5和final= MAXINT，問此程序?qū)⒆鲂┦裁矗科渲蠱AXINT為目標(biāo)機(jī)器允許的最大整數(shù)。(b)試構(gòu)造一個(gè)翻譯pascal的for語句為三地址代碼的語法制導(dǎo)定義。 答：（a）程序?qū)@示如下六個(gè)整數(shù)： MAXIN

45、T -5 MAXINT -4 MAXINT -3 MAXINT -2 MAXINT -1 MAXINT （b）為簡(jiǎn)單起見，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 語法制導(dǎo)定義如下： 產(chǎn)生式 動(dòng)作 Sfor E do S1 S.begin := newlabel S.first := newtemp S.last := newte

46、mp 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.i

47、nit := initial.place E.final := final.place18對(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: warning: declaration of x shadows a parameter請(qǐng)回答，對(duì)函數(shù)f2為什么沒有類似的警告錯(cuò)誤。答：對(duì)于函數(shù)f1，局部變量x聲明的作用域是整個(gè)函數(shù)體，導(dǎo)致在函數(shù)體中不可能訪問形式參數(shù)x。由于這是一個(gè)合法的C語言函數(shù)，因此編譯器給出警告錯(cuò)誤。對(duì)于函數(shù)f2，由于局部變量x的作用域只是

48、函數(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)）。Program®StmtListStmtList ®Stmt StmtList | StmtStmt®id := Exp; | read (id ); | write ( Exp ); Exp®id | lit | Exp OP Exp我們把不影響write語句輸出值的賦值（包括通過read語句來賦

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

50、和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_inSt

51、mtList.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.lexemeÎStmt.uses_out then Æ elseid.lexeme; Stmt.uses_in := if id.lexeme&

52、#206;Stmt.uses_out then (Stmt.uses_outid.lexeme)ÈExp.uses else Stmt.uses_outStmt ®read (id ); Stmt.useless:=if id.lexemeÎStmt.uses_out then Æ elseid.lexeme;Stmt.uses_in := Stmt.uses_out id.lexemeStmt ®write ( Exp );Stmt.useless := Æ, Stmt.uses_in := Stmt.uses_out È

53、 Exp.usesExp® idExp.uses:= id.lexemeExp® litExp.uses:= ÆExp® Exp1 OP Exp2Exp.uses:= Exp1.uses È Exp2.uses20 為下列C程序生成目標(biāo)代碼。    main()                    int

54、i;            int a10;            while(i<=10)                 ai=0;     

55、0;    答：21 試構(gòu)造下面的程序的流圖，并找出其中所有回邊及循環(huán)。          read P          x := 1          c := P * P          if c &l

56、t; 100 goto L1          B := P * P          x := x + 1          B := B + x          write x     

57、;     halt      L1: B:= 10          x := x + 2          B := B + x          write B      &

58、#160;   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

59、C I := I + 1 if I < 100 goto L halt答：把本題的三地址代碼劃分成基本塊并畫出其程序流圖顯示在圖9.4(1)中，其中有三個(gè)基本塊B1，B2，B3，有一條回邊B2 -> 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.4(3)中 23 考慮下面的三地址語句序列：b := 1b := 2if w <= x goto L2e := bgoto L2L1:goto L3

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

61、4（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)。24 對(duì)下面的程序片段作出其程序流圖并計(jì)算：（1）各基本塊的到達(dá)_定值集INB；（2）各基本塊中各變量引用點(diǎn)的ud鏈；（3）各基本塊出口的活躍變量集V_OUTB；（4）各基本塊中變量定值點(diǎn)的du鏈。            I := 1       

62、0;    J := 0        L1: J := J + I            read I            if I < 100 goto L2         &

63、#160;  write J            halt        L2 : I := I * I答：本題程序的程序流圖如圖9.6(1)所示。 （1）計(jì)算各基本塊的到達(dá)-定值集INB。公式為：                 INB  = OUTP                        PPB