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

Материал из Викиконспекты
Перейти к: навигация, поиск
Определение:
Грамматикой в нормальной форме Грейбах (Greibach normal form) называется к.с. грамматика, в которой содержатся только правила вида

[math]A \rightarrow a B C [/math]

[math]A \rightarrow a B[/math]

[math]A \rightarrow a[/math]

(где [math]a[/math] - терминал, [math]A, B, C[/math] - нетерминалы)

и, возможно, правило [math]S \rightarrow \epsilon[/math] (в этом случае [math]S[/math] - начальный символ и не содержится в правых частях правил)


Определение:
Грамматикой в ослабленной нормальной форме Грейбах называется к.с. грамматика, в которой содержатся только правила вида

[math]A \rightarrow a \alpha[/math]

(где [math]a[/math] - терминал, [math]\alpha[/math] - строка из терминалов и нетерминалов)

и, возможно, правило [math]S \rightarrow \epsilon[/math] (в этом случае [math]S[/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].