コンピュータサイエンスにおいて、チャートパーサーは、曖昧な文法（自然言語の文法を含む）に適したパーサーの一種です。チャートパーサーは動的計画法のアプローチを採用しており、部分的な仮説結果はチャートと呼ばれる構造に保存され、再利用できます。これにより、バックトラッキングが不要になり、組み合わせ爆発を防ぐことができます。
図表の解析は一般的にマーティン・ケイの功績とされています。[1]
チャートパーサーの種類
一般的なアプローチは、ビタビアルゴリズムの変種を用いることです。アーリーパーサーはチャートパーサーの一種で、主に計算言語学の解析に用いられ、発明者にちなんで名付けられました。チャートパーサーの別のアルゴリズムとしては、コック・ヤンガー・カサミ（CYK）アルゴリズムがあります。
チャートパーサーはコンピュータ言語の解析にも使用できます。特に初期のパーサーは、任意の文脈自由文法を用いて解析できるため、特定の言語の文法記述作業が容易になるため、コンパイラ・コンパイラで使用されてきました。しかし、その効率性が低いため、ほとんどのコンパイラ作業ではチャートパーサーは使用されていません。
双方向チャート解析では、チャートのエッジに前方または後方の方向がマークされ、エッジをさらに結合するためにエッジが指す方向に関するルールが適用されます。
増分チャート解析では、テキストがユーザーによって編集されるにつれてチャートが増分的に構築され、テキストが変更されるたびにチャートの対応する変更が最小限に抑えられます。
チャート パーサーは、トップダウンとボトムアップ、およびアクティブとパッシブに区別されます。
参照
参考文献
- ^ 「チャート解析」(PDF) 。 2015年2月21日時点のオリジナル(PDF)からアーカイブ。2011年11月20日閲覧。
外部リンク
- ボトムアップチャート解析Web実装
