期末考试编译原理试题
2、正规式0（0|1）*1
构造该正规式所对应的NFA（画出状态转换图）。
将所求的NFA确定化和最小化。（分别画出确定化和最小化的状态转换图）。（10分）
3、若有文法G（S）的产生式如下：S::=bASB|bA A::=dSa|b B::=cAa|c构造识别所有项目集规范族
的DFA。（20分）
判断该文法是否是LR（0）文法，说明理由。
判断该文法是否是SLR（1）文法，说明理由。
判断该文法是否是LR（1）文法，说明理由。
判断该文法是否是LALR（1）文法，说明理由。
4、简述编译的整个过程（10分）。
德州学院期末考试试题
（ 5 至学年第学期）
课程名称：考试对象：试卷类型：考试时间：分钟
一、选择题（本大题共20小题，每小题1分，共20分）
1、要在某一台机器上为某种语言构造一个编译程序，必须找掌握下述三方面的内容：______。
①高级语言②源语言③目标语言④程序设计方法⑤编译方法⑥测试方法⑦机器语言
可选项有①②③④⑤⑥⑦
a、①③⑤
b、①②⑥
c、②③⑤
d、②④⑦
2、“用高级语言书写的源程序都必须经过编译，产生目标代码后才能投入运行。”这种说法___________。
a、不正确
b、正确
3、若一个文法是递归的，则它所产生的句子个数___________。
a、必定是无穷的
b、是有限个的
c、根据具体情况而定
4、下列文法__________二义文法
E::=EiT|T T::=T+F|iF|F F::=ET|(
可选项有：a、是b、不是c、无法判断。
5、编译程序的语法分析器接受以________为单位的输入，并产生有关信息供以后各阶段使用。可选项有：a、表达式b、产生式c、单词d、语句
6、文法G[Z]：Z→Be A→Ae|e B→Af D→f 中，________是多余产生式
a、Z→Be
b、A→Ae|e
c、B→Af
d、D→f
7、算符优先文法属于________。
a、自顶向下语法分析法
b、LR分析法
c、SLR分析法
d、自底向上语法分析法
8、设有文法G[S]=（{a}，{S,B}，S，{S→a|aB, B→aS}）,该文法描述的语言是_____
a、{a i|i≥0}
b、{ a2i|i≥0}
c、{ a2i+1|i≥0}
d、{ a2i+1|i≥1}
9、描述语言L={a m b n|n≥m≥1}的文法是__________
a、Z→ABb
b、Z→ABb
c、Z→Ab
d、Z→aAb
A→aA|a A→Aa|a A→aAb|a A→Ab|aAb|ε
B→bB|b B→aBb|b
10、一个句型中的最左_______称为该句型的句柄。
a、短语
b、直接短语
c、素短语
d、终结符号
11、通常高级语言的词法规则可用正规式描述，词法分析器可用_________来实现a、语法树b、有限自动机c、栈d、堆
12、文法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、都不是
13、素短语是指_______的短语。
①至少包含一个符号
②至少包含一个非终结符号
③至少包含一个终结符号
④除自身外不再包含其它终结符号
⑤除自身外不再包含其它非终结符号
⑥除自身外不再包含其它短语
⑦除自身外不再包含其它素短语
可选项有：
a、①④
b、①⑤
c、①⑥
d、②④
e、③⑤
f、③⑦
g、②⑦
14、给定文法G[S]：S→ACc A→aA|Sb C→Def D→hACDd|eC| E→bDe|ε该文法是____________。（1）右线性文法（2）前后文无关文法（3）左递归文法（4）LL（1）文法
可选项有：
a、②
b、③
c、②③
d、②③④
15、算符文法是指____________的文法。
①没有形如U→…VW…的规则（U、V、W为非终结符）
②终结符号集中任意两个符号对之间至多有一种优先关系成立
③没有相同的规则右部
④没有形如U→ε的规则
可选项有
a、①
b、①②
c、①②③
d、①②③④
16、下列正规表达式中________与(a|b)*(c|d)等价。
a、（a*|b*）(c|d)
b、（a*|b*）*(c|d)
c、(ab)*(d|c)
d、（a*b*）(cd)
17、若一个句型中出现了某一产生式的右部，则此右部_______是该句型的句柄
a、一定
b、不一定
18、前后文无关文法和正规文法所产生的语言类相比_______
a、前后文无关文法产生的语言类大
b、正规文法产生的语言类大
c、两者产生的语言类一样大
d、无法比较
19、编译过程中，比较常见的中间语言有___________。
①波兰表示
②逆波兰表示
③三元式
④四元式
⑤树形表示
可选项有：a、①③④b、②③④c、③④①⑤d、②③④⑤
20、LL（1）文法的条件是_______________。
a、对形如U→X1|X2|…|Xn的规则，要求FIRST（Xi）)∩FIRST (Xj)=? (i≠j)
b、对形如U→X1|X2|…|Xn的规则若Xi?* ε则要求FIRST(Xj) ∩FOLLOW (U)=?
c、a和b