直觀理解 Pratt 解析法

背景

這篇文章探討了編譯器如何將平面的程式碼文本轉換為抽象語法樹（AST），特別聚焦於處理運算子優先順序的挑戰。作者透過視覺化「左傾」與「右傾」樹結構的變化，直觀地解釋了 Pratt 解析法（Pratt Parsing）的核心機制，即如何透過回溯樹的脊柱（spine）來處理優先順序的轉換，並提供了一套簡潔的遞迴實作邏輯。

社群觀點

在 Hacker News 的討論中，多數開發者對 Pratt 解析法抱持極高的評價，認為它是處理表達式解析最優雅且實用的技術。許多留言者指出，雖然學術界常強調形式語法理論與複雜的解析器生成工具，但在實際開發中，結合遞迴下降解析（Recursive Descent）與 Pratt 解析法往往就足以應對絕大多數需求。這種組合不僅實作簡單，且對於現代編譯器來說，僅需兩到三個標記（token）的預讀量即可運作，甚至許多主流的大型編譯器也是採用類似的架構，而非僅限於玩具語言。

然而，也有討論指出這種解析方式的侷限性。有觀點認為，當需求超出單純的「全有或全無」解析，轉向需要增量解析（Incremental Parsing）的場景時，例如為了提升語言伺服器（LSP）的效率，可能就需要如 tree-sitter 這類更複雜的工具。此外，關於實作的簡潔性，有開發者提出另一種「優先順序爬升」（Precedence Climbing）的思路，主張透過為不同優先級編寫顯式函數來達成類似效果，這種做法的結構與 EBNF 語法定義高度一致，易於理解。但反對者反駁，Pratt 解析法的優勢在於其靈活性，特別是當語言需要支援使用者自定義運算子時，Pratt 解析法的表格驅動特性會比硬編碼的函數調用更具擴充性。

討論中亦觸及了對傳統教科書的不滿。部分開發者直言如《龍書》（Dragon Book）等經典教材過於艱澀且不夠實用，認為解析與編譯的邏輯在函數式語言中更容易被理解，隨後再轉譯回指令式語言會更清晰。此外，還有留言者分享了更直觀的視覺化思考方式，將運算子視為物理上的分割線，透過尋找結合力最低的運算子來遞迴切分表達式，這種方式在概念上與笛卡爾樹（Cartesian trees）的構建不謀而合。整體而言，社群共識傾向於支持更直覺、更具實踐價值的解析方法，並對過度理論化的形式證明保持距離。

延伸閱讀

在討論中，參與者推薦了幾項具代表性的資源。首先是 Vaughan Pratt 於 1973 年發表的原始論文《Top Down Operator Precedence》，留言者稱讚其寫作風格獨樹一幟且充滿力量。其次，針對「優先順序爬升」與 Pratt 解析法的比較與推導，有開發者推薦了 Theodore Norvell 撰寫的專題文章。最後，對於希望深入了解增量解析的讀者，tree-sitter 專案被視為當前工業界處理複雜解析需求的重要參考。