44b52008-a编译答案

《44b52008-a编译答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、课程名称编译方法考试日期2009.1.9考生姓名学号专业或类别考生注意事项：1、本试卷共9页，请查看试卷中是否有缺页。2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。一、填空题(每小题1分，共10分)clcnsy1．LL(1)文法一定不含左递归。2．设G[S]是一文法，如果符号串x∈VT*是从识别符号S推导出来的，即有S=>*x,则称x是文法G[S]的句型。3．编译过程中词法分析器所完成的任务是从源程序中识别单词。4．表达式y:=-a+c*(-b+d)的后缀表达式是auminuscbuminusd+*+。5．局部优化是局限于一个基本块范围内的一种优化。6．如

2、果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义性。7．所有文法符号的属性都是综合属性的属性文法称为S属性文法。8．在栈式存储分配里，栈中相邻的活动记录在活动树中的关系是。9．有文法G[Z]：Z→aAbA→Ab

3、aAb

4、e该文法产生的语言为anbmbn(n>=1,m>=0)。10.动态存储分配时，可以采用的分配方法是堆和栈。二、选择题(每小题1分，共10分)1．一个语言的文法是。A．唯一的B．不唯一的C．个数有限的2．若一个文法是递归的，则它所产生语言的句子个数。A．必定是无穷的B．是有限个的C．根据具体情况而定3．给定文法A→bA

5、cc，下面的符号串

6、中，为该文法句子的是。①cc②bcbc③bcbcc④bccbcc⑤bbbccA．①⑤B．①③④⑤C．①④⑤D．①②③④⑤第8页共8页1．这样一些语言，它们能被确定的有穷自动机识别，但不能用正规表达式表示。A．存在B．不存在C．无法判定2．LR语法分析栈中存放的状态是识别的DFA状态。A．前缀B．可归前缀C．项目D．句柄3．PASCAL程序中有名为p的过程，其声明的局部变量的地址分配在。A．调用p的过程的活动记录中B．p的活动记录中C．主过程的活动记录中D．公共数据区4．设r=(a

7、b

8、c)(x

9、y)则L(r)中元素为。A．4个B．6个C．9个D．18个5．下面文法对

10、应的正规式是。S→Ax

11、ByA→y

12、AyB→e

13、BxA．yy*x

14、xyB．yy*x

15、x*yC．yy*x

16、yD．y*x

17、x*y6．有这样一个符号表∑={aa，b，cc}，下列选项中哪一个不是该符号表上的符号串。A．aabaaB．abcccC．ccaabD．ccbaab7．LR(k)方法。A．都是无二义的B．都是二义的C．一部分是二义的二、简答题(共44分)1．（本小题10分）设字母表∑={a，b}，给出正规式(a

18、ba)*（1）构造与之等价的NFA。(2分)（2）将该NFA确定化。(6分)（3）将得到的DFA最小化。(2分)ab[0,1,6][1,2,5,6][3][

19、1,2,5,6][1,2,5,6][3][3][1,4,5,6]-[1,4,5,6][1,2,5,6][3]第8页共8页1．（本小题8分）给出语句：ifa

20、=recorda:integer;b:integerend;varf(a，b:char):↑row；next:link；p：np；q:nqr；r:nqr；第8页共8页要求：①给出f的类型表达式。(4分)②画出f的dag。(3分)③分别在名字等价、结构等价的前提下next、p、q、r的类型相同吗？(3分)2．（本小题8分）若在栈式存储分配中采用display表解决对非局部变量的引用问题，试给出下列程序执行到语句“b：=10；”时运行栈及Display表的示意图。programmain；varx,y;(1)procedurep;(2)vara;procedureq;(3

21、)varb;begin(q)b:=10;end(q);procedures;(3)varc,d;procedurer;(4)vare,f;begin(r)callq;end(r);begin(s)callr;end(s);begin(p)calls;end(p);begin(main)callp;第8页共8页end(main).5．（本小题8分）考虑下面程序　　programtest(input,output);　　Vari,j：integer；procedurecall(x,y：integer)；　　　Begin　　　　y：＝y2；　　　　x：＝x-y；y：＝