1

ウィキペディアで言及されている例を誰かが明確にしてくれれば、とてもうれしいです。

http://en.wikipedia.org/wiki/Earley_algorithm

文法を考えてみましょう:

P → S      # the start rule
S → S + M | M
M → M * T | T
T → number

そして入力：

2 + 3 * 4

Earley アルゴリズムは次のように機能します。

 (state no.) Production          (Origin) # Comment
 ---------------------------------
 == S(0): • 2 + 3 * 4 ==
 (1)  P → • S         (0)    # start rule
 (2)  S → • S + M     (0)    # predict from (1)
 (3)  S → • M         (0)    # predict from (1)
 (4)  M → • M * T     (0)    # predict from (3)

これは最初のセット S(0) にすぎませんが、私の質問は、アルゴリズムがステップ (4) で (3) から予測しているのに、(2) からの予測を省略しているのはなぜですか?

誰かがアイデアを理解し、助けてくれることを願っています

4

1 に答える 1

4

ドットの横の記号はSであるため、予測に（2）を使用しても、新しいプロダクションは作成されません。したがって、情報を追加しないプロダクション（2）と（3）のみが再度取得されます。

于 2010-10-18T20:31:43.090 に答える