编译原理作业集-第七章

1、西安理工大学计算机科学与工程学院，张发存编写西安理工大学计算机科学与工程学院，张发存编写2020-6-9，19:50:31- -西安理工大学计算机科学与工程学院，张发存编写西安理工大学计算机科学与工程学院，张发存编写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.试编写翻译模式，用来实现do-while语句的回填算法8.答案：do-while语句的三地址代码结构如下：从do-while语句的三地址代码结构可以知道，开始，要记录下L.code的开始地址，以填写E.truelist。生成E.code之前，要记录下E.code的开始地址，用它填写L.nex

5、tlist。为此，在规则相应处添加标记非终结符，以完成相应的语义动作。翻译模式如下：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，问此程序将做些什么？其中MAX

7、INT为目标机器允许的最大整数。(2)试构造一个翻译pascal的for语句为三地址代码的语法制导定义。9.(1)显示如下六个整数：MAXINT-5MAXINT-4MAXINT-3MAXINT-2MAXINT-1MAXINT(2)为简单起见，for语句的三地址代码如下：t1:=initialt2:=finalift1t2gotoS.nextv:=t1stmt.codeS.begin:ifvt2gotoS.nextv:=succ(v)stmt.codegotoS.begin语法制导定义如下：产生式动作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的类型表达式。答案：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修改该翻译方案，使之能够处理：语句有值。赋值语句的值是赋值号右边的表达式的值。条件语句或当语句的值是语句体的值，语句表的值是表中最后一个语句的值。(2)布尔表达式。加上逻辑算符and,or和not,还有关系算符的产生式，然后给出适当的翻译规则，计算出这些表达式的类型。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为关系运算符，包括=,=12.文法GP及其产生式如下：PD;EDD;D|id:TTlistofT|char|integerEf（L）|Literal|num|idLE,L|E这个文法产生由字面常量组成的表。符号的解释和文法711）相同，增加类型List，它表示类型为T的元素构成的表。写一个翻译模式，以确定表达式（E）和表（L）的类型（注：表中每个元素的类型是一样的）。答案：D-id:Taddtype(id.entry,T.type)T-charT.type:=charT-i