编译原理学期期考试

1、毕节学院课程考试试卷纸毕节学院期中课程试卷2009 2010学年度第二学期编译原理计科系_级计算机科学与技术专业 班姓名 学号 得分 主考教师：黄正鹏 试卷类型：（半期考试）得分评卷人一、填空题（每空2分，共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,BVN ， a 、 bVT 。 ( )5每个文法都能改写为 LL(1) 文法。 ( )（2班做）6.有穷自动机接受的语言是正规语言。 ( )（1

3、班做）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 产生的_的全体是该文法描述的语言。A句型 B终结符集 C非终结符集 D句子2 若文法 G 定义的语言是无限集，则文法必然是 _。  A 递归的   B前后文无关的  C 二义性的 D无二义性的3 四种形式语言文法中，1

4、型文法又称为 _文法。A短语结构文法       B 前后文无关文法 C前后文有关文法     D正规文法 4 一个文法所描述的语言是_。A 唯一的         B 不唯一的   C 可能唯一，好可能不唯一   D 都不对5 _和代码优化部分不是每个编译程序都必需的。A 语法分析   B 中间代码生成       C词法分析    &

5、#160;  D 目标代码生成 6_是两类程序语言处理程序。 A 高级语言程序和低级语言程序       B 解释程序和编译程序 C 编译程序和操作系统                 D 系统程序和应用程序 7 编译程序是对_。  A 汇编程序的翻译   B 高级语言程序的解释执行  C 机器语言的执行 D高级语言的翻译 8（2班做）

6、采用自上而下分析，必须_。A 消除左递归  B消除右递归  C 消除回溯   D 提取公共左因子 9（1班做）词法分析器用于识别_。  A 字符串   B语句 C单词 D标识符10文法分为四种类型，即0型、1型、2型、3型。其中0型文法是_。A.短语文法     B 正则文法     C 上下文有关文法 D 上下文无关文法11一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 _。 A 句子 B 句型 C 单词 D 产生式得

7、分评卷人四、简答题（每小题5分，共30分）1.高级语言程序有哪两种执行方式？其特点是什么？ 2、考虑文法GS：SaSbS|bSaS|(1)试用最左推导说明此文法是二义性的（2）对于句子abab构造两个相应的最右推导（3）对于句子abab构造两个相应的分析树3. 构造正规式相应的 NFA : 1(0|1)*101 4、已知文法 GE 为：     ET|E+T|E-T     TF|T*F|T/F     F(E) |i 该文法的开始符号（识别符号）是什么？ 请给出该文法的终结符号集合 VT 和非终结符号集合 VN 。 找出句型 T+T*F+i 的所有短语、简单短语和句柄。5.画出接受以/*和*/括起来的注释的状态转换图。6.用状态转换图表示识别偶数个0或偶数个1的字符串的有穷自动机。得分评卷人五.计算题（每题10分，20分）1、构造下述文法 GS 的自动机： S->A0 A->A0|S1|0 该自动机是确定的吗？若不确定，则对它确定化。2、设计一个状态数最小的DFA,其输入字母表是0,1，它能接受以00或01结尾的所有序列，并给出相应的正规文法。3、对下面的文法G: （2班做） ETE E