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

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