北华航天工业学院20xx —20xx 学年第 x 学期
《编译原理》 课程考试卷（x）
考核形式：闭卷 班级： 姓名： 学号：
题号 得分 一 二 三 四 五 六 七 八 九 十 十一 总分 一、填空题（30分，每空2分）
1．由文法开始符号经0步或多步推导产生的文法符号序列是_________。
2．编译器通常经历_______________、___________________、________________
________________、___________________、_________________等几个阶段；其中第一个阶段是以__________为输入，___________为输出；最后一阶段是以_____ ___________为输入，___________为输出。同时___________和___________贯穿编译器的各个阶段。
3．解释器与编译器的主要区别是：_______________________________________。
4．高级语言到低级语言的翻译过程称为_____________。汇编语言到机器语言的翻译过程称为____________。
二、单项选择题（20分，每小题2分）
1．正规表达式(ε|a|b)2表示的集合是（ ）。 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．分析树的内部结点仅由（ ）组成。 A．开始符号和非终结符号 B．终结符号和非终结符号 C．非终结符号 D．终结符号 3．文法 S→(L)|a
L→L，S|S 的终结符号是（ ）。 A．S B．S L C． a , ( ) D．a , ( ) | 4．NFA M所识别的语言是（ ）。
A．0型语言 B．上下文有关语言 C．上下文无关语言 D．正规语言 5．同正规式a*b*等价的文法是（ ）。
A．S→aS|bS|ε B． S→aSb|ε C．S→aS|Sb|ε D．S→abS|ε
6．对LR分析表的构造，不可能存在( )动作冲突。 A．移进/归约 B．归约/归约 C．移进/移进 D.以上都不对 7．LR分析模式中，改变格局变化的动作不包括（ ）。 A．移进 B．匹配终结符 C．归约 D．接受
8．如果一个文法G是二义文法，则必存在某个句子X∈L（G），该句子（ ）。 A．存在两个不同的最右推导和一个最左推导
共 5 页 第 1 页
B．存在两个不同的最左推导和一个最右推导 C．最左推导和最右推导不同
D．存在两个不同的最左推导和两个不同的最右推导 9．一个句型的最左直接短语称为（ ）。 A．句型 B．句子 C．语言 D．句柄 10．下图所能接受的字集所对应的正规式是（ ） 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*）
b 1 b a 3 b a 2 a a 4 b
三、判断题（10分，每小题1分）
（ ）1．一个LL（1）文法是一个无二义性和无回溯文法。 （ ）2．每个非终结符产生的终结符号串都是该语言的子集。
（ ）3．正规式所描述的语言结构均可以用CFG描述，反之也成立。 （ ）4．一个非确定的有限自动机NFA，可以通过多条路识别一个符号串 （ ）5．自动机M和M'的状态数不同，则二者必不等价。 （ ）6．最小化的DFA所识别接受的正规集最小。
（ ）7．一个状态转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。
（ ）8．语法分析时必须先消除文法中的左递归。
（ ）9．确定的自动机和不确定的自动机都能正确的识别正规集。 （ ）10．规范归约是最右推导的逆过程。
四、对于正规式（a∣b）* a (a∣b) (a∣b)
1．画出此正规式的NFA；（5分）
2．构造此正规式的DFA；（5分）
共 5 页 第 2 页
20 —20 学年第 学期 课程考试卷
五、文法G如下：
S→aBcD|cd B→Bb|b D→d|dD
1．改写G为等价的LL(1)文法G'；（5分）
2．求G'中每个非终结符的FIRST集合和FOLLOW集合；（5分） 3．构造预测分析表。（5分）
共 5 页 第 3 页
六、给出接受文法：S→（L）|a L→L，S|S 的活前缀的DFA，并构造LR（0）分 共 5 页 第
4 页 析表。（10分）。
七、证明文法S→AaAb|BbBa A→ε B→ε 是LL（1）文法，但不是SLR（1）文 共 5 页 第
5 页 法（5分）。
