2008～2009学年度第二学期《编译原理》考试试卷答案-A

2008～2009学年度第二学期《编译原理》考试试卷

（A卷） 标准答案和评分 课程性质：（必修） 使用范围：（本科） 考试时间：2009 年 5月 日 考试方式：（闭卷）

学号__________年级专业____________班级________姓名____________

一、单选题（将正确的答案的字母，填入题干的下划线中。每题2分，共14分） 1．语言学家Chomsky将文法和语言分为四大类，其中3型文法又称为 D。

A．无限制文法

B．上下文有关文法

D．正规文法

C．上下文无关文法

2．设有文法G[S]：S→(T)|a|∧ ，T→TbS|S，则 FOLLOW(S)= B。

A．{ ),b }

B．{ ),b,# }

C．{ ),a,# }

D．{ ( , b }

3．在语法分析方法中，算符优先分析法采用A文法。

A．OPG

B．LL(1)

C．LR(0)

D．LR(1)

4．对程序中的表达式的识别工作，编译程序通常都在A阶段完成。

A．语法分析 C．词法分析

B．语义分析

D．目标代码的生成

5．自下而上语法分析的工作原理是C。

A．“移进—推导法” C．“移进—规约法”

B．“最左推导法”

D．“推导—规约法”

6．已知∑＝{a,b}，与文法G[S]:S→Sa| Sb| a等价的正规式是C。

A．ab*

B．ba* C．a(a|b)*

D．aa*|b*

7．LR分析法每次都是对当前句型的B进行规约。

A．素短语

B．句柄 C．短语

D．最左素短语

二、填空题（每空2分，共22分）

1．已知文法G[S]：S→(A)|a ，A→AcS|S|b ；该文法的开始符号是 S，非终结符

号集合为 {S,A}，终结符号集合为{a,b,c,(,)}。

2．描述源程序中的单词结构有3种方法：有穷自动机，正规式和正规文法。 3．自上而下的语法分析方法有LL(1)和递归下降方法。

4．设有文法G[S]：S→Sa|a ，构造它的拓广文法，引入一个产生式：Sˊ→S ；则I。=Closure（{[Sˊ→·S，＃]}）= {[Sˊ→·S，＃], [S→·Sa，＃/a], [S→·a，＃/a]}。

5．在LR（0）项目集规范族中，若有项目：AAbB，其中bVT，称该项目为

移进项目。

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分）n

{ an+1bn| n≥0 }

2

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） 试将它用状态图表示； a a b x y b

（2） 试将它用状态矩阵表示。

a b

x {x,y} {y} y {y} 3．已知文法G[E]：（8分）

E→T|E+T|E-T T→F|T*F|T/F F→(E)|i

用语法树求出句型：T+T*F+i 的短语，简单短语，素短语和句柄。

短语:i,T, T*F, T+T*F, T+T*F+I ………2分 简单短语: i,T, T*F ………2分 素短语: i, T*F ………2分 句柄:T ………2分

4．设有文法G[A]： A→Bc|a，B→aB|c（共5分）

（1）．G是LL（1）文法吗？为什么？ 不是。………1分

将B→aB|c替换A→Bc|a中的B:A→aBc|cc|a ………1分 可见有左公共因子a，所以G不是LL(1)文法。

3

（2）．若G不是LL（1）文法，则将它改造成等价的LL（1）文法G1。 文法：A→aBc|cc|a ………（1） B→aB|c

将（1）提取左公共因子，变换为：A→aAˊ|cc 和Aˊ→Bc| ε ……2分 G1为：A→aAˊ|cc 和Aˊ→Bc| ε ，B→aB|c ………1分 5. 试用语法树证明：文法G[S]：S→aSbS| aS| ε 具有二义性 (5分) S S a S b S a S a S ε a S b S ε ε ε 五、设字母表{0,1},上的正规式为：0(1|0) （共6分） 1．构造该正规式对应的NFA N ；

0,1 X 0 A ε B ε

2．将NFA N确定化，得到DFA M（用DFA图表示），使得L（M）=L（N）； 0 1

{X} {A,B,y} 0,1

A 0 B {A,B,y} {B,y} {B,y} 0 C

Y *

{B,y} {B,y} {B,y} 1

3．将DFA M最小化（用DFA图表示）。

A 0 B 0,1

4

六、已知文法G[S]：S→＊A，A→＊|0A1 ：（8分）

1.计算非终结符的FIRSTVT集和LASTVT集.并找出终结符之间的所有优先关系（包括句子左右的语句括号＃）。

FIRSTVT LASTVT S {*} {*,1} A {*.0} {*,1}

0=1,#=#,左边＃右边#

2．根据1，构造G的算符优先关系矩阵。此文法是算法符优先文法吗？ 0 1 * # 0 < ＝ < 1 > > * < > < > # < =

七、设有文法G[S]：S→(S)|b （共6分）

1．构造能识别文法G[S]的规范句型活前缀的DFA；（3分）

Sˊ→·S S →· (S) S S→·b ( Sˊ→S· S→(·S) b (S) S S → (S · ) ) S→(S)· S →·S→·b S→b· (

2．构造它的LR(0)分析表。（3分）

5

ACTION GOTO ( ) b # S

0 S1 S3 1 1 acc 2 S3 4 3 r2 r2 r2 4 5 r1 S5 r1 r1

6