《编译原理半期考试答案》由会员分享，可在线阅读，更多相关《编译原理半期考试答案（8页珍藏版）》请在金锄头文库上搜索。
1、毕节学院课程考试试卷纸毕节学院编译原理课程试卷 第 页 共 8 页 1一、填空题（每空 1 分，共 20 分）1编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析,中间代码生成,代码优化等几个基本阶段,同时还会伴有_表格处理_和 _出错处理_。 2若源程序是用高级语言编写的,_目标程序_是机器语言程序或汇编程序,则其翻译程序称为 _编译程序_ 。3编译方式与解释方式的根本区别在于_是否生成目标代码_。4对编译程序而言,输入数据是_源程序_, 输出结果是_目标程序_。5若两个正规式 e1 和 e2 所表示的正规集相同,则 e1 和 e2 等价,写作 e1=e2。6一个句型中的最左简单短
2、语称为该句型的_句柄_。7词法分析基于_正则_文法进行，即识别的单词是该类文法的句子。二、是非题（请在括号内，正确的划，错误的划） （每个 1 分，共 10 分）1计算机高级语言翻译成低级语言只有解释一种方式。()2在编译中进行语法检查的目的是为了发现程序中所有错误。()3甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。 ( )4正则文法其产生式为 A-a ， A-Bb, A,BV N ， a 、 bV T 。 ()5每个文法都能改写为 LL(1) 文法。 ()（2 班做）得分 评卷人得分 评卷人毕节学院期中课程试卷2009 2010 学年度第二学期 编译原理
3、计科系 07 级计算机科学与技术专业 班姓名 学号 得分 主考教师：黄正鹏 试卷类型：（半期考试）毕节学院课程考试试卷纸毕节学院编译原理课程试卷 第 页 共 8 页 26.有穷自动机接受的语言是正规语言。 ()（1 班做）7.对任何一个 NFA M 都存在一个 DFA M,使得 L(M)=L(M).( )8设 r 和 s 分别是正规式，则有 L(r|s)=L(r)L(s)。()9确定的自动机以及不确定的自动机都能正确地识别正规集。()10词法分析作为单独的一遍来处理较好。 ( )11有穷自动机接受的语言是正规语言。 （）三、选择题（每小题 2 分，共 20 分）1 文法 G 产生的_的全体是该
4、文法描述的语言。A( ) 句型 B( ) 终结符集 C ( ) 非终结符集 D ( ) 句子2 若文法 G 定义的语言是无限集，则文法必然是 _。 A ( ) 递归的 B( ) 前后文无关的C( ) 二义性的 D( ) 无二义性的3 四种形式语言文法中，1 型文法又称为 _文法。A( ) 短语结构文法 B( ) 前后文无关文法 C ( ) 前后文有关文法 D( ) 正规文法 4 一个文法所描述的语言是_。A ( ) 唯一的 B( ) 不唯一的 C( ) 可能唯一，好可能不唯一 D ( ) 都不对5 _和代码优化部分不是每个编译程序都必需的。A( ) 语法分析 B ( ) 中间代码生成 C( )
5、 词法分析 D( ) 目标代码生成 6_是两类程序语言处理程序。 A( ) 高级语言程序和低级语言程序 B ( ) 解释程序和编译程序 C( ) 编译程序和操作系统 D ( ) 系统程序和应用程序 7 编译程序是对_。 A( ) 汇编程序的翻译 B( ) 高级语言程序的解释执行C( ) 机器语言的执行 D ( ) 高级语言的翻译 8 采用自上而下分析，必须_。（2 班做）A( ) 消除左递归 B( ) 消除右递归C ( ) 消除回溯 D ( ) 提取公共左因子 9在规范归约中，用_来刻画可归约串。（2 班做）A( ) 直接短语 B ( )句柄 C( )最左素短语 D ( ) 素短语 得分 评卷
6、人毕节学院课程考试试卷纸毕节学院编译原理课程试卷 第 页 共 8 页 310词法分析器用于识别_。 A( ) 字符串 B( ) 语句C ( )单词 D( ) 标识符11文法分为四种类型，即 0 型、1 型、2 型、3 型。其中 0 型文法是_。A. ( ) 短语文法 B( ) 正则文法 C( ) 上下文有关文法 D( ) 上下文无关文法12一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 _。 A( ) 句子 B( ) 句型 C ( ) 单词 D( ) 产生式四、简答题（每小题 5 分，共 30 分）1.高级语言程序有哪两种执行方式？其特点
7、是什么？答：高级语言程序有编译程序和解释程序两种执行方式；编译程序（Compiler）将高级程序设计语言程序翻译成逻辑上等价的低级语言(汇编语言,机器语言)程序的翻译程序。解释程序（Interpreter）将高级程序设计语言写的源程序作为输入，边解释边执行源程序本身，而不产生目标程序的翻译程序。2、考虑文法 GS：SaSbS|bSaS| (1)试用最左推导说明此文法是二义性的（2）对于句子 abab 构造两个相应的最右推导（3）对于句子 abab 构造两个相应的分析树解答：(1) 句子 abab 有如下两个不同的最左推导：S = aSbS = abS =abaSbS = ababS = aba
8、bS = aSbS = abSaSbS = abaSbS = ababS = abab所以此文法是二义性的。(2) 句子 abab 的两个相应的最右推导：S = aSbS = aSbaSbS = aSbaSb = aSbab = ababS = aSbS = aSb = abSaSb = abSab = abab(3) 句子 abab 的两棵分析树： 得分 评卷人毕节学院课程考试试卷纸毕节学院编译原理课程试卷 第 页 共 8 页 4(a) (b)3、已知文法 GE 为： ET|E+T|E-T TF|T*F|T/F F(E) |i 该文法的开始符号（识别符号）是什么？ 请给出该文法的终结符号集合
9、 VT 和非终结符号集合 VN 。 找出句型 T+T*F+i 的所有短语、简单短语和句柄。解： 该文法的开始符号（识别符号）是 E。 该文法的终结符号集合 VT=+、-、*、/、 （、 ） 、i。 非终结符号集合 VN=E、T、F。句型 T+T*F+I 的短语为 i、 T*F、第一个 T、T+T*F+i; 简单短语为 i、T*F、第一个 T;句柄为第一个 T。4. 构造正规式相应的 NFA : 1(0|1)*101 解：1(0|1)*101 对应的 NFA 为 5.画出接受以/*和*/括起来的注释的状态转换图。毕节学院课程考试试卷纸毕节学院编译原理课程试卷 第 页 共 8 页 5解答：6.用状
10、态转换图表示识别偶数个 0 或偶数个 1 的字符串的有穷自动机。解答：五.计算题（10 分）1、构造下述文法 GS 的自动机： S-A0 A-A0|S1|0 该自动机是确定的吗？若不确定，则对它确定化。解：由于该文法的产生式 S-A0，A-A0|S1 中没有字符集 VT 的输入，所以不是确定的自动机。 要将其他确定化，必须先用代入法得到它对应的正规式。把 S-A0 代入产生式A-S1 有：A=A0|A01|0=A(0|01)|0=0(0|01)*。 代入 S-A0 有该文法的正规式：0(0|01)*0，所以，改写该文法为确定的自动机为： 由于状态 A 有 3 次输入 0 的重复输入，所以上图只
11、是 NFA，下面将它确定化： 下表由子集法将 NFA 转换为 DFA:得分 评卷人毕节学院课程考试试卷纸毕节学院编译原理课程试卷 第 页 共 8 页 6由上表可知 DFA 为：2、设计一个状态数最小的 DFA,其输入字母表是0,1，它能接受以 00 或 01 结尾的所有序列，并给出相应的正规文法。 （1 班做）解答：正规式为：(0|1) *(00|01) 化简：(0|1) *0(0|1)不确定的有穷自动机为：确定化，并最小化得到：正规文法为：S1S | 0AA0B | 0 | 1C | 1B0B | 0 | 1C | 1C1S | 0A3、对下面的文法 G:ETEE+E| 毕节学院课程考试试卷
12、纸毕节学院编译原理课程试卷 第 页 共 8 页 7TFTTT| FPFF*F| P(E)|a|b|(1) 计算这个文法的每个非终结符的 First 集和 Folow 集；(2) 证明这个文法是 LL(1)的；(3) 构造它的预测分析表。解答：(1) 求 First 和 Follow 集 First(E)=First(T)=(,a,b, First(E)=+, First(T)=First(F)=(,a,b, First(T)=(,a,b, , First(F)=First(P)=(,a,b, First(F)=*， First(P)=(,a,b, （计算顺序）Follow(E)= #, ) F
13、ollow(E)= Follow(E)=#，) (1)（使用的产生式）Follow(T) = First(E)Follow(T) (1,2)= +),#=+,),#Follow(T)= Follow(T)=+,# (3)Follow(F)= First(T) Follow(T) (3,4)= (,a,b,+ ,),#Follow(F)= Follow(F) (5)= (,a,b,+ ,),#Follow(P)= First(F)Follow(F) (5,6)=*,(,a,b,+ ,),# (2) 证明: a. 文法不含左递归；b. 每个非终结符的各个侯选式的 First 集不相交；c. First(E)Follow(E)=+, #,) ,=First(T)Follow(T)=(,a,b, +,)=First(F)Follow(F)=*, ,a,( ,+, ,#= 毕节学院课程考试试卷纸毕节学院编译原理课程试卷 第 页 共 8 页 8改造后的文法满足 LL(1)文法的三个条件，是 LL(1)文法。(3) 预测分析表如下所示。a b
