西安邮电学院2007 2008 学年第 二 学期 编译原理 课程期中考试卷（A）考核形式：闭卷 班级： 姓名： 学号： 题号一二三四五六七八九十十一总分得分一、填空题（30分，每空2分）1由文法开始符号经0步或多步推导产生的文法符号序列是_句型_。2编译器通常经历_词法分析_、_语法分析_、_语义分析和中间代码生成_、_优化_、_目标代码生成_等几个阶段；其中第一个阶段是以_源程序_为输入，_单词符号_为输出；最后一阶段是以_中间代码_为输入，_机器语言程序或汇编语言程序_为输出。同时_表格管理_和_出错处理_贯穿编译器的各个阶段。3解释器与编译器的主要区别是：_编译程序生成目标代码，而解释程序不生成目标代码_。4高级语言到低级语言的翻译过程称为_编译_。汇编语言到机器语言的翻译过程称为_汇编_。二、单项选择题（20分，每小题2分）1正规表达式(|a|b)2表示的集合是（ D ）。A，ab，ba，aa，bb Bab，ba，aa，bbCa，b，ab，aa，ba，bbD，a，b，aa，bb，ab，ba2分析树的内部结点仅由（ C ）组成。A开始符号和非终结符号B终结符号和非终结符号C非终结符号 D终结符号3文法S(L)|aLL，S|S 的终结符号是（C）。ASBS LC a , ( )Da , ( ) |4NFA M所识别的语言是（ D ）。A0型语言 B上下文有关语言C上下文无关语言 D正规语言5同正规式a*b*等价的文法是（ C ）。ASaS|bS| B SaSb|CSaS|Sb| DSabS|6对LR分析表的构造，不可能存在( C )动作冲突。A移进/归约B归约/归约 C移进/移进 D.以上都不对7LR分析模式中，改变格局变化的动作不包括（ B ）。A移进 B匹配终结符 C归约 D接受8如果一个文法G是二义文法，则必存在某个句子XL（G），该句子（ ）。 A存在两个不同的最右推导和一个最左推导 共 5 页 第 1 页B存在两个不同的最左推导和一个最右推导 C最左推导和最右推导不同 D存在两个不同的最左推导和两个不同的最右推导9一个句型的最左直接短语称为（ D ）。A句型B句子C语言D句柄10下图所能接受的字集所对应的正规式是（ B ）Aa*b*（aabb）a*b*B（ab）*（aabb）（ab）*C（a*b*）（aabb）（a*b*）D（a*b*）aa（a*b*）（a*b*）bb（a*b*）三、判断题（10分，每小题1分）（ T ）1一个LL（1）文法是一个无二义性和无回溯文法。（ F ）2每个非终结符产生的终结符号串都是该语言的子集。（ F ）3正规式所描述的语言结构均可以用CFG描述，反之也成立。（ T ）4一个非确定的有限自动机NFA，可以通过多条路识别一个符号串（ F ）5自动机M和M的状态数不同，则二者必不等价。（ F ）6最小化的DFA所识别接受的正规集最小。（ F ）7一个状态转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。（ F ）8语法分析时必须先消除文法中的左递归。（ T ）9确定的自动机和不确定的自动机都能正确的识别正规集。 （ T ）10规范归约是最右推导的逆过程。四、对于正规式（ab）* a (ab) (ab)1画出此正规式的NFA；（5分）2构造此正规式的DFA；（5分）共 5 页 第 2 页20 20 学年第 学期 课程考试卷 IIaIb x,1,21,2,31,21,2,31,2,3,41,2,41,21,2,31,21,2,3,41,2,3,41,2,4,y1,2,41,2,3,y1,2,y1,2,3,4,y1,2,3,4,y1,2,4,y1,2,4,y1,2,3,y1,2,y1,2,3,y1,2,3,41,2,41,2,y1,2,31,2Sab012134212356478556678734812 DFA那个图不太好画，在这就不画了五、文法G如下：SaBcD|cdBBb|bDd|dD1改写G为等价的LL(1)文法G；（5分）2求G中每个非终结符的FIRST集合和FOLLOW集合；（5分）3构造预测分析表。（5分）答：1、SaBCD|cd BbB B bB|空 DdD D空|D2、FIRST(S)=a,c FOLLOW(S)=# FIRST(B)=b FOLLOW(B)=c FIRST(B)=b,空 FOLLOW(B)=cFIRST(D)=d FOLLOW(D)=# FIRST(D)=d,空 FOLLOW(D)=#3、预测分析表abcd#SSaBcDScdBBbBBB bBB 空DDdDDD DD 空共 5 页 第 3 页六、给出接受文法：S（L）|a LL，S|S 的活前缀的DFA，并构造LR（0）分析表。（10分）。解：将文法GS拓广为文法GS: GS:(0)S S (1)S(L) (2)Sa (3)LL,S (4)LS状态actiongotoa(),#SL0S3S211all2S3S2543r 2r 2r 2r 2r 24S6S75r 4r 4r 4r 4r 46r 1r 1r 1r 1r 17S3S288r 3r 3r 3r 3r 3共 5 页 第 4 页七、证明文法SAaAb|BbBa A B 是LL（1）文法，但不是SLR（1）文法（5分）。证明：非终结符S产生的2个不同的产生式 S1 AaAb S2BbBa 得FIRST(S1)=空,a FIRST(S2)=空,b 且FIRST(S1)FIRST(S2)=空集 又因为S为无左递归，无公共左因子S是LL(1)文法GS的拓广文法S S SAaAb SBbBa A 空 B空 其DFA中 其中：FLLOW(A)=a,b FOLLOW(B)=a,b FOLLOW(A) FOLLOW(B)空集S文法有规约-规约冲突，不能由SLR（1）解决S不是SLR（1）文法共 5 页 第 5 页