编译原理 文法题目

Question

已知文法G[S]:
S->a|^|(T)
T->T,S|S
计算每个非终结符的FIRSTVT和LASTVT集
1.构造算符优先关系表
2.构造优先函数
3.消除左递归

Answer 1

首先扩展文法为：
1) S1->S
2) S->aS
3) S->bS
4) S->a
则：
I0 = Closure({S1->.S})={S1->.S,S->.aS,S->.bS,S->.a}
go(I0,S) = Closure({S1->S.})={S1->S.} = I1
go(I0,a) = Closure({S->a.S,S->a.})={S->a.S,S->.aS,S->.bS,S->.a,S->a.} = I2
go(I0,b) = Closure({S->b.S})={S->b.S,S->.aS,S->.bS,S->.a}=I3
go(I2,S) = closure({S->aS.})={S->aS.}=I4
go(I2,a) = Closure({S->a.S,S->a.}) = I2
go(I2,b) = Closure({S->b.S}) =I3
go(I3,S) = Closure({S->bS.}) = {S->bS.} = I5
go(I3,a) = Closure({S->a.S,S->a.}) = I2
go(I3,b) = Closure({S->b.S}) = I3

由图所示，状态I2,既有归约项目(S->a.)又有移近项目(S->.aS,S->.bS,S->.a)，产生冲突。当用SRL分析法时，需向前看一步，即求出：
Follow(S) = Follow(S1) = {#}
则，Follow(S)∩{a,b} =∮
故而Action(I2,a) = s2
Action(I2,b) = s3
Action(I2,#) = r4

则构造出srl分析表如下所示：
Action Goto
a b # S
I0 s2 s3 1
I1 acc
I2 s2 s3 r4 4
I3 s2 s3 5
I4 r2 r2 r2
I5 r3 r3 r3

希望对你能有所帮助。