LL (1) грамматика. Следуйте за установкой. Рекурсия [дубликат]

Поскольку FIRST и FOLLOW являются (обычно) рекурсивными, полезно думать о них как о системах уравнений, которые нужно решить; решение может быть достигнуто с помощью простого инкрементного алгоритма, состоящего из многократного применения всех правых сторон до тех пор, пока не будет изменено ни одного набора во время цикла.

Итак, возьмем отношение FOLLOW для данной грамматики:

A → B | Cx | ε
B → C | yA
C → B | w | z

Мы можем непосредственно вывести уравнения:

FOLLOW(A) = FOLLOW(B) ∪ {$}
FOLLOW(B) = FOLLOW(A) ∪ FOLLOW(C)
FOLLOW(C) = FOLLOW(B) ∪ {x}

Итак, мы изначально установили все последующие множества в {} и продолжим.

Первый раунд:

FOLLOW(A) = {} ∪ {$} = {$}
FOLLOW(B) = {$} ∪ {} = {$}
FOLLOW(C) = {$} U {x} = {$,x}

Второй раунд:

FOLLOW(A) = {$} ∪ {$} = {$}
FOLLOW(B) = {$} ∪ {$,x} = {$,x}
FOLLOW(C) = {$,x} U {x} = {$,x}

Третий раунд:

FOLLOW(A) = {$,x} ∪ {$} = {$,x}
FOLLOW(B) = {$} ∪ {$,x} = {$,x}
FOLLOW(C) = {$,x} U {x} = {$,x}

Четвертый раунд:

FOLLOW(A) = {$,x} ∪ {$} = {$,x}
FOLLOW(B) = {$,x} ∪ {$,x} = {$,x}
FOLLOW(C) = {$,x} U {x} = {$,x}

Здесь мы останавливаемся потому что никаких изменений в последнем раунде не было.

Этот алгоритм должен завершиться, потому что есть конечное количество символов, и каждый раунд может добавлять символы только к шагам. Это не самый эффективный метод, хотя на практике он достаточно хорош.