как удалить круговую зависимость в наборе FOLLOW

Question

Рассмотрим короткий грамматический сильфон

S -> Bc | DB
B -> ab | cS
D -> d | epsilon

Первый набор

FIRST(S) ={a,c,d}
FIRST(B) = { a,c }
FIRST(D)= { d, epsilon }

, в нем

Follow(S)={ Follow(B) }

и

Follow(B) ={ c , Follow(S) }

мой вопрос в том, как разрешить эту круговую зависимость?

Answer 1

Эта круговая зависимость не должна быть с самого начала. это алгоритм поиска 'follow's:

Инициируйте все последующие группы в {}, кроме S, который является инициатором в {$}.
Пока есть изменения, для каждого A∈V выполните:
Для каждого Y → αAβ сделать:
следовать (A) = следовать (A) ∪ сначала (β)
Если β ⇒ * ε, также выполните: следовать (A) = следовать (A) ∪ следовать (Y)

Итак, в вашем случае вы должны получить:
Последующие (S) = {с, $}
Следуйте (B) = {с, $}
Последующие (D) = {а, с}