177
правок
Изменения
→Идея алгоритма
'''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>, т.к в противном случае грамматика будет самоприменима.
В основе алгоритма будет рекурсивный обход грамматики. Спускаемся по грамматике до тех пор не приходим в нетерминал или символ алфавита:
