48
правок
Изменения
Нет описания правки
=== Модификация с очередью ===
Заведем несколько структур:
*<tex>\mathtt{is\text{-}epsilon[nonterm_i]}</tex> {{---}} для каждого нетерминала будем хранить пометку, является он <tex>\varepsilon</tex>-порождающим или нет.*<tex>\mathtt{concerned\text{-}rules[nonterm_i]}</tex> {{---}} для каждого нетерминала будем хранить список номеров тех правил, в правой части которых он встречается;*<tex>\mathtt{counter[rule_i]}</tex> {{---}} для каждого правила будем хранить счетчик количества нетерминалов в правой части, которые еще не помечены <tex>\varepsilon</tex>-порождающими;*<tex>\mathtt{Q}</tex> {{---}} очередь нетерминалов, помеченных <tex>\varepsilon</tex>-порождающими, но еще не обработанных.
Сначала объявим все нетерминалы не проставим <tex>\varepsilonmathtt{false}</tex>в <tex>\mathtt{is\text{-порождающими}epsilon}</tex> для всех нетерминалов, а в <tex>\mathtt{counter}</tex> для каждого правила запишем количество нетерминалов справа от него. Те правила, для которых <tex>\mathtt{counter}</tex> сразу же оказался нулевым, добавим в <tex>\mathtt{Q}</tex> и объявим истинным соответствующий <tex>\mathtt{is\text{-}epsilon}</tex>, так как это <tex>\varepsilon</tex>-правила. Теперь будем доставать из очереди по одному нетерминалу, смотреть на список <tex>\mathtt{concerned\text{-}rules}</tex> для него и уменьшать <tex>\mathtt{counter}</tex> для всех правил оттуда. Если <tex>\mathtt{counter}</tex> какого-то правила в этот момент обнулился, то нетерминал из левой части этого правила помечается <tex>\varepsilon</tex>-порождающим, если еще не был помечен до этого, и добавляется в <tex>\mathtt{Q}</tex>. Продолжаем, пока очередь не станет пустой.
=== Время работы алгоритма ===
# Добавить все правила из <tex>P</tex> в <tex>P'</tex>.
# Найти все <tex>\varepsilon</tex>-порождаюшие нетерминалы]].# Для каждого правила вида <tex>A \rightarrow \alpha_0 B_1 \alpha_1 B_2 \alpha_2 ... B_k \alpha_k</tex> (где <tex>\alpha_i</tex> — последовательности из терминалов и нетерминалов, <tex>B_j</tex> — <tex>\varepsilon</tex>-порождающие нетерминалы) добавить в <tex>P'</tex> все возможные варианты правил, в которых либо присутствует, либо удалён каждый из нетерминалов <tex>B_j\; (1 \le leqslant j \le leqslant k)</tex>.
# Удалить все <tex>\varepsilon</tex>-правила из <tex>P'</tex>.
# Если в исходной грамматике <tex>\Gamma</tex> выводилось <tex>\varepsilon</tex>, то необходимо добавить новый нетерминал <tex>S'</tex>, сделать его стартовым, добавить правило <tex>S' \rightarrow S|\varepsilon</tex>.
'''Предположение индукции'''. Пусть из <tex>A \underset{\Gamma}{\Rightarrow}^*w \ne \varepsilon</tex> менее, чем за <tex>n</tex> шагов, следует, что <tex>A \underset{\Gamma'}{\Rightarrow}^*w </tex>.<br/>
'''Переход'''. Пусть в порождении <tex>n</tex> шагов, <tex>n > 1</tex>. Тогда оно имеет вид <tex>A\underset{\Gamma}{\Rightarrow}Y_1 Y_2...Y_m \underset{\Gamma}{\Rightarrow}^*w</tex>, где <tex>Y_i \in N \cup \Sigma </tex>. Цепочку <tex>w</tex> можно разбить на <tex>w_1 w_2...w_m</tex>, где <tex>Y_i \underset{\Gamma}{\Rightarrow}^*w_i</tex>.<br/>
Пусть <tex>Y_{i_1}, Y_{i_2}, ..., Y_{i_p}</tex> — подпоследовательность, состоящая из всех элементов, таких, что <tex>w_{i_k} \ne \varepsilon</tex>, то есть <tex>Y_{i_1} Y_{i_2} ... Y_{i_p} \underset{\Gamma}{\Rightarrow}^*w</tex>. <tex>p \ge geqslant 1</tex>, поскольку <tex>w \ne \varepsilon</tex>. Значит, <tex>A \rightarrow Y_{i_1} Y_{i_2} ... Y_{i_p}</tex> является правилом в <tex>\Gamma'</tex> по построению <tex>\Gamma'</tex>.<br/>
Так как каждое из порождений <tex>Y_i \underset{\Gamma}{\Rightarrow}^*w_i</tex> содержит менее <tex>n</tex> шагов, к ним можно применить предположение индукции и заключить, что, если <tex>w_i \ne \varepsilon</tex>, то <tex>Y_i \underset{\Gamma'}{\Rightarrow}^*w_i</tex>.<br/>
Таким образом, <tex>A \underset{\Gamma'}{\Rightarrow} Y_{i_1} Y_{i_2} ... Y_{i_p} \underset{\Gamma'}{\Rightarrow}^* w</tex>.
:<tex>A\rightarrow a</tex>
:<tex>B\rightarrow A|AC|C</tex>
:<tex>C\rightarrow c</tex>:
== Источники информации ==
