2

何が起こっているのか誤解しているのか、ウィキペディアの説明が間違っているのかわかりません。

ウィキペディアは次のように述べています。

FOLLOW(k,B)項目セットkと非終端記号の は、 の後にが続くBすべての項目の次のセットの和集合です。K'•'B

文法の例は次のようになります。

S → E
E → T
E → ( E )
T → n
T → + T
T → T + n

彼らは、LR(0) アイテム セット 0 が次のようになっていることを発見しました。

[S → • E]
[E → • T]
[E → • ( E )]
[T → • n]
[T → • + T]
[T → • T + n]

つまりFOLLOW(0,T)、アイテム セット 0 内のすべてのアイテムの次のセットの和集合であり、'•' の後に が続きTます。

彼らの論理を適用すると、「'•' が後に続くアイテム セット 0 のアイテムT」は、実際には次の 2 つのアイテムであることがわかります。

  • [E → • T]
  • [T → • T + n]

ただし、ここで行き詰まります
。2 番目のフォロー セットには、シンボル が含まれています。これは)、アイテム[E → • ( E )]が を生成できるためです。[E → • ( T )])

ただし、ウィキペディアは次のように述べていFOLLOW(0,T) = { $, '+' }ます。

私は何を間違っていますか？

4

1 に答える 1

1

この本の中に「ウォーシャルの閉鎖アルゴリズム」の記述を見つけました

Bornat : コンパイラの理解と記述

ここで役に立ちます。(全体として、この本は、コンパイラー設計に関する有名な本よりも読みやすく、実用的であることがわかりました!)

アルゴリズムについては、他にも適切な説明があるかもしれません。

編集：私はさびていますが、ウィキペディアの記事はこの点で正しいと思います：

これは であることを覚えておいてくださいFollow(0,T)。
これで、状況によっては ')' が T の後に続く可能性があることは明らかです。

ただし、0 の開始点からではありません ... これはn)orの形式の式を意味しn+n)、n+n+n)このように明示的に書き出すと、明らかな構文エラーになります。

(これらのことを数学的な表記法に埋め込むのではなく、明示的にすることが、私がその本で本当に気に入った点です!)

于 2012-12-20T13:37:47.880 に答える