1632
правки
Изменения
м
rollbackEdits.php mass rollback
'''bool''' isRightType(<tex>N_i</tex>: '''nonterminal'''):
'''return''' <tex> \exists (A \Rightarrow \alpha B \beta) \in P[ A \in N_i \land B \in N_i \land \beta \neq \varepsilon ]</tex>
Будем называть <tex>\mathtt {typeRecursive}</tex> набор четырех величин <tex>\{left, right, self, cycle\} </tex>
Определим функцию <tex>\mathtt {getTheTypeOfMutualRecursiveSet}(N_i): P \rightarrow \mathtt {left, right, self, cycle\typeRecursive} </tex>: '''function''' getTheTypeOfMutualRecursiveSet(<tex>N_i</tex>: '''nonterminal'''): '''inttypeRecurcive'''
'''if''' !isLeftType(<tex>N_i</tex>) '''and''' isRightType(<tex>N_i</tex>)
'''return''' left
'''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>
