アーリー法

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

アーリー法: Earley parser)は、チャートパーサの一種であり、主に計算言語学での構文解析に使われる。名称の由来は発明者の 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) を加える。

これらを追加すべき状態がなくなるまで繰り返す。この集合は一般にプロセスの状態のキューとして実装され、各状態がどのようなものかによって適切な操作を行う。

[編集]

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

 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")。

関連項目[編集]

参考文献[編集]

  • J. Earley, "An efficient context-free parsing algorithm", Communications of the Association for Computing Machinery, 13:2:94-102, 1970. at ACM Portal
  • J. Aycock and R.N. Horspool. Practical Earley Parsing. The Computer Journal, 45:6:620-630, 2002.

外部リンク[編集]

  • Parse::Earley Perlによるアーリー・パーサ・モジュール
  • 'early' C言語ライブラリによるアーリー法実装
  • Spark Pythonでアーリー法を実装したオブジェクト指向「小型言語フレームワーク」
  • NLTK Pythonによるツールキット(アーリー法も含まれる)