|
チャートパーサ（）は、自然言語などの曖昧な文法に向いた構文解析器の一種である。動的計画法を用い、中間的かつ仮説的な結果をチャート（chart）と呼ばれるデータ構造に格納しておき、再利用する。これによりバックトラッキングを省き、同時に組合せ爆発を防ぐ。 チャートパーサは Martin Kay が開発した。 == チャートパーサの種類 == * ビタビアルゴリズムを変形したものを用いることが多い。 * アーリー法はチャートパーサの一種であり、計算言語学での構文解析に主に使われる。 * CYK法もチャートパーサの一種である。 チャートパーサはコンピュータ言語の構文解析にも利用可能である。アーリー法は任意の文脈自由文法の構文解析が可能で、特定の言語の文法記述が容易であることから、パーサジェネレータで使われてきた。しかし、他の一般的手法よりも効率が低いため、主要なコンパイラでは使われていない。 双方向チャートパーサでは、チャートのエッジには方向（前か後ろ）が付与され、構文規則はそのエッジの方向に従う。 インクリメンタル・チャートパーサでは、テキストをユーザーが編集するのと同期してチャートがインクリメンタル（漸増的）に構築される。 チャートパーサにはトップダウン方式とボトムアップ方式がある。また、能動的チャートパーサと受動的チャートパーサにも分類できる。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「チャートパーサ」の詳細全文を読む スポンサード リンク
|