パーサジェネレータ

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

概要

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

代表的なパーサジェネレータに、yaccがある。名前は「Yet Another コンパイラコンパイラ」の略だが、実際はパーサジェネレータである。yaccの上位互換のものとしてGNUのbisonがある。

近年の発展

パーサコンビネータ

パーサは一種のプロシージャないし関数（サブルーチン）であり、プログラミング言語にそれらを組み合わせたりする能力（高階関数）があれば、演算子（コンビネータ）によりパーサを組み上げることができる。Parsecなどのパーサコンビネータライブラリが実装・公開され、使われている。

Packrat Parser

テンプレート:Main 文脈自由文法に代わるものとして、Parsing Expression Grammarの研究がすすんでいる。PEGの実用的なパーサとして提案されているものにPackrat Parserがあり、Packrat Parserを生成するパーサジェネレータが実装・公開され、使われている。

実装

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

参考文献

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