编译原理考试试卷+答案A卷.doc

编译原理期末试卷

1．给出LL(1)分析方法的总控流程图。〔5分〕

2．按指定类型给出以下语言的文法。〔10分〕

(1)L1={canbm|n≥0,m0}用正规文法。S→cAA→aA|aB|aB→bB|b

(2)L2={0na1nbm|n0，m≥0}用二型文法。S→0S1B|0a1B→bB|c

3．文法G[S]为：〔10分〕

S→SdT|TT→TG|GG→(S)|a

试给出句型adT(S)的短语、简单(直接)短语、句柄和最左素短语。

短语：a,T,(S),T(S),adT(S)直接短语：a,(S)句柄：a最左素短语：a

4．将文法G[S]改写为等价的G[S]，使G[S]不含左递归和左公共因子。〔5分〕

S→[A A→B]|AS B→aB|+a

S→[A A→B]A’A’→SA’|εB→aB|+a

5．判断下面文法是否为LL(1)文法，假设是，请构造相应的LL(1)分析表，并写出aabbb的分析过程。〔10分〕

S→aDD→STe|εT→bMM→bHH→M|ε

a

b

e

#

S

S→aD

D

D→STe

D→ε

D→ε

T

T→bM

M

M→bH

H

H→M

H→ε

步骤

栈

输入串

动作(规那么右部逆序入栈)

0

#S

aabbb#

PushS→aD

1

#Da

abbb#

Popa

2

#D

abbb#

PushD→STe

3

#eTS

abbb#

PushS→aD

4

#eTDa

abbb#

Popa

5

#eTD

bbb#

PushD→ε

6

#eT

bbb#

PushT→bM

7

#eMb

bbb#

Popb

8

#eM

bb#

PushM→bH

9

#eHb

bb#

Popb

10

#eH

b#

PushH→M

11

#eM

b#

PushM→bH

12

#eHb

b#

Popb

13

#eH

#

出错，故句子不合法

6．简述编译程序概念及构成。〔10分〕

编译程序是现代计算机系统的根本组成局部.从功能上看，一个编译程序就是一个语言翻译程序，它把一种语言(称作源语言)书写的程序翻译成另一种语言(称作目标语言)的等价的程序.

7．设G=〔VN，VT，P，S〕是上下文无关文法，产生式集合P中任意一个产生式应具有什么样的形式？假设G是正那么文法呢？〔10分〕

2型〔上下文无关〕：规那么形式：A??

A?VN，??(VT?VN)*

3型〔右线性〕：A?aB或A?a〔右线性〕

A?Ba或A?a〔左线性〕a?VT?{?}

8．为文法G[E]：〔10分〕

V→N|N[E]E→V|V+EN→i

构造递归下降识别程序

E(){V();ifsymbol=‘+’E();}

V(){N();ifsymbol=‘[’{E();ifsymbol!=‘]’error();}

N(){ifsymbol!=‘i’error();}

/*这样的写法很简化，当文法提取左公因子后，需要计算相关非终结符的Follow集，才能确定什么时候用空串规那么推导。*/

9．对给定正那么表达式(d|ad)(b|ab)+构造其DFAM〔10分〕

10．将以下图的NFA确定化为DFA。〔10分〕

2

εεbaεb

X013Y

ab

ab

a

b

S

A

B

A

A

C

B

Ф

D

C

E

D

Ia

Ib

{X,0,1,3}

{0,2,1,3}

{3,Y}

{0,2,1,3}

{0,2,1,3}

{1,3,Y}

{3,Y}

Ф

{Y}

{1,3,Y}

{2}

{Y}

含有Y的状态子集为DFA的终态

11．简答题〔10分〕

(1)什么是文法，给出DFA的定义

一个确定的有穷自动机〔DFA〕M是一个五元组：M=〔K，Σ，f，S，Z〕其中

1.K是一个有穷集，它的每个元素称为一个状态；

2.Σ是一个有穷字母表，它的每个