アーリー法
以下の解説において、α、β、γは任意の終端記号と非終端記号の文字列(空文字列を含む)を表し、X、Y、Z は1つの非終端記号を表し、a は終端記号を表す。
アーリー法はトップダウン型の動的計画法である。以下では Earley のドット記法を使用する。生成規則 X → αβ があるとき、X → α • β という表記は、αが既に解析済みで、βをこれから解析しようとしていることを表す。
全ての入力位置(字句と字句の間の位置)について、アーリー法では順序付きの「状態集合」を生成する。各状態はタプル (X → α • β, i) で表され、各要素は次の意味を持つ。
現在マッチングさせようとしている生成規則 (X → α β)
その生成規則における現在位置(ドットで表される)
i は入力における位置であり、この生成規則のマッチングが開始された位置「開始位置」を示す。
Earley のオリジナルのアルゴリズムでは、状態に先読みを含めていたが、後の研究であまり意味がないことがわかり、現在では省かれることが多い。