山东科技大学编译原理试卷

山东科技大学编译原理试卷第1页共7页山东科技大学2015—2016学年第二学期《编译原理》考试试卷（A卷）班级姓名学号一、单项选择题(共15小题，每小题2分，共30分)1.一个上下文无关文法G包括四个组成部分：一组终结符，一组非终结符，一个开始符号，以及一组（B）。A．字符串B．产生式C．开始符号D．文法2．一个句型中称为句柄的是该句型的最左（D）A．非终结符号B．短语C．句子D．直接短语3．自动机识别的语言是（B）A．0型语言B．1型语言C．2型语言D．3型语言4．编译程序各阶段工作都涉及（B）A.词法分析B.表格管理题号一二三四总得分评卷人审核人得分山东科技大学编译原理试卷第2页共7页C.语法分析D.语义分析5．代码生成阶段的主要任务是（C）A．把高级语言翻译成汇编语言B．把高级语言翻译成机器语言C．把中间代码变换成依赖具体机器的目标代码D．把汇编语言翻译成机器语言6．作为编译程序的源语言，不能是(C)A.高级语言B.C语言C.低级语言D.Pascal语言7．词法分析器的输入是（B）A.单词符号串B.源程序C.语法单位D.目标程序8．给定文法A-bA︱cc,下面符号串中不是该文法的句子的是（B）①cc②bcbc③bcbcc④bccbcc⑤bbbccA．①⑤B.②③④C.①④⑤D.①②⑤9．若B是非终结符，则A-a.aBb为（B）项目A．移进B．待约C．接受D．规约10．文法G：S→b|∧|(T)山东科技大学编译原理试卷第3页共7页T→T,S|S则FIRSTVT(T)结果是（C）。A.{b,∧,(}B.{b,∧,)}C.{b,∧,(,，}D.{b,∧,),，}11．常用的中间代码形式不含（D）A．三元式B．四元式C．逆波兰式D．语法树12.正规式M1和M2等价是指（C）。A．M1和M2的状态数相等B．M1和M2的有向边条数相等C．M1和M2所识别的语言集相等D．M1和M2状态数和有向边条数相等13.文法G：S→xSx|y所识别的语言是（C）。A．xyxB．(xyx)*C．xnyxn(n≥0)D．x*yx*14．如果文法G是无二义的，则它的任何句子α（A）。A．最左推导和最右推导对应的语法树必定相同B．最左推导和最右推导对应的语法树可能不同C．最左推导和最右推导必定相同D．可能存在两个不同的最左推导，但它们对应的语法树相同15．词法分析器的输出结果是（C）。A.单词的种别编码B.单词在符号表中的位置C.单词的种别编码和自身值D.单词自身值山东科技大学编译原理试卷第4页共7页二、填空题（本大题共10空，每空2分，共20分）1．对于文法G[E]：E→T|E+TT→F|T*FF→P^F|PP→(E)|i，句型T+T*F+i的句柄是__T____，最左素短语是_T*F______。2．编译器常用的语法分析方法有自上而下分析和自下而上分析两种。3．算符优先分析法每次都是对___句柄_进行归约。4．编译程序的工作过程主要分为如下几个阶段：词法分析、语法分析、___语义分析、中间代码生成、代码优化、目标代码生成。5．假设有文法G[S]：S-Sa|b，对该文法消除左递归后得到的文法为（注：新的符号用S′表示）_S-bS’;S’-aS’|ε。6．对于文法G，仅含终结符号的句型称为_句子________。三、简答题（共6题，每题5分，共30分）1．已知文法G[Z]：Z→aZb|ab，写出L（G（Z））的全部元素。aⁿbⁿ，n=12．已知文法G[S]为S→aSb|Sb|b，试证明文法G[S]为二义文法。例如abbb有两棵语法树SS/\/|\SbaSb/|\/\aSbSb||bb3．设有文法E→E+T|TT→T*F|F山东科技大学编译原理试卷第5页共7页F→(E)|i求下列表达式的最左推导和语法树（1）3+4*5+6(数字指的是文法中的i)E-E+T-E+T+T-3+T+T-3+T*F+T-3+4*F+T-3+4*5+T-3+4*5+6E/|\E+T/|\|E+T6|/|\3T*F||45（2）3*（4+5）E-T-T*F-3*F-3*(E)-3*(E+T)-3*(4+T)-3*(4+5)E|T/|\T*F|/|\3(E)/|\E+T||454.将如下正规文法转换为自动机。山东科技大学编译原理试卷第6页共7页S→0A|1BA→1S|1B→0S|0正规式：（01|10）（01|10）*自动机5．已知文法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→ε山东科技大学编译原理试卷第7页共7页3)B→ab（1）证明文法G为LL(1)文法？（2）构造该文法的预测分析表。（3）写出句子babaaba的分析过程。