アーリー法

アーリー法（）は、チャートパーサの一種であり、主に計算言語学での構文解析に使われる。名称の由来は発明者の Jay Earley。このアルゴリズムは動的計画法に基づいている。
アーリー法は全ての文脈自由言語の構文解析が可能である。アーリー法は通常、入力の3乗の時間がかかり、曖昧でない文法の場合は2乗の時間がかかる。特に左再帰で書かれた生成規則を効率的に解析できる。
アルゴリズム.
以下の解説において、α、β、γは任意の終端記号と非終端記号の文字列（空文字列を含む）を表し、X、Y、Z は1つの非終端記号を表し、"a" は終端記号を表す。
アーリー法はトップダウン型の動的計画法である。以下では Earley のドット記法を使用する。生成規則 X → αβ があるとき、X → α • β という表記は、αが既に解析済みで、βをこれから解析しようとしていることを表す。
全ての入力位置（字句と字句の間の位置）について、アーリー法では順序付きの「状態集合」を生成する。各状態はタプル (X → α • β, "i") で表され、各要素は次の意味を持つ。
Earley のオリジナルのアルゴリズムでは、状態に先読みを含めていたが、後の研究であまり意味がないことがわかり、現在では省かれることが多い。
入力位置 "k" における状態集合を S("k") と呼ぶ。初期状態では、トップレベルの生成規則だけからなる S(0) を用意する。その後、「予測」、「走査」、「完了」という3つの段階を繰り返して処理をする。
これらを追加すべき状態がなくなるまで繰り返す。この集合は一般にプロセスの状態のキューとして実装され、各状態がどのようなものかによって適切な操作を行う。
例.
次のような簡単な数式に関する文法を考える。
 P → S # 開始規則
 S → S + M
 | M
 M → M * T
 | T
 T → number
次の文字列を入力とする。
 2 + 3 * 4
以下に状態集合の変化を示す。
 (状態番号) 生成規則 (開始位置) # コメント
 S(0): • 2 + 3 * 4 
 (1) P → • S (0) # 開始規則
 (2) S → • S + M (0) # (1)からの予測
 (3) S → • M (0) # (1)からの予測
 (4) M → • M * T (0) # (3)からの予測
 (5) M → • T (0) # (3)からの予測
 (6) T → • number (0) # (5)からの予測
 S(1): 2 • + 3 * 4 
 (1) T → number • (0) # S(0)(6) からの走査
 (2) M → T • (0) # S(0)(5) からの完了
 (3) M → M • * T (0) # S(0)(4) からの完了
 (4) S → M • (0) # S(0)(3) からの完了
 (5) S → S • + M (0) # S(0)(2) からの完了
 (6) P → S • (0) # S(0)(1) からの完了
 S(2): 2 + • 3 * 4 
 (1) S → S + • M (0) # S(1)(5) からの走査
 (2) M → • M * T (2) # (1) からの予測
 (3) M → • T (2) # (1) からの予測
 (4) T → • number (2) # (3) からの予測
 S(3): 2 + 3 • * 4 
 (1) T → number • (2) # S(2)(4) からの走査
 (2) M → T • (2) # S(2)(3) からの完了
 (3) M → M • * T (2) # S(2)(2) からの完了
 (4) S → S + M • (0) # S(2)(1) からの完了
 (5) S → S • + M (0) # S(0)(2) からの完了
 (6) P → S • (0) # S(0)(1) からの完了
 S(4): 2 + 3 * • 4 
 (1) M → M * • T (2) # S(3)(3) からの走査
 (2) T → • number (4) # (1) からの予測
 S(5): 2 + 3 * 4 • 
 (1) T → number • (4) # S(4)(2) からの走査
 (2) M → M * T • (2) # S(4)(1) からの完了
 (3) M → M • * T (2) # S(2)(2) からの完了
 (4) S → S + M • (0) # S(2)(1) からの完了
 (5) S → S • + M (0) # S(0)(2) からの完了
 (6) P → S • (0) # S(0)(1) からの完了
状態 (P → S •, 0) が構文解析の完了を示している。この状態は S(3) と S(1) にも現れているが、その時点の文字列が式として完全であったことを示している（それぞれ、"2" と "2 + 3"）。