西邮《编译原理》考试试卷-附带参考答案

西安邮电学院2007—2008学年第二学期《编译原理》课程期中考试卷（A）考核形式：闭卷班级：姓名：学号：一、填空题（30分，每空2分）1．由文法开始符号经0步或多步推导产生的文法符号序列是__句型__。2．编译器通常经历___词法分析______、____语法分析_______、__语义分析和中间代码生成___、____优化___、__目标代码生成___等几个阶段；其中第一个阶段是以__源程序__为输入，_单词符号_为输出；最后一阶段是以_中间代码_为输入，_机器语言程序或汇编语言程序__为输出。同时_表格管理_和_出错处理_贯穿编译器的各个阶段。3．解释器与编译器的主要区别是：____编译程序生成目标代码，而解释程序不生成目标代码____。4．高级语言到低级语言的翻译过程称为__编译__。汇编语言到机器语言的翻译过程称为__汇编__。二、单项选择题（20分，每小题2分）1．正规表达式(ε|a|b)2表示的集合是（D）。A．{ε，ab，ba，aa，bb}B．{ab，ba，aa，bb}C．{a，b，ab，aa，ba，bb}D．{ε，a，b，aa，bb，ab，ba}2．分析树的内部结点仅由（C）组成。A．开始符号和非终结符号B．终结符号和非终结符号C．非终结符号D．终结符号3．文法S→(L)|aL→L，S|S的终结符号是（C）。A．SB．SLC．a,()D．a,()|4．NFAM所识别的语言是（D）。A．0型语言B．上下文有关语言C．上下文无关语言D．正规语言5．同正规式a*b*等价的文法是（C）。A．S→aS|bS|εB．S→aSb|εC．S→aS|Sb|εD．S→abS|ε6．对LR分析表的构造，不可能存在(C)动作冲突。A．移进/归约B．归约/归约C．移进/移进D.以上都不对7．LR分析模式中，改变格局变化的动作不包括（B）。A．移进B．匹配终结符C．归约D．接受8．如果一个文法G是二义文法，则必存在某个句子X∈L（G），该句子（）。A．存在两个不同的最右推导和一个最左推导题号一二三四五六七八九十十一总分得分共5页第1页B．存在两个不同的最左推导和一个最右推导C．最左推导和最右推导不同D．存在两个不同的最左推导和两个不同的最右推导9．一个句型的最左直接短语称为（D）。A．句型B．句子C．语言D．句柄10．下图所能接受的字集所对应的正规式是（B）A．a*b*（aa︱bb）a*b*B．（a︱b）*（aa︱bb）（a︱b）*C．（a*︱b*）（aa︱bb）（a*︱b*）D．（a*︱b*）aa（a*︱b*）︱（a*︱b*）bb（a*︱b*）bbbbaaa1234a三、判断题（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．规范归约是最右推导的逆过程。四、对于正规式（a∣b）*a(a∣b)(a∣b)1．画出此正规式的NFA；（5分）2．构造此正规式的DFA；（5分）共5页第2页20—20学年第学期课程考试卷IIaIb{x,1,2}{1,2,3}{1,2}{1,2,3}{1,2,3,4}{1,2,4}{1,2}{1,2,3}{1,2}{1,2,3,4}{1,2,3,4}{1,2,4,y}{1,2,4}{1,2,3,y}{1,2,y}{1,2,3,4,y}{1,2,3,4,y}{1,2,4,y}{1,2,4,y}{1,2,3,y}{1,2,y}{1,2,3,y}{1,2,3,4}{1,2,4}{1,2,y}{1,2,3}{1,2}DFA那个图不太好画，在这就不画了五、文法G如下：S→aBcD|cdB→Bb|bD→d|dD1．改写G为等价的LL(1)文法G'；（5分）2．求G'中每个非终结符的FIRST集合和FOLLOW集合；（5分）3．构造预测分析表。（5分）答：1、S→aBCD|cdB→bB’B’→bB’|空D→dD’D’→空|D2、FIRST(S)={a,c}FOLLOW(S)={#}FIRST(B)={b}FOLLOW(B)={c}FIRST(B’)={b,空}FOLLOW(B’)={c}Sab012134212356478556678734812FIRST(D)={d}FOLLOW(D)={#}FIRST(D’)={d,空}FOLLOW(D’)={#}3、预测分析表abcd#SS→aBcDS→cdBB→bB’B’B’→bB’B’→空DD→dD’D’D’→DD’→空共5页第3页六、给出接受文法：S→（L）|aL→L，S|S的活前缀的DFA，并构造LR（0）分析表。（10分）。解：将文法G[S]拓广为文法G’[S]:G’[S]:(0)S’→S(1)S→(L)(2)S→a(3)L→L,S(4)L→S状态actiongotoa(),#SL0S3S211all2S3S2543r2r2r2r2r24S6S75r4r4r4r4r46r1r1r1r1r17S3S288r3r3r3r3r3共5页第4页七、证明文法S→AaAb|BbBaA→εB→ε是LL（1）文法，但不是SLR（1）文法（5分）。证明：非终结符S产生的2个不同的产生式S1→AaAbS2→BbBa得FIRST(S1)={空,a}FIRST(S2)={空,b}且FIRST(S1)∩FIRST(S2)=空集又因为S为无左递归，无公共左因子∴S是LL(1)文法G[S]的拓广文法S’→SS→AaAbS→BbBaA→空B→空其DFA中其中：FLLOW(A)={a,b}FOLLOW(B)={a,b}∵FOLLOW(A)∩FOLLOW(B)≠空集∴S文法有规约-规约冲突，不能由SLR（1）解决∴S不是SLR（1）文法共5页第5页