编译原理第4章习题解答

1，2，3，4 解答   略！

5. 解答：

(1)×  (2)√  (3)×  (4)√  (5)√    (6)√    (7)×    (8)×

6. 解答：

(1)A：④      B：③     C：③      D：④     E：②

(2)A：④      B：④     C：③      D：③     E：②

7.解答：

(1) 消除给定文法中的左递归，并提取公因子：

bexpr→bterm {or bterm }

bterm→bfactor {and bfactor} 

bfactor→not bfactor | (bexpr) | true |false 

(2) 用类C语言写出其递归分析程序:   

void bexpr();

{

  bterm();

  WHILE(lookahead =='or') {

      match ('or');

      bterm();

   }

}

void bterm();

{

  bfactor();

  WHILE(lookahead =='and'){

    match ('and');

    bfactor();

  }

消除所给文法的左递归，得G'：

        S →(L)|a 

        L → SL'

        L'→ ,SL' |  

实现预测分析器的不含递归调用的一种有效方法是使用一张分析表和一个栈进行联合控制，下面构造预测分析表：

根据文法G'有：

First(S) = { ( , a )    Follow(S) = { ) , , , #}

First(L) = { ( , a )    Follow(L) = { ) }

First(L') = { ,}    Follow(L') = { ) }

按以上结果，构造预测分析表M如下：

文法G'是LL(1)的，因为它的LL(1)分析表不含多重定义入口。

预测分析器对输入符号串(a,(a,a))做出的分析动作如下：

各非终结符的First集：

First(S)={First(A)\\{ }}∪{First(B)\\{ }}∪{ }∪{b}={a,b,  }

First(A)={b}∪{ }={b, }

First(B)＝{ }∪{a}={a, }

First(C)={First(A) \\{ }}∪First(D)∪First(b) ={a,b,c}

First(D)={a}∪{c}={a,c}

各个候选式的First集为：

First(AB)={a,b,  }    First(bC)={b}

First( )＝{ }        First(b)＝{b}

First(aD)={a}       First(AD)={a,b,c}

First(b)={b}        First(aS)={a}

First(c)={c}        

各非终结符的Follow集的计算：

Follow(S)={#}∪Follow(D) ={#}

Follow(A)=(First(B)\\{ })∪Follow(S)∪First(D) ={a,#,c}

Follow(B)=Follow(S) ={#}

Follow(C)=Follow(S) ={#}

Follow(D)=Follow(B)∪Follow(C) ={#}

10．解答：

(1) 求First和Follow集                    

First(E)=First(T)={(,a,b,∧}             ⑦

First(E')={+,  }                       ⑥

First(T)=First(F)={(,a,b, ∧}             ④

First(T')=｛(,a,b, ∧,  ｝                ⑤ 

First(F)=First(P)={(,a,b, ∧}              ③

First(F')=｛*， ｝                     ②

First(P)={(,a,b, ∧}                     ①（计算顺序）

Follow(E)= {#, ) }

Follow(E')= Follow(E)={#，)}            (1)（使用的产生式）

Follow(T) = First(E')＼{ }∪Follow(T')     (1,2)

          = {+}∪{),#}={+,),#}

Follow(T')= Follow(T)={+,},#}            (3)

Follow(F)= First(T')＼{ }∪Follow(T)      (3,4)

         = {(,a,b,∧,+ ,),#}

Follow(F')= Follow(F)                   (5)

          = {(,a,b,∧,+ ,),#}

Follow(P)= First(F')＼{ }∪Follow(F)    (5,6)

∵a. 文法不含左递归；

b. 每个非终结符的各个侯选式的First集不相交；

c. First(E')∩Follow(E')={+,  }∩{#,),}=

First(T')∩Follow(T')={(,a,b,∧,  }∩{+,)}=

First(F')∩Follow(F')={*,  }∩{,a,( ∧,+,},#}= 

∴改造后的文法满足LL(1)文法的三个条件，是LL(1)文法。

(3) 预测分析表如下所示。

(1)

S→Abc                    

A→a│ 

b. S,A,B各候选式的First集不相交；

c. First(A)∩Follow(A)={a, }∩{b}=

    First(B)∩Follow(B)={b, }∩=

∴该文法为LL(1)文法。

(2) 

S→Ab

A→a│B│         

b. S,A,B各候选式的First集不相交；

c. First(A)∩Follow(A)={a,b,  }∩{b}={b }≠

∴ 该文法不是LL(1)文法。

12. 解答：

① 最右推导：

E=>T=>F=>(E)=>(E＋T)=>(E＋F)=>(E＋i)=> (T＋i)=>(T*F＋i)

语法树：

　　　 　素短语：T*F，i

最左素短语：T*F

③ 由于E =>E+T =>E+T*F，故E+T*F为该文法的句型    

短语：T*F、E+T*F 

直接短语：  T*F    

句柄：      T*F

13. 解答：

最左推导：

S=> (T) => (T,S) => (S,S) => (a,S) => (a,(T)) => (a,(T,S)) 

=> (a,(S,S)) => (a,(a,S)) => (a,(a,a))

最右推导：

S=> (T) => (T,S) => (T,(T)) => (T,(T,S)) => (T,(T,a)) 

=> (T,(T,a)) => (T,(a,a)) => (S,(a,a)) => (a,(a,a))

文法中S和T的FirstVT和LastVT集为：

FirstVT(S)={a,(}     FirstVT(T)={,,a, (}      

lastVT(S)={a, ）}    lastVT(T)={,,a,)}

  文法G[S]的算符优先关系表： 

根据优先关系表，对每个终结符或#建立符号f与g，把f(和g)分成一组。根据G[S]的算符优先关系表，画出如下的有向图。

优先函数如下：

用算符优先分析法分析句子(a,(a,a))。

给定的输入符号串是文法的一个句子。

14. 解答：

(1) 该文法的拓广文法G'为 

0．S' → S    

1．S → aSAB

2．S → BA    

3．A → aA

4．A → B    

5．B → b

其LR(0)项目集规范族和识别活前缀的DFA如下:

I0 = {S'→·S, S→·aSAB, S→·BA, B→·b}

I1 = {S'→S·}

I2 = {B→b·}

I3 = {S→a·SAB, S→·aSAB, S→·BA, B→·b}

I4 = {S→B·A, A→·aA, A→·B, B→·b}

I5 = {S→aS·AB, A→·aA, A→·B, B→·b}

I6 = {S→aSA·B, B→·b}

I7 = {A→a·A, A→·aA, A→·B, B→·b}

I8 = {A→B·}

I9 = {S→BA·}

I10 = {S→aSAB·}

I11 = {A→aA·}

显然，上述状态中没有出现冲突。显然，该文法是LR(0)的文法，因此也是SLR(1)的。

    求各个非终结符的Follow集，以便构造分析表：    

Follow(S')={#}        Follow(S)={a,b,#}

    Follow(A)={a,b,#}    Follow(B)={a,b,#}

构造的SLR(1)分析表如下：

 (2) 该文法的拓广文法G'为 

0．S' → S      

1．S → Sab 

2．S → bR      

3．R → S         

4．R → a    

其LR(0)项目集规范族和识别活前缀的DFA如下:

I0 = {S'→·S, S→·Sab, S→·bR}

I1 = {S'→S·, S→S·ab}

I2 = {S→b·R, R→·S, R→·a, S→·Sab, S→·bR}

I3 = {S→Sa·b}

I4 = {S→bR·}

I5 = {R→S·, S→S·ab}

I6 = {R→a·}

I7 = {S→Sab·}

显然，I1和I5存在移进-归约冲突。求S'和R的Follow集：

        Follow(S')={#    }

        Follow(R)=Follow(S)={a,#}

在I5中，出现的移进－归约冲突，且Follow(R)∩{a}={a}，不能用SLR(1)方法解决。因此，此文法不是SLR(1)文法。

15. 解答：

(1) 构造其拓广文法G'的产生式为 

0．S' → S    

1．S → A

2．A → BA    

3．A →  

4．B → aB    

5．B → b

构造其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下:

I0 = { [S'→·S, #], [S→·A, #], [A→·BA, #, [A→·, #],

         [B→·aB, a/b/#], [B→·b, a/b/#]} 

I1 = {[S'→S·, #]}

I2 = {[S→A·, #]}

I3 = {[A→B·A, #], [A→·BA, #], [A→·, #],

        [B→·aB, a/b/#], [B→·b, a/b/#]}

I4 = {[B→b·, a/b/#]}              

I5 = {[B→a·B, a/b/#], [B→·aB, a/b/#], 

        [B→·b, a/b/#]}

I6 = {[A→BA·, #]}

构造LR(1)分析表如下：

以上分析表无多的定义入口，所以该文法为LR(1)文法。

(3)对于输入串abab，其分析过程如下： 

16. 解答：

(1) 对于产生式S→AaAb|BbBa 来说

First(AaAb)∩First(BbBa)={a}∩{b}=

A，B∈VN仅有一条候选式。

因此，这个文法是LL(1)的。

(2) 下面构造这个文法的识别活前缀的DFA。

I0 = {S'→·S, S→·AaAb, S→·BbBa, A→·, B→·} 

I1 = {S'→S·}

I2 = {S→A·aAb}

I3 = {S→B·bBa}

I4 = {S→Aa·Ab, A→·}

I5 = {S→Bb·Ba, B→·}

I6 = {S→AaA·b}

I7 = {S→BbB·a}

I8 = {S→AaAb·}

I9 = {S→BbBa·}

由于Follow(A)=Follow(B)={a, b},因此项目集I0中存在归约-归约冲突。在I0状态下，当输入符号是a或是b时，不知用A→ 还是B→ 进行归约。故此文法不是SLR(1)的。但是，此文法时LR(1)的。

17. 解答：

该文法的拓广文法G'为 

0．S' → S    

1．S → (SR

2．S → a    

3．R → ,SR

4．R → )    

构造其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下:

I0 = {S'→·S, S→·(SR, S→·a}

I1 = {S'→S·}

I2 = {S→(·SR, S→·(SR, S→·a}

I3 = {S→a·}

I4 = {S→(S·R, R→·,SR, R→·)}

I5 = {S→(SR·}

I6 = {R→)·}

I7 = {R→,·SR, S→·(SR, S→·a}

I8 = {R→,S·R, R→·,SR, R→·)}

I9 = {R→,SR·}

每个LR(0)项目集中没有冲突。因此，此文法是LR(0)文法。其分析表如下：

18．解答：  略！