構文解析器
構文解析器（こうぶんかいせきき）とは、構文解析をおこなうプログラム。パーサまたはパーザ[1] (parser)とも。プログラミング言語処理系の入力部分が代表的であるが、それに限らず設定ファイルの読み込みなど、構造を持った入力テキストの処理を行う。自然言語処理でも使われる。
構文解析のアルゴリズムには複雑なものも多いが[2]、パーサジェネレータの研究は盛んであり、そういったものを使用すれば、構文規則を記述するだけで構文解析器を自動的に生成できる（プログラムのソースコードが出力される）。
構文解析器の種類
[編集]構文解析器の役割は基本的に、開始記号に形式文法の規則を適用することで入力された文字列が得られるかどうかを判定することである。これは次の2種類の手法で行われる:
- トップダウン構文解析 - 構文解析器は開始記号を始点として、それを変換していって入力された文字列を得ようとする。直観的に言えば、まず大きな要素から開始して徐々に細部に分解していく。例えば JavaCC はトップダウン構文解析手法を使っている。
- ボトムアップ構文解析 - 構文解析器は入力された文字列を始点として、それを変換して開始記号に帰結させようとする。直観的に言えば、最も基本的な要素をまず特定し、それを含むより大きな要素、さらに大きな要素、と解析していく。例えば、Yacc はボトムアップ構文解析手法を使っている。
その他の重要な分類法として、構文解析器が「左端導出」なのか、「右端導出」なのかという分類もある（文脈自由文法参照）。LL法は左端導出であり、LR法は右端導出である（ほぼ正反対である）。
構文解析器の例
[編集]トップダウン構文解析器
[編集]トップダウン構文解析に従った構文解析器を以下に示す:
ボトムアップ構文解析器
[編集]ボトムアップ構文解析に従った構文解析器を以下に示す:
パーサジェネレータ
[編集]→詳細は「パーサジェネレータ」を参照
- ANTLR [1]
- Bison
- Coco/R [2]
- GOLD [3]
- JavaCC
- Lemon Parser [4]
- LRgen [5]
- Rebol [6]
- SableCC [7]
- Spirit Parser Framework [8]
- Yacc
注
[編集]- ^ 英語でも"s"の発音に揺れがある(wikt:parser)。
- ^ 再帰下降構文解析など、簡単なものもある。
 | この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。 |