Prattパーサ

情報科学の分野において、 Prattパーサ は文法規則の代わりにトークンの意味ごとに関連付けを作るように改良された再帰下降構文解析のひとつ。これはPratt, Vaughan が1973年の論文 "Top down operator precedence" において初めて記述し、彼の監督の元にさらに深く修士論文の中で扱われた。もともと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

構文解析アルゴリズム