1

さて、私はフォローセットを理解しようとしていますが、1つのことを除いて理解できたと思います:

X -> a X
X -> b X
X -> epsilon

このページのルールに従い、FOLLOW(X) にはファイルの終わり文字である $ を含める必要があります (ルール 1)。次に、ルール 3 に従って、FOLLOW(X) には FOLLOW(X) のすべてが含まれており、私の脳は溶けてしまいます。

私にとって、直感的に、FOLLOW(X) は {a,b,$} のはずですが、この例をkfg Editで試してみると{$} しか得られません。なんで？

4

1 に答える 1

2

FOLLOW(X) は自明にそれ自体のサブセットであるため、ルール 3 は右再帰生成に適用されても何も寄与しません。

これは記述的に簡単にアプローチできますが、計算するアルゴリズムについて考えることが困難な場合があります。FOLLOW セットを計算する場合、ルールに従って飽和するまで反復的に埋めることができます。次に、些細なケースでも何もする必要はありません。

ただし、a または b を FOLLOW(X) に取得するルールはなく、FOLLOW(X) でそれらを期待する理由がわかりません。文法は、生成できる構文ツリーの完全なセットを想像するのに十分単純です。

                                                                  X
                                                                 /|
                                                 X              / X
                                                /|             / /|
                                  X            / X            / / X
                                 /|           / /|           / / /|
                     X          / X          / / X          / / / X
                    /|         / /|         / / /|         / / / /|
          X        / X        / / X        / / / X        / / / / X
         /|       / /|       / / /|       / / / /|       / / / / /|
 X      / X      / / X      / / / X      / / / / X      / / / / / X
 |     /  |     / /  |     / / /  |     / / / /  |     / / / / /  |
 ε    α   ε    α α   ε    α α α   ε    α α α α   ε    α α α α α   ε    ...

( for α ∊ {a, b} )

彼らは X を一番右にしか許可しないので、X の後に a または b を続ける方法はありません。

于 2010-08-23T19:41:03.620 に答える