Prattパーサーは操車場アルゴリズムの再帰版だと気づけば一気に理解できる
Writing about pratt parsing so I remember it
Cの式パーサーを作る過程でPratt parsingを学んだ著者が、理解の鍵となった操車場アルゴリズムとの対応関係を解説。明示的な演算子スタックをコールスタックに置き換えることで、部分式への再帰的な進入が可能になり、括弧や単項演算子の追加が格段に簡単になる。両アルゴリズムのC実装を比較しながら、拡張性の違いを具体的に示している。
操車場アルゴリズムでより低い結合強度に遭遇したときにスタックを巻き戻すのは、Prattパーサーで再帰呼び出しから戻ることと同じだ。