资源描述：
《编译原理模拟试卷及答案集.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、1．由文法开始符号经0步或多步推导产生的文法符号序列是__句型__。2．编译器通常经历___词法分析______、____语法分析_______、__语义分析和中间代码生成___、____优化___、__目标代码生成___等几个阶段；其中第一个阶段是以__源程序__为输入，_单词符号_为输出；最后一阶段是以_中间代码_为输入，_机器语言程序或汇编语言程序__为输出。同时_表格管理_和_出错处理_贯穿编译器的各个阶段。3．解释器与编译器的主要区别是：____编译程序生成目标代码，而解释程序不生成目标代码____。4．高级语
2、言到低级语言的翻译过程称为__编译__。汇编语言到机器语言的翻译过程称为__汇编__。二、单项选择题（20分，每小题2分）1．正规表达式(ε
3、a
4、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)
5、aL→L，S
6、S的终结符号是（C）。A．SB．SLC．a,()D．a,()
7、4．
8、NFAM所识别的语言是（D）。A．0型语言B．上下文有关语言C．上下文无关语言D．正规语言5．同正规式a*b*等价的文法是（C）。A．S→aS
9、bS
10、εB．S→aSb
11、εC．S→aS
12、Sb
13、εD．S→abS
14、ε6．对LR分析表的构造，不可能存在(C)动作冲突。A．移进/归约B．归约/归约C．移进/移进D.以上都不对7．LR分析模式中，改变格局变化的动作不包括（B）。A．移进B．匹配终结符C．归约D．接受8．如果一个文法G是二义文法，则必存在某个句子X∈L（G），该句子（）。A．存在两个不同的最右推导和一个最左推导B．存在
15、两个不同的最左推导和一个最右推导C．最左推导和最右推导不同D．存在两个不同的最左推导和两个不同的最右推导9．一个句型的最左直接短语称为（D）。A．句型B．句子C．语言D．句柄三、判断题（10分，每小题1分）（T）1．一个LL（1）文法是一个无二义性和无回溯文法。（F）2．每个非终结符产生的终结符号串都是该语言的子集。（F）3．正规式所描述的语言结构均可以用CFG描述，反之也成立。（T）4．一个非确定的有限自动机NFA，可以通过多条路识别一个符号串（F）5．自动机M和M'的状态数不同，则二者必不等价。5（F）6．最小化的D
16、FA所识别接受的正规集最小。（F）7．一个状态转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。（F）8．语法分析时必须先消除文法中的左递归。（T）9．确定的自动机和不确定的自动机都能正确的识别正规集。（T）10．规范归约是最右推导的逆过程。文法G如下：S→aBcD
17、cdB→Bb
18、bD→d
19、dD1．改写G为等价的LL(1)文法G'；（5分）2．求G'中每个非终结符的FIRST集合和FOLLOW集合；（5分）3．构造预测分析表。（5分）答：1、S→aBCD
20、cdB→bB’B’→bB’
21、空D→dD’D’→空
22、
23、D2、FIRST(S)={a,c}FOLLOW(S)={#}FIRST(B)={b}FOLLOW(B)={c}FIRST(B’)={b,空}FOLLOW(B’)={c}FIRST(D)={d}FOLLOW(D)={#}FIRST(D’)={d,空}FOLLOW(D’)={#}3、预测分析表abcd#SS→aBcDS→cdBB→bB’B’B’→bB’B’→空DD→dD’D’D’→DD’→空证明文法S→AaAb
24、BbBaA→εB→ε是LL（1）文法，但不是SLR（1）文法（5分）。证明：非终结符S产生的2个不同的产生式S1→
25、AaAbS2→BbBa得FIRST(S1)={空,a}FIRST(S2)={空,b}且FIRST(S1)∩FIRST(S2)=空集又因为S为无左递归，无公共左因子∴S是LL(1)文法G[S]的拓广文法S’→SS→AaAbS→BbBaA→空5B→空其DFA中其中：FLLOW(A)={a,b}FOLLOW(B)={a,b}∵FOLLOW(A)∩FOLLOW(B)≠空集∴S文法有规约-规约冲突，不能由SLR（1）解决∴S不是SLR（1）文法1、符号表项的组织常采用线性法、二分法和（）。2、整个编译过程可以划分成五个阶段：（）、
26、语法分析阶段、（）、（）和目标代码生成阶段。5、语言翻译常用的两种形式是（）和（）。6、词法分析器输出的是单词符号，语法分析器输出的是（）。二、选择题：（每空2分，共10分）1、3型文法是（），（）是语法分析使用的文法。A．短语文法B.上下文有关文法C.上下文无关文法D.正规文法2、语法分析是依据语言的（）规则进行的
