構文解析器（こうぶんかいせきき）とは、構文解析をおこなうプログラム。パーサ (parser)とも。 プログラミング言語のコンパイラや自然言語処理などで使われる。 一般的に構文解析のアルゴリズムには複雑なものが多いが、 最近はyaccやbisonなどといったツールの普及により、 文法を記述するだけで構文解析器を自動的に生成できる （プログラムのソースコードが出力される）。
目次

1 構文解析器の種類

2 構文解析器の例

2.1 トップダウン構文解析器

2.2 ボトムアップ構文解析器


3 パーサ開発ソフトウェア

//

構文解析器の種類

構文解析器の役割は基本的に、開始記号に形式文法の規則を適用することで入力された文字列が得られるかどうかを判定することである。これは次の2種類の手法で行われる:

トップダウン構文解析 - 構文解析器は開始記号を始点として、それを変換していって入力された文字列を得ようとする。直観的に言えば、まず大きな要素から開始して徐々に細部に分解していく。例えば JavaCC はトップダウン構文解析手法を使っている。

ボトムアップ構文解析 - 構文解析器は入力された文字列を始点として、それを変換して開始記号に帰結させようとする。直観的に言えば、最も基本的な要素をまず特定し、それを含むより大きな要素、さらに大きな要素、と解析していく。例えば、Yacc はボトムアップ構文解析手法を使っている。

その他の重要な分類法として、構文解析器が「左端導出」なのか、「右端導出」なのかという分類もある（文脈自由文法参照）。LL法は左端導出であり、LR法は右端導出である（ほぼ正反対である）。

構文解析器の例

トップダウン構文解析器

トップダウン構文解析に従った構文解析器を以下に示す:

再帰下降構文解析

LL法

解析表現文法(PEG)

末尾再帰構文解析

ボトムアップ構文解析器

ボトムアップ構文解析に従った構文解析器を以下に示す:

LR法

SLR法

LALR法

正規LR法

GLR法


アーリー法

CYK法

パーサ開発ソフトウェア

ANTLR ⇒[1]

Bison

Coco/R ⇒[2]

GOLD ⇒[3]

JavaCC

Lemon Parser ⇒[4]

Lex

LRgen ⇒[5]

Rebol ⇒[6]

SableCC ⇒[7]

Spirit Parser Framework ⇒[8]

Yacc

この「構文解析器」はコンピュータに関連した書きかけ項目です。この記事を加筆して下さる人を求めています（Portal:コンピュータ）。
カテゴリ: 構文解析 (プログラミング) | コンピュータ関連のスタブ項目

更新日時:2008年1月27日(日)08:12
取得日時:2008/10/11 09:21