Последующих наборы для самостоятельных рекурсивных правил

Question

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

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

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

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

Answer 1

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 сопровождаемый или б.