试题编号 :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|ε
E→gAf|c