177
правок
Изменения
→Идея алгоритма
'''function''' getTheTypeOfMutualRecursiveSet (<tex>N_i</tex>):
'''if''' !isLeftType(<tex>N_i</tex>) && isRightType(<tex>N_i</tex>)
'''return''' left;
'''if''' isLeftType(<tex>N_i</tex>) && !isRightType(<tex>N_i</tex>)
'''return''' right;
'''if''' (isLeftType(<tex>N_i</tex>) && isRightType(<tex>N_i</tex>)
'''return''' self;
'''if''' !isLeftType(<tex>N_i</tex>) && !isRightType(<tex>N_i</tex>)
'''return''' cyclic;
Заметим, что <tex> \forall i </tex> <tex>getTheTypeOfMutualRecursiveSet(N_i) \neq self </tex>, т.к в противном случае грамматика будет самоприменима.
В основе алгоритма будет рекурсивный обход грамматики. Спускаемся по грамматике до тех пор не приходим в нетерминал или символ алфавита:
