Изменения

*<tex>\mathtt{isEpsilon[nonterm_i]}\ </tex> {{---}} для каждого нетерминала будем хранить пометку, является он <tex>\varepsilon</tex>-порождающим или нет.*<tex>\mathtt{concernedRules[nonterm_i]}\ </tex> {{---}} для каждого нетерминала будем хранить список номеров тех правил, в правой части которых он встречается;*<tex>\mathtt{counter[rule_i]}\ </tex> {{---}} для каждого правила будем хранить счетчик количества нетерминалов в правой части, которые еще не помечены <tex>\varepsilon</tex>-порождающими;*<tex>\mathtt{Q}\ </tex> {{---}} очередь нетерминалов, помеченных <tex>\varepsilon</tex>-порождающими, но еще не обработанных.

Сначала проставим <tex>\mathtt{false}</tex> в <tex>\mathtt{isEpsilon}\ </tex> для всех нетерминалов, а в <tex>\mathtt{counter}\ </tex> для каждого правила запишем количество нетерминалов справа от него. Те правила, для которых <tex>\mathtt{counter}\ </tex> сразу же оказался нулевым, добавим в <tex>\mathtt{Q}</tex> и объявим истинным соответствующий <tex>\mathtt{isEpsilon}</tex>, так как это <tex>\varepsilon</tex>-правила. Теперь будем доставать из очереди по одному нетерминалу, смотреть на список <tex>\mathtt{concernedRules}\ </tex> для него и уменьшать <tex>\mathtt{counter}</tex> для всех правил оттуда. Если <tex>\mathtt{counter}\ </tex> какого-то правила в этот момент обнулился, то нетерминал из левой части этого правила помечается <tex>\varepsilon</tex>-порождающим, если еще не был помечен до этого, и добавляется в <tex>\mathtt{Q}</tex>. Продолжаем, пока очередь не станет пустой.