2014-2015学年1学期12级《编译原理》期末考试试题(A卷)

1、北京邮电大学世纪学院20142015学年第1学期期末考试试题（a卷）考试科目编译原理姓名考试专业/班级软工专业/12级1-3班学号考试形式闭卷考试时间120分钟考 试 注息 事 项一、学生参加考试须带学生证，术带学生证者不允许参加考试。学生必须按照监考教师指定座位就坐。二、书本、参考资料、书包等与考试无关的东西一律放到监考教师指定的位置。三、学生不得另行携带、 使用稿纸，要遵守北京邮酎大学世纪学院考场规则 ，有考场违纪或作弊行为者，按相应规定严肃处理。四、学生不允许携带手机进入考场。注意：所有答案一律写在答题纸上，写在试卷上无效。一、单项选择题（共15小题，每小题2分，共30分）1. 一个上下

2、文无关文法g包括四个组成部分：一组终结符，一组非终结符, 一个开始符号，以及一组（）。a.字符串b.产生式c.开始符号d.文法2. 一个句型中称为句柄的是该句型的最左（）a.非终结符号b.短语c.句子d.直接短语3 .自动机识别的语言是（）a. 0型语言b. 1型语言c. 2型语言d. 3型语言4 .编译程序各阶段工作都涉及（）a. 词法分析b.表格管理c.语法分析d.语义分析5代码生成阶段的主要任务是 （）a 把高级语言翻译成汇编语言b.把高级语言翻译成机器语言c 把中间代码变换成依赖具体机器的目标代码d 把汇编语言翻译成机器语言6作为编译程序的源语言，不能是（ ）a. 高级语言b.c 语言

3、c.低级语言d.pascal 语言7词法分析器的输入是（）a. 单词符号串b.源程序c.语法单位d. 目标程序8.给定文法a-ba | cc,下面符号用中不是该文法的句子的是（）cc bcbc bcbcc bccbcc bbbcca.b. c. d. 9.若b是非终结符，则a-a.abb为（）项目a.移进b.待约c.接受d 规约10文法 g：sf b|a|(t)t- t,s|s 则 firstvt(t)结果是()。a. b, a ,(b. b, a ,)c.b,a,j d.b, a,), 11 常用的中间代码形式不含( )a 三元式b.四元式c 逆波兰式d 语法树12.正规式 m 1 和 m

4、2 等价是指( ) 。a m1 和 m2 的状态数相等b m1 和 m2 的有向边条数相等c m1 和 m2 所识别的语言集相等d m1 和 m2 状态数和有向边条数相等13.文法g: s-xsx|y所识别的语言是()。a xyxb (xyx)*c. xnyxn (n0)d x*yx*14.如果文法g是无二义的，则它的任何句子a ()。a 最左推导和最右推导对应的语法树必定相同b.最左推导和最右推导对应的语法树可能不同c 最左推导和最右推导必定相同d 可能存在两个不同的最左推导，但它们对应的语法树相同15词法分析器的输出结果是( ) 。a. 单词的种别编码b.单词在符号表中的位置c.单词的种别

5、编码和自身值d.单词自身值二、填空题（本大题共10 空，每空 2 分，共 20 分）1对于文法ge ：e-t|e+tt-f|t*fffpaf|pp-（e）|i,句型 t+t*f+i 的句柄是 ，最左素短语是。2编译器常用的语法分析方法有和两种。3算符优先分析法每次都是对 进行归约。4 编译程序的工作过程主要分为如下几个阶段：词法分析、语法分析、 、 、目标代码生成。5 .假设有文法gs: s-sa对该文法消除左递归后得到的文法为（注：新 的符号用s表示）。6 .对于文法g,仅含终结符号的句型称为 。三、简答题（共6题，每题 5 分，共 30分）1 .已知文法gz: z-azb |ab,写出l

6、（g （z）的全部元素。2 .已知文法 gs为s - asb|sb|b,试证明文法 gs为二义文法。3设有文法e- e+t | tt-t*f | f一 （e） i i求下列表达式的最左推导和语法树 1） 1） 3+4*5+6 2） 3* （4+5）4.将如下正规文法转换为自动机。s-0a|1ba -1s|1b-0s|05已知文法gs ：s-a i （t）tftbs | s（1）写出句型（tbs）ba）的语法树（ 2）写出该句型短语、简单短语、句柄、素短语6.有文法gs ：0） s -bb1） b -ab|b构造此文法的 lr（ 0）项目集规范簇，并写出识别活前缀的dfa四、综合应用（共2 题，共 20 分）1 构造下列正规式 1（0i1）*101 相应的 dfa（ 1）由正规表达式构造nfa（ 2）由转换系统nfa 构造确定的有穷自动机dfa（ 3） dfa 的最小化2已知文法gs ：0）