Follow устанавливает парсинг сверху вниз

Однако, поскольку L' имеет значение Nullable, будет ли Follow(L) содержать также Follow(C)?

Противоположный. Follow(C) будет содержать Follow(L). Подумайте о следующем предложении:

...Lx...

где X - некоторый терминал и, следовательно, находится в Follow(L). Это может быть расширено до:

...CL'x...

и далее к:

...Cx...

Итак, то, что следует за L, также может следовать за C. Обратное не обязательно верно.

Чтобы вычислить следующее, представьте граф, где узлы (NT, n), что означает нетерминал NT с длиной маркеров, как показано ниже (в LL (1), n равно 1 или 0). График для вас будет выглядеть так:

     _______
   |/_      \
(L, 1)----->(L', 1)         _(C, 1)
 |  \__________|____________/| |
 |             |               |
 |             |               |
 |   _______   |               |
 V |/_      \  V               V
(L, 0)----->(L', 0)         _(C, 0)
    \_______________________/|

Где (X, n)--->(Y, m) означает, что длина n из X зависит от длины m из Y (конечно, m <= n). То есть, чтобы вычислить (X, n), сначала вы должны вычислить (Y, m), а затем вы должны просмотреть каждое правило, которое содержит X в правой части и Y в левой части, например:

Y -> ... X REST

возьмите то, что REST расширяется до длины n - m для каждого m в [0, n), а затем объедините каждый результат с каждым последующим из набора (Y, m). Вы можете рассчитать, до чего расширяется REST, при вычислении первых чисел REST, просто удерживая флаг, указывающий, расширяется ли REST полностью до этого первого или частично. Кроме того, добавьте первые числа REST с длиной n, как следует из X. Например:

S -> A a b c
A -> B C d
C -> epsilon | e | f g h i

Затем, чтобы найти следы B с длиной 3 (это e d a, d a b и f g h), мы смотрим на правило:

A -> B C d

возьмем предложение C d и посмотрим, что оно может дать:

"C d" with length 0 (complete):
"C d" with length 1 (complete):
    d
"C d" with length 2 (complete):
    e d
"C d" with length 3 (complete or not):
    f g h

Теперь мы берем их и объединяем с follow(A, m):

follow(A, 0):
    epsilon
follow(A, 1):
    a
follow(A, 2):
    a b
follow(A, 3):
    a b c

"C d" with length 0 (complete) concat follow(A, 3):
"C d" with length 1 (complete) concat follow(A, 2):
    d a b
"C d" with length 2 (complete) concat follow(A, 1):
    e d a
"C d" with length 3 (complete or not) concat follow(A, 0) (Note: follow(X, 0) is always epsilon):
    f g h

Именно тот набор, который мы искали. Итак, вкратце, алгоритм становится таким:

• Создайте график следующих зависимостей
• Найдите связанные компоненты и создайте DAG из него.
• Пройдите через DAG с конца (от узлов, которые не имеют никакой зависимости) и вычислите последующие с помощью приведенного выше алгоритма, предварительно рассчитав первые.

Стоит отметить, что приведенный выше алгоритм подходит для любого LL(K). Для LL(1) ситуация намного проще.