Prattパーサーは他のパーサータイプとどのように比較されますか？

Question

私は最近、thisの優れた記事からPrattパーサーについて学びました。Prattパーサーは、再帰的な降下パーサーよりもシンプルで洗練されています。私は彼らが他のパーサーのタイプと比較してどのように多くの情報を見つけようとしましたが、Wikipediaの記事はほとんどスタブではなく、それを使用する大きなプロジェクトの量が2と等しいことがわかりました。

なぜPrattパーサーはほとんど使われていないのですか？彼らには私が知らない重大な制限や欠点がありますか？どのくらい正確に他のパーサーのタイプと比較していますか？いつ、どうすればいいのですか？

Answer 1

Prattパーサーと、いわゆる "シャンティングヤード"パーサー（これははるかに長いWikipediaの記事が添付されています）との違いはごくわずかです。主な違いは、Prattが再帰を使用し、スタックを使用しているのに対し、Djikstra（ "shunting yard"）は明示的なスタックを保持していることです。それ以外は、まったく同じ操作シーケンスを実行します。私は、アルゴリズムのDjikstraの表現は、再聴覚障害のために一般的であると考えています。

プログラムスタックを使用することにはいくつかの利点があります。それらのうちの1つは、スタック全体が1つの型である必要はないので、型の安全性を維持する方が簡単だということです。一方、多くの式パーサは1つの型しか持たない。

ドラゴンブックには、文法から演算子優先順位テーブルを生成するためのヒントが含まれています。それが指摘しているように、アルゴリズムが成功するという事実は必ずしもオペレータ優先パーザがまったく同じ言語を解析することを意味するものではない。私が確かに忘れてしまった興味深い情報があります。アルゴリズムに興味があるなら、それはあなたが見ることができる場所の1つです。プロダクトの結果を<と>で明示的に囲むと、派生を見て<と>の優先順位関係演算子を生成できるという興味深い洞察が含まれています。

全体的に私の経験は、「​​私の神、私はXを見つけたばかりで、それは素晴らしいですし、もっと多くの人がそれについて知っているのはなぜですか？ ？ "、答えは"あなたの無知が普遍的であるとは思わないでください "と答えています。しかし、多分私は今日、ただの皮肉な気分に過ぎません。

ちなみに、Luaパーサーは、Prattスタイルの解析を使用して式を解析する手作業の再帰的降下パーサーです。これはかなり一般的なテクニックだと思いますが、パターンを見るためにコードを理解しなければならないかもしれませんが、おそらく他の場所でそれを見つけることができます。