编译原理试卷

1S11110，100+ABCDEFG华东师范大学试卷及答案（A）学生姓名：_____________学号：___________________学生系别：_____________专业：______________年级___________班级_____________课程名称：编译原理课程性质：专业必修一、问答题1.设G=（VN，VT，P，S）是上下文无关文法，产生式集合P中任意一个产生式应具有什么样的形式？若G是正则文法呢？（5％）答：一般形式为v→，vVN，(VN∪VT)*。若G是正则文法，则一般形式为A→aB或A→a，A、BVN，aVT（或A→Ba，A→a）。2.何谓二义性文法？试举一例说明。（5％）答：若文法G的一个句子对应有两棵或两棵以上不同的推导树，则称该句子是二义性的。产生二义性句子的文法称为二义性文法，否则该文法是无二义性的。例子：给定文法G[R]：R→R*|RR|a|b考察句子ab*，它有两棵不同的推导树，如下所示：RRRaR*bRR*RRaab3.试正确消除下述传递图的弧，使其接收的语言不变。（10％）总分任课教师签名杨宗源1-－2答：1CSDEGF-0100,111111+++14.试将下述程序段翻译成三地址形式的中间代码表示。（8％）答：三地址代码如下：100:t:=a+b101:iftcgoto105102:goto103103:ifa=bgoto105104:goto0105:ifa5goto107106:goto100107:ifb10goto109108:goto100109:a:=a+1110:b:=b+1111:goto105112:5.适合采用静态存储分配的程序设计语言应有哪些限制？（5％）答：①数据实体所需空间在编译时能确定②运行时每个数据对象只能有一个实例③数组的上下界是常量④过程调用不允许递归⑤不能动态建立数据实体6.在一个基本块内通常可实现哪些优化？（5％）while(a+bcORa=b)while(a5ANDb10){a=a+1;b=b+1;}3答：①合并已知量②删除公共子表达式③删除无用代码④复写传播二、试判定下述文法G［S］是否是LR（1）文法？为什么？（12％）S→AAA→AaA→a答：1）因为对文法G[S]存在的句子aaa，有两棵不同的推导树，如图4.5所示。aAAaaASaAAaaAS图4.5两棵不同的推导树所以该文法是二义性文法，G[S]不是LR(1)文法。2）可构造文法G[S]的状态集，考虑增广文法G[S’]，如表4.29所示。表4.29文法G[S’]的LR(1)状态集状态T项目集输入符号下一状态0[S’→·S⊥,]S1[S→·AA,⊥]A2[A→·Aa,a]A2[A→·a,a]a31[S’→S·⊥,]⊥Accept2[S→A·A,⊥]A[A→A·a,a]a4[A→·Aa,a/⊥]A[A→·a,a/⊥]a43[A→a·,a]a#34[A→Aa·,a]a#2[A→a·,a/⊥]a/⊥#3到此不用继续计算，因为状态T4是不适定状态，对输入符a出现了“归约—归约”冲突，因此文法G[S]不是LR(1)文法。三、Pascal语言中，循环语句forV:=initialtofinaldostmt与下述代码序列有相同的含义：4若不考虑后续语句问题，要求：(1)写出循环语句三地址形式的中间代码表示。（5%）(2)编写符合上述规定的翻译方案。（15%）答：(1)三地址的中间代码如下：100:106:110:t1:=initial.val111:t2:=final.val112:ift1t2goto123113:V:=t1114:120:V:=succV121:ifV≠t2goto114123:goto0(2)将for语句的产生式拆因子为：for1forV:=initialtofinalSfor1dostmt各产生式的语义动作子程序为：for1forV:=initialtofinal{CheckType(V.type,initial.type,final.type)；t1:=newtemp;emit(t1,:=,initial.val);t2:=newtemp;emit(t2,:=,final.val);for1.nextlist=makelist(nextcode);emit(ift1t2goto0)；emit(V,:=,t1)；for1.var:=V.var；t1:=initial;t2:=final;ift1t2thenBeginV:=t1;L1:stmtV:=succ(V);ifVt2thenGotoL1End;initialfinalstmt5for1.final:=t2;for1.con=nextcode;}Sfor1dostmt{backpatch(stmt.nextlist,nextcode);emit(for1.var,:=,SUCC,for1.var)；emit(iffor1.var≠for1.finalgotofor1.con)；t:=makelist(nextcode);emit(goto0);S.nextlist=merge(for1.next,t)；}四、对如下类ALGOL语言的程序框架（已列出所有的定义与说明），若采用以过程为单位，二级存储区的存储分配方法。试分别写出当程序流到达Li(1i4)时，整个运行栈的内容。要求用图的形式详细列出活动记录中各个项的分布情况。（20％）答:programmain()procedureP(k:int)beginx1,y1:real;arrayA[1..10]ofint;i1,i2:int;….beginx2:intarrayB[1..i1]ofint;L2:….endbeginx3:int;arrayC[1..i2]ofint;L3:…end;L4:end；//PbeginarrayX[1..i1]ofint;…L1:CALLP(10);…end.//main6数组X数组X的信息向量begin的stpmain过程的stp形实参数通讯区调用点的机器状态OldSPmain过程的区头地址表SP栈增长方向图1执行到L1时运行栈的情形数组B数组A数组B的信息向量x2b2的stp2i1,i2数组A的信息向量x1,y1b1的stp1P过程的stp形实参数通讯区调用点的机器状态OldSPP过程的区头地址表数组X数组X的信息向量begin的stpmain过程的stp形实参数通讯区调用点的机器状态OldSPmain过程的区头地址表SP栈增长方向图2执行到L2时运行栈的情形7数组C数组A数组C的信息向量x3b3的stp3i1,i2数组A的信息向量x1,y1b1的stp1P过程的stp形实参数通讯区调用点的机器状态OldSPP过程的区头地址表数组X数组X的信息向量begin的stpmain过程的stp形实参数通讯区调用点的机器状态OldSPmain过程的区头地址表SP栈增长方向图3执行到L3时运行栈的情形8数组Ai1,i2数组A的信息向量x1,y1b1的stp1P过程的stp形实参数通讯区调用点的机器状态老的SPP过程的区头地址表数组X数组X的信息向量begin的stpmain过程的stp形实参数通讯区调用点的机器状态老的SPmain过程的区头地址表SP栈增长方向图4执行到L4时运行栈的情形五、设有如下基本块：（10％）T0:=2;T1:=3/T0;T2:=S-C;T3:=S+C;R:=T0/T3;H:=R;T4:=3/T1;T5:=S+C;T6:=T4/T5;H:=T6*T2;a)试利用DAG对进行基本块内的优化，并重写基本块。b)若只有R,H在基本块的出口是活跃的，试给出优化后的基本块。答：1）基本块的DAG如图7.2所示。97,*0016,/5,+234,-R,T6T0,T421.5SCHT3,T5T2T1图7.2基本块的DAG重写的基本块为：T0:=2;T4:=2;T1:=1.5;T2:=S-C;T3:=S+C;T5:=T3;R:=2/T3;T6:=R;H:=T6*T2;2）因为只有R、H是活跃的，所以优化后的基本块为：S1:=S-C;S2:=S+C;R:=2/S2;H:=R*S1;