遞迴下降剖析(recursive-descent parsing)
想像每條文法規則都變成一個小小的輔助函數,懂得辨認某一種東西,而這些輔助函數彼此呼叫,正如規則彼此引用一般。要辨認一個 Expression,你呼叫 parseExpression,它呼叫 parseTerm,後者呼叫 parseFactor,而 parseFactor 看到括號時又可能回頭呼叫 parseExpression。遞迴下降剖析正是如此:一個寫成一組相互遞迴函數的由上而下剖析器,每個非終端符號一個函數。
每個函數試著把它的非終端符號與詞符串流的目前位置匹配。它看下一個詞符,決定走哪條產生式,吃掉該產生式所需的詞符,並對該產生式內任何非終端符號呼叫對應函數。E -> num | ( E ) 的函數檢查下一個詞符:若是數字便吃掉它;若是左括號便吃掉它、遞迴呼叫 parseE、然後預期一個右括號。程式自身的呼叫堆疊負責記憶,恰好對映剖析樹的巢狀。當一個前瞻詞符總足以挑出產生式時,這稱為預測式遞迴下降,無需回溯;沒有這個性質時,剖析器可能得試一條產生式、失敗後再退回。
遞迴下降是多數人最先接觸的剖析技術,許多真實編譯器,包括正式的 C 與 C# 前端,都用手寫的遞迴下降剖析器。它的吸引力在於直接:程式碼看起來就像文法,錯誤容易精準回報,而且你能在恰好需要的地方插入客製處理。代價是,和所有由上而下方法一樣,它無法處理左遞迴,而手寫剖析器得隨語言成長以人工維護。
一個 factor 剖析函數:parseFactor() { 若下一個是 NUMBER 則吃掉它;否則若下一個是 '(' 則吃掉 '('、呼叫 parseExpr()、預期 ')';否則回報語法錯誤。} 程式堆疊上每個呼叫框對應剖析樹的一個節點。
每個非終端符號一個函數;程式的呼叫堆疊成了剖析樹的脊柱。
遞迴下降是實作由上而下(常為 LL)剖析器的一種方式,而非另一類文法。它繼承了由上而下的盲點:除非改寫文法,否則遇到左遞迴會無限迴圈。