構文解析器

構文解析器（こうぶんかいせきき）とは、構文解析をおこなうプログラム。パーサまたはパーザ英語でも"s"の発音に揺れがある(wikt:parser)。 (parser)とも。プログラミング言語処理系の入力部分が代表的であるが、それに限らず設定ファイルの読み込みなど、構造を持った入力テキストの処理を行う。自然言語処理でも使われる。

構文解析のアルゴリズムには複雑なものも多いが再帰下降構文解析など、簡単なものもある。、パーサジェネレータの研究は盛んであり、そういったものを使用すれば、構文規則を記述するだけで構文解析器を自動的に生成できる（プログラムのソースコードが出力される）。

構文解析器の種類
構文解析器の役割は基本的に、開始記号に形式文法の規則を適用することで入力された文字列が得られるかどうかを判定することである。これは次の2種類の手法で行われる:
トップダウン構文解析 - 構文解析器は開始記号を始点として、それを変換していって入力された文字列を得ようとする。直観的に言えば、まず大きな要素から開始して徐々に細部に分解していく。例えば JavaCC はトップダウン構文解析手法を使っている。
ボトムアップ構文解析 - 構文解析器は入力された文字列を始点として、それを変換して開始記号に帰結させようとする。直観的に言えば、最も基本的な要素をまず特定し、それを含むより大きな要素、さらに大きな要素、と解析していく。例えば、Yacc はボトムアップ構文解析手法を使っている。

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

 構文解析器の例 
 トップダウン構文解析器 
トップダウン構文解析に従った構文解析器を以下に示す:
 再帰下降構文解析
 LL法
 末尾再帰構文解析
 パックラット構文解析

 ボトムアップ構文解析器 
ボトムアップ構文解析に従った構文解析器を以下に示す:
 LR法
 SLR法
 LALR法
 CLR法
 GLR法
 アーリー法
 CYK法

 パーサジェネレータ 

 ANTLR 
 Bison
 Coco/R 
 GOLD 
 JavaCC
 Lemon Parser 
 LRgen 
 Rebol 
 SableCC 
 Spirit Parser Framework 
 Yacc

 注 

*こうふんかいせきき

sr:Парсер