编译原理卷B.doc

编译原理 试卷（B卷）（课程代号：9047 ）题号一二三四五总分题分2010103525100一、单项选择题（本大题共20小题，每小题1分，共20分）在每小题列出四个备选项中只有一个是符合题目要求的，请将其代码填写在题前的括号内。错选、多选或未选均无分。1.（）描述一个语言的文法是A.唯一的 B.不唯一的 C.个数是固定的 D.可能唯一，也可能不唯一2. 若文法G定义的语言是无限集，则文法必然是（ ）A.上下文无关文法 B.正规文法 C.二义性文法 D.递归文法3. 文法 G描述的语言是该文法产生的A 句型的全体 B. 终结符集 C. 非终结符集 D. 句子的全体 4. 简单优先分析每次归约的是（ ）A. 最左直接短语 B.直接短语 C.最左素短语 D.控制结点5. 最适合动态建立数据实体的内存分配方式是（ ）A. 栈式分配 B.堆式分配 C.编译时预先分配 D.以上三种均可6 Chomsky 定义的四种形式语言文法中， 1 型文法又称为A 短语结构文法 B 上下文无关文法 C 上下文有关文法 D 正规文法 7. 0型文法的识别能力相当于A图灵机 B. 有限自动机 C.下推自动机 D.确定的有限自动机8.一个文法所描述的语言是 ；描述一个语言的文法是 。 A 唯一的 B 不唯一的 C 可能唯一，好可能不唯一 9.数组的内情向量中肯定不含有数组的哪一一种信息 A.维数 B.类型 C.各维的上下界 D.各维的界差10._不是NFA的成分。A.有穷字母B.开始状态集合 C.终止状态集合D.非空有穷状态集合11._不是编译程序的组成部分。A.词法分析程序B.代码生成程序 C.设备管理程序D.语法分析程序12.有文法GS：SaA|aAaS|bBBbA|b则下面哪一个为L(G)中的句子。A.a5b2 B.b500aba C.a2AbD.a4b213.有文法G=(S，a，SSaS，Se，S)，该文法是_。A.LL(1)文法B.二义性文法 C.算符优先文法D.SLR(1)文法14.（）赋值语句X: = ACBD的逆波兰式表示是A. XACBD:= B. XABCD:= C. X:=ACBD D.XACBD:=15.（）下面哪一个程序一定是编译程序的一部分？A.中间代码生成程序 B. 中间代码优化程序C.目标代码生成程序 D. 目标代码优化程序16.（）下面的正规表达式哪一个描述了=a,b上所有长度不为3的符号串？A. (|a|b|ab|ba)(a|b)(a|b)* B. (|a|b|ab|ba)(a|b) C. (|a|b|ab|ba)* D. (|a|b|ab|ba)(a|b|)17.（）一个变量能够引用的程序区间称为A. 变量的作用域 B. 变量的生存期 C. 变量的值 D. 变量的类型18.（）算符优先文法中，存在优先关系ab,a=c,则下列优先关系可能成立的是A.a=b B.bc D.ac19.（）对自动机描述正确的是A.一个非确定有穷的自动机，一定存在着一个确定的有穷自动机和它等价。B.一个正规表达式，一定存在着一个唯一的确定的有穷自动机和它等价。C.一个确定的有穷自动机是一个五元组DFA(Q,t,Q0,F)，其中Q0是开始状态集。D.上下文无关文法的能力相当于自动机。20.（）对自动机描述正确的是A.一个非确定有穷的自动机，一定存在着一个确定的有穷自动机和它等价。B.一个正规表达式，一定存在着一个唯一的确定的有穷自动机和它等价。C.一个确定的有穷自动机是一个五元组DFA(Q,t,Q0,F)，其中Q0是开始状态集。D.上下文无关文法的能力相当于自动机。二、多项选则题（本小题共5小题，每小题2分，共10分）在每小题列出的五个备选项中至少有两个是符合题目要求的，请将其代码填写在题前的括号内。错选、多选或未选均无分。21. （）符号表的功能包括A. 静态存储 B.上下文语义的合法检查 C. 动态存储 D. 收集符号属性 E. 作为目标代码生成阶段的地址分配的依据22.（）关于正规语言描述正确的是A. 2型语言一定是正规语言 B.正规语言一定是2型语言 C.正规语言一定是3型语言 D. 正规语言可以用正规文法描述E.正规语言可以用正规表达式描述23. () 已知文法GS: EE EE+T|TTT*F|FF(E)|a，下面的项目属于集合CLOSURE(E E )的有A.T F B. F a C. EE D. T T*F E. EE24.（）代码优化的目的A.目标程序所占的存储空间的大小 B.容易读写 C.保证代码的正确性 D.减少执行出错率 E. 提高运行速度25.（）已知文法GS:SaHHaMd|dMAb|AaM|e，下面哪一个符号是FOLLOW（M）的元素？A.a B.d C.# D.b E.e三、填空题（本小题共5题，每题2分）请在每小题的空格中填上正确答案，错填、少填均无分。26.编译程序的输入是 ，输出是 。27.乔姆斯基把文法分为四种类型： 。 28.活前缀是 的一个前缀，它不含该句型的 右边的任何符号。29.LL（k）文法从 扫描源程序，生成句子的 推导。 30.递归下降子程序的基本思想是对文法的每一个 符号设计一个相应的子程序。五、计算题。（本大题共5小题，每小题7分，共35分）31. 已知文法GS为：Sa|b|（A）ASdA|S, 给出句型（SdSdS）的短语，简单短语句柄，素短语和最左素短语。baabABCDEaba32. 已知题32的自动机，给出相应的正规文法。 题32图33. 构造产生语言anbmcp|n,m,p0的文法。34. 设有基本块如下：T1:=A+BT2:=5M:=T2*4T3:=C-DT4:=M+T3L:=T1*T3T4:=A+BN:=T4画出DAG图。35.已知文法的产生集为： ABaC|CbB,BAC|c,CBb|c ,试消除G的左递归。六、设计分析题。（本大题共2小题，每小题10分，共25分）36. 已知文法GS:Sa|(T)T