編譯原理作業(yè)集-第七章

1、西安理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，張發(fā)存編寫西安理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，張發(fā)存編寫2020-6-9，19:50:31- -西安理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，張發(fā)存編寫西安理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，張發(fā)存編寫2020-6-9，l9:50:3l-l3-BEGINT.truelist,T,falselist:=F;WHILE(lookahead=and)DOBEGINmatch(and);M.quad:=nextquad;F.truelist,F.falselist:=F;backpatch(T.truelist,F.truelist);T.truelist:=F.truelist;T.f

2、alselist:=merge(T.falselist,F.falselist)END;return(T.truelist,T.falselist)END;PROCEDUREF;VARF.truelist,F.falselist,E.truelsit,E.falselist:link;BEGINCASE(lookahead)OFnot:BEGINmatch(not);E.truelist,E.falselist:=F;F.truelist:=E.falselist;F.falselist:=E.truelistEND;(:BEGINmatch();E.truelist,E.falselist)

3、:=E;match();F.truelist:=E.truelist;F.falselist:=E.falselistEND;id:BEGINmatch(id);match(relop);match(id);F.truelist:=makelist(nextquad);F.falselist:=makelist(nextquad+1);emit(ifidl.placerelopid2.placegoto-);emit(goto-)END；true:BEGINmatch(true);F.truelist:=makelist(nextquad);F.falselist:=null;emit(got

4、o-)END;false:BEGINmatch(false);F.truelist:=makelist(nextquad);F.falselist:=null;emit(goto-)ENDotherwise:errorENDofCASEreturn(F.truelist,F.falselist)END;8.試編寫翻譯模式，用來實(shí)現(xiàn)do-while語句的回填算法8.答案：do-while語句的三地址代碼結(jié)構(gòu)如下：從do-while語句的三地址代碼結(jié)構(gòu)可以知道，開始，要記錄下L.code的開始地址，以填寫E.truelist。生成E.code之前，要記錄下E.code的開始地址，用它填寫L.nex

5、tlist。為此，在規(guī)則相應(yīng)處添加標(biāo)記非終結(jié)符，以完成相應(yīng)的語義動(dòng)作。翻譯模式如下：S-doMLwhileNEbackpatch(E.tru&list,M.quad):backpatch(L.n&xtliat,N.quad);TOC o 1-5 h zS.nest1iatr=E.falaeliat片:PSbackpatchF、quad);L.nest1iatr=8.nextlist;L-*SL.n&srt1iati=S.n&stlistM-*eQU4d:=nextaudN-*e(N,quad:=ft&xtquad)PePFauad:=nextauad)9.Pascal語言中，語句forv：=i

6、nitialtofinaldostmt與下列代碼序列有相同含義begint1:=initial;t2:=final;ift1=t2thenbeginv:=t1;stmtwhilevt2dobeginv：=succ(v)；stmtendendend(1)試考慮下述Pascal程序programforloop(input,output);vari,initial,final:integer;beginread(initial,final);fori:=initialtofinaldowrite(i)end對于initial=MAXINT-5和final=MAXINT，問此程序?qū)⒆鲂┦裁?？其中MAX

7、INT為目標(biāo)機(jī)器允許的最大整數(shù)。(2)試構(gòu)造一個(gè)翻譯pascal的for語句為三地址代碼的語法制導(dǎo)定義。9.(1)顯示如下六個(gè)整數(shù)：MAXINT-5MAXINT-4MAXINT-3MAXINT-2MAXINT-1MAXINT(2)為簡單起見，for語句的三地址代碼如下：t1:=initialt2:=finalift1t2gotoS.nextv:=t1stmt.codeS.begin:ifvt2gotoS.nextv:=succ(v)stmt.codegotoS.begin語法制導(dǎo)定義如下：產(chǎn)生式動(dòng)作SforEdoSIS.begin:=newlabelS.first:=newtempS.last

8、:=newtempS.curr:=newtempS.code:=gen(S.first“:=E.init)llgen(S.last“:=E.final)llgen(“if”S.first“S.last“gotoS.next)llgen(S.curr“:=”S.first)llgen(S.begin“:)llgen(“if”S.curr“S.Last“gotoS.next)llSl.codellgen(S.curr:=succ(S.curr)llgen(“gotoS.begin)Ev:=initialtofinalE.init:=initial.placeE.final:=final.place

9、10.假如有下面的Pascal說明TYPEatype=ARRAY0.9,-10.10OFinteger;cell=RECORDa,b:integerEND;pcell=fcell;foo=ARRAY1.100OFcell;FUNCTIONbar(r:integer;y:cell):pcell;BEGINEND;寫出atype,cell,pcell,foo和bar的類型表達(dá)式。答案：atype:ARRAY(0.9,ARRAY(-10.10,integer);cell:RECORD(axinteger)x(bxinteger);pcell:POINTER(cell);或:POINTER(RECOR

10、D(axinteger)x(bxinteger);foo:ARRAY(1.100,cell);或:ARRAY(1.100,RECORD(axinteger)x(bxinteger);bar:integercellpcell;或：integercellfPOINTER(RECORD(axinteger)x(binteger);已知語句序列的類型檢查翻譯方案：Sid:=Eifid.type=E.typethenS.type:=voidelseS.type:=type_errorSfifEthenS1ifE.type=booleanthenS.type:=S1.typeelseS.type:=typ

11、e_errorSfwhileEdoSIifE.type=booleanthenS.type:=S1.typeelseS.type:=type_errorSfS1:S2ifS1.type=voidandS2.type=voidthenS.type:=voidelseS.type:=type_error修改該翻譯方案，使之能夠處理：語句有值。賦值語句的值是賦值號右邊的表達(dá)式的值。條件語句或當(dāng)語句的值是語句體的值，語句表的值是表中最后一個(gè)語句的值。(2)布爾表達(dá)式。加上邏輯算符and,or和not,還有關(guān)系算符的產(chǎn)生式，然后給出適當(dāng)?shù)姆g規(guī)則，計(jì)算出這些表達(dá)式的類型。11.答案：(1)S-id:=E

12、S.type:=IFid.type=E.typeTHENE.typeELSEtype_error;S.val:=IFid.type=E.typeTHENE.valELSEval_errorS-IFETHENS1S.type:=IFE.type=booleanTHENS1.typeELSEtype_errorS.val:=IFE.type=booleanTHENS1.valELSEval_errorS-WHILEEDOS1S.type:=IFE.type=booleanTHENS1.typeELSEtype_errorS.val:=IFE.type=booleanTHENS1.valELSEva

13、l_errorS-S1;S2S.type:=S2.type;S.val:=S2.val(2)E-E1ANDE2E.type:=IF(E1.type=boolean)AND(E2.type=boolean)THENbooleanELSEtype_errorE-E1ORE2E.type:=IF(E1.type=boolean)AND(E2.type=boolean)THENbooleanELSEtype_errorE-NOTE1E.type:=IF(E1.type=boolean)THENbooleanELSEtype_errorE-E1opE2E.type:=IF（E1.type=E2.type）THENbooleanELSEtype_error注：op為關(guān)系運(yùn)算符，包括=,=12.文法GP及其產(chǎn)生式如下：PD;EDD;D|id:TTlistofT|char|integerEf（L）|Literal|num|idLE,L|E這個(gè)文法產(chǎn)生由字面常量組成的表。符號的解釋和文法711）相同，增加類型List，它表示類型為T的元素構(gòu)成的表。寫一個(gè)翻譯模式，以確定表達(dá)式（E）和表（L）的類型（注：表中每個(gè)元素的類型是一樣的）。答案：D-id:Taddtype(id.entry,T.type)T-charT.type:=charT-i