3622
правки
Изменения
м
→Идея алгоритма
'''if''' !isLeftType(<tex>N_i</tex>) '''and''' !isRightType(<tex>N_i</tex>)
'''return''' cyclic
:Когда функция Состояние <tex>\mathtt {getTheTypeOfMutualRecursiveSet}(N_i) = left</tex> означает, что <tex> N_i </tex> состоит только из лево-рекурсивных нетерминалов. :Аналогично для Состояние <tex> right</tex> означает, что <tex>\mathtt {getTheTypeOfMutualRecursiveSet}(N_i) = right </tex>состоит только из право-рекурсивных нетерминалов.:Когда функция Состояние <tex>\mathtt {getTheTypeOfMutualRecursiveSet}(N_i) = cyclic</tex> означает, что <tex> N_i </tex> состоит только из правил, участвующих в рекурсии.:Функция Состояние <tex>\mathtt {getTheTypeOfMutualRecursiveSet}(N_i) = self</tex>означает, для такого что <tex>i </tex>такое, при котором грамматика самоприменима.
Заметим, что <tex> \forall i </tex> <tex>\mathtt {getTheTypeOfMutualRecursiveSet}(N_i) \neq self </tex>, т.к в противном случае грамматика будет самоприменима.
В основе алгоритма будет рекурсивный обход грамматики. Спускаемся по грамматике до тех пор не приходим в нетерминал или символ алфавита:
<tex>\mathtt{Q} \leftarrow \varnothing</tex>
<tex>\Delta \leftarrow \varnothing </tex>
s = createState() <font color=green>// createState создает некоторый объект, не принадлежащий <tex>Q</tex>, возвращает этот объект и добавляет его в <tex>Q</tex> </font>
f = createState()
<tex>F \leftarrow \{f\} </tex>
