## 概念簡述 回溯：分析工作部分地或全部地退回到之前的一個階段，在當前階段采取與之前不同的決策重新推進工作 FIRST(α)：令Ｇ是一個不含左遞歸的文法，對G的所有非終結符的每個候選α定義它的終結首符集FIRST(α)為： - FIRST(α)={a | α=>*a…, a∈VT} - 若α=>*ε，則規定ε∈FIRST(α) - FIRST(α)是α的所有可能推導的開頭終結符或可能的ε ## 消除回溯 - 回溯的問題 回溯帶來的問題就是低效率 - 回溯的條件 文法中，對于某個非終結符的規則其右部有多個選擇，并根據所面臨的輸入字符不能準確的判斷所要的選擇，那么就需要搜索，就會導致回溯。 - 避免回溯的要求 FIRST(αi)∩FIRST(αj)=? 令Ｇ是一個***不含左遞歸***的文法，對G的所有非終結符的每個候選α定義它的終結首符集FIRST(α)為： - FIRST(α)={a | α=>*a…, a∈VT} 若α=>*ε，則規定ε∈FIRST(α) FIRST(α)是α的所有可能推導的開頭終結符或可能的ε - 如果非終結符Ａ的所有候選首符集兩兩不相交，即Ａ的任何兩個不同候選αi和αｊ FIRST(αi) ∩FIRST(αj)=Φ - 那么當要求Ａ匹配輸入串時，Ａ就能根據它所面臨的第一個輸入符號ａ，準確的指派某一個候選前去執行任務。這個候選就是那個終結首符集含ａ的α。 - 提取左因子法消除回溯 - 假定Ａ的規則是： Ａ→δβ1 |δβ2 | … |δβn |γ1 |γ2 | … |γm（其中，每個γ不以δ開頭） 那么這些規則可以改寫為： A→δA’ |γ1 |γ2 | … |γm A’→β1 |β2 | … |βn - 經過反復提取左因子，就能夠把每個非終結符（包括新引進者）的所有候選首符集便成為兩兩不相交。我們為此要***付出的代價是大量引進新的非終結符和ε產生式***。 - 實現過于簡單，故不再實現代碼