编译原理复习题一、选择题1、编译原理是对(C)。

A、机器语言的执行B、汇编语言的翻译C、高级语言的翻译D、高级语言程序的解释执行2、(A)是一种典型的解释型语言。

A．BASIC B．C C．FORTRAN D．PASCAL3、把汇编语言程序翻译成机器可执行的目标程序的工作是由(B)完成的。

A. 编译器B. 汇编器C. 解释器D. 预处理器4、用高级语言编写的程序经编译后产生的程序叫(B)A．源程序 B．目标程序C．连接程序D．解释程序5、(C)不是编译程序的组成部分。

A.词法分析程序B.代码生成程序C.设备管理程序D.语法分析程序6、通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成等六个部分，还应包括(C)。

A．模拟执行器B．解释器 C．表格处理和出错处理D．符号执行器7、编译程序绝大多数时间花在(D)上。

A．出错处理B．词法分析C．目标代码生成D．表格管理8、源程序是句子的集合，(B)可以较好地反映句子的结构。

A. 线性表B. 树C. 完全图D. 堆栈9、词法分析器的输出结果是(D)。

A、单词自身值B、单词在符号表中的位置C、单词的种别编码D、单词的种别编码和自身值10、词法分析器不能(D)A. 识别出数值常量B. 过滤源程序中的注释C. 扫描源程序并识别记号D. 发现括号不匹配11、文法：G：S→xSx | y所识别的语言是(D)。

A、xyxB、(xyx)*C、x*yx*D、x n yx n (n≥0)12、如果文法G是无二义的，则它的任何句子α(A)A．最左推导和最右推导对应的语法树必定相同B．最左推导和最右推导对应的语法树可能不同C．最左推导和最右推导必定相同D．可能存在两个不同的最左推导，但它们对应的语法树相同13、正则文法(A)二义性的。

A. 可以是B. 一定不是C. 一定是14、(B)这样一些语言，它们能被确定的有穷自动机识别，但不能用正则表达式表示。

A. 存在B. 不存在C. 无法判定是否存在15、给定文法A→bA | ca，为该文法句子的是(C)A. bbaB. cabC. bcaD. cba16、设有文法G[S]：S S1|S0|Sa|Sc|a|b|c，下列符号串中是该文法的句子有(D)A. ab0B. a0c01C. a0b0aD. bc1017、文法G产生的(D)的全体是该文法描述的语言。

A．句型 B. 终结符集 C. 非终结符集 D.句子18、若文法G定义的语言是无限集，则文法必然是(A)A．递归的 B. 上下文无关的 C. 二义性的 D. 无二义性的19、描述一个语言的文法是(B)A．唯一的 B. 不唯一的 C. 可能唯一20、一个文法所描述的语言是(A)A．唯一的 B. 不唯一的 C. 可能唯一21、采用自上而下分析，必须(A)。

A、消除回溯B、消除左递归C、消除右递归D、提取公共左因子22、编译过程中，语法分析器的任务是(A)①分析单词的构成②分析单词串如何构成语句③分析语句是如何构成程序④分析程序的结构A. ②③B. ④C. ①②③④D. ②③④23、词法分析器的输入是( A)。

A．符号串B．源程序C．语法单位D．目标程序24、两个有穷自动机等价是指它们的(C)。

A．状态数相等B．有向弧数相等C．所识别的语言相等D．状态数和有向弧数相等25、若状态k含有项目“A→α·”，且仅当输入符号a∈FOLLOW(A)时，才用规则“A →α”归约的语法分析方法是(D)。

A．LALR分析法B．LR(0)分析法C．LR(1)分析法D．SLR(1)分析法26、若a为终结符，则A→α ·aβ为(B)项目。

A．归约B．移进C．接受D．待约27、在使用高级语言编程时,首先可通过编译程序发现源程序的全部和部分(A)错误。

A. 语法B. 语义C. 语用D. 运行28、乔姆斯基(Chomsky)把文法分为四种类型，即0型、1型、2型、3型。

其中3型文法是(B)A. 非限制文法B. 正则文法C. 上下文有关文法D. 上下文无关文法29、一个句型中的(A)称为该句型的句柄。

A. 最左直接短语B. 最右直接短语C. 终结符D. 非终结符30、在自底向上的语法分析方法中，分析的关键是(D)A. 寻找句柄B. 寻找句型C. 消除递归D. 选择候选式31、在自顶向下的语法分析方法中，分析的关键是(C)A. 寻找句柄B. 寻找句型C. 消除递归D. 选择候选式32、在LR分析法中，分析栈中存放的状态是识别规范句型(C)的DFA状态。

A.句柄B. 前缀C. 活前缀D. LR(0)项目33、一个上下文无关文法G包括四个组成部分，它们是一组非终结符号，一组终结符号，一个开始符号，以及一组(B)A. 句子B. 产生式C. 单词D. 句型34、词法分析器用于识别(C)A. 句子B. 产生式C. 单词D. 句型35、编译程序是一种(B)A. 汇编程序B. 翻译程序C. 解释程序D. 目标程序36、按逻辑上划分，编译程序第三步工作是(A)A. 语义分析B. 词法分析C. 语法分析D. 代码生成37、在语法分析处理中，FIRST集合、FOLLOW集合均是(B)A. 非终结符集B.终结符集C. 字母表D. 状态集38、编译程序中语法分析器接收以(A)为单位的输入。

A. 单词B. 表达式C. 产生式D. 句子39、编译过程中，语法分析器的任务就是(B)A. 分析单词是怎样构成的B. 分析单词串是如何构成语句和说明的C. 分析语句和说明是如何构成程序的D. 分析程序的结构40、若一个文法是递归的，则它所产生的语言的句子(A)。

A.是无穷多个B.是有穷多个C.是可枚举的D.个数是常量41、识别上下文无关语言的自动机是(C)A. 下推自动机B. NFAC. DFAD. 图灵机42、编译原理各阶段工作都涉及(B)A.词法分析B.表格管理C.语法分析D.语义分析43、正则表达式R1和R2等价是指(C)A. R1和R2都是定义在一个字母表上的正则表达式B. R1和R2中使用的运算符相同C. R1和R2代表同一正则集D. R1和R2代表不同正则集44、已知文法G[S]:S→A1，A→A1|S0|0。

与G 等价的正规式是(C)A. 0(0|1)*B. 1*|0*1C. 0(1|10)*1D. 1(10|01)*045、与(a|b)*(a|b)等价的正规式是(C)。

A.a*| b*B.(ab)*(a|b)C. (a|b)(a|b)*D.(a|b)*46、(D)文法不是LL(1)的。

A. 递归B. 右递归C. 2型D.含有公共左因子的47、给定文法A→bA|cc，则符号串①cc ②bcbc ③bcbcc ④bccbcc ⑤bbbcc中，是该文法句子的是(D)A. ①B. ③④⑤C. ②④D. ①⑤48、L R(1)文法都是()A. 无二义性且无左递归B. 可能有二义性但无左递归C. 无二义性但可能是左递归D. 可以既有二义性又有左递归49、文法E→E+E|E*E|i的句子i*i+i*i有(C)棵不同的语法树。

A. 1B. 3C. 5D.750、文法S→aaS|abc 定义的语言是(C)。

A.{a2kbc|k>0}B.{akbc|k>0}C.{a2k-1bc|k>0}D.{akakbc|k>0}51、若B为非终结符，则A→α.Bβ为(D)。

A.移进项目B.归约项目C.接受项目D.待约项目52、同心集合并可能会产生新的(D)冲突。

A.二义B.移进/移进C.移进/归约D.归约/归约53、就文法的描述能力来说，有(C)A．SLR(1) ⊂ LR(0) B．LR(1) ⊂ LR(0) C．SLR(1) ⊂LR(1) D．无二义文法⊂LR(1)54、如图所示自动机M，请问下列哪个字符串不是M所能识别的(D)。

A. bbaaB. abbaC. ababD. aabb55、有限状态自动机能识别(C)A.上下文无关语言B.上下文有关语言C.正规语言D.0型文法定义的语言56、已知文法G是无二义的，则对G的任意句型α(A)A.最左推导和最右推导对应的语法树必定相同B.最左推导和最右推导对应的语法树可能相同C.最左推导和最右推导必定相同D.可能存在两个不同的最左推导，但他们对应的语法树相同57、(B)不是DFA的成分A.有穷字母表B.多个初始状态的集合C.多个终态的集合D.转换函数58、与逆波兰式(后缀表达式)ab+c*d+对应的中缀表达式是(B)A. a+b+c*dB. (a+b)* c+dC. (a+b)* (c+d)D. a+b*c+d59、后缀式abc−+−d+可用表达式(B)来表示。

A．(− (a+b)−c)+d B．−(a+(b−c))+d C．−(a−(b+c))+d D．(a−(−b+c))+d 60、表达式A*(B-C*(C/D))的后缀式为(B)。

A．ABC-CD/** B．ABCCD/*-* C．ABC-*CD/* D．以上都不对61、(D)不是NFA的成分。

A. 有穷字母表B. 初始状态集合C. 终止状态集合D. 有限状态集合62、二、简答题1、编译程序将高级语言的源程序翻译成低级语言的程序称作编译程序。

2、编译程序和解释程序有哪些区别？解释程序是源程序的一个执行系统，而编译程序是源程序的一个转换系统；解释器直接由源程序得到运行结果，而编译器是生成等价于源程序的某种目标机程序。

3、词法分析从左到右地一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，识别出一个个单启这过程，称为词法分析。

4、最左推导在推导过程中，如果在推导的任何一步α=>β，其α，β是句型，都是对α中的最左非终结符进行替换，则这种推导为最左推导。

5、合法的日期表示有如下三种形式，请给出描述日期的正规式。

年.月.日，如1992.08.12日月年，如12 08 1992月/日/年，如08/12/1992解：digit=[0-9]year =(digit)(digit)(digit)(digit)month=0[1-9]|1[0-2]day =0[1-9]|[1-2][0-9]|3[0-1]date1=year.month.daydate2=day month yeardate3=month/day/yeardate =date1|date2|date36、First集设G=（Vt,Vn,S,P）是上下文无关文法α是任意的文法符号串，FIRST(α)是从α推导出的串的开始符号的终结符集合即First(α)={a|α=>*aβ，a∈Vt,α，β∈V*}若α=>*ε，则规定ε∈first(α)。

7、什么是文法？什么是语言？什么是上下文无关文法？8、编译程序有哪些主要构成分？各自的主要功能是什么？9、什么是NFA?什么是DFA?有限自动机分为两类：确定的有限自动机(DFA)和非确定的有限自动机(NFA)。