上海大学编译原理试卷2013-2014春(附答案)

试卷序号：第1页(共8页)第2页(共8页)得分阅卷人二、选择题（本大题共10小题，每小题1分，共10分）在每小题列出的备选项中只有一个是符合题目要求的，请将其代码填写在题中的空格内。错选、多选或未选均无分。1．以下优化技术除b外，都是针对循环优化进行的。a)强度削弱b)删除多余运算c)变换控制条件d)代码外提2．下列d工作不属于编译阶段的前端。a)语法分析b)词法分析c)中间代码生成d)目标代码生成3表达式(a+b)*c/d对应的逆波兰式是a。a)ab+c*d/b)abc+/*dc)ab*c+/dd)abc*/d+4．一个句型中称为句柄的是该句型中最左的d。a)非终结符b)句子c)短语d)直接短语5．以下c函数是PL/0编译程序中的词法分析器。a)termb)expressionc)getsymd)factor6．PL/0编译程序的语法分析采用的是b。a)LR分析法b)递归子程序法c)算符优先分析法d)预测分析法7．程序所需的数据空间在程序运行前就可确定，称为d方法。上海大学2013～2014学年春季学期试卷A课程名：编译原理课程号：08305013学分：5参考答案题号一（10）二(10)三(10)四(15)五(12)六(15)七(12)八(16)得分一、判断题（本大题共10小题，每小题1分，共10分）判断下列各题正误，正确者在括号内打“√”，错误者在括号内打“×”。1.对中间代码的优化不依赖于具体的计算机。（√）2.程序流图中的每条回边对应于一个循环。（√）3.自底向上语法分析时必须先消除文法中的左公共因子。（×）4.使用逆波兰式描述表达式时无须使用括号。（√）5.编译程序是对高级语言程序的解释执行。（×）6.符号表内容的一个重要作用是作为上下文语义合法性检查的依据。（√）7.状态中含有冲突的文法有可能是一个SLR(1)文法。（√）8.语义处理中“拉链”的作用是使“回填”更为有效。（√）9.算符优先分析法是一种自下而上的语法分析方法。（√）10.编译程序能找出源程序中所有错误。（×）成绩第3页(共8页)三、设计题（本大题共2小题，每小题5分，共10分）1．定义一个上下文无关文法G[S]，生成下述语言L：L={andmbn|n,m≥1}答G[A]：A→aAb|aBbB→dB|d2．证明下列文法G[A]是一个二义文法：A→B+B|BB→B*B|A|a答：∵对于句子a+a*a存在两个不同的最左推导：1:A=B+B=a+B=a+B*B=a+a*B=a+a*a2:A=B=B*B=A*B=B+B*B=a+B*B=a+a*B=a+a*a∴G[A]是一个二义文法四、设计题（本大题共3小题，每小题5分，共15分）设有正规式r=(a|ab)(a|b)*b1．构造一个NFAM，接受L(r)。SCAaa,bBbba2.把上述NFAM转化为等价的DFAM。SCAaBababab3．给出DFAM所对应的正规文法。G[S]：S→aAA→aB|bCB→aB|bCC→aB|bC|ε第4页(共8页)五、设计题（本大题共2小题，第1题7分，第2题5分，共12分）对下列基本块B应用DAG进行优化，设只有S、W在基本块后面还要继续引用。B:T1:=a+bT2:=3.14S:=T1*T2T3:=a+bT4:=2.56T5:=T2+T4W:=T5*T1S:=T5*T31．基本块B的DAG答：n1n4n2n5n8n6T1T11ST1,T3T25.70a3..14bn7T42.56n3T5W,S*+*2．优化后的基本块B’答：T1:=a+bT5:=5.70W:=T5*T1S:=W第5页(共8页)第6页(共8页)六、分析题（本大题共2小题，第1题5分，第2题10分，共15分）1．对下列属性文法中的语义处理功能作简略说明：E→id1ropid2{E.true:=nextstat;E.false:=nextstat+1;E.Codebegin:=nextstat;emit(‘if’id1.place‘rop’id2.place‘goto’–);emit(‘goto’-)}答：E.true：E的真出口链E.false：E的假出口链E.Codebegin:E的代码开始地址Nextstat：下一条代码地址emit：生成一条四元式2．在下划线处填写正确内容，完成下列源语句通过语法制导翻译后生成的四元式序列。源语句：while(s100)and((ab)or(a=b))dobegina:=a+1;if(ab)thens:=s+a;end;四元式序列：1)ifs100goto(3)2)goto(14)3)ifabgoto(7)4)goto(5)5)ifa=bgoto(7)6)goto(14)7)t1:=a+18)a:=t19)ifabgoto(11)10)goto(1)11)t2:=s+a12)s:=t213)goto(1)14)七、证明题（本大题共3小题，每题4分，共12分）设有文法G[S]：S→BAA→AB|Aa|aB→ba|bB1)证明G[S]是一个非LL(1)文法。答：∵A含左递归（以及A、B含公共左因子）∴G[S]非LL(1)文法。2)把G[S]等价改写为LL(1)文法G1[S]。答：G1[S]:S→BAA→aA’A’→BA’|aA’|εB→bB’B’→a|B3)证明G1[S]为LL(1)文法。答：对于S,A,B:仅有一个候选，选择唯一；第7页(共8页)第8页(共8页)2.对输入串n+r+n#给出分析过程：步骤状态符号输入串动作1．2.3.4.5.6.7.8.9.10.11.12.0#03#n02#T01#E015#E+0154#E+r0156#E+T01#E015#E+0153#E+n0156#E+T01#En+r+n#+r+n#+r+n#+r+n#r+n#+n#+n#+n#n####s3r3r2s5s4r4r1s5s3r3r1acc3．将文法G[S’]扩充为属性文法:(0)S’→E{}(1)E→E+T{print(“+”)}(2)E→T{}(3)T→n{print(“n”)}八、综合题（本大题共3小题，第1题6分，第2，3题各5分共16分）设有文法G[S’]:(0)S’→E(1)E→E+T(2)E→T(3)T→n(4)T→r1.证明G[S]是SLR(1)文法,构造G[S]的SLR(1)分析表。答：LR(0)项目集规范族：I0:S’→.EE→.E+TE→.TT→.nT→.rT→r(1)E→EI3:T→n.I4:T→r.I2:E→T.I6:E→E+T.I1:S’→E.E→E.+TI5:E→E+.TT→.nT→.rETnr+Trn∵状态I1含有移进-归约冲突∴G[S]是非LR(0)文法∵follow(S’)={#}∩{+}=∴G[S]是SLR(1)文法SLR(1)分析表：状态ACTIONGOTO+nr#ET0123456s3s4s5accr2r2r3r3r4r4s3s4r1r1126