山东科技大学《编译原理》期末考试试题(A卷)

山东科技大学20152016学年第二学期编译原理考试试卷（A卷）班级 姓名 学号 题号一二三四总得分评卷人审核人得分一、单项选择题(共15小题，每小题2分，共30分)1. 一个上下文无关文法G包括四个组成部分：一组终结符，一组非终结符，一个开始符号，以及一组（ ）。 A 字符串 B 产生式 C 开始符号 D 文法2一个句型中称为句柄的是该句型的最左（ ） A非终结符号 B短语 C句子 D直接短语 3自动机识别的语言是（ ） A0型语言 B1型语言 C2型语言 D3型语言4编译程序各阶段工作都涉及（ ）A.词法分析 B.表格管理 C.语法分析 D.语义分析5代码生成阶段的主要任务是 （）A把高级语言翻译成汇编语言 B把高级语言翻译成机器语言 C把中间代码变换成依赖具体机器的目标代码 D把汇编语言翻译成机器语言6作为编译程序的源语言，不能是( )A.高级语言 B.C语言 C.低级语言 D.Pascal语言7词法分析器的输入是（ ）A.单词符号串 B.源程序 C.语法单位 D.目标程序8给定文法A-bAcc,下面符号串中不是该文法的句子的是（ ）cc bcbc bcbcc bccbcc bbbccA B. C. D. 9若B是非终结符，则A-a.aBb为（ ）项目A移进 B待约 C接受 D规约10文法G：Sb|(T) TT,S|S 则FIRSTVT(T)结果是（ ）。A. b,(B. b,)C.b,(,，D.b,),，11常用的中间代码形式不含（ ）A三元式 B四元式 C逆波兰式 D语法树12.正规式 M 1 和 M 2 等价是指（ ）。 AM1和M2的状态数相等 BM1和M2的有向边条数相等 CM1和M2所识别的语言集相等 DM1和M2状态数和有向边条数相等13.文法G：SxSx|y所识别的语言是（ ）。 Axyx B(xyx)* Cxnyxn (n0) Dx*yx*14如果文法G是无二义的，则它的任何句子（ ）。 A最左推导和最右推导对应的语法树必定相同B最左推导和最右推导对应的语法树可能不同 C最左推导和最右推导必定相同 D可能存在两个不同的最左推导，但它们对应的语法树相同15词法分析器的输出结果是（ ）。 A.单词的种别编码 B.单词在符号表中的位置 C.单词的种别编码和自身值 D.单词自身值二、填空题（本大题共10空，每空2分，共20分）1对于文法GE：ET|E+T TF|T*F FPF|P P(E)|i，句型T+T*F+i的句柄是_，最左素短语是 _。 2编译器常用的语法分析方法有_和_两种。3算符优先分析法每次都是对_ 进行归约。4编译程序的工作过程主要分为如下几个阶段：词法分析、语法分析、_、_、_、目标代码生成。5假设有文法GS：S-Sa|b，对该文法消除左递归后得到的文法为（注：新的符号用S表示）_。6对于文法G，仅含终结符号的句型称为_ 。三、简答题（共6题，每题5分，共30分）1已知文法GZ：ZaZb |ab，写出L（G（Z）的全部元素 。2已知文法 GS 为 S aSb|Sb|b ，试证明文法 GS 为二义文法。3设有文法EE+T | TTT*F | FF(E) | i求下列表达式的最左推导和语法树（1）3+4*5+6（2）3*（4+5）4.将如下正规文法转换为自动机。S0A|1BA1S|1B0S|05已知文法GS：Sa | (T)TTbS | S（1）写出句型(TbS)ba)的语法树（2）写出该句型短语、简单短语、句柄、素短语6.有文法GS：0) SBB1) BaB|b构造此文法的LR（0）项目集规范簇，并写出识别活前缀的DFA四、综合应用（共2题，共20分）1构造下列正规式1(0|1)*101 相应的DFA（1）由正规表达式构造NFA（2）由转换系统NFA构造确定的有穷自动机DFA（3）DFA的最小化2已知文法GS：0)