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

平時(shí)作業(yè)對(duì)于以下語(yǔ)言分別寫出它們正規(guī)表示式。

(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(k≥0）。則S→S10|S21，|S1|=2k(k>0），|S2|=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ī)表示式，即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ī)表示式，即S2為：((00|11)|(01|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ī)以下：對(duì)應(yīng)正規(guī)表示式：(1(01*0)1|0)*給出接收以下在字母表{0,1}上語(yǔ)言DFA。

(1)

全部以00結(jié)束符號(hào)串集合。

(2)

全部具備3個(gè)0符號(hào)串集合。答：(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)正則表示式:1*01*01*01*DFA

M=({0，1}，{q0，q1，q2，q3}，q0，{q3}，δ)其中δ定義以下:δ（q0，0）=q1

δ（q0，1）=q0δ（q1，0）=q2

δ（q1，1）=q1δ（q2，0）=q3

δ（q2，1）=q2δ（q3，1）=q3

3下面是用正規(guī)式表示變量申明： (int|float)id(,id)*;請(qǐng)改用上下文無(wú)關(guān)文法表示，也就是寫一個(gè)上下文無(wú)關(guān)文法，它和該正規(guī)式等價(jià)。答：DTL; Tint|float LL,id|id試分析下面給出if-then-else語(yǔ)句文法，它提出原本是為了矯正dangling-else(懸而未決-else)文法二義性：

stmt→ifexprthenstmt

|matched-stmt

matched-stmt→ifexprthenmatched-stmtelsestmt

|other

試說(shuō)明此文法依然是二義性。答：考慮句子ifethenifethenotherelseifethenotherelseother它具備以下所表示兩種分析樹stmtexprtheneifstmtifmatched-stmtexprthenmatched-stmteotherifeslestmtmatched-stmtexprthenmatched-stmteothereslestmtmatched-stmtotherstmtmatched-stmtifexprthenmatched-stmteifeslestmteslestmtmatched-stmtexprthenestmtotherexprthenmatched-stmteotherifmatched-stmtother則上面給出if-then-else文法仍是二義性。證實(shí)下面文法是SLR(1)文法，并結(jié)構(gòu)其SLR分析表。

E→E+T|T

T→TF|F

F→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)以下:I0={E'→·E,E→·E+T,E→·T,T→·TF,T→·F,F→·F*,

F→·a,F→·b}I1={E'→E·,E→E·+T}I2={E→T·,T→T·F,F→·F*,F→·a,F→·b}I3={T→F·,F→F·*}I4={F→a·}I5={F→b·}I6={E→E+·T,T→·TF,T→·F,F→·F*,F→·a,F→·b}I7={T→TF·,F→F·*}I8={F→F*·}I9={E→E+T·,T→T·F,F→·F*,F→·a,F→·b}求FOLLOW集：

FOLLOW(E)={＋,＄}

FOLLOW(T)={＋,＄,a,b}FOLLOW(F)={＋,＄,a,b,*}結(jié)構(gòu)SLR分析表以下：顯然，此分析表無(wú)多重定義入口，所以此文法是SLR文法。為下面文法結(jié)構(gòu)LALR(1)分析表

S→E

E→E+T|T

T→(E)|a答：其拓廣文法G'：(0)S'→S(1)S→E(2)E→E+T(3)E→T(4)T→(E)(5)T→a結(jié)構(gòu)其LR(1)項(xiàng)目集規(guī)范族和goto函數(shù)(識(shí)別活前綴DFA)以下:I0={[S’→·S,$],[S→·E,$],[E→·E+T,$/+],[E→·T,$/+],

[T→·(E),$/+],[T→·a,$/+]}I1={[S’→S·,$]}I2={[S→E·,$],[E→E·+T,$/+]}I3={[E→T·,$/+]}I4={[T→(·E),$/+],[E→·E+T,)/+],[E→·T,)/+],

[T→·(E),)/+],[T→·a,)/+]}I5={[T→a·,$/+]}I6={[E→E+·T,$/+],[T→·(E),$/+],[T→·a,$/+]}I7={[T→(E·),$/+],[E→E·+T,)/+]}I8={[E→T·,)/+]}I9={[T→(·E),)/+},[E→·E+T,)/+],[E→·T,)/+],[T→·(E),)/+],[T→·a,)/+]}I10={[T→a·,)/+]}I11={[E→E+T·,$/+]}I12={[T→(E)·,$/+]}I13={[E→E+·T,)/+],[T→·(E),)/+],[T→·a,)/+]}I14={[T→(E·),)/+],[E→E·+T,)/+]}I15={[E→E+T·,)/+]}I16={[T→(E)·,)/+]}合并同心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={[S’→S·,$]}I2={[S→E·,$],[E→E·+T,$/+]}I3,8={[E→T·,$/+/)]}I4,9={[T→(·E),$/+/)],[E→·E+T,)/+],[E→·T,)/+],

[T→·(E),)/+],[T→·a,)/+]}I5,10={[T→a·,$/+/)]}I6,13={[E→E+·T,$/+/)],[T→·(E),$/+/)],[T→·a,$/+/)]}I7,14={[T→(E·),$/+/)],[E→E·+T,)/+]}I11,15={[E→E+T·,$/+/)]}I12,16={[T→(E)·,$/+/)]}LALR分析表以下：（1）經(jīng)過(guò)結(jié)構(gòu)識(shí)別活前綴DFA和結(jié)構(gòu)分析表，來(lái)證實(shí)文法EE+id|id是SLR(1)文法。答：先給出接收該文法活前綴DFA以下：EE·EE·E+idE·idI0EE·EE·+idI1Eid·I2Eid+EE+·idI3EE+id·I4id再結(jié)構(gòu)SLR分析表以下：狀態(tài)狀態(tài)動(dòng)作轉(zhuǎn)移id+$E0s211s3acc2r2r23s44r1r1表中沒(méi)有多重定義條目，所以該文法是SLR(1)。（2）下面左右兩個(gè)文法都和（1）文法等價(jià) EE+Mid|id EME+id|id M M請(qǐng)指出其中有幾個(gè)文法不是LR(1)文法，并給出它們不是LR(1)文法理由。答：只有文法 EME+id|id M不是LR(1)文法。因?yàn)閷?duì)于句子id+id+…+id來(lái)說(shuō)，分析器在面臨第一個(gè)id時(shí)需要做空歸約次數(shù)和句子中+id個(gè)數(shù)一樣多，而此時(shí)句子中+id個(gè)數(shù)是未知。8 依照自上而下語(yǔ)法分析方法，結(jié)構(gòu)下面文法LL（1）分析表。 DTL Tint|real LidR R,idR|答：先計(jì)算FIRST和FOLLOW

FIRST(D)=FIRST(T)={int,real}

FIRST(L)={id}

FIRST(R)={,,ε}

FOLLOW(D)=FOLLOW(L)={$}

FOLLOW(T)={id}

FOLLOW(R)={$}LL(1)分析表以下：intrealid,$DD->TLD->TLTT->intT->realLL->idRRR->,idRR->ε9下面文法產(chǎn)生表示式是對(duì)整型和實(shí)型常數(shù)應(yīng)用算符+形成。當(dāng)兩個(gè)整數(shù)相加時(shí)，結(jié)果仍為整數(shù)，不然就是實(shí)數(shù)。

E→E+T|T

T→num.num|num

（a）給出一個(gè)語(yǔ)法制導(dǎo)定義以確定每個(gè)子表示式類型。

（b）擴(kuò)充（a）中語(yǔ)法制導(dǎo)定義把表示式翻譯成前綴形式，而且決定類型。使用一元算符inttoreal把整型值轉(zhuǎn)換成相等實(shí)型值，以使得前綴形式中+兩個(gè)操作對(duì)象是同類型。答：(a):產(chǎn)生式語(yǔ)義規(guī)則EE1+TIF(E1.type=integer)and(T.type=integer)THENE.type:=integerELSEE.type:=realETE.type:=T.typeTnum.numT.type:=realTnumT.type:=integer(b):產(chǎn)生式語(yǔ)義規(guī)則EE1+TIF(E1.type=integer)and(T.type=integer)THENBEGINE.type:=integerPrint(‘+’,E1.val,T.val)ENDELSEBEGINE.type:=realIFE1.type=integerTHENBeginE1.type:=realE1.val:=inttoreal(E1.val)EndIFT.type:=integerTHENBeginT.type:=realT.val:=inttoreal(T.val)EndPrint(‘+’,E1.val,T.val)ENDETE.type:=T.typeE.val:=T.valTnum.numT.type:=realT.val:=num.num.lexvalTnumT.type:=integerT.val:=num.lexval10假設(shè)說(shuō)明是由以下文法產(chǎn)生：

D→idL

L→,idL|:T

T→integer|real

（a）建立一個(gè)翻譯模式，把每一個(gè)標(biāo)識(shí)符類型加入到符號(hào)表中。

（b）從（a）中翻譯模式結(jié)構(gòu)一個(gè)預(yù)翻譯程序。答：(a)：產(chǎn)生式翻譯模式DidL{D.Type:=L.Type}{addtype(id.entry,D.type)}L,idL1{L.Type:=L1.Type}{addtype(id.entry,L.type)}L:T{L.type:=T.type}Tinteger{T.type:=integer}Treal{T.type:=real}(b)： ProcedureD; begin Iflookahead=idthenBeginMatch(id);D.type=L;addtype(id.entry,D.type)endelseerror endFunctionL:DataType;BeginIflookahead=’,’thenBeginMatch(‘,’);Iflookahead=idthenbeginmatch(id);L.Type=L;addtype(id.entry,L.type);return(L.type)endElseerrorEndElseiflookahead=’:’thenBeginMatch(‘:’);L.Type=T;return(L.Type)endelseerrorEnd FunctionT:DataType;BeginIflookahead=integerthenBeginMatch(integer);return(integer)endelseIflookahead=realthenBeginMatch(real);return(real)endelseerrorend11 為下面算術(shù)表示式文法寫一個(gè)語(yǔ)法制導(dǎo)翻譯方案，它將每個(gè)子表示式E符號(hào)（即值大于零還是小于零）統(tǒng)計(jì)在屬性E.sign中（屬性值分別用POS或NEG表示）。你能夠假定全部整數(shù)都不為零，這么就不用擔(dān)心零符號(hào)。EE*E|+E|E|unsigned_integer答： EE1*E2{ifE1.sign=E2.signthenE.sign:=POSelseE.sign:=NEG}E+E1{E.sign:=E1.sign}EE1{ifE1.sign=POSthenE.sign:=NEGelseE.sign:=POS}Eunsigned_integer{E.sign:=POS}12 為下面文法寫一個(gè)語(yǔ)法制導(dǎo)定義，用S綜合屬性val給出下面文法中S產(chǎn)生二進(jìn)制數(shù)值。比如，輸入101.101時(shí)，S.val:=5.625。（不得修改文法。） SL.R|L LLB|B RBR|B B0|1答： SL.R S.val:=L.val+R.valSL S.val:=L.val LL1B L.val:=L1.val2+B.valLB L.val:=B.val RBR1 R.val:=(R1.val+B.val)/2RB R.val:=B.val/2 B0 B.val:=0B1 B.val:=113試問(wèn)下面程序?qū)⒂性鯓虞敵觯糠謩e假定：

（a）傳值調(diào)用（call-by-value）；

（b）引用調(diào)用（call-by-reference）；

（c）復(fù)制恢復(fù)（copy-restore）；

（d）傳名調(diào)用（call-by-name）。

programmain(input,output）；

procedurep（x,y,z）；

begin

y：＝y(tǒng)＋1；

z：＝z＋x；

end；

begin

a：＝2；

b：＝3；

p(a＋b,a,a)；

printa

end.答：1)．傳地址：所謂傳地址是指把實(shí)在參數(shù)地址傳遞給對(duì)應(yīng)形式參數(shù)。在過(guò)程段中每個(gè)形式參數(shù)都有一對(duì)應(yīng)單元，稱為形式單元。形式單元將用來(lái)存放對(duì)應(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)自己對(duì)應(yīng)形式單元中，過(guò)程體對(duì)形式參數(shù)任何引用1或賦值都被處理成對(duì)形式單元間接訪問(wèn)。當(dāng)調(diào)用段工作完成返回時(shí)，形式單元(它們都是指示器)所指實(shí)在參數(shù)單元就持有所指望值。2)．傳結(jié)果：和“傳地址”相同(但不等價(jià))另一個(gè)參數(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)．傳值：所謂傳值，是一個(gè)簡(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)．傳名：所謂傳名，是一個(gè)特殊形——實(shí)參數(shù)結(jié)合方式。解釋“傳名”參數(shù)意義：過(guò)程調(diào)用作用相當(dāng)于把被調(diào)用段過(guò)程體抄到調(diào)用出現(xiàn)地方，但把其中任一出現(xiàn)形式參數(shù)都替換成對(duì)應(yīng)實(shí)在參數(shù)(文字替換)。它與采取“傳地址”或“傳值”方式所產(chǎn)生結(jié)果均不相同。(a)2；(b)8；(c)7； (d)9。14對(duì)以下Pascal程序畫出過(guò)程c第二次被激活時(shí)運(yùn)行棧，控制鏈和訪問(wèn)鏈。說(shuō)明在c中怎樣訪問(wèn)變量x。programenv；

procedurea；

varx:integer；

procedureb；

procedurec；

beginx:=2；bend；{procedurec}

begincend；{procedureb}

beginbend；{procedurea}

beginaend.{main}

答：envenvcontrollinkaccesslinkcontrollinkaccesslinkaacontrollinkcontrollinkaccesslinkxaccesslinkxbbcontrolcontrollinkaccesslinkaccesslinkcccontrolcontrollinkaccesslinkaccesslinkbbcontrolcontrollinkaccesslinkaccesslinkccaccesslinkcontrollinkaccesslinkcontrollink說(shuō)明：c中沿著存取鏈向前走兩步，到過(guò)程a活動(dòng)統(tǒng)計(jì)中就能夠訪問(wèn)到變量x。15下面給出一個(gè)C語(yǔ)言程序及其在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)shorti,j;floatf,e;{shorti1,j1;floatf1,e1;printf("Addressofi,j,f,e=%o,%o,%o,%o\n",&i,&j,&f,&e);printf("Addressofi1,j1,f1,e1=%o,%o,%o,%o\n",&i1,&j1,&f1,&e1);printf("Sizesofshort,int,long,float,double=%d,%d,%d,%d,%d\n",sizeof(short),sizeof(int),sizeof(long),sizeof(float),sizeof(double));}main(){shorti,j;floatf,e;func(i,j,f,e);}運(yùn)行結(jié)果是：Addressofi,j,f,e=,,,Addressofi1,j1,f1,e1=,,,Sizesofshort,int,long,float,double=2,4,4,4,8，請(qǐng)問(wèn)為何？答：C語(yǔ)言編譯器是不做實(shí)在參數(shù)和形式參數(shù)個(gè)數(shù)和類型是否一致檢驗(yàn)，由程序員自己確保它們一致性。不過(guò)對(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編譯器作約定是，當(dāng)整型或?qū)嵭蛿?shù)據(jù)作為實(shí)在參數(shù)時(shí)，分別將它們提升到long和double類型數(shù)據(jù)傳遞到被調(diào)用函數(shù)。被調(diào)用函數(shù)依照形式參數(shù)所申明類型，決定是否要將實(shí)在參數(shù)向低級(jí)別類型轉(zhuǎn)換。低地址放高位高地址放低位shortlong圖5.2長(zhǎng)整型和短整型 在本例中，long低地址放高位高地址放低位shortlong圖5.2長(zhǎng)整型和短整型注意，對(duì)于SUN工作站來(lái)說(shuō)，低地址存放整型數(shù)據(jù)高位。floatfloatdoublee圖5.3雙精度型和浮點(diǎn)型 對(duì)于實(shí)型來(lái)說(shuō)。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)容都是為了增加精度用，見(jiàn)圖5.3。ee，8個(gè)字節(jié)在main函數(shù)中參數(shù)壓棧時(shí)觀點(diǎn)在func函數(shù)中存取形式參數(shù)時(shí)觀點(diǎn)4個(gè)字節(jié)，起始地址4個(gè)字節(jié)，起始地址2個(gè)字節(jié)，起始地址2個(gè)字節(jié)，起始地址f，8個(gè)字節(jié)j，4個(gè)字節(jié)i，4個(gè)字節(jié)棧增加方向圖5.4參數(shù)在棧中情況 這么在main函數(shù)中依次將參數(shù)提升后反序進(jìn)棧，大小分別為8,8,4,4。在func函數(shù)中，按形式參數(shù)類型，把這些存放單元一部分看成是形式參數(shù)存放單元，見(jiàn)圖5.4。從這個(gè)圖不難了解為何形式參數(shù)地址間隔和它們類型大小不一致了。 注意，現(xiàn)在編譯器將需要進(jìn)行類型轉(zhuǎn)換形式參數(shù)（類型是char、short、float等）另行分配在局部數(shù)據(jù)區(qū)，當(dāng)控制進(jìn)入被調(diào)用過(guò)程時(shí)，首先將調(diào)用過(guò)程壓棧需要進(jìn)行類型轉(zhuǎn)換實(shí)在參數(shù)取出，把它們存入所分配局部數(shù)據(jù)區(qū)存放單元，并同時(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大小一樣）。 Typepromote(Typety) { switch(ty->op){ caseENUM: returninttype; caseINT: if(ty->size<inttype->size) returninttype; break; caseUNSIGNED: if(ty->size<inttype->size) returninttype; break; caseFLOAT: if(ty->size<doubletype->size) returndoubletype; } returnty; }16試把以下C語(yǔ)言程序可執(zhí)行語(yǔ)句翻譯為

(a)一棵語(yǔ)法樹，

(b)后綴式，

(c)三地址代碼。main(){inti;inta[10];while(i<=10)a[i]=0;while}while答：(a).一棵語(yǔ)法樹賦值表示式布爾表示式賦值表示式布爾表示式表示式表示式表示式數(shù)組元素表示式<=表示式數(shù)組元素表示式<=下標(biāo)表示式110a0下標(biāo)表示式110a011(b)后綴式為：i10<=ai[]0=while從理論上能夠說(shuō)while(i<=10)a[i]=0;后綴式如上面表示。但若這么表示，在執(zhí)行while操作時(shí)，賦值語(yǔ)句已經(jīng)執(zhí)行，這顯然與語(yǔ)義不符，所以改為： i10<=<下一個(gè)語(yǔ)句開(kāi)始地址>BMai[]0=<本語(yǔ)句地址>BRL其中BM操作為當(dāng)表示式為假時(shí)轉(zhuǎn)向<下一個(gè)語(yǔ)句開(kāi)始地址>，BRL是一個(gè)一目運(yùn)算，無(wú)條件轉(zhuǎn)向<本語(yǔ)句始址>。(c)三地址代碼序列為：100ifi<=10got102101goto106102t1:=4*i103t2:=a104t2[t1]:=0105goto10010617 Pascal語(yǔ)言中，語(yǔ)句：forv：＝initialtofinaldostmt 與以下代碼序列有相同含義begint1:=initial;t2:=final;ift1<=t2thenbeginv:=t1;stmtwhilev<>t2dobeginv：=succ（v)；stmtendendend(a)試考慮下述Pascal程序programforloop(input,output);vari,initial,final:integer;beginread(initial,final);fori:=initialtofinaldowrite(i)end對(duì)于initial=MAXINT-5和final=MAXINT，問(wèn)此程序?qū)⒆鲂┦裁?？其中MAXINT為目標(biāo)機(jī)器允許最大整數(shù)。(b)試結(jié)構(gòu)一個(gè)翻譯pascalfor語(yǔ)句為三地址代碼語(yǔ)法制導(dǎo)定義。答：（a）程序?qū)@示以下六個(gè)整數(shù)：MAXINT-5MAXINT-4MAXINT-3MAXINT-2MAXINT-1MAXINT（b）為簡(jiǎn)單起見(jiàn)，for語(yǔ)句三地址代碼以下：t1:=initialt2:=finalift1>t2gotoS.nextv:=t1stmt.codeS.begin:ifv>t2gotoS.nextv:=succ(v)stmt.codegotoS.begin語(yǔ)法制導(dǎo)定義以下：產(chǎn)生式動(dòng)作S→forEdoS1S.begin:=newlabelS.first:=newtempS.last:=newtempS.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“:”)||gen(“if”S.curr“>”S.Last“goto”S.next)||S1.code||gen(S.curr:=succ(S.curr))||gen(“goto”S.begin)E→v:=initialtofinalE.init:=initial.placeE.final:=final.place18 對(duì)于下面C語(yǔ)言文件s.c f1(intx) { longx; x=1; } f2(intx) { { longx; x=1; } }某編譯器編譯時(shí)報(bào)錯(cuò)以下： s.c:Infunction‘f1’: s.c:3:warning:declarationof‘x’shadowsaparameter請(qǐng)回答，對(duì)函數(shù)f2為何沒(méi)有類似警告錯(cuò)誤。答： 對(duì)于函數(shù)f1，局部變量x申明作用域是整個(gè)函數(shù)體，造成在函數(shù)體中不可能訪問(wèn)形式參數(shù)x。因?yàn)檫@是一個(gè)正當(dāng)C語(yǔ)言函數(shù)，所以編譯器給出警告錯(cuò)誤。對(duì)于函數(shù)f2，因?yàn)榫植孔兞縳作用域只是函數(shù)體一部分，不會(huì)出現(xiàn)上述問(wèn)題，因而編譯器不報(bào)錯(cuò)。19 考慮一個(gè)簡(jiǎn)單語(yǔ)言，其中全部變量都是整型（不需要顯式申明），而且僅包含賦值語(yǔ)句、讀語(yǔ)句和寫語(yǔ)句。下面產(chǎn)生式定義了該語(yǔ)言語(yǔ)法（其中l(wèi)it表示整型常量；OP產(chǎn)生式?jīng)]有給出，因?yàn)樗拖旅嬗懻搯?wèn)題無(wú)關(guān)）。 Program StmtList StmtList StmtStmtList|Stmt Stmt id:=Exp;|read(id);|write(Exp); Exp id|lit|ExpOPExp 我們把不影響write語(yǔ)句輸出值賦值（包含經(jīng)過(guò)read語(yǔ)句來(lái)賦值）稱為無(wú)用賦值，寫一個(gè)語(yǔ)法指導(dǎo)定義，它確定一個(gè)程序中出現(xiàn)過(guò)賦予無(wú)用值變量集合（不需要知道無(wú)用賦值位置）和沒(méi)有置初值變量集合（不影響write語(yǔ)句輸出值未置初值變量不在考慮之中）。 非終止符StmtList和Stmt用下面3個(gè)屬性（你依照需要來(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表示它引用變量集合。Programuseless和no_initial分別表示程序無(wú)用賦值變量集合和未置初值變量集合。 Program StmtList StmtList.uses_out:=; Program.useless:=StmtList.useless; Program.no_initial:=StmtList.uses_in; StmtList StmtStmtList1 StmtList1.uses_out:=StmtList.uses_out; Stmt.uses_out:=StmtList1.uses_in; StmtList.uses_in:=Stmt.uses_in StmtList.useless:=StmtList1.uselessStmt.useless; StmtList Stmt Stmt.uses_out:=StmlList.uses_out; StmlList.uses_in:=Stmt.uses_in; StmtList.useless:=Stmt.useless Stmt id:=Exp; Stmt.useless:=ifid.lexemeStmt.uses_outthenelse{id.lexeme}; Stmt.uses_in:=ifid.lexemeStmt.uses_out then(Stmt.uses_out–{id.lexeme})Exp.useselseStmt.uses_out Stmt read(id); Stmt.useless:=ifid.lexemeStmt.uses_outthenelse{id.lexeme}; Stmt.uses_in:=Stmt.uses_out–{id.lexeme} Stmt write(Exp); Stmt.useless:=,Stmt.uses_in:=Stmt.uses_outExp.uses Exp id Exp.uses:={id.lexeme} Exp lit Exp.uses:= Exp Exp1OPExp2 Exp.uses:=Exp1.usesExp2.uses20為以下C程序生成目標(biāo)代碼。

main()

{

inti;

inta[10];

while(i<=10)

a[i]=0;

}答：21試結(jié)構(gòu)下面程序流圖，并找出其中全部回邊及循環(huán)。

readP

x:=1

c:=P*P

ifc<100gotoL1

B:=P*P

x:=x+1

B:=B+x

writex

halt

L1:B:=10

x:=x+2

B:=B+x

writeB

ifB<100gotoL2

halt

L2:x:=x+1

gotoL1答：程序流圖以下

22試求出以下四元式程序中循環(huán)并進(jìn)行循環(huán)優(yōu)化.I:=1readJ,KL:A:=K*IB:=J*IC:=A*BwriteCI:=I+1ifI<100gotoLhalt答：把本題三地址代碼劃分成基本塊并畫出其程序流圖顯示在圖9.4(1)中，其中有三個(gè)基本塊B1，B2，B3，有一條回邊B2->B2，對(duì)應(yīng)循環(huán)是{B2}。（1）代碼外提：因?yàn)檠h(huán)中沒(méi)有不變運(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考慮下面三地址語(yǔ)句序列： b:=1 b:=2 ifw<=xgotoL2 e:=b gotoL2 L1: gotoL3 L2: c:=3 b:=4 c:=6 L3: ify<=zgotoL4 gotoL5 L4: g:=g+1 h:=8 gotoL1 L5: h:=9（1）在該代碼中用水平橫線將代碼分成基本塊，并給每個(gè)基本塊一個(gè)序號(hào)。 （2）畫出該代碼控制流圖，每個(gè)基本塊就用（1）序號(hào)表示。 （3）若有循環(huán)話，列出組成每個(gè)循環(huán)結(jié)點(diǎn)。答：（1） （2）114237865 b:=1 b:=2 ifw<=xgotoL2 （1） e:=b gotoL2 （2） L1: gotoL3 （3） L2: c:=3 b:=4 c:=6 （4） L3: ify<=zgotoL4 （5） gotoL5 （6） L4: g:=g+1 h:=8 gotoL1 （7） L5: h:=9 （8）結(jié)點(diǎn)5、7和3組成一個(gè)循環(huán)，其中5是入口結(jié)點(diǎn)。24對(duì)下面程序片段作出其程序流圖并計(jì)算：

（1）各基本塊抵達(dá)_定值集IN[B]；

（2）各基本塊中各變量引用點(diǎn)ud鏈；

（3）各基本塊出口活躍變量集V_OUT[B]；

（4）各基本塊中變量定值點(diǎn)du鏈。

I:=1

J:=0

L1:J:=J+I

readI

ifI<100gotoL2

writeJ

halt

L2:I:=I*I答：本題程序程序流圖如圖9.6(1)所表示。（1）計(jì)算各基本塊抵達(dá)-定值集IN[B]。公式為：

IN[B]

=∪OUT[P]

P∈P[B]

OUT[B]=GEN[B]∪(IN[B]-KILL[B])

GEN[B]和KILL[B]由程序流圖直接求出，顯示在表9.6(1)中。表9.6(1)基本塊GEN[B]位向量KILL[B]位向量B1{d1,d2}11000000{d3,d4,d6}00110100B2{d3,d4}00110000{d1,d2,d6}11000100B3{d6}00000100{d1,d4}10010000B4{}00000000{}00000000

求各基本塊抵達(dá)-定值初值及各遍執(zhí)行結(jié)果顯示在表9.6(2)中。表9.6(2)基本塊初值第一遍后第二遍后第三遍后IN[B]OUT[B]IN[B]OUT[B]IN[B]OUT[B]IN[B]OUT[B]B10000000011000000000000001100000000000000110000000000000011000000B20000000000110000110001000011000011100100001100001110010000110000B30000000000000100001100000010010000110000001001000011000000100100B40000000000000000001100000011000000110000001100000011000000110000（2）求各基本塊中各變量引用點(diǎn)ud鏈：

假設(shè)在程序中某點(diǎn)u引用了變量a，則把能抵達(dá)ua全部定值點(diǎn)，稱為a在引用點(diǎn)u引用-定值鏈（簡(jiǎn)稱ud鏈）。能夠利用抵達(dá)-定值信息來(lái)計(jì)算各個(gè)變量在任何引用點(diǎn)ud鏈。

由圖9.6(1)程序流圖可知，I引用點(diǎn)是d3、d5和d6，J引用點(diǎn)是d3和d8。

B2中I和J引用點(diǎn)d3前面沒(méi)有對(duì)I和J定值點(diǎn)，其ud鏈在IN[B2]={d1,d2,d3,d6}中，所以I在引用點(diǎn)d3ud鏈?zhǔn)莧d1,d6}；J在引用點(diǎn)d3ud鏈?zhǔn)莧d2,d3}。

在B2中I引用點(diǎn)d5前面有I定值點(diǎn)d4，且在d4定值后抵達(dá)d5，所以I在引用點(diǎn)d5ud鏈?zhǔn)莧d4}。

B3中I引用點(diǎn)d6前面沒(méi)有I定值點(diǎn)，其ud鏈?zhǔn)荌N[B3]中I全部定值點(diǎn)，所以是{d4}。

B4中J引用點(diǎn)d8前面沒(méi)有對(duì)J定值點(diǎn)，其ud鏈?zhǔn)荌N[B4]中J全部定值點(diǎn)。已知IN[B4]={