编译原理学期期考试.doc

得分 评卷人 一、填空题（每空2分，共20分） 1．编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析,间代码生成,代码优化等几个基本阶段,同时还会伴有___________和 ___________。 2．若源程序是用高级语言编写的,____________是机器语言程序或汇编程序,则其翻译程序称为 ______________ 。 3．编译方式与解释方式的根本区别在于_________________。 4．对编译程序而言,输入数据是_________________, 输出结果是___________________。 ． 6．一个句型中的最左简单短语称为该句型的____________。．词法分析基于_____________文法进行，即识别的单词是该类文法的句子。、是非题（请在括号内，正确的划√，错误的划×）（每个分，共0分） 1．计算机高级语言翻译成低级语言只有解释一种方式。() 2．在编译中进行语法检查的目的是为了发现程序中所有错误。() 3．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。 () 4．正则文法其产生式为 A-a ， A-Bb,? A,BVN ， a 、 bVT 。 () 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．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． 系统程序和应用程序 ． 编译程序是对_____。? 　A． 汇编程序的翻译 ? 　 　 B． 高级语言程序的解释执行　　??C． 机器语言的执行 　　　　D．高级语言的翻译 ． 采用自上而下分析，必须_____。 　A． 消除左递归? 　　　　　 B．消除右递归??C． 消除回溯 ?　　　　　　 D． 提取公共左因子 ．词法分析器用于识别_____。? 　 A． 字符串 ? 　 　B．语句　 C．单词　　　　　 D．标识符 ．文法分为四种类型，即0型、1型、2型、3型。其中0型文法是_____。 　A.短语文法 ???　　　 B． 正则文法 ??? 　C． 上下文有关文法　　 D． 上下文无关文法 ．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 _____。 　A． 句子 　 　　B． 句型 　C． 单词 　　　 D． 产生式四、简答题（分） →aSbS|bSaS| (1)试用最左推导说明此文法是二义性的 （2）对于句子abab构造两个相应的最右推导 （3）对于句子abab构造两个相应的分析树 3. 构造正规式相应的 NFA : 1(0|1)*101 已知文法 G[E] 为： ????E→T|E+T|E-T ????T→F|T*F|T/F ????F→E) |i ① 该文法的开始符号（识别符号）是什么？  请给出该文法的终结符号集合 VT 和非终结符号集合 VN 。  找出句型 T+T*F+i 的所有短语、简单短语和句柄。五.计算题（0分） 构造下述文法 G[S] 的自动机： ①S-A0 ②A-A0|S1|0 该自动机是确定的吗？若不确定，则对它确定化。→TE’ E’→+E| ( T→FT’ T’→T| ( F→