アーリー法

アーリー法は、チャートパーサの一種であり、主に計算言語学での構文解析に使われる。名称の由来は発明者の Jay Earley。このアルゴリズムは動的計画法に基づいている。

アーリー法は全ての文脈自由言語の構文解析が可能である。アーリー法は通常、入力の3乗の時間がかかり、曖昧でない文法の場合は2乗の時間がかかる。特に左再帰で書かれた生成規則を効率的に解析できる。

1. アルゴリズム
---------

以下の解説において、α、β、γは任意の終端記号と非終端記号の文字列を表し、X、Y、Z は1つの非終端記号を表し、//a// は終端記号を表す。

アーリー法はトップダウン型の動的計画法である。以下では Earley のドット記法を使用する。生成規則 X → αβ があるとき、X → α • β という表記は、αが既に解析済みで、βをこれから解析しようとしていることを表す。

全ての入力位置について、アーリー法では順序付きの「状態集合」を生成する。各状態はタプル  で表され、各要素は次の意味を持つ。

現在マッチングさせようとしている生成規則 
その生成規則における現在位置
//i// は入力における位置であり、この生成規則のマッチングが開始された位置「開始位置」を示す。Earley のオリジナルのアルゴリズムでは、状態に先読みを含めていたが、後の研究であまり意味がないことがわかり、現在では省かれることが多い。

入力位置 //k// における状態集合を S と呼ぶ。初期状態では、トップレベルの生成規則だけからなる S を用意する。その後、「予測」、「走査」、「完了」という3つの段階を繰り返して処理をする。

予測: Sの中で  という形式の各状態について、 という形式の Y を左辺に持つ生成規則全てを S に含める。
走査: //a// が入力ストリームの次の記号であるとき、S から  という形式の状態全てを選び、S に  を加える。
完了: S の中で  という形式の各状態について、S に  という形式の状態があるかを調べ、S に  を加える。これらを追加すべき状態がなくなるまで繰り返す。この集合は一般にプロセスの状態のキューとして実装され、各状態がどのようなものかによって適切な操作を行う。

2. 例
----

次のような簡単な数式に関する文法を考える。

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

次の文字列を入力とする。

2 + 3 * 4

以下に状態集合の変化を示す。

 生成規則  # コメント

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

S: • 2 + 3 * 4  P → • S  # 開始規則  S → • S + M  # からの予測  S → • M  # からの予測  M → • M * T  # からの予測  M → • T  # からの予測  T → • number  # からの予測

S: 2 • + 3 * 4  T → number •  # S からの走査  M → T •  # S からの完了  M → M • * T  # S からの完了  S → M •  # S からの完了  S → S • + M  # S からの完了  P → S •  # S からの完了

S: 2 + • 3 * 4  S → S + • M  # S からの走査  M → • M * T  #  からの予測  M → • T  #  からの予測  T → • number  #  からの予測

S: 2 + 3 • * 4  T → number •  # S からの走査  M → T •  # S からの完了  M → M • * T  # S からの完了  S → S + M •  # S からの完了  S → S • + M  # S からの完了  P → S •  # S からの完了

S: 2 + 3 * • 4  M → M * • T  # S からの走査  T → • number  #  からの予測

S: 2 + 3 * 4 •  T → number •  # S からの走査  M → M * T •  # S からの完了  M → M • * T  # S からの完了  S → S + M •  # S からの完了  S → S • + M  # S からの完了  P → S •  # S からの完了

状態  が構文解析の完了を示している。この状態は S と S にも現れているが、その時点の文字列が式として完全であったことを示している。

3. 関連項目
-------

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

4. 参考文献
-------

J. Earley, "An efficient context-free parsing algorithm", //Communications of the Association for Computing Machinery//, 13:2:94-102, 1970. [1]
J. Aycock and R.N. Horspool. [2]. //The Computer Journal//, 45:6:620-630, 2002.

5. 外部リンク
--------

[3] Perlによるアーリー・パーサ・モジュール
[4] C言語ライブラリによるアーリー法実装
[5] Pythonでアーリー法を実装したオブジェクト指向「小型言語フレームワーク」
[6] Pythonによるツールキット