编译原理期末考试试卷及答案(共11页).doc
《编译原理期末考试试卷及答案(共11页).doc》由会员分享,可在线阅读,更多相关《编译原理期末考试试卷及答案(共11页).doc(11页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、精选优质文档-倾情为你奉上期末考试试卷 (A)卷一、填空题(每小题2分,共20分)1、字母表,用* 表示上所有有穷长的串集合,*称为的 。2、设z=abc,则z的固有头是 。3、如何由语言基本符号组成程序中各个语法成分(包括程序)的一组规则叫 。4、设a,b, 上的正规式(a|b)(a|b) 相应的正规集为 5、NFA的映象f是从状态字映射到状态子集,f为 值函数。6、LR分析是按规范句型的 为可归约串。7、结点的 属性值由该结点的兄弟结点和父结点的属性值计算。8、如果分析树中一结点的属性b依赖于属性c,那么这个结点的属性b的语义规则的计算必须在定义属性c的语义规则的计算 。9、对于栈式符号表
2、,引入一个显示嵌套层次关系表- 表,该表总是指向当前正在处理的最内层的过程的子符号表在栈符号表中的起始位置。10、任一有向边序列n1 n2,n2 n3,nk-1 nk为从结点n1到结点nk的一条通路。如果n1=nk,则称该通路为 。二、单项选择(每小题2分,共14分)1、乔姆斯基把文法分成4种类型,即0型、1型、2型和3型。其中3型文法也称为( )。 A上下无关文法 B.正规文法 C上下文有关文法 D.无限制文法2、生成非0开头的正偶数集的文法是( )。 A Z:=ABC B. Z:=ABC C:=0|2|4|6|8 C:=0|2|4|6|8 B:=BA|B0| B:=BA|B0|0 A:=1
3、|2|3|9 A:=1|2|3|9 C. Z:=ABC|2|4|6|8 D. Z:=ABC|2|4|6|8 C:=0|2|4|6|8 C:=0|2|4|6|8 B:=BA|B0|0 B:=BA|B0| A:=1|2|3|9 A:=1|2|3|93、简单优先分析法从左到右扫描输入串,当栈顶出现( )时进归约。A.素短语 B.直接短语 C.句柄 D.最左素短语4、同心集合并有可能产生新的( )冲突。 A.归约 B.移进移进 C.移进归约 D.归约归约5、在编译中,动态存储分配的含义是( )。A在运行阶段对源程序中的量进行存储分配B. 在编译阶段对源程序中的量进行存储分配C. 在说明阶段对源程序中的
4、量进行存储分配D. 以上都不正确6、活动记录中的连接数据不包含( )。 A.老SP B.返回地址 C.全局DISPLAY地址 D形式单元7、有一语法制导翻译如下:SbAb printer(“1”)A(B printer(“2”)Aa printer(“3”)BAa) printer(“4”)若输入序列为b(aa)a)a)b,且采用自下而上的分析法,则输出序列为( )。A B C D三、写出条件语句 IF a0 THEN x:=x+1 ELSE x:=4*( x- 1) 的四元式序列(6分)四、设有基本块 (8分)B1: B:=3 D:=A+C E:=A*C F:=D+E G:=B*F H:=A
5、+C I:=A*C J:=H+I K:=B*5 L:=K+J M:=L (1) 画出DAG图; (2) 假设只有L在基本块后被引用,请写出优化后的四元序列。 五、将下图DFA最小化,并写出最小化后DFA的正规式。(10分)cbba631dbadbca5bb742六、对下面的文法进行改写,并判断改写后是否是LL(1)文法。(15分)S Aa|bA SBB ab七、已知文法:SS;G|GGG(T)|HHa|(S)TT+S|S求句型#a;(T+S);H;(S)#短语、句柄、素短语、最左素短语(12分)八、【注意】计算机061/062班和计教061/062请做第1、2题,计算机063(海外班)请做第3
6、题,做错题得0分。(15分)【计算机061/062班和计教061/062班做】1、给出文法GS的LR(1)项目集规范族中I0项目集的全体项目。(5分)GS为: (1) E E+T (2) E T (3) T T*F (4) T F (5) F (E) (6) F a2、文法GM及其LR分析表如下,请给出对串dbba#的分析过程。(10分)GM: 1) M VbA 2) V d 3) V 4) A a 5) A Aba 6) A ACTIONGOTObda#MAV0r3 S3121acc2S43r24r6S5r665r4r46S7r17S88r5r5【计算机063海外班做】3、判断下列各题所示是
7、否为LR类文法,若是请说明是LR(0),SLR(1),LALR(1)或LR(1)的哪一种,并构造相应分析表。(15分) SaAdeBdaBreAr Aa Ba答案:一、填空题(每空2分,共20分)1、 闭包 2、 , a, ab 3、 语法 4、 aa,bb,ab,ba 5、 多 6、 句柄 7、 继承 8、 之后 9、 DISPLAY 10、 环路 二、单项选择(每小题2分,共14分)题号1234567答案BDCDADB三、写出条件语句 IF a0 THEN x:=x+1 ELSE x:=4*( x- 1) 的四元式序列(6分)解: (j,a ,0 , ) 评分标准:标号对给1分, (j,
8、, , ) 四元式格式对给1分, (+,x ,1 ,T1) 每2条四元式序列对给1分。 (:= ,T1, , T2 ) (j , , , ) (- ,x, 1,T3) (*,4,T3, T4 ) (:= ,T4 , , x)四、 设有基本块 (8分)(1) 画出DAG图; (2) 假设只有L在基本块后被引用,请写出优化后的四元序列。评分标准:DAG图正确给4分,代码每条1分。解:(1)对于B1其DAG图:L,Mn1n9n3n4n2n7n6n5n8153KBAC+G*+F,JD,HE,I+*若只有L活跃,则代码为D:=A+C E:=A*C F:=D+E L:=F+15五、将下图DFA最小化,并写
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 期末考试 试卷 答案 11
限制150内