アーリー法 - Wikipediaアーリー法（英: Earley parser）は、チャートパーサの一種であり、主に計算言語学での構文解析に使われる。名称の由来は発明者の Jay Earley。このアルゴリズムは動的計画法に基づいている。 アーリー法は全ての文脈自由言語の構文解析が可能である。アーリー法は通常、入力の3乗の時間がかかり、曖昧でない文法の場合は2乗の時間がかかる。特に左再帰で書かれた生成規則を効率的に解析できる。 アルゴリズム[編集] 以下の解説において、α、β、γは任意の終端記号と非終端記号の文字列（空文字列を含む）を表し、X、Y、Z は1つの非終端記号を表し、a は終端記号を表す。 アーリー法はトップダウン型の動的計画法である。以下では Earley のドット記法を使用する。生成規則 X → αβ があるとき、X → α • β という表記は、αが既に解析済みで、βをこれから解析しようとしていることを表す
