编译原理第三版何炎祥第四章习题答案.pdf

作业四

P72

5.2

（1）

（2）FIRST(+E)={+}

FIRST(ε)={ε}

FIRST(*F)={*}

FIRST((E))={(}

FIRST(a)={a}

FIRST(^)={^}

所以FIRST(P)={(,a，^}

FIRST(F)=FIRST(P)={(,a，^}

FIRST(F’)={*,ε}

FIRST(T)=FIRST(F)={(,a，^}

FIRST(T’)={(,a，^,ε}

FIRST(E)=FIRST(T)={(,a，^}

FIRST(E’)={+,ε}

FOLLOW(E)={),$}

FOLLOW(E’)=FOLLOW(E)={),$}

FOLLOW(T)={+,),$}

FOLLOW(T’)=FOLLOW(T)={+,),$}

FOLLOW(F)=FIRST(T’)={(,a，^,ε}

FOLLOW(F’)=FOLLOW(F)={(,a，^,ε}

FOLLOW(P)=FIRST(F’)={*,ε}

（3）

+ε*()a^$

EE→TE’E→TE’E→TE’

E’E’→+EE’→εE’→εE’→ε

TT→FT’T→FT’T→FT’

T’T’→εT’→εT’→TT’→εT’→TT’→TT’→ε

FF→PF’F→PF’F→PF’

F’F’→εF’→εF’→*FF’→εF’→εF’→εF’→εF’→ε

PP→（E）P→aP→^

因为SELECT(E’→+E)={+}∩SELECT()={}=∅

E’→εε,),$

SELECT()={(,a,^}∩SELECT()={+,}=∅

T’→TT’→εε,),$

SELECT()={*}∩SELECT()={+,}=∅

F’→*FF’→εε,(,),a,^,$

SELECT(P→（E）)={(}∩SELECT(P→a)={a}∩SELECT(P→^)={^}=∅

所以该文法是LL（1）文法。

5.4

(1)S→SbA|aA存在左递归，消除左递归后改写为S→aA{bA}

则文法G[S]:

S→aA{bA}

B→Sb

A→Bc

该文法满足LL（1）文法条件。

（2）对于产生式S→aA{bA}

FIRST（aA{bA}）={a}

所以M[S,a]=’S→aA{bA}’

对于产生式B→Sb

FIRST(Sb)={a}

所以M[B,a]=’B→Sb’

对于产生式A→Bc

FIRST（B）={a}