编译原理 龙书答案(10)

编译原理 龙书答案

g) 利用高效构造方法构造LALR分析表 解：LR(0)项目集的核： I0 = { S’→ S }

I1 = { S’→S , A→S A } I2 = { S→A S } I3 = { A→a } I4 = { S→b } I5 = { A→S A }

I6 = { A→SA , S→A S } I7 = { S→AS , A→S A }

closure([S’→ S, #]) = { [S’→ S, #], [S→ AS, #/a/b], [S→ b, #/a/b], [A→ SA, a/b], [A→ a, a/b] } I0:S’→ S传播到I1: S’→S ，I2: S→A S，I4: S→b

自生搜索符a/b：I1: A→S A，I2: S→A S，I3: A→a ，I4: S→b

closure([A→S A, #])={[A→S A, #], [A→ SA, #/a/b], [A→ a, #/a/b], [S→ AS, a/b], [S→ b, a/b]} I1:A→S A传播到I6: A→SA ，I5: A→S A，I3: A→a

自生搜索符a/b：I5: A→S A，I6: S→A S，I3: A→a ，I4: S→b

closure([S→A S, #])={[S→A S, #] , [S→ AS, #/a/b], [S→ b, #/a/b], [A→ SA, a/b], [A→ a, a/b] } I2: S→A S传播到I7: S→AS ，I4: S→b

自生搜索符a/b：I2: S→A S，I7: A→S A，I3: A→a ，I4: S→b

I5:A→S A传播到I6: A→SA ，I3: A→a

自生搜索符a/b：I5: A→S A，I6: S→A S，I3: A→a ，I4: S→b

I6: S→A S传播到I7: S→AS ，I2: S→A S，I4: S→b

自生搜索符a/b：I2: S→A S，I7: A→S A，I3: A→a ，I4: S→b

closure([A→S A, #])={[A→S A, #], [A→ SA, #/a/b], [A→ a, #/a/b], [S→ AS, a/b], [S→ b, a/b]} I7:A→S A传播到I6: A→SA ，I5: A→S A，I3: A→a

自生搜索符a/b：I5: A→S A，I6: S→A S，I3: A→a ，I4: S→b

编译原理 龙书答案

（Aho）4.35 考虑下面文法 E → E + T | T T → T F | F F → F *| a | b

a） 构造SLR分析表 解：拓广文法 E' → E

I0={ E' → E, E → E + T, E → T, T → T F, T → F, F → F *, F → a, F → b } goto(I0, E) = { E' → E , E → E + T } = I1

goto(I0, T) = { E → T , T → T F, F → F *, F → a, F → b } = I2 goto(I0, F) = { T → F , F → F * } = I3 goto(I0, a) = { F → a } = I4 goto(I0, b) = { F → b } = I5

goto(I1, +) = { E → E + T, T → T F, T → F, F → F *, F → a, F → b } = I6 goto(I2, F) = { T → T F , F → F * } = I7 goto(I2, a) = I4 goto(I2, b) = I5

goto(I3, *) = { F → F * } = I8

goto(I6, T) = { E → E + T , T → T F, F → F *, F → a, F → b } = I9 goto(I6, F) = I3 goto(I6, a) = I4 goto(I6, b) = I5

编译原理 龙书答案

goto(I7, *) = I8 goto(I9, F) = I7 goto(I9, a) = I4 goto(I9, b) = I5

follow(E) = { +, $ } follow(T) = { a, b, +, $ } follow(F) = { a, b, *, +, $ }

b） 构造LALR分析表

解：LR(0)项目集规范族的核 I0 = { E' → E }

I1 = { E' → E , E → E + T } I2 = { E → T , T → T F } I3 = { T → F , F → F * } I4 = { F → a } I5 = { F → b } I6 = { E → E + T }

I7 = { T → T F , F → F * } I8 = { F → F * }

I9 = { E → E + T , T → T F }

closure({[E' → E , #]}) = { [E' → E , #], [E → E + T, #], [E → T, +], [T → T F, +/a/b], [T → F, +/a/b], [F → F *, +/a/b/*], [F → a, +/a/b/*], [F → b, +/a/b/*] } 传播：I0：E' → E I1：E' → E , I1：E → E + T

自生：I2：E → T ，I2：T → T F，I3：T → F ，I3：F → F *，I4：F → a ，I5：F → b

传播：I1：E → E + T I6：E → E + T

closure({[T → T F, #] }) = {[T → T F, #], [F → F *, #/*], [F → a, #/*], [F → b, #/*] } 传播：I2：T → T F I7：T → T F ，I7：F → F *，I4：F → a ，I5：F → b 自生：I7：F → F *，I4：F → a ，I5：F → b