Prattパーサ
 |
情報科学の分野において、 Prattパーサ は文法規則の代わりにトークンの意味ごとに関連付けを作るように改良された再帰下降構文解析のひとつ。これはPratt, Vaughan が1973年の論文 "Top down operator precedence" において初めて記述し[1]、彼の監督の元にさらに深く修士論文の中で扱われた[2]。もともとPrattはCGOL プログラミング言語を実装するためにその論文を設計した。 Douglas Crockford はその技術を JSLint の構築のために用いた[3]。
概要
[編集]Prattパーサーはパーサージェネレータは使わず、演算子の優先度を重視して構文木を構築する。発表当初はあまり有名ではなかったが、初心者にも理解しやすく実用に耐えるため、近年[いつ?]注目されている[要出典]。
仕組み
[編集]Prattパーサーは常に現在の読み込み位置とその次の位置を確認しながら解析する。これをLL(1)文法と言う。例えば「3+5*4」であれば、まず「3」と「＋」を読んで次に「＋」と「５」を読んでというのを繰り返しながら構文木を構築する。 Prattパーサーは現在の優先順位と、次に追加するものの優先順位を比較することで、新しく読み込んだものの、構文木のなかでの位置を決定する。
脚注
[編集]- ^ 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.
- ^ Crockford, D (2007年2月21日). “Top Down Operator Precedence”. 2018年12月27日閲覧。
関連項目
[編集]外部リンク
[編集]- Pratt Parsers: Expression Parsing Made Easy
- A Pratt Parser implementation in Python
- A general-purpose configurable Pratt Parser library in Rust
 | この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。 |