如何判斷一個(gè)文法是ll課件文法

如何判斷一個(gè)文法是LL文法學(xué)習(xí)LL文法的定義和特點(diǎn)，查看文法是否存在左遞歸，二義性，可空產(chǎn)生式，確定每個(gè)非終結(jié)符的FIRST集和FOLLOW集，檢查FIRST集是否互斥等方法。什么是LL文法？1定義一種上下文無(wú)關(guān)文法（CFG）2特點(diǎn)每一步分析都可以找到唯一一個(gè)產(chǎn)生式（左遞歸、可空產(chǎn)生式、二義性會(huì)破壞這個(gè)特性）3應(yīng)用語(yǔ)法分析器、編譯器等為什么存在左遞歸就不是LL文法？左遞歸會(huì)導(dǎo)致無(wú)限遞歸，判斷一個(gè)文法是否為L(zhǎng)L文法，需要消除左遞歸，才能保證每一步分析都可以找到唯一一個(gè)產(chǎn)生式。左遞歸出現(xiàn)遞歸，使得規(guī)則沒(méi)有固定的輸入規(guī)則沒(méi)有左遞歸只有固定的輸入規(guī)則，分析器可用確定的方式發(fā)現(xiàn)正確的產(chǎn)生式二義性會(huì)破壞LL文法的唯一產(chǎn)生式特性二義性產(chǎn)生的原因是同一個(gè)輸入串可以有不止一種分析方法，從而找到不止一套產(chǎn)生式。如果一個(gè)文法是二義性的，那么它就不能是LL文法。1原因同一輸入串有不止一種分析方法2結(jié)果不止一套產(chǎn)生式檢查是否存在可空產(chǎn)生式可空產(chǎn)生式容易造成FIRST和FOLLOW集的沖突，影響分析器的判斷，需要把可空產(chǎn)生式行文不變地消除。存在可空產(chǎn)生式一些非終結(jié)符的派生可以推導(dǎo)出空串，即Λ不存在可空產(chǎn)生式?jīng)]有一個(gè)非終結(jié)符可以推出空串如何確定每個(gè)非終結(jié)符的FIRST集和FOLLOW集？為了判斷一個(gè)文法是否為L(zhǎng)L文法，需要明確每個(gè)非終結(jié)符的FIRST集和FOLLOW集，利用以下方法來(lái)解決此問(wèn)題。1FIRST集的求法把產(chǎn)生式的右側(cè)的符號(hào)的FIRST集加入該非終結(jié)符的FIRST集，如果存在則遞歸2FOLLOW集的求法找到一個(gè)非終結(jié)符A，看一下整個(gè)文法中的table中使用到了這個(gè)非終結(jié)符后面的符號(hào)有哪些，對(duì)于這一串拿出來(lái)，如果to的FIRST集中有Λ就繼續(xù)找，否則FIRST集直接加入A的FOLLOW集檢查FIRST集是否互斥如果兩個(gè)產(chǎn)生式的非終結(jié)符的FIRST集重疊，就稱(chēng)它們的FIRST集是互斥的。判斷一個(gè)文法是否是LL(1)文法，需要保證每個(gè)非終結(jié)符的FIRST集是唯一的?；コ獾腇IRST集兩個(gè)產(chǎn)生式的非終結(jié)符的FIRST集重疊，導(dǎo)致FIRST集無(wú)法唯一判斷非互斥的FIRST集兩個(gè)產(chǎn)生式非終結(jié)符的FIRST集不重疊，F(xiàn)IRST集唯一如何使用預(yù)測(cè)分析表判斷文法是否是LL(1)文法？預(yù)測(cè)分析表可以用于判斷一個(gè)文法是否為L(zhǎng)L(1)文法，如果預(yù)測(cè)分析表中每個(gè)格子最多只有一個(gè)產(chǎn)生式，則該文法為L(zhǎng)L(1)文法。步驟求解各非終結(jié)符的FIRST集和FOLLOW集根據(jù)FIRST集、FOLLOW集填表檢查各表格是否唯一優(yōu)點(diǎn)簡(jiǎn)單、直接，效率更高缺點(diǎn)僅適用于LL(1)文法如何使用遞歸下降分析器分析文法？遞歸下降分析器是一種自頂向下的分析器，它通過(guò)各產(chǎn)生式的遞歸調(diào)用實(shí)現(xiàn)對(duì)輸入串的分析。如果遞歸下降分析器能夠正確處理輸入串，則該文法是LL(1)文法。遞歸調(diào)用對(duì)每個(gè)非終結(jié)符，都編寫(xiě)一個(gè)語(yǔ)法分析程序，如果滿足下列性質(zhì)，即為遞歸下降分析器分析輸入串采用深度優(yōu)先策略，對(duì)輸入串進(jìn)行分析如何嘗試實(shí)現(xiàn)文法？嘗試實(shí)現(xiàn)文法，觀察文法分析器是否能夠正確地處理輸入串，是驗(yàn)證一個(gè)文法是否是LL(1)文法的有效方法。文法分析器能夠正確處理輸入串該文法是LL(1)文法文法分析器不能正確處理輸入串說(shuō)明該文法不是LL(1)文法如何使用其他方法判斷文法是否為L(zhǎng)L文法？當(dāng)不能使用預(yù)測(cè)分析表、遞歸下降分析器等方法來(lái)驗(yàn)證一個(gè)文法是否是LL文法時(shí)，可以考慮使用其他方法，例如狀態(tài)機(jī)等方法。狀態(tài)機(jī)將輸入串看作一個(gè)狀態(tài)機(jī)的輸入，根據(jù)狀態(tài)機(jī)的規(guī)則，確定該文法的分析表如何消除左公因子和檢查產(chǎn)生式右部？消除左公因子和檢查產(chǎn)生式右部是否只有一個(gè)終結(jié)符或一個(gè)非終結(jié)符，并檢查每個(gè)產(chǎn)生式右部是否存在相同的前綴，是判斷一個(gè)文法是否為L(zhǎng)L（1）文法的步驟。1步驟消除左