编译原理复习题一(含答案).docVIP

PAGE PAGE 6 一、 单选题（每题2分，共20分） 1. 编译器的（ ）阶段可将源程序的字符流收集到若干记号中。 A. 语法分析 B. 语义分析 C. 代码生成 D. 词法分析 2. 文法A?aA | b属于正则文法，正则文法在乔姆斯基层次中对应于（ ）文法。 A. 1型 B. 2型 C. 3型 D. 0型 3. 某C语言源代码文件包含#include stdio.h，（ ）将对源代码进行处理，把文件stdio.h包含进去。 A.编译器 B.解释器 C.汇编器 D.预处理器 4. LL(1)文法的充要条件是（ ）。 A.对于文法中的每条产生式U?α1|α2|…|αn，要求FIRST(αi)∩FIRST(αj)＝Φ（i≠j） B.该文法对应的LL(1)分析表中每个项目最多只有一条产生式。 C.A和B D.都不是 5. 以下说法中正确的是（ ）。 A.任何语言都可以描述为一个正则表达式。 B.对于任何一个NFA M，都存在一个DFA M’，满足L(M)= L(M’)。 C.任何一个DFA只有一个终态。 D.NFA的弧上标记只含输入字母表中的元素。 6.合成属性的计算可以通过对语法树进行（ ）遍历进行。 A. 前序 B.中序 C.后序 D.任意 7.乔姆斯基的2型文法是这样一种语言，其产生式限制为（ ）。 A. α-β B. P-β C. P-a或P-aβ D. αPγ-αβγ 8. 正则式的“*”读作（ ）。 A. 并且 B.连接 C.正则闭包 D.闭包 9. 编译程序中的语义分析器接受以（ ）为单位的输入，并产生信息供以后各阶段使用。 A. 语法树 B.子程序 C.单词 D.语句 10.文法A-aAb|ab生成的语言是（ ）。 A. {ab} B.{aAb} C. {anbn|n≥1} D.{anbn|n≥0} 二、 判断题（每题2分，共10分，对的打√，错的打×） 1. 一个LR(0)文法一定是SLR(1)文法。 （ ） 2. 在类型声明文法中，类型属性type是继承属性。 （ ） 3. 在构造递归下降伪代码时，将非终结符A翻译为一个匹配过程match（A）。 （ ） 4. 三元式和四元式都是三地址码的实现形式。 （ ） 5. 存在这样的语言，它们能被确定的有穷自动机识别，但不能用正则表达式表示。 （ ） 三、 填空题（每空2分，共10分） 1. 若文法G的某个句子存在两棵以上的语法树，则称该文法是 文法。 2. 自上而下语法分析方法的基本思想是：从文法的 出发，不断进行 ，最终得到输入串。 3. 程序设计语言中名字的作用域一般遵循 的原则，即若有多个同名定义，该名字的引用应对应于与其引用最近的那个声明。 4. 表达式a－b*(c＋d)对应的逆波兰式是 。 四、 简答题（每题6分，共30分） 1. 简述前端和后端，并说明为什么要区分前端和后端。 2. 设标识符为以一个字母（letter）开头、后跟任意字母或者数字（digit）的串，请画出识别标识符的DFA。 3. 对下图NFA M构造其DFA。 a a a b b b X Y 4．令文法G为： N?D| ND D?0|1|…|9 (1) 该文法的语言是什么？ (2) 给出句子456的最左推导。 5. 试将布尔表达式ab or cd 翻译成四元式（设起始四元式标号为100）。 属性文法如下： E?id1 relop id2 { E.place:=newtemp; emit(‘if’id1.place relop. op id2. place ‘goto’ nextstat+3); emit(E.place‘:=’‘0’); emit(‘goto’nextstat+2); emit(E.place‘:=’‘1’) } E→id { E.place:=id.place } E→E1 or E2 { E.place:=newtemp; emit(E.place‘:=’ E 1.place ‘or’ E2.place)} E→E1 and E2 { E.place:=newtemp; emit(E.place ‘:=’ E 1.place ‘and’ E2.place) } 五、 综合题(30分