アーリー法

アーリー法（Earley parser）

アーリー法は、計算言語学で用いられる構文解析アルゴリズムの一つであり、チャートパーサの一タイプです。この手法は、Jay Earleyによって提案され、その名が付けられました。アーリー法は、主に動的計画法に基づいた手法であり、全ての文脈自由言語に対して有効な構文解析を行うことができます。

アーリー法の特性

通常、アーリー法による解析には入力の長さの三乗に比例した時間が必要ですが、曖昧でない文法の場合は二乗にまで短縮することが可能です。特に、左再帰を持つ生成規則に対しては、効率的に処理できる特徴があります。これにより、文法の種類に応じて解析の速度が変わるため、さまざまな条件下で効果を発揮します。

アーリー法のアルゴリズム

アーリー法は、トップダウンアプローチを採用した動的計画法です。ここで使用されるのは、Earleyのドット記法という表記法です。生成規則が X → αβ の場合、表記 X → α • β は、αが解析を終え、これからβを解析する段階であることを示しています。

アルゴリズムの中で、各入力位置間の文字間における「状態集合」を生成します。各状態はタプル (X → α • β, i) で表され、内容は以下の通りです：

• - 現在マッチング中の生成規則 (X → α β)
• - 現在位置を示すドット
• - 生成規則に関連するマッチングの開始位置を示すi

アーリー法では、最初にトップレベルの生成規則のみを用いた初期状態 S(0) を作成し、その後、予測、走査、完了という三つの段階を通じて解析を進めます。

1. 予測

状態 S(k) の中で形式が (X → α • Y β, j) という状態を持つ場合、Yに対応する左辺の生成規則を全て S(k) に追加します。

2. 走査

次の入力記号が a の時、S(k) から形式 (X → α • a β, j) の状態を選出します。それを S(k+1) に追加し、現在の解析位置を更新します。

3. 完了

S(k) の中から形式 (X → γ •, j) を保持する状態を見つけ、S(j) に存在する状況に応じて、新たな状態を S(k) に追加します。これを状態が追加されなくなるまで続けます。

解析の例

簡単な算数の文法を考えてみましょう。以下の文法規則に従った場合：

• - P → S # 開始規則
• - S → S + M | M
• - M → M T | T
• - T → number

この文法に基づいて、「2 + 3 4」という入力を解析すると、次のように状態集合が変化します。


この解析の結果として、状態 (P → S •, 0) が得られ、これが構文解析の完了を示しています。この状態は S(3) と S(1) にも登場していますが、それぞれの時点で入力が完結した数式を表しています。

関連項目

• - CYKアルゴリズム
• - 文脈自由文法

参考文献

• - J. Earley, "An efficient context-free parsing algorithm", Communications of the Association for Computing Machinery, 13:2:94-102, 1970. at ACM Portal
• - J. Aycock and R.N. Horspool. Practical Earley Parsing. The Computer Journal, 45:6:620-630, 2002.

外部リンク

• - Parse::Earley Perlによるアーリー・パーサ・モジュール
• - 'early' C言語ライブラリによるアーリー法実装
• - Spark Pythonでアーリー法を実装
• - NLTK Pythonによるツールキット（アーリー法も含まれる）

もう一度検索