剖析與文法的應用

由下而上剖析(bottom-up parsing)

由上而下剖析從大概念出發、朝單字推進;由下而上剖析反其道而行。想像拼拼圖不是靠猜最終圖樣,而是把眼前看得到的小塊拼成越來越大的塊,直到整塊板子成為一片。由下而上剖析從真正的詞符出發,反覆把它們組合起來,反向套用文法規則,直到一切合併回起始符號為止。

在機制上,由下而上剖析器由左到右掃描輸入,把目前看到的符號保存在一個堆疊上。每一步它做兩件事之一:移位(shift),把下一個詞符壓入堆疊;或歸約(reduce),認出堆疊頂端幾個符號匹配某規則 A -> alpha 的右側,並把它們換成左側 A。被歸約的那一塊稱為句柄(handle)。由下而上剖析器從葉子往上建到根的剖析樹,而反向讀來則勾勒出一個最右推導。整門技藝在於每一步要決定該移位還是歸約,若歸約又該用哪條規則,這正是 LR 家族剖析器用一張由文法狀態預先算好的表所解決的。

由下而上的 LR 剖析嚴格強於由上而下的 LL 剖析:它能直接處理左遞迴(所以自然的算術文法照寫就行),並能應付遠為廣泛的文法類別。這正是 yacc 與 bison 等自動剖析器產生器產出由下而上的 LR 剖析器、而非由上而下者的原因。代價是對人不友善:LR 表由工具產生,幾乎無法閱讀或手動編輯,而文法中的衝突會以晦澀的移位-歸約或歸約-歸約訊息浮現。

對 E -> E + E | num 與輸入 num + num,由下而上剖析器移位 num、把它歸約為 E、移位 +、移位 num、把它歸約為 E,再把 E + E 歸約為 E。反向讀這些歸約即得一個最右推導;樹是從葉子先建起的。

由下而上:從詞符出發,移位到堆疊上,把句柄向上歸約回起始符號。

由下而上剖析器自然地處理左遞迴,這正是由上而下剖析器辦不到的。那份額外能力正是為何產生出的剖析器幾乎總是由下而上的 LR,而非由上而下。

又称
shift-reduce strategy由下而上剖析自底向上剖析