Loading article…
コンピュータサイエンスにおいて、チャートパーサーは、曖昧な文法（自然言語の文法を含む）に適したパーサーの一種です。動的計画法の手法を用い、部分的な仮説結果をチャートと呼ばれる構造に格納し、再利用します。これにより、バックトラッキングが不要になり、組み合わせ爆発を防ぐことができます。
一般的なアプローチとしては、ビタビアルゴリズムの変種を用いる方法がある。アーリー構文解析器は、主に計算言語学における構文解析に用いられるチャート構文解析器の一種で、その考案者の名にちなんで名付けられている。別のチャート構文解析アルゴリズムとしては、コック・ヤンガー・カサミ（CYK）アルゴリズムがある。
チャートパーサーは、コンピュータ言語の構文解析にも使用できます。特にアーリーパーサーは、コンパイラコンパイラで使用されており、任意の文脈自由文法を用いて構文解析できるため、特定の言語の文法記述作業が容易になります。しかし、効率が低いことから、ほとんどのコンパイラ開発作業では使用が避けられています。
双方向チャート解析では、チャートのエッジに前方または後方の方向がマークされ、エッジがさらにエッジに結合するためにどの方向を向いている必要があるかについてルールが適用されます。
インクリメンタルチャート解析では、ユーザーがテキストを編集するにつれてチャートが段階的に構築され、テキストへの変更ごとにチャートへの変更は最小限に抑えられます。
チャート解析器は、トップダウン型とボトムアップ型、アクティブ型とパッシブ型に分類される。