Prattパーサ

情報科学の分野において、 Prattパーサ は文法規則の代わりにトークンの意味ごとに関連付けを作るように改良された再帰下降構文解析のひとつ。これはPratt, Vaughan が1973年の論文 "Top down operator precedence" において初めて記述しPratt, Vaughan. "Top down operator precedence." Proceedings of the 1st Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (1973).、彼の監督の元にさらに深く修士論文の中で扱われたVan De Vanter, Michael L. "A Formalization and Correctness Proof of the CGOL Language System." (Master's Thesis).  MIT Laboratory for Computer Science Technical Report MIT-LCS-TR-147 (Cambridge, Massachusetts).  1975.。もともとPrattは プログラミング言語を実装するためにその論文を設計した。 Douglas Crockford はその技術を JSLint の構築のために用いた。

 概要 
Prattパーサーはパーサージェネレータは使わず、演算子の優先度を重視して構文木を構築する。。

 仕組み 
Prattパーサーは常に現在の読み込み位置とその次の位置を確認しながら解析する。これをLL(1)文法と言う。例えば「3+5*4」であれば、まず「3」と「＋」を読んで次に「＋」と「５」を読んでというのを繰り返しながら構文木を構築する。
Prattパーサーは現在の優先順位と、次に追加するものの優先順位を比較することで、新しく読み込んだものの、構文木のなかでの位置を決定する。

 脚注 

 関連項目 
 :en:Operator-precedence parser

 外部リンク 
Pratt Parsers: Expression Parsing Made Easy
A Pratt Parser implementation in Python
A general-purpose configurable Pratt Parser library in Rust

Category:構文解析アルゴリズム