パーサジェネレータ

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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

概要[編集]

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

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

近年の発展[編集]

パーサコンビネータ[編集]

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

Packrat Parser[編集]

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

実装[編集]

参考文献[編集]

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