编译原理(陈火旺第三版)练习答案

P81-2

文法：E→TE' E'→+E|ε T→FT' T'→T|ε F→PF' F'→*F'|ε P→（E）|a|b| （1）

First(E) = {(,a,b, } First(E') = {+,ε} First(T) = {(,a,b, } First(T') = {(,a,b, , ε} First(F) = {(,a,b, } First(F') = {*,ε} First(P) = {(,a,b, }

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

Follow(T')={+,),#} Follow(F)= {+,(,a,b, ,),# } Follow(F')={+，(,a,b, ,),# } Follow(P) ={*，+,(,a,b, ,),# }

（2）文法无左递归，考察E'→+E|ε T'→T|ε F'→*F'|ε P→（E）|a|b| E'→+E|ε： First(E') = {+,ε}∩Follow(E')={#,)} = Φ

T'→T|ε： First(T') = {(,a,b, , ε} ∩Follow(T')={+,),#} = Φ F'→*F'|ε：First(F') = {*,ε}∩Follow(F')={ (,a,b, ,),# } = Φ P→（E）|a|b| ：候选式终结首符集两两不相交 所以该文法为LL(1)文法。 （3） LL(1)分析表 + * （ ） a b # E E→TE' E→TE'E→TE'E→TE' E' E'→+E E'→ε E'→εT T→FT' T→FT'T→FT'T→FT' T' T'→ε T'→T T'→εT'→T T'→T T'→T

T'→ε

F F→PF'

F→PF'F→PF'F→PF' F' F'→εF'→*F' F'→ε

F'→ε

F'→εF'→εF'→ε F'→εP

P→（E）

P→a

P→b

P→

（4） 构造递归下降程序

Procedure E; Begin

If sym = ‘（’ or sym = ‘a’ or sym = ‘b’ or sym = ‘ ’ Then begin T；E' end Else error End

Procedure E'; Begin

If sym = ‘+’

Then begin advance ; E end

Else if sym <> ‘)’ and sym <> ‘#’ then error End

Procedure T; Begin

If sym = ‘(’ or sym = ‘a’ or sym = ‘b’ or sym = ‘ ’ Then begin F; T' end Else error End