编译原理小测验(有答案).doc

一、选择题1. 词法分析器的输入（ ）A单词符号B源程序C语法单位D目标程序2.构造编译程序应该掌握( )。 A. 源程序 B.目标语言 C.目标代码生成 D.以上三者都要3. 编译程序绝大多数时间花在（ ）。 A.出错处理 B.词法分析 C.目标代码生成 D.表格管理4. 编译程序的各阶段都涉及到（ ）。 A.词法分析 B.表格管理 C. 语法分析 D. 语义分析5. 解释程序和编译程序的区别是（ ）之间的转换。 A.是否生成中间代码 B.加工的对象不同 C. 使用的实现技术不同 D.是否生成目标代码6. 一个上下文无关文法G包含四个组成部分，依次为：一组 （G），一组（H），一个（E）和一组（C）。A字符串B. 字母数字串 C.产生式 D.结束符号 E.开始符号 F.文法 G.非终结符 H.终结符7. 一个语言的文法是（ ）。 A唯一的 B. 不唯一的 C.数量有限的8. 编译程序中的语法分析器接受以（ ）为单位的输入，并产生有关信息供以后各阶段使用。 A.表达式 B.产生式 C.单词 D.语句9. 文法的二义性和语法的二义性是两个（ ）的概念。 A.不同 B.相同 C.无法判断10、如果L(M)=L(M），则M与M（ ）A等价BM与M都是二义的CM与M都是无二义的D他们的状态数相等11、如果文法G是无二义的，则它的任何句子（ ）A最左推导和最右推导对应的语法树必定相同B最左推导和最右推导对应的语法树可能不同C最左推导和最右推导必定相同D可能存在两个不同的最左推导，但它们对应的语法树相同12、给定文法, A- bA | cc, 下面哪些符号串可由其推导出（ ）。 cc b*cc b*cbcc bccbcc bbbcc可选项有：a.b.c.d.e.13. 若一个文法是递归的，则它所产生语言的句子个数（ ）。a.必定是无穷的 b.是有限个的 c.根据具体情况而定14. Chmosky的3型语言是这样一种语言，其产生式限制为_。a.A- b. A-a A-aB c.- d. A-15. 词法分析器的输出结果是（ ）。A、单词自身值B、单词在符号表中的位置C、单词的种别编码D、单词的种别编码和自身值16、文法：G：SxSx | y所识别的语言是（ ）。A、xyxB、（xyx）*C、x+yx+D、xnyxn |（n0）二、判断题设有文法GI: I-I1/I0/Ia/Ic/a/b/c 判断下面符号串中哪些是该文法的句子. (1) ab0 (2)a0c01 (3)aaa (4)bc10 (5)aabc (6)bbca答：(1)错误 (2)正确 (3)正确 (4)正确 (5)错误 (6)错误 三、问答题1. 什么是正规式，正规式的递归定义是什么？答：正规式也称正则表达式，也是表示正规集的工具。也是我们用以描述单词符号的方便工具。下面是正规式和它所表示的正规集的递归定义。 设字母表为，辅助字母表为=，|，*，(，) (1). 和都是上的正规式，它们所表示的正规集分别为和 (2). 任意a，a是上的一个正规式， 它所表示的正规集为a (3). 若e1，e2都是上的一个正规式， 它们所表示的正规集分别为L(e1)和L(e2)，那么e1|e2，e1e2和，( e1)也都是正规式, 它们所表示的正规集分别为L(e1)L(e2), L(e1) L(e2)和，L(e1) (4). 仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的字集才是上正规集。2. 何谓二义性文法？试举一例说明。答：若文法G的一个句子对应有两棵或两棵以上不同的推导树，则称该句子是二义性的。产生二义性句子的文法称为二义性文法，否则该文法是无二义性的。3. 什么是有穷自动机？什么是确定的有穷自动机？答：有穷自动机(也称有限自动机)作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。 有穷自动机分为两类：确定的有穷自动机(Deterministic Finite Automata)和不确定的有穷自动机(Nondeterministic Finite Automata)，下面我们分别给出确定有穷自动机和不确定的有穷自动机的定义，有关概念及不确定的有穷自动机的确定化，确定的有穷自动机的化简等算法。确定的有穷自动机（DFA） 一个确定的有穷自动机（DFA）是一个五元组：M=（K，f，S，Z），其中(1) K是一个有穷集，它的每个元素称为一个状态；(2) 是一个有穷字母表，它的每个元素称为一个输入字符，所以也称为输入符号字母表；(3) f是转换函数，是在KK上映像，即，如f（ ，a）=（K，K），就意味着，当前状态为，输入字符为a时，将转换到下一状态，我们把称作的一个后继状态；(4) SK是唯一的一个初态；(5) ，是终态集，终态也称可接受状态或结束状态。四、综合题ETF(E)E+TFiTT*F1. 对于文法G(E): ET|E+TTF|T*FF(E)|i1. 写出句型(T*F+i)的最右推导并画出语法树。2. 写出上述句型的短语，直接短语、句柄。答：1. ETF(E) (E+T) (E+F) (E+i) (T+i) (T*F+i) 2. 短语：(T*F+i), T*F+i, T*F, i直接短语：T*F, i句柄：T*F2. 设S=0，1上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA。答：构造相应的正规式：(0|1)*1(0|1) NFA: 1 110432 e e e e 1 0 0确定化：I0,1,21,21,2,31,21,21,2,31,2,31,2,41,2,3,41,2,41,21,2,31,2,3,41,2,41,2,3,4 0 143210 0 1 0 0 0 1 1