|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana) ・ 法 ： [ほう] 1. (n,n-suf) Act (law: the X Act)
アーリー法（）は、チャートパーサの一種であり、主に計算言語学での構文解析に使われる。名称の由来は発明者の Jay Earley。このアルゴリズムは動的計画法に基づいている。 アーリー法は全ての文脈自由言語の構文解析が可能である。アーリー法は通常、入力の3乗の時間がかかり、曖昧でない文法の場合は2乗の時間がかかる。特に左再帰で書かれた生成規則を効率的に解析できる。 == アルゴリズム == 以下の解説において、α、β、γは任意の終端記号と非終端記号の文字列（空文字列を含む）を表し、X、Y、Z は1つの非終端記号を表し、''a'' は終端記号を表す。 アーリー法はトップダウン型の動的計画法である。以下では Earley のドット記法を使用する。生成規則 X → αβ があるとき、X → α • β という表記は、αが既に解析済みで、βをこれから解析しようとしていることを表す。 全ての入力位置（字句と字句の間の位置）について、アーリー法では順序付きの「状態集合」を生成する。各状態はタプル (X → α • β, ''i'') で表され、各要素は次の意味を持つ。 * 現在マッチングさせようとしている生成規則 (X → α β) * その生成規則における現在位置（ドットで表される） * ''i'' は入力における位置であり、この生成規則のマッチングが開始された位置「開始位置」を示す。 Earley のオリジナルのアルゴリズムでは、状態に先読みを含めていたが、後の研究であまり意味がないことがわかり、現在では省かれることが多い。 入力位置 ''k'' における状態集合を S(''k'') と呼ぶ。初期状態では、トップレベルの生成規則だけからなる S(0) を用意する。その後、「予測」、「走査」、「完了」という3つの段階を繰り返して処理をする。 * 予測: S(''k'')の中で (X → α • Y β, ''j'') という形式の各状態について、(Y → • γ, ''k'') という形式の Y を左辺に持つ生成規則全てを S(''k'') に含める。 * 走査: ''a'' が入力ストリームの次の記号であるとき、S(''k'') から (X → α • ''a'' β, ''j'') という形式の状態全てを選び、S(''k''+1) に (X → α ''a'' • β, ''j'') を加える。 * 完了: S(''k'') の中で (X → γ •, ''j'') という形式の各状態について、S(''j'') に (Y → α • X β, ''i'') という形式の状態があるかを調べ、S(''k'') に (Y → α X • β, ''i'') を加える。 これらを追加すべき状態がなくなるまで繰り返す。この集合は一般にプロセスの状態のキューとして実装され、各状態がどのようなものかによって適切な操作を行う。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「アーリー法」の詳細全文を読む スポンサード リンク
|