《编译原理教学-华南理工》第四章作业.pptVIP

文法G： A-aABe | a B-Bb | d （1）对文法G进行改写，判断改写以后的文法是否为LL(1)文法； （2）给出它的预测分析表； （3）给出输入串aadbe#的分析过程，并说明该串是否为该文法的一个句子 （1）对文法G进行改写 A-aABe | a B-Bb | d 文法含有左递归和左公共因子，一定不是LL(1)文法。提取左公共因子，消除左递归后得： A- aA’ A’-ABe | ε B- dB’ B’-bB’ | ε 判断改写以后的文法是否为LL(1)文法 A- aA’ A’-ABe | ε B- dB’ B’-bB’ | ε 1 求出能推出ε非终结符 { A’ , B’ } FIRST A A’ B B’ 3计算FOLLOW集 FOLLOW A A’ B B’ 2计算FIRST集 ε ε a a d b # # d e e d select(A- aA’) =first(aA’) ={a} select(A’-ABe ) =first(ABe) ={a} select(A’-ε) =follow(A’) ={#, d} select(B- dB’) =first(dB’) ={d} select(B’-bB’ ) =first(bB’) ={b} select(B’-ε) =follow(B’) ={e} FIRST A A’ B B’ FOLLOW集 FOLLOW A A’ B B’ FIRST集 ε ε a a d b # # d e e d 4计算SELECT集 select(A- aA’) =first(aA’) ={a} select(A’-ABe ) =first(ABe) ={a} select(A’-ε) =follow(A’) ={#, d} select(B- dB’) =first(dB’) ={d} select(B’-bB’ ) =first(bB’) ={b} select(B’-ε) =follow(B’) ={e} select(A’-ABe ) ∩ select(A’-ε) = Φ Select(B’-bB’ ) ∩ select(B’-ε) = Φ 因为具有相同左部的产生式的SELECT集的交集为空，所以此文法是LL(1)文法。 （2）给出它的预测分析表； 已求得产生式的SELECT集 select(A- aA’) ={a} select(A’-ABe ) ={a} select(A’-ε) ={#, d} select(B- dB’) ={d} select(B’-bB’ ) ={b} select(B’-ε) ={e} 构造预测分析表如下： a b d e # A A-aA’ A’ A’-ABe A’-ε A’-ε B B- dB’ B’ B’-bB’ B’-ε （3）给出输入串aadbe#的分析过程，并说明该串是否为该文法的一个句子 a b d e # A A-aA’ A’ A’-ABe A’-ε A’-ε B B- dB’ B’ B’-bB’ B’-ε 步骤 分析栈 剩余输入串 所用产生式 1 #A aadbe# A-aA’ 2 #A’a aadbe# a匹配 3 #A’ adbe# A’-ABe 4 #eBA adbe# A-aA’ 5 #eBA’a adbe# a匹配 6 #eBA’ dbe# A’-ε a b d e # A A-aA’ A’ A’-ABe A’-ε A’-ε B B- dB’ B’ B’-bB’ B’-ε 步骤 分析栈 剩余输入串 所用产生式 6 #eBA’ dbe# A’-ε 7 #eB dbe# B-dB’ 8 #eB’d dbe# d匹配 9 #eB’ be# B’-bB’ 10 #eB’b be# b匹配 11 #eB’ e# B’-ε 12 #e e# e匹配 13 # # acc