構文解析器

IT用語辞典バイナリ

パーサ

別名：構文解析器
【英】parser

パーサとは、構文解析を行うためのプログラムの総称である。

プログラミング言語におけるパーサは、コンパイルの際に、記述がプログラミング言語の構文の規則に則っているかどうかを判定するために用いられる。通常は、字句解析器（lexer）によって字句レベルでの分析が行われた後、続けて実行される。

また、自然言語処理においては、自然言語における文法上の構造を解析するためにパーサが利用される。

パーサの中には、特定の解析対象を明示する形で、HTMLパーサやXMLパーサといった具合に呼称される場合がある。とりわけXMLパーサは、自由度の高いXML文書について、それを読み込むアプリケーションにとって利用しやすい形に変換する機能を持っており、多くの場面で利用されている。

ソフトウェアのほかの用語一覧

機能：	バックスペース  パラメータ  ハングアップ  パーサ  バイナリレベル互換  暴走  ポーリング

>>機能カテゴリの他の用語

ウィキペディア

構文解析器

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/07/31 07:19 UTC 版)

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

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

構文解析器の種類

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

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

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

構文解析器の例

トップダウン構文解析器

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

• 再帰下降構文解析
• LL法
• 末尾再帰構文解析
• パックラット構文解析

ボトムアップ構文解析器

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

• LR法
  • SLR法
  • LALR法
  • CLR法
  • GLR法
• アーリー法
• CYK法

パーサジェネレータ

• ANTLR [1]
• Bison
• Coco/R [2]
• GOLD [3]
• JavaCC
• Lemon Parser [4]
• LRgen [5]
• Rebol [6]
• SableCC [7]
• Spirit Parser Framework [8]
• Yacc