由上而下剖析(top-down parsing)
假設有人告訴你答案是一個句子,你得弄清它是怎麼建出來的,但你從大概念開始往下推到單字。你先假設「這是一個 Sentence」,再猜「Sentence 是 Subject 後接 Predicate」,然後展開 Subject,如此繼續,直到你的猜測抵達紙上真正的單字。由上而下剖析正是如此:它從文法的起始符號出發,試圖向下朝輸入長出一個推導。
在機制上,由上而下剖析器從根開始建剖析樹,並在每個非終端符號處預測接下來要套用哪條產生式,再檢查該預測能否匹配即將到來的詞符。它產生一個最左推導:總是先展開最左邊剩下的非終端符號。核心難處在於選對規則。若非終端符號 A 有規則 A -> b... 與 A -> c...,剖析器偷看下一個詞符,選擇其展開能以該詞符開頭的規則。當一個詞符的前瞻總是足以決定時,該文法即為 LL(1),剖析既乾淨又快。有兩件事會破壞這種預測、必須先修正:左遞迴(像 A -> A x 這樣的規則會讓剖析器猜 A 時無限迴圈),以及規則間的共同前綴(會模糊選擇,需要左因子分解)。
由上而下剖析是遞迴下降剖析器與 LL 剖析器的基礎,是你能輕易手寫的那種,也是 ANTLR 之類工具產生的那種。它的一大優點是程式碼對映文法,每個非終端符號一個函數,因此易讀、易加入客製錯誤訊息、易除錯。它的限制在於能力:由上而下剖析器能處理的文法類別比由下而上的 LR 剖析器小,因此有些自然的文法在由上而下剖析器能應付前必須先改寫。
對 E -> num T、T -> + num T | epsilon 與輸入 1 + 2,由上而下剖析器從 E 開始,展開為 num T(匹配 1),接著對 T 偷看到 + 而選 T -> + num T(匹配 + 2),再對下一個 T 偷看到輸入結束而選 T -> epsilon。完成,找到最左推導。
由上而下:從起始符號出發,每個非終端符號預測一條規則,向下長到詞符。
由上而下剖析器無法直接處理左遞迴文法;A -> A x 會把剖析器送入無限遞迴。必須先改寫文法以消除左遞迴。