张淑艳+编译原理试题及答案.doc

郑州大学软件技术学院编译原理课程2010-2011学年第二学期期末试题（A）卷题号一二三四总分分数（适用专业：08级所有专业 考试时间：120分钟）合分人： 复查人： 一、 选择题 ：（每空 2 分，共 20 分）（说明：将答案写在试卷后面的答题纸上）分数评卷人1、乔母斯基将文法分为四种类型，即0型、1型、2型和3型，上下文无关文法是_。(A) 0型文法 (B) 1型文法 (C) 2型文法 (D) 3型文法2、在上下文无关文法中，语言是_的集合。 (A) 产生式 (B) 字符串 (C) 句子 (D) 句型3、一个确定有限自动机M是一个五元式 M = (S, , , s0, F)，其中，S表示状态集，表示_，表示_，s0表示唯一的初态，F表示_。(A) 字符串 (B) 从S至S的映射 (C) 开始符号 (D) 有穷字母表 (E) 终态集 (F) 产生式集合4、下列表示含奇数个1的二进制串的正规式为_。 (A) 10*(10*10*)* (B) 0*10*(10*10*)* (C) 1(10*10*)*0* (D) 0*(10*10*)*15、不能被如下状态转换图识别的句子是_。 (A) ab (B) b0b (C) a01b (D) a10b20110ba6、由E E + T, T T * F, 则可推断终结符对(+, *)的优先关系为 _。 (A) + * (B) * + (C) + * (D) * +7、若存在项目 A a.bS (其中a和b是终结符，A和S是非终结符), 则它是_。(A) 移进项目 (B) 归约项目 (C) 接受项目 (D) 待约项目8、编译过程中，以下不是常见的中间语言有_。(A) 后缀式 (B) 抽象语法树 (C) 三元式 (D) 语法树 二、 填空题 ：（每空 2 分，共 20 分）（说明：将答案写在试卷后面的答题纸上）分数评卷人1、编译程序是将_翻译成_的程序。2、有文法G: SaSb, Sab, 它确定的语言是_。3、有如下的状态转换图，与其等价的正规式为_。201baa4、对于文法 SSa | Sbc | b, 取消左递归后为 SbS ，S_。5、在对文法G构造识别活前缀的DFA时，若有一个项目集有两个项目 SrD 和DD i（其中r和i为终结符，S和D为非终结符），则此时存在_冲突。6、对于文法G： SS, SBB, BaB, Bb，现在构造了两个规范LR的项目集I0和I1，请在I1中填出第一个项目的搜索符。I0 SS, #SBB, #BaB, a/bBb, a/bI1 SBB, _BaB, # Bb, #B7、b*(c + d / e)的后缀式为_。8、把if a b or c d then x:= y+1翻译成如下四元式序列，请填出转移到的行的标号。100 ( j , a, b, _)101 ( j , -, -, 102 )102 ( j , c, d, 104 )103 ( j , -, -, _)104 ( +, y , 1, t1 )105 ( : =, t1, - , x)106 三、 简述题 ：（每题 5 分，共 10 分）(说明：将答案写在试卷后面的答题纸上)分数评卷人1、编译程序主要分为哪几个逻辑阶段。2、请说明名字和标识符的区别。四、 计算题 ：（1-5题各10分，共50 分）（说明：将答案写在试卷后面的答题纸上）分数评卷人1、考虑文法S A | SAA 0 | 1 (1) 给出1101的最左推导。(2) 画出1101的语法分析树。2、考虑下面的表达式文法，它包括加和赋值： E E + E | E = E | i(1) 它是二义的吗？(2) 如果是二义的，用某个句型的两个不同的最右推导来说明。3、(1) 把下面的NFA确定化；(2) 将确定后的DFA化简。142aaabbb354、就下面文法S A | SAA 0 | 1 给出一个翻译方案，打印0和1的串的值（如110的值为6，010的值为2）。5、有拓广文法G:(0) S S(1) S A a (2) S b A c(3) S d c(4) S b d a(5) A d活前缀的DFA见下图。(其中，first(S) = b, d, first(A) = d, follow(S) = #, follow(A) = a, c)(1) 请根据这个DFA来构造该文法的SLR(1)分析表(2) 说明该文法为什么不是SLR(1)文法。I0: S .SS .A aS .b A cS .d cS .b d a A .dI4: S d .cA d .I1: S S .I2: S A .aI3: S b .A cS b .d aA .dI8: S d c .I5: S A a .I6: S b A .cI7: S b d .aA d .I10: S b d a .I9: S b A c .SdbdcaAAca郑州大学软件技术学院请填写课程课程试卷答 题 纸（适用专业：请填写适用专业专业 考试时间：请填写所需时间分钟）题号一二三四总分分数合分人： 复查人： 一、 选择题 ：（每空 2 分，共 20 分）分数评卷人1、_ 2、_ 3、_、_、_ 4、_ 5、_ 6、_7、_8、_二、 填空题 ：（每空 2 分，共 20 分）分数评卷人1、