毕节学院期中课程试卷
2009 ~2010学年度第二学期《编译原理》
计科系07级计算机科学与技术专业      班
姓名            学号        得分     
主考教师：黄正鹏 试卷类型：（半期考试）
得分
评卷人
一、填空题（每空1分，共20分）
1．编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析,中间代码生成,代码优化等几个基本阶段,同时还会伴有__表格处理___和 ___出错处理__。
2．若源程序是用高级语言编写的,___目标程序__是机器语言程序或汇编程序,则其翻译程序称为 ___编译程序__ 。
3．编译方式与解释方式的根本区别在于__是否生成目标代码___。
4．对编译程序而言,输入数据是___源程序__, 输出结果是__目标程序___。
5．若两个正规式e1和e2所表示的正规集相同,则e1和e2等价,写作e1=e2。
6．一个句型中的最左简单短语称为该句型的___句柄__。
7．词法分析基于__正则___文法进行，即识别的单词是该类文法的句子。
得分
评卷人
二、是非题（请在括号内，正确的划√，错误的划×）（每个1分，共10分）
1．计算机高级语言翻译成低级语言只有解释一种方式。(×)
2．在编译中进行语法检查的目的是为了发现程序中所有错误。(×)
3．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。 (√ )
4．正则文法其产生式为 A->a ， A->Bb,  A,B∈VN ， a 、 b∈VT 。 (×)
5．每个文法都能改写为 LL(1) 文法。 (√)（2班做）
6.有穷自动机接受的语言是正规语言。 (√)（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 产生的_____的全体是该文法描述的语言。
　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．( ) 词法分析      　 D．( ) 目标代码生成
6．_____是两类程序语言处理程序。
　A．( ) 高级语言程序和低级语言程序        　　B．( ) 解释程序和编译程序
　C．( ) 编译程序和操作系统                  D．( ) 系统程序和应用程序
7． 编译程序是对_____。 
　A．( ) 汇编程序的翻译  　 　 B．( ) 高级语言程序的解释执行 
  C．( ) 机器语言的执行     D．( ) 高级语言的翻译
8． 采用自上而下分析，必须_____。（2班做）
　A．( ) 消除左递归      　 B．( ) 消除右递归
  C．( ) 消除回溯  　    　 D．( ) 提取公共左因子
9．在规范归约中，用_____来刻画可归约串。（2班做）
　A．( )直接短语 　 　 　 　 　 B．( )句柄
  C．( )最左素短语  　 　 　 　D．( )素短语
10．词法分析器用于识别_____。 
　 A．( ) 字符串  　 　B．( )语句
　 C．( )单词　　  　 D．( )标识符
11．文法分为四种类型，即0型、1型、2型、3型。其中0型文法是_____。
　A. ( ) 短语文法    　  B．( ) 正则文法   
　C．( ) 上下文有关文法  D．( ) 上下文无关文法
12．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 _____。源程序能直接执行吗
　A．( ) 句子 　   B．( ) 句型 　C．( ) 单词   　 D．( ) 产生式
得分
评卷人
四、简答题（每小题5分，共30分）
1.高级语言程序有哪两种执行方式？其特点是什么？
    答：高级语言程序有编译程序和解释程序两种执行方式；
编译程序（Compiler）——将高级程序设计语言程序翻译成逻辑上等价的低级语言(汇编语言,机器语言)程序的翻译程序。
解释程序（Interpreter）——将高级程序设计语言写的源程序作为输入，边解释边执行源程序本身，而不产生目标程序的翻译程序。
2、考虑文法G[S]：S→aSbS|bSaS|
(1)试用最左推导说明此文法是二义性的
（2）对于句子abab构造两个相应的最右推导
（3）对于句子abab构造两个相应的分析树
解答：
(1) 句子abab有如下两个不同的最左推导：
S => aSbS => abS =>abaSbS => ababS => abab
    S => aSbS => abSaSbS => abaSbS => ababS => abab
    所以此文法是二义性的。
(2) 句子abab的两个相应的最右推导：
   S => aSbS => aSbaSbS => aSbaSb => aSbab => abab
    S => aSbS => aSb => abSaSb => abSab => abab
(3) 句子abab的两棵分析树：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。