VT
i

E
E→TE’E→TE’
E’E’→TE’
T
T→FT’T→FT’
T’T’→εT’→FT’
F
F→E


E’→εE’→ε
T’→εT’→εF→i
1．（10分）对于文法G：
SaSbSaSd证明该文法是二义性文法。答：一个文法，如果存在某个句子有不只一棵语法分析树与之对应，那么称这个文法是二义性文法。（5分）
句子aadbd有两棵语法树（5分，划一棵树给3分）。如下图：（６分）
S
S
a
S
b
S
a
S
a
S
d
a
S
b
S
d
d
1
d2
由此可知，SaSbSaSd定义的文法是二义性文法。
３．（20分）给定一个简单的算术表达式文法GE：E→ETTT→TFFF→Ei该文法是SLR1文法吗？（要求给出详细过程，如果是SLR文法，给出分析表）
答：1该文法的拓广文法是：2分
fE’→EE→ETE→TT→TFT→FF→EF→i
（1）（2）（3）（4）（5）
（6）（7）
（2）相应的LR（0）的DFA：（10分）
I0E’→EE→ETE→TT→TFT→FF→EF→i
i
I5F→i
E
I1
E’→E
E→ET
F
T
I2

I3T→F
I6
E→ET
T→TF
i
F
T→F
F→E
F→i
E→T
T→TF
T

（
T
F（I7
I8E→ET
T→TF
I4
F→E
T→TF
i
F→E
F→i
E→ET
E→T
i
T→TF
（
F
E
T→F
I11
F→E
T→TF

F→i
I9F→EE→ET

（3）冲突与解决3分）①I1状态中有移进规约冲突
FollowE’不含可解决移进规约冲突②I2状态中有移进规约冲突FollowE，），不含可解决移进规约冲突③I8状态中有移进规约冲突
I10F→E
fFollowE，），不含
可解决移进规约冲突
4SLR分析表5分
ACTION
GOTO


i
（
）

E
T
F
0
S5
S4
1
2
3
1
S6
接受
2
r3
S7
r3
r3
3
r5
r5
r5
R5
r5
r5
4
S5
S4
9
2
3
5
r7
r7
r7
r7
r7
r7
6
S5
S4
8
3
7
S5
S4
11
8
r2
S7
r2
r2
9
S6
S10
10
r6
r6
r6
r6
r6
r6
11
r4
r4
r4
r4
r4
r4
二、单项选择题（每小题2分，共20分）
1．语言是____C_
A．终结符与非终结符的符号串的集合B．非终结符符号串的集合C．终结符符号串的集合
2．编译程序分两阶段工作，前阶段完成的工作是__C___
A．词法分析、语法分析和代码优化
B．代码生成、代码优化和词法分析
C．词法分析、语法分析、语义分析和中间代码生成
D．词法分析、语法分析和代码优化
3．一个句型中称为句柄的是该句型的最左C
A．句型B．短语C．直接短语D．最左直接短语
4．自动机识别的语言是D
A．0型语言
B．1型语言C．2型语言D．3型语言
5．自动机所完成的任务是从字符串形r