试题编号 :553

试题名称 :编译原理

一 :

1.试写一正规文法,使其定义的语言是不以0打头的偶整数集合.其中数字可以用简名表示,比如α1→0|2|4|6|8,并把α1看作是终结符.

2.试写一上下文无关文法,它能产生下列语言:

L={ω|ω∈{a,b}*,且ω中a的个数是b的两倍,例如aab等}

二 :请写出由下列文法所确定的语言.

1. G1: S→10S01

S→aA

A→bA

A→a

2. G2: S→aSS

S→a

三 :已知NFA的状态转换图如下,试对它确定化并化简,并写出该FA接受的语言.

　　　∩ b 　　a

　　→ S──────→A

d│ 　　　　│c

　↓ a 　　b 　↓

b＜C──→D──→E＞b

│　 b│←──│

b│　　↓　a 　│b

　　　└─→ T ←──┘

四 :已知文法G4:

S'→S

S→AS

S→b

A→SA

A→a

1.试求closure({(S'→·S,#)})和GO(closure({(S'→·S,#)}),S)

2.文法是LR(1)吗?为什么?

五 :试将下面语句按语法制导翻译成四元式序列.

while (a<c) and (b<d) do

if a=1 then c:=c+1

else while a<=d do a:=a+2;

六 :

1.试对如下四元式序列划分成基本块,并化出程序流图;

2.写出源语句.

(1) I:=1

(2) if I>M goto (19)

(3) J:=1

(4) if J>N goto (17)

(5) T1:=I*N

(6) T2:=T1+J

(7) T3:=addr(A)-C

(8) T4:=I*2

(9) T5:=J+2

(10) T6:=T4*N

(11) T7:=T6+T5

(12) T8:=addr(A)-C

(13) T9:=T8[T7]

(14) T3[T2]:=T9

(15) J:=J+1

(16) goto (4)

(17) I:=I+1

(18) goto (2)

(19) ...

七 :

1.求文法G7的各非终结符的终结首符集First和随符集Follow.

2.判定该文法是LL(1)吗?

G7: A→BCc|gDB

B→bCDE|ε

C→DaB|ca

D→dD|ε