勵志

勵志人生知識庫

自上而下分析法

自上而下分析法是一種基於文法的語法分析方法,它從文法的開始符號出發,通過不斷進行推導,直到推導所得的符號串與輸入串相同為止。這種方法本質上是一種試探過程,是反覆使用不同產生式謀求匹配輸入串的過程。

自上而下分析法可以分為帶回溯和不帶回溯的兩種。帶回溯的分析方法可能會陷入無限循環,即當試圖用某個非終結符去匹配輸入串時,如果沒有識別任何輸入符號,又得重新要求這個非終結符去進行新的匹配。不帶回溯的遞歸子程式(遞歸下降)分析方法則不會陷入無限循環,它每個非終結符對應一個遞歸子程式,每個這種子程式可作為一個布爾過程。一旦發現它的某個候選與輸入串相匹配,就用這個候選去擴展語法樹,並返回「真」值;否則,保持原來的語法樹和IP值不變,並返回「假」值。

自上而下分析法在實現過程中可能會遇到一些問題,例如文法的左遞歸性問題、回溯問題、效率問題和代價問題等。因此,在進行自上而下分析法時,需要消除文法的二義性,消除左遞歸,提取左公共因子,計算FIRST集合和FOLLOW集合,判斷文法是否為LL(1)型文法,一個文法經過這些步驟,並且是LL(1)文法,則可以用LL(1)分析法的兩個具體實現去分析。