Следуйте сетам для саморекурсивных правил - PullRequest
Новая
       3

Следуйте сетам для саморекурсивных правил

1 голос
/ 06 августа 2010

Хорошо, я пытаюсь понять, следите за сетами, и я думаю, что получил это за исключением одной вещи: 

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

Следуя правилам этой страницы , FOLLOW (X) должен содержать $, символ конца файла (правило 1). Затем, следуя правилу 3, FOLLOW (X) содержит все объекты FOLLOW (X), которые заставляют мой мозг таять.

Для меня, интуитивно понятно, FOLLOW (X) должен быть {a, b, $}, но пробный пример в kfg Edit дает мне только {$}. Почему?

1 Ответ

2 голосов
/ 23 августа 2010

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.

...