期末考试编译原理试题
9、____这样的语言，他们能被确定的有限自动机识别，但不能用正规表达式表示：
A、存在
B、不存在
C、无法判定是否存在
10、LR（K）文法是_________。
A、从左到右分析，共经过K步的一种编译方法。
B、从左到右分析，每次向前预测K步的一种编译方法。
C、从左到右分析，每次向貌似句柄的符号串后看K个输入符号的一种编译方法。
D、从左到右分析，每次走K步的一种编译方法。
11、-a-（b*c/（c-d）+（-b）*a）的逆波兰表示是___________。
A、a-bc*cd-/b-a*+-
B、a-bc*/cd-b-a*+-
C、abc*cd-b-a*+/--
D、a-bc*cd-b-a*+/-
12、设有文法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
13、素短语是指_______的短语。
①至少包含一个符号
②至少包含一个非终结符号
③至少包含一个终结符号
④除自身外不再包含其它终结符号
⑤除自身外不再包含其它非终结符号
⑥除自身外不再包含其它短语
⑦除自身外不再包含其它素短语
可选项有：
A、①④
B、①⑤
C、①⑥
D、②④
E、③⑤
F、③⑦
G、②⑦
14、算符优先分析属于分析方法。
A、自顶向下
B、自底向上
C、自左向右
D、自右向左
15、简单优先分析法每次都是对进行归约
A、最左短语
B、直接短语
C、句柄
D、素短语
E、最左素短语
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
17、程序基本块是指
A、一个子程序
B、一个仅有一个入口和一个出口的语句
C、一个没有嵌套的程序段
D、一组顺序执行的程序段，仅有一个入口和一个出口
18、设有文法G[Z]：Z→Z*Z|Z+Z|（Z）|a 该文法二义性文法
A、是
B、不是
C、无法判断
19、下列正规表达式中________与(a|b)*(c|d)等价。
A、（a*|b*）(c|d)
B、（a*|b*）*(c|d)
C、(ab)*(d|c)
D、（a*b*）(cd)
20、语法分析的任务是
①分析单词是怎样构成的②分析单词串是如何构成语句和说明的
③分析语句和说明是如何构成程序的④分析程序的结构
A、②③
B、②③④
C、③④
D、①②③④
二、（简答题，共计20分）
1、(10分)已知文法G（T)：T→T*F|F F→F↑P|P P→(T)|i
(1)写出句型T *P↑（T*F）推导过程，画出语法树；
(2)写出句型T *P↑（T*F）的短语、直接短语、句柄和素短语。
2、(5分)构造识别下面正规式的NFA
b（aa|bb）*ab
3、（5分）消除文法G[S]的左递归
G[S]：S→AB A→bB|Aa B→Sb|a
三、（综合题，共计30分）
1
2、(10分)
（1）对下面的文法G[Z]
Z→aB A→aB B→bB B→aA B→b
构造状态转换图,并说明符号串aaaabbb是否是该文法接受的句子
（2）写出G[Z]文法相应的正规式：
3、（10分）设有以下文法G[S]：S→aAbDe|d A→BSD|e B→SAc|cD|εD→Se|ε（1）求出文法中每个非终结符的FOLLOW集
（2）该文法是LL（1）文法吗？构造LL（1）分析表
四、（综合题，共计30分）
1、（10分）将表达式（（B*D+A）/E+D）*F+G分别表示为三元式、四元式、逆波兰式序列
2、（10分）对基本块P画出DAG图
B:=3
D:=A+C
E::=A*C
F:=E+D
G:=B*F
H:=A+C
I:=A*C
J:=H+I
K:=B*5
L:=K+J
M:=L
假定只有L在基本块出口之后活跃，写出优化后的四元式序列。
3、（10分）对于文法G[S]：S→aBb | aAa |bAb|bBa A→x B→x
（1）判断该文法是否是LR（1）文法，构造LR（1）分析表
（2）判断该文法是否是LALR（1）文法，说明理由
德州学院期末考试试题
（ 4 至学年第学期）
课程名称：考试对象：试卷类型：（1）考试时间：分钟