编译原理 龙书答案(11)

编译原理 龙书答案

传播：I3：F → F * I8：F → F *

closure({[E → E + T, #]}) = {[E → E + T, #], [T → T F, #/a/b], [T → F, #/a/b], [F → F *, #/a/b/*], [F → a, #/a/b/*], [F → b, #/a/b/*] }

传播：I6：E → E + T I9：E → E + T ，I9：T → T F，I3：T → F ，I3：F → F *，I4：F → a ，I5：F → b

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

传播：I7：F → F * I8：F → F *

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

计算搜索符：

编译原理 龙书答案

（Aho）4.37 对文法

S→AaAb | BbBa A→ B→

a) 证明它是LL(1)文法但不是SLR(1)文法 解：

构造预测分析表： FIRST(S) = {a, b}, FIRST(A)=FIRST(B)={ }

所以，文法是LL(1)文法 构造SLR分析表：

LR(0)项目集I0={S’→ S, S→ AaAb, S→ BbBa, A→ , B→ }

而FOLLOW(A)=FOLLOW(B)={a, b}，因此action[0, a] = action[0, b] = r3/r4，冲突！ 所有，文法不是SLR(1)文法

（Aho）4.39 证明文法 S→Aa | bAc | dc | bda A→d

是LALR(1)文法但不是SLR(1)文法 解：

构造SLR分析表：

项目集I4={ S→d c, A→d }，而FOLLOW(A)={a, c}，因此action[4, c]=s8/r5，冲突！ I7={ S→bd a, A→d }，因此action[7, a]=s10/r5，冲突！ 这是SLR分析表仅有的两个冲突的地方 因此文法不是SLR(1)文法

高效构造LALR分析表：

通过计算搜索符，所有项目都具有搜索符$，I4：A→d 具有搜索符a，I7：A→d 具有搜索符c，因此action[4, c]=s8，action[7, a]=s10，LALR分析表不冲突 因此文法是LALR(1)文法

（Aho）4.40 证明文法 S→Aa | bAc | Bc | bBa

编译原理 龙书答案

A→d B→d

是LR(1)文法但不是LALR(1)文法 解：

构造规范LR分析表：

I0 = { [S’→ S, $], [S→ Aa, $], [S→ bAc, $], [S→ Bc, $], [S→ bBa, $], [A→ d, a], [B→ d, c]} goto(I0, S)={ [S’→S , $] } = I1 goto(I0, A)={ [S→A a, $]} = I2 goto(I0, B)={ [S→B c, $]} = I3

goto(I0, b)={ [S→b Ac, $], [S→b Ba, $], [A→ d, c], [B→ d, a]} = I4 goto(I0, d)={ [A→d , a], [B→d , c]} = I5 goto(I2, a)={ [S→Aa , $]} = I6 goto(I3, c)={ [S→Bc , $]} = I7 goto(I4, A)={ [S→bA c, $]} = I8 goto(I4, B)={ [S→bB a, $]} = I9

goto(I4, d)={ [A→d , c], [B→d , a]} = I10 goto(I8, c)={ [S→bAc , $]} = I11 goto(I9, a)={ [S→bBa , $]} = I12 规范LR分析表为：

构造LALR分析表，同心集I5和I10合并，显然会造成归约/归约冲突。 因此，文法是LR(1)文法，但不是LALR(1)文法

（Aho）4.42 试编写一个算法，为文法中每个NT A计算集合{B | A* B , 其中B是NT， 文法符号串} 解：算法描述如下

1． 设置一个栈，保存NT，初始栈中只有A，将结果集合设置为空 2． 若栈空，算法结束，否则执行以下步骤 3． 将栈顶NT B弹出，将B加入结果集合