期末考试编译原理试题
德州学院期末考试试题
（ 1 至学年第学期）
课程名称：考试对象：试卷类型：（1）考试时间：分钟
一、填空题：（10分，第1小题每2个1分，其余每空1分）
1、编译程序一般含有八部分，分别是、、
、、、、、。
2、编译程序与解释程序的根本区别是
3、一个上下文无关文法G包括四个组成部分依次为：一组_____、一个_____、一组_____、一组______。
4、设G是一个文法，S是文法的开始符号，如果S?* X，则称X是。
二、选择题（本大题共15小题，每小题1分，共15分）
1、编译程序生成的目标程序是机器语言程序。
A、一定
B、不一定
2、设有文法G[S]=（{b},{S,B},S,{S→b|bB, B→bS}）,该文法描述的语言是。
A、b i | i≥0
B、b2i | i≥0
C、b2i+1 | i≥0
D、b2i+1 | i≥1
3、设有文法G[S]：S→S*S|S+S|（S）|a
该文法二义性文法
A、是
B、不是
C、无法判断
4、汇编程序是将______翻译成______；编译程序是将_______翻译成__________。
A、汇编语言程序
B、机器语言程序
C、高级语言程序
D、汇编语言或机器语言程序
5、给定文法A→bA|cc, 下面符号串中，为该文法句子的是。
①cc ②bcbc ③bcbcc ④bccbcc ⑤bbbcc
A、①
B、①③④⑤
C、①⑤
D、①④⑤
E、①②③④⑤
6、语法分析的常用方法是。
①自顶向下②自底向上③自左向右④自右向左
A、①②③④
B、①②
C、③④
D、①②③
7、已知语言L={a n bb n|n≥1}，则下述文法中，可以产生语言L
A、Z→aZb|aAb|b A→aAb|b
B、A→aAb A→b
C、Z→AbB A→aA|a B→bB|b
D、Z→aAb A→aAb|b
8、下列正规表达式中________与(a|b)*(c|d)等价。
A、（a*|b*）(c|d)
B、（a*|b*）*(c|d)
C、(ab)*(d|c)
D、（a*b*）(cd)
9、算符优先分析法每次都是对进行归约。
A、最左短语
B、直接短语
C、句柄
D、素短语
E、最左素短语
10、简单优先分析法每次都是对进行归约
A、最左短语
B、直接短语
C、句柄
D、素短语
E、最左素短语
11、下列文法G[S] ]：S→AA A→Aa|a不是LR（1）文法，理由是
A.、FIRST(S)∩FIRST（A）≠?B、FIRST（A）∩FOLLOW（A）≠?
C、FIRST（Aa）∩FIRST（a）≠?
D、都不是
12、设有文法G[E]：E→E*E|E+E|（E）|a 该文法LR（1）文法
A、是
B、不是
C、无法判断
13、对于文法G[A]：A→aABe|Ba B→dB|ε有人说，因为FIRST（aABe）∩FOLLOW（A）≠?并且FIRST（Ba）∩FOLLOW（A）≠?，所以文法G[A]不是LL（1）文法。这种说法
A、正确
B、不正确
14、素短语是指_______的短语。
①至少包含一个符号
②至少包含一个非终结符号
③至少包含一个终结符号
④除自身外不再包含其它终结符号
⑤除自身外不再包含其它非终结符号
⑥除自身外不再包含其它短语
⑦除自身外不再包含其它素短语
可选项有：
A、①④
B、①⑤
C、①⑥
D、②④
E、③⑤
F、③⑦
G、②⑦
15、表达式A*（B-C*（C/D））的逆波兰式为
A、ABC-CD/**
B、ABCCD/*-*
C、ABC-*CD/*
D、都不正确
三、简答题（共35分）
1、(10分)现有文法G[E]:
E→E+T|E-T|T T→T*F|T/F|F F→(E)|i
画出句型E+F*（E+i）的语法树,找出它的短语，直接短语，句柄和素短语
2、(5分)对下面的文法G[S]构造状态转换图,并说明符号串aaba是否是该文法接受
的句子： S→aA S→B A→abS A→bB B→b B→cC C→D D→d D→bB
3、(10分)将下面具有ε的NFA确定化
4、(5分)求出下列文法所产生语言对应的正规式。S→aA A→bA|aB|b B→aA。
5、(5分)构造识别下面正规式的NFA （a|b）*ba。
四、综合题（共40分）
1、（10分）下面的文法G[S]是否是LL（1）文法，说明理由，构造LL（1）分析表
S→aBc|bAB A→aAb|Bb B→cB|ε
2、（5分）消除下列文法的左递归，消除左递归后判断是否是LL（1）文法。
S→SaB|bB A→S|a B→Ac
3、（5分）构造下面算符文法的优先矩阵，判断是否是算符优先文法
S→A[] A→[ A→aA A→B] B→a
4、（10分）将表达式A+B*(C-D)-E/F↑G分别表示为三元式、四元式、逆波兰式序列
5、（10分）现有文法如下：
S→aS|bS|a 判断该文法是哪一类LR文法，说明理由，并构造相应的分析表。