2008～2009学年度第二学期《编译原理》考试试卷 （A卷） 成绩____________
课程性质：（必修） 使用范围：（本科）
考试时间：2009 年 5月 日 考试方式：（闭卷）
学号__________年级专业____________班级________姓名____________
一、单选题（将正确的答案的字母，填入题干的下划线中。每题2分，共14分）
1．语言学家Chomsky将文法和语言分为四大类，其中3型文法又称为 ______。
A．无文法 B．上下文有关文法
C．上下文无关文法 D．正规文法
2．设有文法G[S]：S→(T)|a|∧ ，T→TbS|S，则 FOLLOW(S)= ______。
A．{ ),b } B．{ ),b,# } C．{ ),a,# } D．{ ( , b }
3．在语法分析方法中，算符优先分析法采用______文法。
A．OPG B．LL(1) C．LR(0) D．LR(1)
4．对程序中的表达式的识别工作，编译程序通常都在______阶段完成。
A．语法分析 B．语义分析
C．词法分析 D．目标代码的生成
5．自下而上语法分析的工作原理是______。
A．“移进—推导法” B．“最左推导法”
C．“移进—规约法” D．“推导—规约法”
6．已知∑＝{a,b}，与文法G[S]:S→Sa| Sb| a等价的正规式是______。
A．ab* B．ba* C．a(a|b)* D．aa*|b*
7．LR分析法每次都是对当前句型的______进行规约。
A．素短语 B．句柄 C．短语 D．最左素短语
二、填空题（每空2分，共22分）
1．已知文法G[S]：S→(A)|a ，A→AcS|S|b ；该文法的开始符号是____________，非终结符号集合为____________，终结符号集合为____________。
2．描述源程序中的单词结构有3种方法：有穷自动机，_____________和____________。
3．自上而下的语法分析方法有____________和______________。
4．设有文法G[S]：S→Sa|a ，构造它的拓广文法，引入一个产生式：Sˊ→S ；则I。=Closure（{[Sˊ→·S，＃]}）= _______________________。
5．在LR（0）项目集规范族中，若有项目：，其中，称该项目为_____________项目。
6.LL(1)语法分析方法中应解决的主要问题是__________；LR语法分析方法中应解决的主要问题是_____________。
三、判断题（判断下列各题的正错，若正确，在括号中写“正”；否则写“错”。每题2分，共16分）
1．一个文法有二义性，则由它描述的语言一定具有二义性。（ ）
2．若一个语言有无穷多个句子，则定义该语言的文法一定是递归的。（ ）
3．若有正规式a*b，则与之等价的文法应该是G[A]：A→aA|b 。（ ）
4．设有文法G[A]：A→aB ，B→bB|b，则该文法是LL(1)文法。（ ）
5．由文法法G的开始符号S推导出来的符号串，称为文法G的句子。（ ）
6．最左素短语是句型最左边的短语。（ ）
7．LR语法分析法是一种规范规约的分析方法。（ ）
8．存在能够被确定的有穷自动机DFA识别，却不能用正规式表示的语言。（ ）
四、解答题（共２8分）
1．已知文法G[S]：S→aAb，A→aAb|a；求：L(G[S])=?（5分）
2．设M＝（{x，y}，{a，b}，f，x，{y}）为一有穷自动机，其中f定义如下：
f(x,a)={x,y}, f(x,b)={y}, f(y,a)=Φ , f(y,b)={y}。（5分）
（1）试将它用状态图表示；
（2）试将它用状态矩阵表示。
3．已知文法G[E]：（8分）
E→T|E+T|E-T
T→F|T*F|T/F
F→(E)|i
用语法树求出句型：T+T*F+i 的短语，简单短语，素短语和句柄。
4．设有文法G[A]： A→Bc|a，B→aB|c（共5分）
（1）．G是LL（1）文法吗？为什么？
（2）．若G不是LL（1）文法，则将它改造成等价的LL（1）文法G1。
5. 试用语法树证明：文法G[S]：S→aSbS| aS| ε 具有二义性 (5分)
五、设字母表上的正规式为：0(1|0) * （共6分）
1．构造该正规式对应的NFA N ；
2．将NFA N确定化，得到DFA M（用DFA图表示），使得L（M）=L（N）；
3．将DFA M最小化（用DFA图表示）。
六、已知文法G[S]：S→＊A，A→＊|0A1 ：（8分）
1.计算非终结符的FIRSTVT集和LASTVT集.并找出终结符之间的所有优先关系（包括句子左右的语句括号＃）。
2．根据1，构造G的算符优先关系矩阵。此文法是算法符优先文法吗？
七、设有文法G[S]：S→(S)|b （共6分）
1．构造能识别文法的规范句型活前缀的DFA；（3分）
2．构造它的LR(0)分析表。（3分）下载本文
