Бюрократы, editor, Администраторы
422
правки
Изменения
Оформление и структура. Вроде, лучше уже не получится…
==Определение==
{{Определение
|definition=Грамматикой в '''ослабленной нормальной форме Грейбах''' (''Greibach weaked normal form'') называется [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], в которой могут содержатся правила только следующего вида:
}}
==Приведение грамматики к ослабленной нормальной форме Грейбах==
{{Теорема
|statement=Любую контекстно-свободную грамматику можно привести к ослабленной нормальной форме Грейбах.
<ol>
<li> Избавимся от <tex> \varepsilon </tex>-правил.
Для этого воспользуемся [[Удаление_eps-правил_из_грамматики | алгоритмом удаления <tex> \varepsilon </tex>-правил]]. Получим грамматику <tex> \Gamma_1 </tex>.
</li>
<li> Воспользуемся [[Устранение_левой_рекурсии|алгоритмом устранения левой рекурсии]].
Получим грамматику <tex> \Gamma_2 </tex>, все правила которой будут иметь следующий вид:
<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>.
</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>. </fontdiv> Получим грамматику <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>.
</li>
</ol>
