パーサジェネレータ

パーサジェネレータ（）は、構文解析器（パーサ）を作成するプログラムである。

 概要 
プログラミング言語のコンパイラの開発には技術と手間とを要する。それを支援するために、言語の構文などの定義から、コンパイラを生成するコンパイラジェネレータ（コンパイラコンパイラとも）が研究された。その過程で、入力を処理する構文解析器を自動生成するプログラムが開発され、広く実用に供されるようになった。これがパーサジェネレータである。

 歴史 
伝統的には1970年代から開発されている yacc が有名である。名前は「Yet Another コンパイラコンパイラ」の略だが、実際はパーサジェネレータである。yaccの上位互換のものとしてGNUプロジェクトのbisonがある。

 近年の発展 
 パーサコンビネータ 
パーサは入力を引数に取って解析結果を返す関数とみなすことができる。プログラミング言語に関数を組み合わせたりする能力（高階関数）があれば、演算子（コンビネータ）によりパーサを組み上げることができる。Parsecなどのパーサコンビネータライブラリが実装・公開され、使われている。

 Packrat Parser 

曖昧性の無い文法の解析のために、文脈自由文法の代わりとして使えるものとして、Parsing Expression Grammarの研究がすすんでいる。PEGの実用的なパーサとして提案されているものにPackrat Parserがあり、Packrat Parserを生成するパーサジェネレータが実装・公開され、使われている。

 実装 
 LL法
 ANTLRANTLR（前身はPCCTS）
 JavaCCJavaCC
 Coco/RCoco/R
 Boost.Spirit - LL(∞)構文解析器生成フレームワークであり、文法は C++ のプログラム内にインラインで書かれる。Boostライブラリに含まれている。
 JetPAG - 最適化 LL(k)構文解析器生成ツール
 JFLAP - LL(1)構文解析の教育用ツール
 Ocaml Genlex Module
 Parsec - Haskell 向けのパーサーコンビネータのライブラリ
 Scala Standard Parser Combinator Library
 SLK
 LR法
 bison
 yacc
 SableCCSableCC
 lemon - C用のプッシュ型パーサを生成
 caper - C++/JavaScript/C#/D用のプッシュ型パーサーを生成
 kp19pp - caperを引き継ぎ、高速化と曖昧さ･衝突の回避の改良を行ったもの
 kmyacc - 多言語対応LALRパーサー生成系
 CUP - LALR Parser Generator in Java
 JS/CC - The LALR(1) parser and lexical analyzer generator for JavaScript, written in JavaScript 
 RACC - Rubyで書かれたパーサジェネレータ
 PEG
 XPEG - C++用
 Peggy - Haskell用
 PackCC - C用 Packrat Parser 生成器（左再帰サポート）

 脚注 

参考文献

 P．レッヒェンベルク、H．メッセンベック共著、玉井浩　訳『マイクロコンピュータのための「コンパイラ・コンパイラ」―コンパイラ自動生成にむけて』〈Information & Computing 52〉サイエンス社1991年　ISBN 978-4-7819-0607-2

*
Category:ソフトウェア開発ツール
Category:ドメイン固有言語