編譯原理經(jīng)典習(xí)題詳解(1)計(jì)算文法G[S]各非終結(jié)符的First集和Follow集。(2)判斷該文法是否為L(zhǎng)L(1)文法。(3)若為L(zhǎng)L(1)文法，構(gòu)造其預(yù)測(cè)分析表。分析與解答：(1)計(jì)算First集和Follow集：First集定義：First(X)是由所有從X推導(dǎo)出的句型的第一個(gè)終結(jié)符組成的集合，若X能推導(dǎo)出ε，則ε也在First(X)中。Follow集定義：Follow(A)是由所有在句型中緊跟在A之后的終結(jié)符組成的集合，若A是句型的最右符號(hào)，則#（句子結(jié)束符）也在Follow(A)中。首先，我們列出所有非終結(jié)符：S,A,B。終結(jié)符：a,b。計(jì)算First集：*First(S)：S有兩個(gè)產(chǎn)生式：S→aAb和S→bBA。第一個(gè)產(chǎn)生式以終結(jié)符a開頭，所以a∈First(S)。第二個(gè)產(chǎn)生式以終結(jié)符b開頭，所以b∈First(S)。因此，F(xiàn)irst(S)={a,b}。*First(A)：A有三個(gè)產(chǎn)生式：A→ab,A→a,A→ε。A→ab：以a開頭，a∈First(A)。A→a：以a開頭，a∈First(A)。A→ε：ε∈First(A)。因此，F(xiàn)irst(A)={a,ε}。*First(B)：B有兩個(gè)產(chǎn)生式：B→a,B→ε。B→a：以a開頭，a∈First(B)。B→ε：ε∈First(B)。因此，F(xiàn)irst(B)={a,ε}。計(jì)算Follow集：首先，令Follow(S)={#}(因?yàn)镾是開始符號(hào))。*Follow(A)：尋找所有包含A的產(chǎn)生式右部，并查看A之后的符號(hào)。1.S→aAb：A后面是終結(jié)符b。所以b∈Follow(A)。2.A→ab：A是產(chǎn)生式左部，看右部末尾，無(wú)后續(xù)符號(hào)，故需將Follow(A)的計(jì)算依賴于其左部非終結(jié)符的Follow集？不，這里A是產(chǎn)生式左部，對(duì)于A的產(chǎn)生式右部的末尾符號(hào)b，它會(huì)影響使用該A產(chǎn)生式的上下文。但計(jì)算Follow(A)本身，是看A在其他產(chǎn)生式中作為右部符號(hào)時(shí)，其后的符號(hào)。3.A→a：同上。4.A→ε：同上。另，A在S→aAb中是作為右部中間符號(hào)出現(xiàn)的，其后是b，已考慮。A是否在其他產(chǎn)生式中出現(xiàn)？沒有了。所以，F(xiàn)ollow(A)=。*Follow(B)：尋找所有包含B的產(chǎn)生式右部，并查看B之后的符號(hào)。B出現(xiàn)在S→bBA中，B后面是A。所以，F(xiàn)irst(A)中除ε外的元素都屬于Follow(B)。First(A)={a,ε}，所以a∈Follow(B)。由于First(A)包含ε，所以還需要將Follow(S)加入Follow(B)。因?yàn)楫?dāng)A推導(dǎo)出ε時(shí)，B后面緊跟著的就是S的Follow符號(hào)。Follow(S)={#}，所以#∈Follow(B)。因此，F(xiàn)ollow(B)={a,#}。*再次檢查Follow(A)和Follow(B)是否有遺漏：對(duì)于A，是否還有其他產(chǎn)生式？沒有。所以Follow(A)=正確。對(duì)于B，是否還有其他產(chǎn)生式？沒有。所以Follow(B)={a,#}正確?？偨Y(jié)：*First(S)={a,b}*First(A)={a,ε}*First(B)={a,ε}*Follow(S)={#}*Follow(A)=*Follow(B)={a,#}(2)判斷該文法是否為L(zhǎng)L(1)文法：LL(1)文法的定義：對(duì)于文法中的任意兩個(gè)產(chǎn)生式A→α和A→β（α≠β），必須滿足：1.First(α)∩First(β)=?。2.若β能推導(dǎo)出ε（即ε∈First(β)），則First(α)∩Follow(A)=?；對(duì)稱地，若α能推導(dǎo)出ε，則First(β)∩Follow(A)=?。我們需要對(duì)文法中每個(gè)非終結(jié)符的所有產(chǎn)生式對(duì)進(jìn)行檢查。*檢查非終結(jié)符S：S有兩個(gè)產(chǎn)生式：S→aAb和S→bBA。First(aAb)={a}，F(xiàn)irst(bBA)=。{a}∩=?。滿足條件1。無(wú)需檢查條件2（因?yàn)閮蓚€(gè)產(chǎn)生式的右部都不能推導(dǎo)出ε，其First集中不含ε）。*檢查非終結(jié)符A：A有三個(gè)產(chǎn)生式：A→ab,A→a,A→ε。需要兩兩檢查：a)A→ab和A→a：First(ab)={a}，F(xiàn)irst(a)={a}。{a}∩{a}={a}≠?。僅此一對(duì)產(chǎn)生式就不滿足LL(1)文法的條件