期末考试编译原理试题
一、选择题（本大题共20小题，每小题1分，共20分）
1、描述一个语言的文法是___________。
a、唯一的
b、不是唯一的
c、个数有限的
2、简单优先分析法每次都是对___________进行归约。
a、最左短语
b、直接短语
c、句柄
d、素短语
e、最左素短语
3、设有文法G[I]：
I→I0 |I1 |Ia |Ic |a |b |c
下列符号串中是该文法的句子的有___________________。
①ab0 ②a0c01 ③aaa ④bc10
可选项有
a、①
b、②③④
c、③④
d、①②③④
4、LR（K）文法________二义性的。
a、都是
b、都不是
c、不一定都是
5、一个上下文无关文法G包括四个组成部分依次为：一组_____、一个_____、一组_____、一组______。
a、字符串
b、字母数字串
c、产生式
d、结束符号
e、开始符号
f、文法
g、非终结符号
h、终结符号
6、文法G所描述的语言是__________的集合
a、文法G的字汇表V中所有符号组成的符号串
b、文法G的字汇表V的闭包V*中的所有符号串
c、由文法的开始符号推出的所有符号串
d、由文法的开始符号推出的所有终结符号串。
7、设有文法G[Z]：Z→Z*Z|Z+Z|（Z）|a 该文法_______二义性文法
a、是
b、不是
c、无法判断
8、语法分析的常用方法是_________：
①自顶向下②自底向上③自左向右④自右向左
可选项有：
a、①②③④
b、①②
c、③④
d、①②③
9、LR（K）文法是_________。
a、从左到右分析，共经过K步的一种编译方法。
b、从左到右分析，每次向前预测K步的一种编译方法。
c、从左到右分析，每次向貌似句柄的符号串后看K个输入符号的一种编译方法。
d、从左到右分析，每次走K步的一种编译方法。
10、素短语是指_______的短语。
①至少包含一个符号
②至少包含一个非终结符号
③至少包含一个终结符号
④除自身外不再包含其它终结符号
⑤除自身外不再包含其它非终结符号
⑥除自身外不再包含其它短语
⑦除自身外不再包含其它素短语
可选项有：
a、①④
b、①⑤
c、①⑥
d、②④
e、③⑤
f、③⑦
g、②⑦
11、文法的二义性和语言的二义性是两个____________概念。
a、不同
b、相同
c、无法判断
12、在编译中产生语法树是为了____________。
a、语法分析
b、语义分析
c、词法分析
d、产生目标代码13、下列正规表达式中________与(a|b)*(c|d)等价。
a、（a*|b*）(c|d)
b、（a*|b*）*(c|d)
c、(ab)*(d|c)
d、（a*b*）(cd)
15、_______这样的语言，他们能被确定的有限自动机识别，但不能用正规表达式表示：
a、存在
b、不存在
c、无法判定是否存在
16、文法G[S]：S→aS S→W S→U U→a V→bV V→ac W→aW
其中的全部无用符号是（）
a、（W，V，U）
b、（V，b）
c、（W，V，a, b ,c）
d、（W，V，b，c）
16、ab3的另一种表示方法是（）
a、abbb
b、ababab
c、abbaab
d、aaabbb
17、编译过程中，比较常见的中间语言有___________。
①波兰表示
②逆波兰表示
③三元式
④四元式
⑤树形表示
可选项有：a、①③④ b、②③④ c、③④①⑤ d、②③④⑤
18、-a-（b*c/（c-d）+（-b）*a）的逆波兰表示是___________。
a、abc*cd-b-a*+/--
b、a-bc*cd-b-a*+/-
c、a-bc*cd-/b-a*+-
d、a-bc*/cd-b-a*+-
19、在编译程序中安排中间代码生成的目的是_______________。
①便于进行存储空间的组织
②利于目标代码优化
③利于编译程序的移植
④利于目标代码的移植
⑤利于提高目标代码的质量
可选项有：
a、②④⑤
b、①②③
c、③④①
d、②③④⑤
20、设有文法G[S]=（{b},{S,B},S,{S→b|bB, B→bS}）,该文法描述的语言是（）。
a、{b2i+1 | i≥1}
b、{b2i+1 | i≥0}
c、{b i | i≥0}
d、{b2i | i≥0}
二、简答题：（每小题5分，共30分）
1、证明下面文法是二义性的。P→PaP|PbP|cP|Pe|f
2、设一文法E→T|E+T|E-T T→F|T*F|T/F F→(E)|i 证明E+T*(E-T)是它的一个句型，并指出该句型的全部短语，直接短语，句柄和素短语。
3、求出下列文法所产生语言对应的正规式。
S→bS|aA A→aA|bB B→aA|bC|b C→bS|aA
4、将表达式（（B*D+A）/E+D）*F+G分别表示为三元式、四元式、逆波兰式序列
5、消除文法G[S]的左递归(G[S])
G[S]：S→AB A→bB|Aa B→Sb|a
6、对下面的文法G[Z]
Z→aB A→aB B→bB B→aA B→b
构造状态转换图,并说明符号串aaaabbb是否是该文法接受的句子
三、问答题：(共50分)
1、已知文法G S::=bBc|aAB A::=bAa|a B::=a|
写出所有非终结符号的First集和Follow集，构造预测分析表并给出输入串abbaaa分析过程。（10分）