南京邮电大学 编译原理 课后习题答案和讲解2.docVIP

南京邮电大学 编译原理 课后习题答案和讲解2 《编译原理》习题解答 P38-39 8、设有文法G 2．A::=BC（ε|D）{X（Z|Y）}::= BC [B] [A, B] 由于M（A, a）={A, B}，故有M’（[A], a）=[A, B] 同样 M’（[A]，b）=[B] M’（[B]，a）= ? M’（[B]，b）=[A，B] 由于M（{A，B}，a）= M（A，a）U M（B，a）= {A，B}U ?= {A，B} 故 M’（[A，B]，a）= [A，B] 由于M（{A，B}，b）= M（A，b）U M（B，b）={B}U {A，B} = {A，B} 故 M’（[A，B]，b）= [A，B] S’=[A]，终态集Z’={[A，B]，[B]} 重新定义：令0=[A] 1=[B] 2=[A, B]，则DFA如下所示： ５ ＃∈FOLLOW(E) FOLLOW(E)={#} 规则二 )∈FOLLOW(E) FOLLOE(E)={ )，#} FIRST(E’)-{ε}FIRST(T’)-{ε}FIRST(F’)-{ε}规则三 FOLLOW(E) FOLLOW(E) FOLLOW(T) FOLLOW(T) FOLLOW(F) FOLLOW(F) 最后结果为： FIRST(E’)={+, ε} FIRST(F’)={*, ε} FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P) ={ (，a，b，∧} FIRST(T’)={ (，a，b, ε，∧) FOLLOE(E)={ ), ＃} FOLLOW(E’)={＃，)} FOLLOW(T)={＋，＃，）} FOLLOW(T’)= {＋，＃，）} FOLLOW(F)={ (，)，a，b，＋，＃，∧} FOLLOW(F’)={ (，)，a，b，＋，＃，∧} FOLLOW(P)= { (，)，a，b，＋，＃，∧,*} （2）证明该文法是LL（1）文法： FOLLOW(E’) FOLLOW(E’)={# ，)} FOLLOW(T) FOLLOW(T)={＋，＃，）} FOLLOW(T’) FOLLOW(T’)= {＋，＃，）} FOLLOW(F) FOLLOW(F)={ (，)，a，b，＋，＃，∧} FOLLOW(F’) FOLLOW(F’)= { (，)，a，b，＋，＃，∧} FOLLOW(P) FOLLOW(P)= { (，)，a，b，＋，＃，∧,*} FOLLOW(T) FOLLOW(T)={+} FOLLOW(F) FOLLOW(F)={ (，a，b，∧} FOLLOW(P) FOLLOW(P)={*} １１ 证明：对于规则E’::=+E |ε，T’::=T |ε，F’::=*F’ |ε （仅有一边能推出空串） 有FIRST(+E)={+}∩FIRST(ε)= ?，FIRST(T)={(, a, b, ∧}∩FIRST(ε)= ? FIRST(*F’)={*}∩FIRST(ε)= ?，FIRST(+E)={+}∩FOLLOW(E’)= {#, )}=? FIRST(T)={(, a, b, ∧}∩FOLLOW(T’)= {+, #, )}=? FIRST(*F’)={*}∩FOLLOW(F’)= { (，)，a，b，＋，＃，∧}=? 所以该文法是LL（1）文法。 （3）构造文法分析表 E E’ T T’ F F’ P 下面分析符号串a*b+b 步骤 分析栈 余留输入串 所用的产生式 1 #E a*b+b# E→TE’ 2 #E’T a*b+b# T→FT’ 3 #E’T’F a*b+b# F→PF’ 4 #E’T’F’P a*b+b# P →a 5 #E’T’F’a a*b+b# 6 # E’T’F’