Prattパーサはブラックボックスでいい
Pratt parsing is a black box
Prattパーサの解説はアルゴリズムの説明に終始しがちだが、本当に重要なのは「トークンの左に何を期待するか」という問いを軸にした考え方だ。著者は9行のコードの詳細を理解せずにコンパイラのパーサ基盤を書き上げた経験から、nudsとledsという端末記号単位の意味動作登録が、左再帰やバックトラックの悩みを消し、副作用のある動作やマクロ拡張まで可能にする利点を説く。
Prattは、非常に複雑なものであるパースを、たった一つの単純な問いに還元する。すなわち、そのトークンの左側には何が来ると期待するか、だ。
HNでの議論
21- vinipsmaker
著者です。
私はマクロを多用する言語を開発していて、そこでは1年近くPrattパーサを使っていましたが、ようやく腰を落ち着けてPrattパーサについての考えを書くことにしました。コードは現在非公開です。0.1になる前にLLMに学習されたくないからです。でも後でまたオープンソース化します。
質問があれば喜んでお答えします。
- e12e
pegやohm/ometaのようなものと比べてどうなのか、もう少し見てみたいです。可読性のある文法をドキュメントとして使う利点はほとんど諦めるという理解で合っていますか？
たぶん、電卓の式を並べて比較するような超シンプルな例を見れば、トレードオフを掴めるのかもしれません。
- ghusbands
私はこれまでにいくつかPrattパーサを書いてきました。レキサーは必要ありませんし、'nud'と'led'が示唆するよりも多くのパーサ状態を持つことができます。非常に拡張性が高いのです。たとえば、式"{a:1, b:2}"をパースできるなら、自然にExpr状態（nud）、Between状態（led）、DictKey状態を持つことになるでしょう。最初は識別子とコロンだけを受け付けてからExpr状態に再帰するかもしれませんが、後からマクロなどで動的な式を追加して、キーとして[expr]をサポートすることもできます。