177
правок
Изменения
→Идея алгоритма
=== Идея алгоритма ===
Пусть, <tex> N^* </tex> множество рекурсивных нетерминалов из <tex> N </tex>.
Пусть, <tex> P = \{N_1,N_2,\ldots,N_K\} </tex> разбиение <tex> N^*</tex> на <tex> k </tex> дизъюнктных множеств взаимно рекурсивных рекурсивN_ных нетерминалов,
<tex> N_1 \cup N_2 \cup \ldots \cup N_k = N^* \land \forall i</tex> <tex> N_i \neq \emptyset </tex>.
'''bool''' isLeftType(<tex>N_i</tex>: '''nonterminal'''):
'''if''' !isLeftType(<tex>N_i</tex>) '''and''' !isRightType(<tex>N_i</tex>)
'''return''' cyclic
:Когда функция <tex>\mathtt {getTheTypeOfMutualRecursiveSet}(N_i) = left, N_i </tex> состоит только из лево-рекурсивных нетерминалов.
:Аналогично для <tex>\mathtt {getTheTypeOfMutualRecursiveSet}(N_i) = right </tex>.
:Когда функция <tex>\mathtt {getTheTypeOfMutualRecursiveSet}(N_i) = cyclic, 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>, т.к в противном случае грамматика будет самоприменима.
В основе алгоритма будет рекурсивный обход грамматики. Спускаемся по грамматике до тех пор не приходим в нетерминал или символ алфавита:
