44B52008-A编译答案.doc

课程名称 编译方法 考试日期 2009.1.9 考生姓名 学号 专业或类别 考生注意事项：1、本试卷共 9 页，请查看试卷中是否有缺页。 2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。一、 填空题( 每小题 1 分，共 10 分 ) clcnsy1 LL(1)文法一定不含 左 递归。2 设GS是一文法，如果符号串x VT*是从识别符号S推导出来的，即有S=*x,则称x是文法GS的 句型 。3 编译过程中词法分析器所完成的任务是从源程序中识别 单词 。4 表达式y:=-a+c*(-b+d)的后缀表达式是 a uminus c b uminus d + * +。5 局部优化是局限于一个 基本块 范围内的一种优化。6 如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是 二义性 。7 所有文法符号的属性都是综合属性的属性文法称为 S属性文法 。8 在栈式存储分配里，栈中相邻的活动记录在活动树中的关系是 。9 有文法GZ：ZaAbAAb| aAb |e该文法产生的语言为 anbmbn(n=1,m=0) 。10. 动态存储分配时，可以采用的分配方法是 堆和栈 。二、 选择题(每小题 1 分，共 10 分)1 一个语言的文法是 。A唯一的B不唯一的C个数有限的2 若一个文法是递归的，则它所产生语言的句子个数 。A必定是无穷的 B是有限个的 C根据具体情况而定 3 给定文法AbA| cc ，下面的符号串中，为该文法句子的是 。 cc bcbc bcbcc bccbcc bbbcc A BCD4 这样一些语言，它们能被确定的有穷自动机识别，但不能用正规表达式表示。A存在B不存在C无法判定5 LR语法分析栈中存放的状态是识别 的DFA状态。A前缀B可归前缀C项目D句柄6 PASCAL程序中有名为p的过程，其声明的局部变量的地址分配在 。A调用p的过程的活动记录中Bp的活动记录中C主过程的活动记录中 D公共数据区7 设r = (a | b | c)(x | y)则L(r)中元素为 。A4个B6个C9个D18个8 下面文法对应的正规式是 。SAx | ByAy | AyBe | BxAyy* x|xyByy* x|x*yCyy*x|yDy*x|x*y9 有这样一个符号表=aa，b，cc，下列选项中哪一个不是该符号表上的符号串 。AaabaaBabcccCccaabDccbaab10 LR(k)方法 。A都是无二义的B都是二义的 C一部分是二义的三、 简答题(共 44 分)1 （本小题10分）设字母表=a，b，给出正规式(a | ba)*（1） 构造与之等价的NFA。(2分)（2） 将该NFA确定化。(6分)（3） 将得到的DFA最小化。(2分)ab0,1,61,2,5,631,2,5,61,2,5,6331,4,5,6-1,4,5,61,2,5,63 2 （本小题8分）给出语句：if ab or cd then i:=i+1 else i:=i-1的四元式序列。(1) (j，a，b，5)(2) (j，3) (3) (j，c，d，5)(4) (j，8) (5) (，i，1，T1)(6) (:=，T1，i)(7) (j，10) (8) (-，i，1，T2)(9) (:=，T2，i)(10)3 （本小题10分）设有如下的类型声明:type link=row； np=row； nqr=row；row=record a:integer; b:integer end;var f(a，b:char):row； next:link； p：np； q: nqr； r: nqr；要求： 给出f的类型表达式。(4分) 画出f的dag 。(3分) 分别在名字等价、结构等价的前提下next、p、q、r的类型相同吗？(3分)4 （本小题8分）若在栈式存储分配中采用display表解决对非局部变量的引用问题，试给出下列程序执行到语句“b：=10；”时运行栈及Display表的示意图。program main；var x, y;(1)procedure p; (2)var a; procedure q; (3)var b; begin(q) b : =10; end (q); procedure s; (3)var c,d; procedure r; (4)var e, f; begin (r) call q; end (r); begin (s) call r; end (s); begin (p) call s; end (p); begin (main) call p; end (main). 5（本小题8分）考虑下面程序program test(input , output);Var i , j：integer；procedure call(x , y：integer)；Beginy：y2；x：x - y；y：x；End；Begini：10；j：2；call(i , j)；Print(j)End试问：若参数传递方式分别采取传地址，传值和传名时，程序执行后哪两种方式输出的结果是相同的？答：传值传地址传值-结果传名四、 综合题(共 36 分)1. （本小题12分）已知文法G A 为： AaABe | a BBb | d 试消除文法G A 的左公共因子和左递归。(3分) 构造修改后文法的预测分析表。(6分)First(A)=a;First(A)=a,First(B)=dFirst(B)=b,Follow(A)=$Follow(A)=Follow(A) V First(B)=d,$Follow(B)=eFollow(B)=Follow(B)=e 利用预测分析表给出输入串aade$的分析过程。(3分)AaAAaABe|BdBBbB|abed$AAaAAAaABeAaccBBdBBBbBB已匹配栈输入动作A$aade$aA$aade$输出 AaAaA$ade$匹配aaaABe$ade$输出AaABeaaABe$de$匹配aaaBe$de$输出AaadB e$de$输出BdBaadB e$e$匹配daade$e$输出Baade$匹配e2（本小题16分）设有文法GS: S LaR | R L bR | c R L 试构造该文法的LR（1）分析表并判断GS是否为LR（1）文法。(11分) 当一个文法是LR（1）而不是LALR（1）时，那么LR（1）项目集的同心集合并后会出现哪几种冲突，请说明理由。(5分)SSSRSSaR|RbR|cFirst(S)= First(S)=First(R)=bFirst(S)=a,Follow(S)=Follow(S)=$Follow(R)=Follow(R) V (First(S)-) V Follow(S) =a,$Follow(S)=Follow(S)=Follow(S) =$状态项目集后继符号后继状态S0SSSRS,$RbR,$Rc,$SRbcS1S2S3S4S1#SSS10S2SRS,$SaR,$S,$Sa#SS5S6S10S3RbR,$RbR,$Rc,$RbcS8S3S4S4Rc,$#RcS10S5SRS,$# SRSS10S6SaR,$RbR,$Rc,$RbcS9S3S4S8 RbR,$#R bRS10S9SaR$#SaRS10压缩过程可