編譯原理平時(shí)作業(yè)-問(wèn)題詳解

1、實(shí)用文檔平時(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)=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 組成的符

2、號(hào)串的全體答：設(shè) S是符合要求的串， |S|=2k+1 (k 0)。 則 SS10|S21，|S1|=2k (k0 )， |S 2|=2k (k 0)。 且 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) *類(lèi)似的考慮有一個(gè)自動(dòng)機(jī) M2 接受 S2，那么自動(dòng)機(jī) M2如下：和 L(M2) 等價(jià)的正規(guī)表達(dá)式，即 S2 為：(00|11)|(0

3、1|10)(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ī)如下：實(shí)用文檔對(duì)應(yīng)的正規(guī)表達(dá)式： (1(01 *0)1|0)2 給出接受下列在字母表 0,1 上的語(yǔ)言的 DFA。（1）（2） 答：所有以 00 結(jié)束的符號(hào)串的集合。 所有

4、具有 3 個(gè) 0 的符號(hào)串的集合。（1） DFAM=（0，1，q0，q1，q2，q0，q 2，）其中定義如下（ q0， 0）=q1（ q1， 0）=q2（ q0， 1）=q0（ q1， 1）=q0( q2， 0)01 01 01( q2， 1)(2) 正則表達(dá)式 : 1DFA M=（0 ， 1 ，q0，q1，q2，q3 ， q0，q 3 ，）其中定義如下（ q0， 0）=q1（ q1， 0）=q2（ q2， 0）=q3（ q3， 1）=q3（ q0， 1）=q0（ q1， 1）=q1（ q2， 1）=q23 下面是用正規(guī)式表示的變量聲明： ( int | float ) id (, id )*

5、 ;請(qǐng)改用上下文無(wú)關(guān)文法表示，也就是寫(xiě)一個(gè)上下文無(wú)關(guān)文法，它和該正規(guī)式等價(jià)。 答：D T L ;T int | floatL L, id | id實(shí)用文檔4 試分析下面給出的 if-then-else 語(yǔ)句的文法，它的提出原本是為了矯正 dangling-else ( 懸而未 決的 -else) 文法的二義性： stmt if expr then stmt|matched-stmt matched-stmt if expr then matched-stmt else stmt |other 試說(shuō)明此文法仍然是二義性的。答：考慮句子 if e then if e then other else

6、 if e then other else other它具有如下所示的兩種分析樹(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 ot

7、her expr then matched-stmt e other if matched-stmt other 則上面給出的 if-then-else 文法仍是二義性的。5 證明下面文法是 SLR(1) 文法，并構(gòu)造其 SLR分析表 EE+T|TTTF|FFF*|a|b答： 該文法的拓廣文法 G為(0) E E(1) EE+T(2) E T(3) TTF(4) T F(5) FF*(6) F a(7) Fb其 LR(0) 項(xiàng)目集規(guī)范族和 goto 函數(shù) ( 識(shí)別活前綴的 DFA)如下 :I0 = E E, E E+T, ET, T TF, T F, F F*,Fa, F bI1 = E E,

8、 E E+TI2 = E T, T TF, F F*, F a, F bI3 = T F, F F* I4 = F a I5 = F bI6 = E E+ T, T TF, T F, F F*, F a, F b I7 = TTF, F F* I8 = F F*求 FOLLOW集：FOLLOW(E)=, I9 = E E+T , T TF, F F*, F a, F bFOLLOW(T)=, , a, b實(shí)用文檔FOLLOW(F)=, , a, b, * 構(gòu)造的 SLR分析表如下：顯然，此分析表無(wú)多重定義入口，所以此文法是SLR文法。6 為下面的文法構(gòu)造 LALR(1) 分析表 SEEE+T|

9、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)如下 : I 0 = SI1 = SI4 = TI 5 = TI7 = TI9 = TI 10 = TI 13 = EI 15 = E S, $, S S, $ I (E), $/+, Ea, $/+ I (E), $/+, E (E), )/+, E a, )/+ I E+T, )/+, T E+T, )/+ IE, $, E E+T, $/+, E T, $/+,T (E), $/+, T2

10、= S E, $, E E+T, $/+ I 3 = E T, $/+ E+T, )/+, E T, )/+,T (E), )/+, Ta, )/+6 = E E+T, $/+, T (E), $/+, Ta, $/+ E +T, )/+ I 8 = E T, )/+ E+T, )/+, E T, )/+, T 11 = E E+T, $/+ I 12 = T (E), )/+, Ta, )/+ I16 = T (E), )/+ (E), )/+, Ta, )/+(E) , $/+14 = T (E), )/+, EEa, $/+T, )/+實(shí)用文檔0= S S, $, S E, $, E E

11、+T, $/+, E T, $/+, T (E), $/+, T 1 =S S, $ I 2 =S E, $, EE+T, $/+I 3,8 = E T ,$/+/)4,9= T(E), $/+/), E E+T, )/+, ET, )/+,T (E), )/+, T a, )/+5,10= Ta, $/+/) I6,13 = E E+T, $/+/), T (E), $/+/), Ta, $/+/)7,14= T(E), $/+/), EE+T, )/+ I11,15 = EE+T, $/+/)12,16= T(E) , $/+/)合并同心的 LR(1) 項(xiàng)目集，得到 LALR 的項(xiàng)目集和轉(zhuǎn)

12、移函數(shù)如下：a, $/+LALR分析表如下：實(shí)用文檔7 ( 1)通過(guò)構(gòu)造識(shí)別活前綴的 DFA和構(gòu)造分析表，來(lái)證明文法 E E + id | id 是 SLR(1)文法。 答： 先給出接受該文法活前綴的 DFA如下：Eid EE + idI3狀態(tài)動(dòng)作轉(zhuǎn)移id + $E0s211s3acc2r2r23s44r1r1I2再構(gòu)造 SLR分析表如下：表中沒(méi)有多重定義的條目，因此該文法是 SLR(1) 的。idEE + idI4EEE+id( 2)下面左右兩個(gè)文法都和( 1)的文法等價(jià)E E + M id | id E M E + id | idM M 請(qǐng)指出其中有幾個(gè)文法不是 LR(1) 文法，并給出它

13、們不是 LR(1)文法的理由 答：只有文法E M E + id | id實(shí)用文檔M不是 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) = , FOLLOW(D) = FOLLOW(L) = $

14、FOLLOW(T) = idFOLLOW(R) = $LL(1) 分析表如下：intrealid$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ù)。EE+T|TTnum. num| num（a）給出一個(gè)語(yǔ)法制導(dǎo)定義以確定每個(gè)子表達(dá)式的類(lèi)型。實(shí)用文檔（b）擴(kuò)充（ a）中的語(yǔ)法制導(dǎo)定義把表達(dá)式翻譯成前綴形式，并且決定類(lèi)型。使用一元算符 inttoreal 把整型值轉(zhuǎn)換成相等的實(shí)型值，以使得前綴形式中的 +的兩個(gè)操作對(duì)象是同類(lèi)型的。 答

15、： （a）:產(chǎn)生式語(yǔ)義規(guī)則E E1+TIF (E1.type=integer) and (T.type=integer) THEN E.type:=integerELSEE.type:=realETE.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) THEN BEGINE.type:=integerPrint( + ,E1.val,T.val)ENDELSE BEGINE.type:=realIF E1.type=int

16、eger THENBeginE1.type:=realE1.val:=inttoreal(E1.val)EndIF T.type:=integer THENBeginT.type:=realT.val:=inttoreal(T.val)EndPrint( + ,E1.val,T.val)ENDETE.type:=T.typeE.val:=T.valT num.numT.type:=realT.val:= num.num.lexvalT numT.type:=integerT.val:= num.lexval10 假設(shè)說(shuō)明是由下列文法產(chǎn)生的：D id LL ,id L|:TT integer |

17、 real（a）建立一個(gè)翻譯模式，把每一個(gè)標(biāo)識(shí)符的類(lèi)型加入到符號(hào)表中（b）從（ a）中的翻譯模式構(gòu)造一個(gè)預(yù)翻譯程序。答：實(shí)用文檔(a) ：產(chǎn)生式翻譯模式D id LD.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(id);D.type=L;ad

18、dtype(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) end Else error EndElse if lookahead= : thenBeginMatch( : );L.Type=T; return(L.Type) endelseerror實(shí)用文檔EndFunction T: D

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

20、integer 答：E E1 * E2 if 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ù)的值。例如，輸入0.101 時(shí)，S. val := 5.625。（不得修改文法。）SL.

21、 R| LLLB |BRBR |BB0| 1答：SL. RS.val= L.val + R. valSLS.val= L.valLL1 BL.val :=L 1. val2 + B.valLBL.val= B.valRBR1R.val= (R1. val +B. val )/2RBR.val= B.val /2B0B.val= 0B1B.val= 1實(shí)用文檔13 試問(wèn)下面的程序?qū)⒂性鯓拥妮敵?？分別假定：(a) 傳值調(diào)用( call-by-value )；(b) 引用調(diào)用( call-by-reference )；(c) 復(fù)制恢復(fù)( copy-restore )；(d) 傳名調(diào)用( call-b

22、y-name )。program main(input,output )；procedure p ( x,y,z )；beginy： y1；z：zx；end；begina：2；b：3；p(a b,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 或

23、賦值都被處理成對(duì)形式單元的間接訪問(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)用段可以拿得到的

24、地方。被調(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 第二次被激活時(shí)的運(yùn)行棧， 控制鏈和訪問(wèn)鏈。 說(shuō)明在 c 中如何訪 問(wèn)變量

25、 x。program env ；procedure a ；實(shí)用文檔var x:integer ； procedure b ； procedure c ；begin x:=2 ；b end；procedure c begin c end；procedure b begin b end； procedure abegin a end. main答：說(shuō)明： c 中沿著存取鏈向前走兩步，到過(guò)程 a 的活動(dò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,

26、 e1的地址間隔和它們類(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 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( Siz

27、es 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é)果是：實(shí)用文檔Address of i, j, f, e = 35777772536, 35777772542, 35777772544, 35777772554Address of i1, j1, f1, e1 = 35777

28、772426, 35777772424, 35777772420, 35777772414Sizes 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í)在

29、參數(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)換。在本例中， long 類(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低地址 放高位高地址 放低位圖 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é)的

30、內(nèi)容都是為了增加精度用的，見(jiàn)圖 5.3 。這樣在 main 函數(shù)中依次將參數(shù)提升后反序進(jìn)棧，大小分別為 8, 8, 4, 4。在 func 函數(shù)中，按形式參數(shù)的類(lèi)型，doublefloat圖 5.3 雙精度型和浮點(diǎn)型把這些存儲(chǔ)單元的一部分看成是形式參數(shù)的存儲(chǔ)單元，見(jiàn)圖 它們的類(lèi)型大小不一致了。5.4 。從這個(gè)圖不難理解為什么形式參數(shù)的地址間隔和在 main 函數(shù)中參 數(shù)壓棧時(shí)的觀點(diǎn)i， 4 個(gè)字節(jié)j， 4 個(gè)字節(jié)f，8 個(gè)字節(jié)棧的增長(zhǎng)方向e， 8 個(gè)字節(jié)在 func 函數(shù)中存取形 式參數(shù)時(shí)的觀點(diǎn)2 個(gè)字節(jié)，起始地址 357777725362 個(gè)字節(jié)，起始地址 357777725424 個(gè)字節(jié)，

31、起始地址 357777725444 個(gè)字節(jié)，起始地址 35777772554圖 5.4 參數(shù)在棧中的情況注意，現(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ù)的高位存放在低地址，而低位存放在高地址。如果是X86 機(jī)器，數(shù)據(jù)的高低位不是按這樣的次序存放，那也不會(huì)出現(xiàn)本題所碰到的現(xiàn)象。下面是某個(gè)編譯器的類(lèi)型

32、提升函數(shù)，供讀者理解用（備注： int 和 long 的大小一樣）。Type promote（Type ty）實(shí)用文檔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 語(yǔ)言程序的可執(zhí)行語(yǔ)句翻譯為(a) 一棵語(yǔ)法樹(shù)，(b) 后綴式，(c) 三

33、地址代碼。main() int i;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 =BM a i 0 = BRL其中 BM操作為當(dāng)表達(dá)式為假時(shí)轉(zhuǎn)向 ，BRL是一個(gè)一目運(yùn)算，無(wú)條件轉(zhuǎn)向 。實(shí)用文檔(c) 三地址代碼序列為：100 if i = 10 got 102101 goto 106102 t1:=4*i103 t2:=a104 t2t1:=0105

34、goto 100 initial to final do stmt10617 Pascal 語(yǔ)言中，語(yǔ)句： for v 與下列代碼序列有相同含義 begint1:=initial;t2:=final;if t1=t2 then beginv:=t1;stmtwhile vt2 do beginv：=succ(v) ；stmtendendend (a) 試考慮下述 Pascal 程序 program forloop(input, output);var i,initial,final: integer; begin read(initial, final); for i:= initial to

35、 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 := final if t1 t2 goto S.next v := t1 stmt.code S.beg

36、in:if v t2 goto S.next v := succ(v) stmt.code goto S.begin 語(yǔ)法制導(dǎo)定義如下：產(chǎn)生式 動(dòng)作 S for E do S1 S.begin := newlabel S.first := newtemp S.last := newtemp S.curr:= newtempS.code:=gen(S.firstS.next) |gen(S.currS.next) |S1.code“:= ” E.init)|gen(S.last“ := ” S.first) |gen(S.begin |gen(S.curr := succ(S.curr)“:=

37、” E.final)|gen( “if ” S.first“: ” ) |gen( “ if ” S.curr|gen( “goto ” S.begin) E v:=initial” S.last “goto” S.Last “ gototo final E.initinitial.place E.final := final.place實(shí)用文檔18 對(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 of x

38、 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 表示整型常量； OP的產(chǎn)生式?jīng)]有給出， 因?yàn)樗拖旅嬗懻摰膯?wèn)題無(wú)關(guān)）。ProgramStmtList

39、StmtListStmt StmtList | StmtStmtid := Exp; | read （ id ）; | write （ Exp ）;Expid | lit | Exp OP 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ǔ)

40、句表或語(yǔ)句入口點(diǎn)的引用變量集合，它們的值影響在該程序點(diǎn)后的輸出。（2）uses_out ：在本語(yǔ)句表或語(yǔ)句出口點(diǎn)的引用變量集合，它們的值影響在該程序點(diǎn)后的輸出。（3）useless ：本語(yǔ)句表或語(yǔ)句中出現(xiàn)的無(wú)用賦值變量集合。答： Exp的屬性 uses 表示它引用的變量集合。 Program 的 useless 和 no_initial 分別表示程序的無(wú)用賦值變量集 合和未置初值變量集合。Program StmtList StmtList.uses_out:= ;Program.useless := StmtList.useless; Program.no_initial := StmtLis

41、t.uses_in;StmtList Stmt StmtList 1 StmtList 1.uses_out := StmtList.uses_out;Stmt.uses_out := StmtList1.uses_in;StmtList.uses_in := Stmt.uses_in實(shí)用文檔1.uselessStmt.useless;StmtList.useless := StmtListStmtList StmtStmt.uses_out := StmlList.uses_out;StmlList.uses_in := Stmt.uses_in;StmtList.useless := St

42、mt.uselessStmt id := Exp; 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.uses else Stmt.uses_outStmt read ( id ); Stmt.useless:= if id .lexeme Stmt.uses_out then else id .lexeme; Stmt.uses_in := Stmt.us

43、es_out id .lexemeStmtwrite ( Exp );Stmt.useless := , Stmt.uses_in := Stmt.uses_out Exp.usesExpidExp.uses:= id .lexemeExplitExp.uses:=Exp Exp 1 OP 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 := 1 c := P * P if c 100

44、goto L1 B := P * P x := x + 1 B := B + x write x haltL1: B:= 10x := x + 2 B := B + x write B if B 100 goto L2 halt L2: x := x + 1 goto L1 答： 程序的流圖如下實(shí)用文檔22 試求出如下四元式程序中的循環(huán)并進(jìn)行循環(huán)優(yōu)化 .I := 1 read J, KL: 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)中沒(méi)有不變運(yùn)算，故不做此項(xiàng)優(yōu)化( 2)

45、強(qiáng)度削弱： B2中 A和 B都是 I 的歸納變量。優(yōu)化結(jié)果顯示在圖 9.4(2) 中。實(shí)用文檔3)刪除歸納變量：變換循環(huán)控制條件，刪除歸納變量I 后的流圖顯示在圖 9.4(3) 中23 考慮下面的三地址語(yǔ)句序列： b := 1b := 2if w = x goto L2e := bgoto L2L1: goto L3L2: c := 3b := 4c := 6L3: if y = z goto L4goto L5實(shí)用文檔L4: g := g + 1h := 8goto L1L5: h := 9（1）在該代碼中用水平的橫線將代碼分成基本塊，并給每個(gè)基本塊一個(gè)序號(hào)（2）畫(huà)出該代碼的控制流圖，每個(gè)基

46、本塊就用（ 1）的序號(hào)表示。（3）若有循環(huán)的話，列出構(gòu)成每個(gè)循環(huán)的結(jié)點(diǎn)。1）b := 1b := 2if w = x goto L2（1）（2）e := b goto L22）L1: goto L3（3）L2:c := 3b := 4c := 6（4）L3:if y = z goto L45）goto L56）L4:g := g + 1h := 8goto L17）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）

47、各基本塊出口的活躍變量集 V_OUTB；（4）各基本塊中變量定值點(diǎn)的 du 鏈。I := 1J := 0L1: J := J + Iread Iif I 100 goto L2 write J haltL2 : I := I * I答： 本題程序的程序流圖如圖 9.6（1） 所示。實(shí)用文檔1)計(jì)算各基本塊的到達(dá) - 定值集 INB 。公式為：INB = OUTP PPBOUTB = GENB ( INB - KILLB ) GENB 和 KILLB 由程序流圖直接求出，顯示在表9.6(1) 中。表 9.6(1)基本塊GENB位向量KILLB位向量B1 d 1, d 2 11000000 d 3

48、, d 4, d6 00110100B2 d 3, d 4 00110000 d 1, d 2, d6 11000100B3 d 6 00000100 d 1, d 4 10010000B4 00000000 00000000求各基本塊到達(dá) - 定值的初值及各遍的執(zhí)行結(jié)果顯示在表 9.6(2) 中。表 9.6(2)基本塊初值第一遍后第二遍后第三遍后NBOUTBINBOUTBINBOUTBINBOUTBB10000000011000000000000001100000000000000110000000000000011000000B20000000000110000110001000011000011100100001100001110010000110000B30000000000000100001100000010010000110000001001000011000000100100B400000000000000