自上而下分析法

基本方法

一：帶回溯的分析方法。

二：不帶回溯的遞歸子程序（遞歸下降）分析方法。

主旨

對任意的輸入串，試圖用一切可能的辦法，從文法開始符號（根結）出發，自上而下地為輸入串建立一棵語法樹。或者説，為輸入串尋找一個最左推導。

性質

這種分析過程本質上是一種試探過程，是反覆使用不同產生式謀求匹配輸入串的過程。

過程

實現這種自上而下的帶回溯試探法的一個簡單途徑是讓每個非終結符對應一個遞歸子程序。每個這種子程序可作為一個布爾過程。一旦發現它的某個候選與輸入串相匹配，就用這個候選去擴展語法樹，並返回“真”值；否則，保持原來的語法樹和IP值不變，並返回“假”值。

面臨的問題

首先，是文法的左遞歸性問題。一個文法是含有左遞歸的，如果存在非終結符P

含有左遞歸的文法將使上述的自上而下的分析過程陷入無限循環。即當試圖用P去匹配輸入串時，我們會發現，在沒有識別任何輸入符號的情況下，又得重新要求P去進行新的匹配。

其次，由於回溯就碰到一大堆麻煩事情。如果我們走了一大段錯路，最後必須回頭，那麼，就應把已經做的一大堆語義工作推倒重來。

第三，在上述的自上而下分析過程中，當一個非終結符用某一個候選匹配成功時，這種成功可能僅是暫時的。

第四，當最終報告分析不成功時，我們難於知道輸入串中出錯的確切位置。

最後，由於帶回溯的自上而下分析實際上採用了一種窮盡一切可能的試探法，因此效率很低，代價極高。 ^[1]