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

Определение

Определение:

Грамматикой в ослабленной нормальной форме Грейбах (Greibach weaked normal form) называется контекстно-свободная грамматика, в которой могут содержатся правила только следующего вида: [math] A \rightarrow a\gamma [/math], [math] S \rightarrow \varepsilon [/math], где [math] a [/math] — терминал, [math] A [/math] — нетерминал, [math] S [/math] — стартовая вершина, [math] \varepsilon [/math] — пустая строка, [math] \gamma [/math] — строка из произвольного количества терминалов и нетерминалов, стартовая вершина не содержится в правых частях правил.

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

Теорема:

Любую контекстно-свободную грамматику можно привести к ослабленной нормальной форме Грейбах.

Доказательство:

[math]\triangleright[/math]

Рассмотрим контекстно-свободную грамматику [math] \Gamma [/math]. Для приведения ее к нормальной ослабленной форме Грейбах нужно выполнить несколько шагов. На каждом шаге мы строим новую [math] \Gamma_i [/math], которая допускает тот же язык, что и [math] \Gamma [/math]. Избавимся от [math] \varepsilon [/math]-правил. Для этого воспользуемся алгоритмом удаления ε-правил. Получим грамматику [math] \Gamma_1 [/math]. Воспользуемся алгоритмом устранения левой рекурсии. Получим грамматику [math] \Gamma_2 [/math], все правила которой будут иметь следующий вид: [math] A_i \rightarrow a \gamma [/math], [math] A_i \rightarrow A_j \gamma [/math], где [math] A_i [/math], [math] A_j [/math] — нетерминалы, [math] a [/math] — терминал, [math] \gamma [/math] — произвольная последовательность из терминалов и нетерминалов, [math] i \lt j [/math].

[math]\triangleleft[/math]

Приведем алгоритм, позволяющий для к.с. грамматики без ε-правил построить эквивалентную ей к.с. грамматику (без ε-правил), содержащую только правила вида [math]A \rightarrow a \alpha[/math].

Произвольную грамматику [math]\Gamma[/math] можно привести к требуемой форме следующим образом:

1. Воспользоваться алгоритмом удаления ε-правил. Получим грамматику без ε-правил для языка [math]L(\Gamma) \setminus \lbrace \epsilon \rbrace[/math]
2. Воспользоваться алгоритмом для новой грамматики
3. Если [math]\epsilon[/math] присутствовал в языке исходной грамматики, добавить новый начальный символ [math]S'[/math] и правила [math]S' \rightarrow S \, | \, \epsilon [/math]

Алгоритм для грамматики без ε-правил

Первым делом, используем алгоритм устранения левой рекурсии. После этого все правила грамматики будут иметь вид

• [math]A_i \rightarrow a \alpha [/math], где [math]\alpha[/math] - терминал
• [math]A_i \rightarrow A_j \alpha [/math], где [math]i \lt j[/math]

Затем проведем процедуру, похожую на используемую при устранении левой рекурсии:

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]

}

}

Легко видеть, что после итерации главного цикла для значения [math]i[/math] все правила для [math]A_k, \, k \ge i[/math] будут иметь вид [math]A_k \rightarrow a \alpha[/math].

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