一、填空题（每题4分，共20分）1乔母斯基定义的3型文法（线性文法）产生式形式ABaa或AaBa，A，B∈V
ab∈Vt。2语法分析程序的输入是单词符号，其输出是语法单位。3型为BaB的LR（0）项目被称为移进项目，型为BaB的LR（0）项目被称为待约项目，4在属性文法中文法符号的两种属性分别为继承属性和综合属性。5、运行时存贮管理方案有静态存储分配、动态存储分配和堆式存储分配和方案。
二已知文法GS1ETET2TFFF3F（E）i
（1）写出句型（TFi）的最右推到并画出语法树。（4分）（2）写出上述句型的短语，直接短语和句柄。（4分）
答：（1）最右推到（2分）ETFEETEFEiTiTFi
2语法树（2分）
（3）（4分）短语：（TFi），TFi，TF，i
直接短语：TF，i句柄：TF
三证明文法GS：SSaSε是二义的。（6分）
答：句子aaa对应的两颗语法树为：

f
因此，文法是二义文法
四给定正规文法G（S）：1SSaAbb2ASa
请构造与之等价的DFA。（6分）答：对应的NFA为：（6分）
状态转换表：
a
b
F
Φ
S
S
SA
Φ
SA
SA
S
五构造识别正规语言babbab最小的DFA（要求写出求解过程）。（15分）答：（1）对应的NFA（5分）
（2）将（1）所得的NFA确定化：（5分）
a
b
0
1，3
0
13
Φ
2，3
23
13
23
六已知文法GS1SaT2TTSS
试：（1）消除文法的左递归；（4分）（2）构造相应的first和follow集合。（6分）
答：（1）消除文法的左递归后文法G’（S）为：1SaT

（5分）
f2TST’S
3T’ST’ε
（2）（6分）
first
follow
Sa
Ta

T’ε


（4分）
七已知文法GS
1SSiAA
2AABB
3BA（
试构造非终止符的firstVT和lastVT集合。（10分）
答：（10分）
firstVT
lastVT
Sii
A

B

八已知文法GS
1SBB
2BaB
S
3Bb
B
的follow集合如表：
试：（1）给出该文法的LR（0）项目集规范族划分；
（2）填写相应的SLR（1）的分析表。（15分）
答：（1）LR（0）项目集规范族划分8分
Follow
ab
I0S’SSBBBaBBb
SBabIIII3412
I1S’S
I2SBB
BBaBb
BabIII345
I3BBB
aBaBb
BabIII346
I4Bb
I5SBB
I6BaB
2SLR1分析表（7分）
状态
Actio

a
b

0
S3
S4
1
Acc
2
S3
S4
3
S3
S4
4
R3
R3
R3
5
R1
Goto
S
B
1
2
56

f
6
R2
R2
R2
九．设某语言的
otthe
else语句的语法形式为：S
otEther