《计算机编译原理》试卷B参考答案
一、单项选择题（每小题1分，共25分）
1、有文法G：E→E*T|T
 T→T+i|i
句子1+2*8+6按该文法G归约，其值为＿＿＿B＿＿＿。
A、23  B、42  C、30  D、17
2、规范归约指＿＿＿B＿＿＿。
A、最左推导的逆过程      B、最右推导的逆过程
C、规范推导            D、最左归约的逆过程
3、词法分析所依据的是＿＿＿B＿＿＿。
A、语义规则  B、构词规则  C、语法规则  D、等价变换规则
4、词法分析器的输出结果是＿＿＿C＿＿＿。
A、单词的种别编码          B、单词在符号表中的位置
C、单词的种别编码和自身值  D、单词自身值
5、正规式M1和M2等价是指＿＿＿C＿＿＿。
A、M1和M2的状态数相等        B、M1和M2的有向弧条数相等
C、M1和M2所识别的语言集相等  D、M1和M2状态数和有向弧条数相等
6、下面的状态转换图接受的字集为＿＿＿D＿＿＿。
A、以 0开头的二进制数组成的集合  B、以0结尾的二进制数组成的集合
C、含奇数个0的二进制数组成的集合D、含偶数个0的二进制数组成的集合
7、词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确，因此，＿＿＿B＿＿＿。
A、词法分析器应作为独立的一遍
B、词法分析器作为子程序较好
C、词法分析器分解为多个过程，由语法分析器选择使用
D、词法分析器并不作为一个独立的阶段
8、若a为终结符，则A→α·aβ为＿＿＿B＿＿＿项目
A、归约  B、移进  C、接受  D、待约
9、若项目集Ik含有A→α·，则在状态k时，仅当面临的输入符号a∈FOLLOW(A)时，才采取“A→α·”动作的一定是＿＿＿D＿＿＿。
A、LALR文法  B、LR（0）文法  C、LR（1）文法      D、SLR（1）文法
10、就文法的描述能力来说，有＿＿＿C＿＿＿。
A、SLR（1）⊂LR（0）  B、LR（1）⊂LR（0）
C、SLR（1）⊂LR（1）  D、无二义文法⊂LR（1）
11、在LR（0）的ACTION子表中，如果某一行中存在标记“rj”的栏，则＿＿＿A＿＿＿。
A、该行必定填满rj  B、该行未填满rj
C、其他行也有rj    D、goto子表中也有rj
12、一个＿＿＿C＿＿＿指明了在分析过程中的某时刻所能看到产生式多大一部分。
A、活前缀  B、前缀  C、项目  D、项目集
13、中间代码生成所依据的是＿＿＿C＿＿＿。
A、语法规则  B、词法规则  C、语义规则  D、等价变换规则
14、四元式之间的联系是通过＿＿＿B＿＿＿实现的。
basic语言是解释型语言吗
A、指示器  B、临时变量  C、符号表  D、程序变量
15、后缀式ab+cd+/可用表达式＿＿＿B＿＿＿来表示。
A、a+b/c+d  B、(a+b)/(c+d)  C、a+b/(c+d)  D、a+b+c/d
16、表达式（┓A∨B）∧（C∨D）的逆波兰表示为＿＿＿B＿＿＿。
A、┓AB∨∧CD∨  B、A┓B∨CD∨∧
C、AB∨┓CD∨∧  D、A┓B∨∧CD∨
17、四元式表示法的优点为＿＿＿C＿＿＿。
A、不便于优化处理，但便于表的更动  B、不便于优化处理，但节省存储空间
C、便于优化处理，也便于表的更动    D、便于表的更动，也节省存储空间
18、终结符具有＿＿＿D＿＿＿属性。
A、传递  B、继承  C、抽象  D、综合
19、编译程序使用＿＿＿B＿＿＿区别标识符的作用域。
A、说明标识符的过程或函数名  B、说明标识符的过程或函数的静态层次
C、说明标识符的过程或函数的动态层次  D、标识符的行号
20、程序所需的数据空间在程序运行前可确定，称为＿＿＿C＿＿＿管理技术。
A、动态存储  B、栈式存储  C、静态存储  D、堆式存储
21、优化可生成＿＿＿D＿＿＿的目标代码。
A、运行时间较短                B、占用存储空间较小
C、运行时间短但占用内存空间大  D、运行时间短且占用存储空间小
22、文法G[N]=（{b}，{N，B}，N，{N→b│bB，B→bN}），该文法所描述的语言是＿＿＿C＿＿＿。
A、L(G[N])={bi│i≥0}    B、L(G[N])={b2i│i≥0}
C、L(G[N])={b2i+1│i≥0}  D、L(G[N])={b2i+1│i≥1}
23、乔姆斯基（Chomsky）把文法分为四种类型，即0型、1型、2型、3型。其中3型文法是＿＿＿B＿＿＿。
A、短语文法  B、正则文法  C、上下文有关文法    D、上下文无关文法
24、文法G所描述的语言是＿＿＿C＿＿＿的集合。
A、文法G的字母表V中所有符号组成的符号串
B、文法G的字母表V的闭包V*中的所有符号串
C、由文法的开始符号推出的所有终极符串
D、由文法的开始符号推出的所有符号串
25、按逻辑上划分，编译程序第二步工作是＿＿＿C＿＿＿。
A、语义分析  B、词法分析  C、语法分析  D、代码优化
二、判断题（每小题1分，共10分）
（ √ ）26、算符优先关系表不一定存在对应的优先函数。
（ × ）27、自底而上语法分析方法的主要问题是候选式的选择。
（ × ）28、LR法是自顶向下语法分析方法。
（ × ）29、简单优先文法允许任意两个产生式具有相同右部。
（ × ）30、若一个句型中出现了某产生式的右部，则此右部一定是该句型的句柄。
（ √ ）31、一个句型的句柄一定是文法某产生式的右部。
（ √ ）32、数组元素的地址计算与数组的存储方式有关。
（ × ）33、在程序中标识符的出现仅为使用性的。
（ × ）34、对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。
（ × ）35、在程序中标识符的出现仅为使用性的。
三、名词解释题（每小题4分，共8分）
36、素短语
至少含有一个终结符的素短语，并且除它自身之外不再含任何更小的素短语。
37、语法树
满足下面4个条件的树称之为文法G[S]的一棵语法树。
①每一终结均有一标记，此标记为VN∪VT中的一个符号；
②树的根结点以文法G[S]的开始符S标记；
③若一结点至少有一个直接后继，则此结点上的标记为VN中的一个符号；
④若一个以A为标记的结点有K个直接后继，且按从左至右的顺序，这些结点的标记分别为X1,X2,…,XK，则A→X1,X2,…,XK，必然是G的一个产生式。
四、简答题（每小题4分，共8分）
38、编译程序和高级语言有什么区别？
答：用汇编语言或高级语言编写的程序，必须先送入计算机，经过转换成用机器语言表示的目标程序（这个过程即编译），才能由计算机执行。执行转换过程的程序叫编译程序。汇编程序是指没有编译过的汇编语言源文件。编译程序转换过的叫目标程序，也就是机器语言。
    编译程序的工作情况有三种：汇编型、解释型和编译型。汇编型编译程序用来将汇编语言编写的程序，按照一一对应的关系，转换成用机器语言表示的程序。解释型编译程序将高级语言程序的一个语句，先解释成为一组机器语言的指令，然后立即执行，执行完了，取下一组语句解释和执行，如此继续到完成一个程序止。用解释型编译程序，执行速度很慢，但可以进行人和计算机的"对话"，随时可以修改高级语言的程序。BASIC语言就是解释型高级语言。编译型编译程序将级语言编写的程序，一次就会部翻译成机器语言表示的程序，而且过程进行很快，在过程中，不能进行人机对话修改。FORTRAN语言就是编译型高级语言。
39、简述自下而上的分析方法。
答：所谓自下而上分析法就是从输入串开始，逐步进行“归约”，直至归约到文法的开始符号；或者说从语法树的末端开始，步步向上“归约”，直到根节点。
五、应用题（每小题5分，共25分）
40、证明下述文法G：
SaSbS|aS|d
是二义性文法。
答：
一个文法，如果存在某个句子有不只一棵语法分析树与之对应，那么称这个文法是二义性文法。
句子aadbd有两棵语法树。如下图：
由此可知，SaSbS|aS|d定义的文法是二义性文法。