2018-2018学年第一学期期末考试答案及评分标准
《编译原理》 课程代码：22801204 b5E2RGbCAP 适用班级：计本12级 教研室主任审核命题教师： 毛静 教案主任 任课教师： (签名>：毛静 (签名>： 题 号 一 二 三 四 五 总分 评卷人 分 值 得 分 得 分 一、选择题 <每小题2分，共20分） 1、编译程序和解释程序的区别是： 【 B】 A、解释程序产生目标程序，编译程序不生成目标代码 B、解释程序不产生目标，编译程序生成目标代码 C、解释程序和编译程序都生成目标代码 D、解释程序和编译程序 2、将编译程序分成若干个“遍”是为了：【 B 】 A、提高程序的执行效率 B、使程序的结构更加清晰 C、利用有限的机器内存并提高机器的执行效率 D、利用有限的机器内存但降低了机器的执行效率 3、词法分析器的输出结果是:【 C】 A、单词的种别编码B、单词在符号表中的位置 C、记号流D、单词自身值 4、编译的各个阶段中，与源程序打交道的阶段是:【 C 】 A、语法分析B、语义分析 C、词法分析D、代码优化 5、语法分析中的立法机构是:【 B 】 A、正规式B、上下文无关文法 C、上下文有关文法 D、预测分析器 6、移近-归约分析表中指导分局发生变化的动作包括:【 C 】 A、移近、归约 B、移近、归约、接受 C、移近、接受、归约、出错 D、移近，归约、出错 7、中间代码生成时所依据的是:【 A 】 A、语义规则B、词法规则 C、语法规则D、等价变换规则 8、程序所需的数据空间在程序运行前就可确定，称为:【 B 】 A、动态存储B、静态存储 C、栈式存储D、堆式存储 9、代码生成阶段的主要任务是:【 C 】 A、把高级语言翻译成汇编语言 B、把高级语言翻译成机器语言 C、把中间代码变换成依赖具体机器的目标代码 D、把汇编语言翻译成机器语言 10、代码优化的方法中不包含：【 D 】 A、窥孔优化 B、强度削弱 C、构造流图 D、基本块优化 得 分 填空题二、 <每空1分，共10分） p1EanqFDPw 1、每个阶段将程序完整分析一遍的工作模式称为_____一遍扫描_____。 2、将高级语言写的源程序翻译成目标语言的程序，这种翻译过程称为 编译______。 3、若有限自动机 M 和 M’____识别同一正规集_____，则称 M 和 M’是等价的。 4、若文法G对同一句子产生不止一棵分析树，则称文法G___具有二义性___。 5、后缀式ab+cd+/可用表达式____ 6、程序设计语言的运行时存储管理方案，主要分为两大类，即__静态存储分配___和____动态存储分配___方案。DXDiTa9E3d 7、经过编译所得到的目标程序是__机器语言程序___或者__汇编语言程序。。 8、局部优化是局限于一个__基本块___范围内的一种优化。 得 分 <正确的在题号后括号内填写“V”,错误的填写判断题三、 “X”）<每小题2分，共20分） RTCrpUDGiT 1.编译程序和机器硬件有关，和具体的语言无关。< X ） 2.NAF在识别记号的时候会产生大量的回溯。< V ） 3.每个文法都能改写为LL(1>文法。< X ） 4.LR分析表是由动作表和转移表两部分组成的。< V ） 5.代码优化的目的是把编译程序进行等价变换。< X ） 6.引用调用中，实参与形参共用同一个内存空间。 < V ） 7.综合属性的计算方式是自上而下包含自身。 < X ） 8.一个完整程序执行的控制流，是对它的活动树的一次深度优先遍历。< V ） 9.在名字绑定的概念下，对一个常量的赋值包含了两次映射，即环境映射和状态映1 / 3 射。 10.通过拷贝语句进行值的传递的语句称为复写传播。 简答题 四、得 分 <第1小题7分，第2小题6分，第3 小题7分，共20分） 1、<7分）简述怎样从正规式构造词法分析器。 答：从正规式构造词法分析器的基本步骤如下： 1) 用正规式对模式进行描述<1分）； 2) 为每个正规式构造一个NFA，它识别正规式所表示的正规集<1分）； 3) 将构造出的 NFA 转换成等价的 DFA，这一过程也被称为确定化<2分）； 4) 优化DFA，使其状态数最少，这一过程也被称为最小化<2分）； 5) 从优化后的 DFA 构造词法分析器<1分）。 2、(6分>下述文法哪些文法是LL(1>文法，哪些不是LL(1>文法，为什么？ <1）S->Ra | a R->Sb | b <2）S->aAc | b A->a|b |ε <3）S->aA | Aa A->b |ε 答： （1） 不是LL(1>文法，S=>Ra=> Sba 含有间接左递归，因此不是不是LL(1>文 法。 -------------------------<2分） （2） 是LL(1>文法，因为满足推论3.2的3条规则。 -------------------------<2分） <3）不是LL(1>文法。对于S->Aa | Aa，求得First 答： 后缀式：abc*-a-b2/c++x= -------------------------<1分） jLBHrnAILg (*,b,c,T1> (-,a,T1,T2> (-,T2,a,T3> (/,b,2,T4> (+,T4,c,T5> (+,T3,T5,T6> (=,x,T6,T7> 五、论述题 得 分 <每小题15分，共30分） 1、<15分）已知某NFA的状态转换矩阵如下表1所示，将此NFA确定化，构造器最小化DFA，要求写出具体解题过程。Zzz6ZB2Ltk 表1 NFA的状态转换矩阵 a b c d 1 2 3 4 5 6 7 3 4 4 2 2 6 7 6 6 3 3 5 5 答：从上表中可以看出，该NFA已经是DFA，所以直接对其进行最小化<5分）。 初始分划Π0: 终态组｛6,7｝，非终态组｛1,2,3,4,5｝---------------------<2分） dvzfvkwMI1 三元式序列： -------------------------<3分） xHAQX74J0X (1>(*,b,c> (2>(-,a,(1>> (3>(-,(2>,a> (4>(/,b,2> (5>(+,(4>,c> (6>(+,(3>,(5>> (7>(=,x,(6>> 四元式序列： -------------------------<3分） LDAYtRyKfE 对{1,2,3,4,5}进行审查： {1,2}输入b到达｛2｝，而{3,4}输入b到达｛6,7｝，{5}输入b不会有任何动作， 故得到新分划{1,2} {3,4} {5} -----------------------<2分）rqyn14ZNXI Π1:{1,2} {3,4} {5} {6,7} Π1即是最后划分, ----------------------<2分）EmxvxOtOco 重新命名, 以1，3，5，6代替{1,2} {3,4} {5} {6,7} 得最小化的DFA如下表2所示 SixE2yXPq5 1 3 5 6 2 / 3 a 3 3 表2 最小化后的DFA b 1 6 6 c 3 d 5 b b 分） c -------------------------------<42、<15分）已知文法G[S]: a b 1 aBc|bAB 3 6 S→A→aAb|b d B→b|ε a <1）构造其LL<1）分析表<12分）； 5 <2）使用自上而下的分析方法判断字符串baabbb是否为该文法的句子<3分）。 答：<1）首先计算所有终结符的FIRST集合和FOLLOW集合。 FIRST(B>={b,ε} FIRST(A>={a,b} FIRST(S>={a,b} FOLLOW(S>={#} FOLLOW(A>={b,#} FOLLOW(B>={c,#} -------------------------------------<6分） 预测分析表如下所示： a b c # S A B S→aBc A→aAb S→bAB A→b B→b B→ε B→ε -------------------------------------<6分） <2）自上而下的分析方法是从文法的开始符号开始进行最左推导得到一个终结符序列，这个终结符序列称为该文法的句子。6ewMyirQFL --------------------------------------<1分） S=>bAB=>b aAbB=>baaAbbB=>baabbbB=>baabbb 所以baabbb是该文法的句子。 --------------------------------------<2分） 3 / 3