Просмотр исходного текста страницы Приведение грамматики к ослабленной нормальной форме Грейбах

{{Определение
|definition=Грамматикой в нормальной форме Грейбах (Greibach normal form) называется к.с. грамматика, в которой содержатся только правила вида
<tex>A \rightarrow a B C </tex> 

<tex>A \rightarrow a B</tex>

<tex>A \rightarrow a</tex>

(где <tex>a</tex> - терминал, <tex>A, B, C</tex> - нетерминалы)
и, быть может, правило <tex>S \rightarrow \epsilon</tex> (где <tex>S</tex> - начальный символ)
}}
{{Определение
|definition=Грамматикой в ослабленной нормальной форме Грейбах называется к.с. грамматика, в которой содержатся только правила вида
<tex>A \rightarrow a \alpha</tex> 

(где <tex>a</tex> - терминал, <tex>\alpha</tex> - строка из терминалов и нетерминалов)
и, быть может, правило <tex>S \rightarrow \epsilon</tex> (в этом случае <tex>S</tex> - начальный символ и не содержится в правых частях правил)
}}
==Алгоритм приведения грамматики к ослабленной нормальной форме Грейбах==
Приведем алгоритм, позволяющий для к.с. грамматики '''без &epsilon;-правил''' построить эквивалентную ей к.с. грамматику (без &epsilon;-правил), содержащую только правила вида <tex>A \rightarrow a \alpha</tex>.

Произвольную грамматику <tex>\Gamma</tex> можно привести к требуемой форме следующим образом:
#Воспользоваться [[Удаление_eps-правил_из_грамматики | алгоритмом удаления &epsilon;-правил]]. Получим грамматику без &epsilon;-правил для языка <tex>L(\Gamma) \setminus \lbrace \epsilon \rbrace</tex>
#Воспользоваться алгоритмом для новой грамматики
#Если <tex>\epsilon</tex> присутствовал в языке исходной грамматики, добавить новый начальный символ <tex>S'</tex> и правила <tex>S' \rightarrow S \, | \, \epsilon </tex>

===Алгоритм для грамматики без ε-правил===
Первым делом, используем [[Устранение_левой_рекурсии|алгоритм устранения левой рекурсии]]. После этого все правила грамматики будут иметь вид
*<tex>A_i \rightarrow a \alpha </tex>, где <tex>\alpha</tex> - терминал
*<tex>A_i \rightarrow A_j \alpha </tex>, где <tex>i < j</tex>

Затем проведем процедуру, похожую на используемую при устранении левой рекурсии:
: for i = n downto 1 {
::for j = n downto i + 1 {
:::* рассмотреть все правила вывода из <math>A_j</math>
:::<math>A_j \rightarrow \delta_1 | \ldots | \delta_k</math>
:::* заменить каждое правило <math>A_i \rightarrow A_j \gamma</math> на
:::<math>A_i \rightarrow \delta_1\gamma | \ldots | \delta_k\gamma</math>
::}
:}
Легко видеть, что после итерации главного цикла для значения <tex>i</tex> все правила для <tex>A_k, \, k \ge i</tex> будут иметь вид <tex>A_k \rightarrow a \alpha</tex>.

Следовательно, после применения процедуры все правила грамматики будут иметь вид <tex>A \rightarrow a \alpha</tex>.