Изменения

Рассмотрим контекстно-свободную грамматику <tex> \Gamma </tex>. Для приведения ее к нормальной ослабленной форме Грейбах нужно выполнить несколько шаговтри шага. На каждом шаге мы строим новую <tex> \Gamma_i </tex>, которая допускает тот же язык, что и <tex> \Gamma </tex>.

#<ol><li> Избавимся от <tex> \varepsilon </tex>-правил.#<div style="margin-left: 22px;">Для этого воспользуемся [[Удаление_eps-правил_из_грамматики | алгоритмом удаления &epsilon;<tex> \varepsilon </tex>-правил]]. Получим грамматику <tex> \Gamma_1 </tex>.#</div></li><li> Воспользуемся [[Устранение_левой_рекурсии|алгоритмом устранения левой рекурсии]]. #<div style="margin-left:22px;">Получим грамматику <tex> \Gamma_2 </tex>, все правила которой будут иметь следующий вид:#<div style="margin-left::*22px;"><ul><li> <tex> A_i \rightarrow a \gamma </tex>,</li>#::*<li> <tex> A_i \rightarrow A_j \gamma </tex>,</li></ul></div>#:где <tex> A_i </tex>, <tex> A_j </tex> {{---}} нетерминалы, <tex> a </tex> {{---}} терминал, <tex> \gamma </tex> {{---}} произвольная последовательность из терминалов и нетерминалов, <tex> i < j </tex>.#</div></li><li>Воспользуемся следующей процедурой для придания грамматике нужного вида.#<div style="margin-left: 22px;"> <font size="3"> for i = n downto 1 #:: for j = i + 1 to n #::: Для каждого правила вывода из <tex> A_j \rightarrow \delta_1 | \ldots | \delta_k </tex> заменить каждое правило <tex> A_i \rightarrow A_j \gamma </tex> на <tex> A_i \rightarrow \delta_1\gamma | \ldots | \delta_k\gamma </tex>. #:</font>Получим грамматику <tex> \Gamma_3 </tex>.<br>#:После каждой итерации главного цикла все правила для <tex> A_k, \, k \ge i </tex> будут иметь вид <tex> A_k \rightarrow a \alpha </tex>. <br>#:Значит, после применения процедуры все правила грамматики будут иметь вид <tex> A \rightarrow a \alpha </tex>.#Если <tex> \varepsilon </texdiv> присутствовал в языке старой грамматики, то добавим новый стартовый символ <tex> S' </texli> и правила <tex> S' \rightarrow S | \varepsilon </texol> в <tex> \Gamma_3 </tex>.