期末考试编译原理试题
T→F|T*F
F→(E)|i
(1) 写出句型T*F+i1*i2的最右推导并画出语法树。
(2) 写出上述句型的短语，直接短语、句柄、素短语和最左素短语。
3、(5分) 求出下列文法所产生语言对应的正规式。
S::=aA A::=bA|aB|b B::=aA
4、(5分) 写出表达式a+b*(c-d)对应的逆波兰式、三元式序列和抽象语法树。
5、(5分)写一个文法使其语言为L(G)={a n b n c m| m,n≥1，n为奇数，m为偶数}。
三、问答题：（共计50分）
1、已知文法G S::=aBc|bAB A::=aAb|b B::=b|ε
构造预测分析表并给出输入串baabbb分析过程。（10分）
2、构造正规式 (0|1)*00 相应的DFA并进行化简。(15分)
9、若有文法G（S）的产生式如下：S::=bASB|bA A::=dSa|b B::=cAa|c构造识别所有项目集规范
族的DFA。（15分）
（1）判断该文法是否是LR（0）文法，说明理由。
（2）判断该文法是否是SLR（1）文法，说明理由。
（3）判断该文法是否是LR（1）文法，说明理由。
（4）判断该文法是否是LALR（1）文法，说明理由。
10、（10分）对文法G(S)：
S → S ∨ a T | a T | ∨ a T
T →∧ a T | ∧ a
(1) 消除该文法的左递归和提取左公因子；
(2) 构造各非终结符的FIRST和FOLLOW集合；
(3) 构造该文法的LL(1)分析表，并判断该文法是否是LL(1)的。
德州学院期末考试试题
（ 10 至学年第学期）
课程名称：考试对象：试卷类型：考试时间：分钟
一、选择题（本大题共20小题，每小题1分，共20分）
1、描述一个语言的文法是___________。
a、唯一的
b、不唯一的
c、个数有限的
2、汇编程序是将______翻译成______；编译程序是将_______翻译成__________。
a、汇编语言程序
b、机器语言程序
c、高级语言程序d汇编语言或机器语言程序
3、设有文法G[I]：
I→I0|I1|I a|Ic|a|b|c
下列符号串中是该文法的句子的有___________________。
①ab0 ②a0c01 ③aaa ④bc10
可选项有
a、①
b、②③④
c、③④
d、①②③④
4、生成非0开头的正偶数集的文法是______________。
a、Z::=ABC c、Z::=ABC|2|4|6|8
C::=0|2|4|6|8 C::=0|2|4|6|8
B::=BA|B0|εB::=BA|B0|0
A::=1|2|3|4|5|6|7|8|9 A::=1|2|3|4|5|6|7|8|9
b、Z::=ABC d、Z::=ABC|2|4|6|8
C::=0|2|4|6|8 C::=0|2|4|6|8
B::=BA|B0|0 B::=BA|B0|ε
A::=1|2|3|4|5|6|7|8|9 A::=1|2|3|4|5|6|7|8|9
5、一个上下文无关文法G包括四个组成部分依次为：一组_____、一个_____、一组_____、一组______。
a、字符串
b、字母数字串
c、产生式
d、结束符号
e、开始符号
f、文法
g、非终结符号
h、终结符号
6、现有前缀表示的表达式文法G1：
E::=-EE E::=-E E::=a|b|c
则文法的句子-a-bc的所有可能语法树有______棵。
a、1
b、2
c、3
d、4
7、下列文法__________二义文法
E::=EiT|T T::=T+F|iF|F F::=E*|(
可选项有：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*（c+d）+b（c+d）
?a*（c+d）*+b（c+d）*
?a*（c+d）+b*（c+d）
?（a+b）*c+（a+b）*d
?（a*+b）*c+（a*+b）*d
可选项有:a、①b、②c、③d、④ e、⑤ f、④⑤ g、③④⑤