内容发布更新时间 : 2024/5/17 19:04:08星期一 下面是文章的全部内容请认真阅读。
??○???? 座位号：
2014-2015学年第一学期期末考试答案及评分标准
《编译原理》（B）卷
课程代码：
5、语法分析中的立法机构是: 【 B 】 A、正规式 B、上下文无关文法 C、上下文有关文法 D、预测分析器
6、移近-归约分析表中指导分局发生变化的动作包括: 【 C 】 22801204 适用班级： 计本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、代码优化
系 院
第1页，共8页 A、移近、归约 B、移近、归约、接受
C、移近、接受、归约、出错
D、移近，归约、出错
7、中间代码生成时所依据的是: A、语义规则 B、词法规则 C、语法规则 D、等价变换规则
8、程序所需的数据空间在程序运行前就可确定，称为: A、动态存储 B、静态存储 C、栈式存储 D、堆式存储
9、代码生成阶段的主要任务是:
A、把高级语言翻译成汇编语言 B、把高级语言翻译成机器语言
C、把中间代码变换成依赖具体机器的目标代码 D、把汇编语言翻译成机器语言
10、代码优化的方法中不包含： A、窥孔优化 B、强度削弱 C、构造流图 D、基本块优化 第2页，共8页
【 A 】 【 B 】 【 C 】 【 D 】
得 分 二、填空题
（每空1分，共10分）
得 分
四、简答题
（第1小题7分，第2小题6分，第3小题7分，共20分）
1、（7分）简述怎样从正规式构造词法分析器。
1、每个阶段将程序完整分析一遍的工作模式称为_____一遍扫描_____。
答：从正规式构造词法分析器的基本步骤如下：
2、将高级语言写的源程序翻译成目标语言的程序，这种翻译过程称为 编译______。
3、若有限自动机 M 和 M’____识别同一正规集_____，则称 M 和 M’是等价的。
4、若文法G对同一句子产生不止一棵分析树，则称文法G___具有二义性___。
5、后缀式ab+cd+/可用表达式____（a+b）/(c+d)____来表示。
6、程序设计语言的运行时存储管理方案，主要分为两大类，即__静态存储分配___和
____动态存储分配___方案。7、经过编译所得到的目标程序是 __机器语言程序___或者__汇编语言程序。。
8、局部优化是局限于一个__基本块___范围内的一种优化。
得 分 三、判断题（正确的在题号后括号内填写“V”,错误的填写“X”） （每小题2分，共20分）
1. 编译程序和机器硬件有关，和具体的语言无关。 （ X ）
2. NAF在识别记号的时候会产生大量的回溯。 （ V ）
3. 每个文法都能改写为LL(1)文法。 （ X ）
4. LR分析表是由动作表和转移表两部分组成的。 （ V ）
5. 代码优化的目的是把编译程序进行等价变换。 （ X ）
6. 引用调用中，实参与形参共用同一个内存空间。 （ V ）
7. 综合属性的计算方式是自上而下包含自身。 （ X ） 8. 一个完整程序执行的控制流，是对它的活动树的一次深度优先遍历。 （ V ） 9. 在名字绑定的概念下，对一个常量的赋值包含了两次映射，即环境映射和状态映射。 （X ）
10. 通过拷贝语句进行值的传递的语句称为复写传播。 （ V ）
第3页，共8页 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（aA）与First（Aa）的交集为a，所以不是LL(1)文法， -------------------------（2分）
第4页，共8页
题答许不内线订装
??○???? 座位号：
3、（7分）写出表达式x=a-b*c-a+（b/2+c）的后缀式，三元式序列，四元式序列。 答：
后缀式：abc*-a-b2/c++x= -------------------------（1分） 三元式序列： -------------------------（3分） 得 分 五、论述题
（每小题15分，共30分）
1、（15分）已知某NFA的状态转换矩阵如下表1所示，将此NFA确定化，构造器最??线????○????订 ????○????装???○????○?? (1)(*,b,c) (2)(-,a,(1)) (3)(-,(2),a) (4)(/,b,2) ：(5)(+,(4),c) 名(6)(+,(3),(5)) 姓(7)(=,x,(6))
四元式序列： ------------------------- (*,b,c,T1) (-,a,T1,T2) (-,T2,a,T3) (/,b,2,T4) ：(+,T4,c,T5) 号(+,T3,T5,T6) 学(=,x,T6,T7) ：级 班 业 专 ： 系
院 （3分） 第5页，共8页
小化DFA，要求写出具体解题过程。
表1 NFA的状态转换矩阵 a b c d 1 3 2 2 4 2 3 6 3 5 4 7 3 5 5 4 6 6 7 6 答：从上表中可以看出，该NFA已经是DFA，所以直接对其进行最小化（5分）。
初始分划Π0: 终态组｛6,7｝，非终态组｛1,2,3,4,5｝---------------------（2分） 对{1,2,3,4,5}进行审查： {1,2}输入b到达｛2｝，而{3,4}输入b到达｛6,7｝，{5}输入b不会有任何动作， 故得到新分划{1,2} {3,4} {5} -----------------------（2分） Π1: {1,2} {3,4} {5} {6,7}
Π1即是最后划分, ----------------------（2分） 重新命名, 以1，3，5，6代替{1,2} {3,4} {5} {6,7} 得最小化的DFA如下表2所示
表2 最小化后的DFA a b c d 1 3 1 3 6 3 5 5 3 6 6
b c b
1 a 3 b 6
a d
5
-------------------------------（4分）
第6页，共8页