搜索
第1页共5页北京邮电大学世纪学院2014——2015学年第1学期期末考试试题（A卷）考试科目编译原理姓名考试专业/班级软工专业/12级1-3班学号考试形式闭卷考试时间120分钟考试注意事项一、学生参加考试须带学生证，未带学生证者不允许参加考试。学生必须按照监考教师指定座位就坐。二、书本、参考资料、书包等与考试无关的东西一律放到监考教师指定的位置。三、学生不得另行携带、使用稿纸，要遵守《北京邮电大学世纪学院考场规则》，有考场违纪或作弊行为者，按相应规定严肃处理。四、学生不允许携带手机进入考场。注意：所有答案一律写在答题纸上，写在试卷上无效。一、单项选择题(共15小题，每小题2分，共30分)1.一个上下文无关文法G包括四个组成部分：一组终结符，一组非终结符，一个开始符号，以及一组（）。A．字符串B．产生式C．开始符号D．文法2．一个句型中称为句柄的是该句型的最左（）A．非终结符号B．短语C．句子D．直接短语3．自动机识别的语言是（）A．0型语言B．1型语言C．2型语言D．3型语言4．编译程序各阶段工作都涉及（）第2页共5页A.词法分析B.表格管理C.语法分析D.语义分析5．代码生成阶段的主要任务是（）A．把高级语言翻译成汇编语言B．把高级语言翻译成机器语言C．把中间代码变换成依赖具体机器的目标代码D．把汇编语言翻译成机器语言6．作为编译程序的源语言，不能是()A.高级语言B.C语言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．规约第3页共5页10．文法G：S→b|∧|(T)T→T,S|S则FIRSTVT(T)结果是（）。A.{b,∧,(}B.{b,∧,)}C.{b,∧,(,，}D.{b,∧,),，}11．常用的中间代码形式不含（）A．三元式B．四元式C．逆波兰式D．语法树12.正规式M1和M2等价是指（）。A．M1和M2的状态数相等B．M1和M2的有向边条数相等C．M1和M2所识别的语言集相等D．M1和M2状态数和有向边条数相等13.文法G：S→xSx|y所识别的语言是（）。A．xyxB．(xyx)*C．xnyxn(n≥0)D．x*yx*14．如果文法G是无二义的，则它的任何句子α（）。A．最左推导和最右推导对应的语法树必定相同B．最左推导和最右推导对应的语法树可能不同C．最左推导和最右推导必定相同D．可能存在两个不同的最左推导，但它们对应的语法树相同15．词法分析器的输出结果是（）。A.单词的种别编码B.单词在符号表中的位置第4页共5页C.单词的种别编码和自身值D.单词自身值二、填空题（本大题共10空，每空2分，共20分）1．对于文法G[E]：E→T|E+TT→F|T*FF→P^F|PP→(E)|i，句型T+T*F+i的句柄是______，最左素短语是_______。2．编译器常用的语法分析方法有_______和_______两种。3．算符优先分析法每次都是对____________进行归约。4．编译程序的工作过程主要分为如下几个阶段：词法分析、语法分析、________、___________、____________、目标代码生成。5．假设有文法G[S]：S-Sa|b，对该文法消除左递归后得到的文法为（注：新的符号用S′表示）_________。6．对于文法G，仅含终结符号的句型称为_________。三、简答题（共6题，每题5分，共30分）1．已知文法G[Z]：Z→aZb|ab，写出L（G（Z））的全部元素。2．已知文法G[S]为S→aSb|Sb|b，试证明文法G[S]为二义文法。3．设有文法E→E+T|TT→T*F|FF→(E)|i求下列表达式的最左推导和语法树（1）3+4*5+6（2）3*（4+5）4.将如下正规文法转换为自动机。S→0A|1BA→1S|1第5页共5页B→0S|05．已知文法G[S]：S→a|(T)T→TbS|S（1）写出句型((TbS)ba)的语法树（2）写出该句型短语、简单短语、句柄、素短语6.有文法G[S]：0)S→BB1)B→aB|b构造此文法的LR（0）项目集规范簇，并写出识别活前缀的DFA四、综合应用（共2题，共20分）1．构造下列正规式1(0|1)*101相应的DFA（1）由正规表达式构造NFA（2）由转换系统NFA构造确定的有穷自动机DFA（3）DFA的最小化2．已知文法G[S]：0)S→bN1)N→BaN2)N→ε3)B→ab（1）证明文法G为LL(1)文法？（2）构造该文法的预测分析表。（3）写出句子babaaba的分析过程。