编译原理期中测试答案.docVIP

精品文档

精品文档

精品文档

精品文档

精品文档

精品文档

编译原理期中测试答案

三、单项选择题(每题3分，共15分)

1．设有文法G[S]:S→(AS)|(b)

A→(SaA)|(a)

该文法的句型(((b)a(a))(b))有C个直接短语。

A.1B.2C.3D.4

2．如果一个文法满足D，则称该文法是二义性文法。

(1)文法的某一个句子存在两个（包括两个）以上的语法树

(2)文法的某一个句子存在两个（包括两个）以上的最左推导

(3)文法的某一个句子存在两个（包括两个）以上的最右推导

(4)在进行归约时，文法的某些规范句型的句柄不唯一

上述描述中的所有正确描述有：

A.(1)B.(1)(2)C.(1)(2)(3)D.(1)(2)(3)(4)

3．构造一个不带回溯的自顶向下语法分析器，要求文法满足E。

A.对每个形如A→x1|x2|…|xn的产生式，要求FIRST(xi)与FIRST(xj)的交集为空集(i≠j)

B.对每个形如A→x1|x2|…|xn的产生式，若xiε，则要求FIRST(xj)与FOLLOW(A)的交集为空集(i≠j)

C.不含左递归

D.A和B同时满足

E.A、B和C同时满足

4、给定文法A→bA|cc，下列符号串中，是该文法的句子的是C。

①cc②bcbc③bcbcc④bccbcc⑤bbbcc

A①B.①③④⑤C.①⑤D.①④⑤

5、若一个句型中出现了某一产生式的右部，则此右部B是该句型的句柄。

A.一定B.不一定C.一定不D.无法判断

四、简述题(每题5分，共20分)

1、写一上下文无关文法,它能产生语言。

S→A#B

A→Aa|?

B→Bb|?

2、将文法G[S]改写为等价的G′[S]，使G′[S]不含左递归和左公共因子。G[S]：S→bSAe|bA

A→Ab|d

答：文法G[S]改写为等价的不含左递归和左公共因子的

G[S]S→bB

B→SAe|A

A→dA

A→bA|ε

3、什么是文法的二义性？下面的文法是二义的吗？为什么？

G[S]：S→AB|ABDA→aB→CD|DC→cD→d

答：如果一个文法存在某个句子对应两棵不同的语法树，则该文法是二义的。

是，句子acd有两个完全不同的语法树。

4、设文法G[A]:A→[B

B→X]|BA

X→Xa|Xb|a|b

试求出文法G[A]产生的语言对应的正则式。

解:X→X(a|b)|a|bX→(a|b)?(a|b)*代入B→X]|BA

B→(a|b)?(a|b)*]|BAB→(a|b)(a|b)*]?A*代入

A→[(a|b)(a|b)*]?A*

[(a|b)(a|b)*]([(a|b)(a|b)*])*

五、计算题(共41分)

1、已知文法G(S):

S→a|∧|(T)

T→T,S|S

⑴给出句子(a,(a,a))的最左推导并画出语法树；

⑵给出句型((T,S),a)的短语、直接短语、句柄。(10分)

答：最左推导：(2分)

S=(T)=(T,S)=(S,S)

=(a,S)=(a,(T))=(a,(T,S))

=(a,(S,S))=(a,(a,S))

=(a,(a,a))

语法树：

S

S

T

(

)

T

,

S

S

a

(

T

)

T

,

S

S

a

a

3给出与正规式R＝（ab）*（a|b*）ba等价的NFA。（5分）

答案：

4将下图的NFA确定化为DFA。（8分）

答案：用子集法确定化如下表

I

Ia

Ib

状态

{X,1,2}

{1,2}..

{1,2,3}

{1,2,Y}

{1,2}..

{1,2}..

{1,2,Y}

{1,2}..

{1,2,3}

{1,2,3}

{1,2,3}

{1,2,3}

X

1

2

3

确定化后如下图

5、设文法G(S):

S→S+aF|aF|+aF

F→*aF|*a

⑴消除左递归和回溯；

⑵构造相应的FIRST和FOLLOW集合；

⑶构造预测分析表(12分)

答：⑴(消除左递归2分，提公共左因子2分)

S→aFS’|+aFS’

S→+aFS’|ε