Языки и трансляции. Мартыненко Б.К. - 57 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

56
Пример 4.2. Преобразуем грамматику G =({A
1
, A
2
, A
3
}, {a, b}, P, A
1
), где
P ={A
1
→ A
2
A
3
, A
2
→ A
3
A
1
, A
2
→ b, A
3
→ A
1
A
2
, A
3
→ a}, к нормальной форме
Грейбах.
Шаг 1. Поскольку правые части правил для A
1
и A
2
начинаются
с
нетерминалов с большими номерами и с терминала, то мы начинаем с правила
A
3
→ A
1
A
2
и подставляем цепочку A
2
A
3
вместо A
1
. Заметим, что A
1
→ A
2
A
3
является
единственным правилом с A
1
в левой части. В результате получаем
следующее множество правил
{A
1
→ A
2
A
3
, A
2
→ A
3
A
1
, A
2
→ b, A
3
→ A
2
A
3
A
2
, A
3
→ a}.
Поскольку правая часть правила A
3
→ A
2
A
3
A
2
начинается с нетерминала с
меньшим номером, мы подставляем вместо первого вхождения A
2
либо A
3
A
1
,
либо b. Таким образом, правило A
3
→ A
2
A
3
A
2
заменяется на
A
3
→ A
3
A
1
A
3
A
2
и
A
3
→ bA
3
A
2
. Новое множество есть
{A
1
→ A
2
A
3
, A
2
→ A
3
A
1
, A
2
→ b, A
3
→ A
3
A
1
A
3
A
2
, A
3
→ bA
3
A
2
, A
3
→ a}.
Теперь применим лемму 4.3 к правилам A
3
→ A
3
A
1
A
3
A
2
, A
3
→ bA
3
A
2
и
A
3
→ a. Введём символ Z
3
и заменим правило A
3
→ A
3
A
1
A
3
A
2
правилами
A
3
→bA
3
A
2
Z
3
, A
3
→aZ
3
, Z
3
→A
1
A
3
A
2
и Z
3
→A
1
A
3
A
2
Z
3
. Теперь мы имеем множество:
{A
1
→ A
2
A
3
, A
2
→ A
3
A
1
, A
2
→ b, A
3
→ bA
3
A
2
, A
3
→ a, A
3
→ bA
3
A
2
Z
3
, A
3
→ aZ
3
,
Z
3
→ A
1
A
3
A
2
Z
3
, Z
3
→ A
1
A
3
A
2
}.
Шаг 2. Все правила с A
3
слева начинаются с терминалов. Они используются
для замены A
3
в правиле A
2
→ A
3
A
1
, а затем правила для A
2
используются для
того, чтобы заменить A
2
в правиле A
1
→ A
2
A
3
.
Получаем:
A
3
→ bA
3
A
2
, A
2
→ bA
3
A
2
A
1
, A
1
→ bA
3
A
2
A
1
A
3
, Z
3
→ A
1
A
3
A
2
Z
3
,
A
3
→ a, A
2
→ bA
3
A
2
Z
3
A
1
, A
1
→ bA
3
A
2
Z
3
A
1
A
3
, Z
3
→ A
1
A
3
A
2
.
A
3
→ bA
3
A
2
Z
3
, A
2
→ aA
1
, A
1
→ aA
1
A
3
,
A
3
→ aZ
3
; A
2
→ aZ
3
A
1
, A
1
→ aZ
3
A
1
A
3
,
A
2
→ b; A
1
→ bA
3
;
Шаг 3. Два правила для Z
3
заменяются
на десять новых в результате
подстановки в них вместо A
1
правых частей правил для A
1
:
Z
3
→ bA
3
A
2
A
1
A
3
A
3
A
2
Z
3
, Z
3
→ bA
3
A
2
A
1
A
3
A
3
A
2
,
Z
3
→ bA
3
A
2
Z
3
A
1
A
3
A
3
A
2
Z
3
, Z
3
→ bA
3
A
2
Z
3
A
1
A
3
A
3
A
2
,
Z
3
→ aA
1
A
3
A
3
A
2
Z
3
, Z
3
→ aA
1
A
3
A
3
A
2
,
Z
3
→ aZ
3
A
1
A
3
A
3
A
2
Z
3
, Z
3
→ aZ
3
A
1
A
3
A
3
A
2
,
Z
3
→ bA
3
A
3
A
2
Z
3
, Z
3
→ bA
3
A
3
A
2
.
Окончательно, получаем следующее множество правил эквивалентной
грамматики в нормальной форме Грейбах:
A
3
→ bA
3
A
2
, A
2
→ bA
3
A
2
A
1
, A
1
→ bA
3
A
2
A
1
A
3
, Z
3
→ bA
3
A
2
A
1
A
3
A
3
A
2
Z
3
,
A
3
→ a, A
2
→ bA
3
A
2
Z
3
A
1
, A
1
→ bA
3
A
2
Z
3
A
1
A
3
, Z
3
→ bA
3
A
2
Z
3
A
1
A
3
A
3
A
2
Z
3
,
A
3
→ bA
3
A
2
Z
3
, A
2
→ aA
1
, A
1
→ aA
1
A
3
, Z
3
→ aA
1
A
3
A
3
A
2
Z
3
,
A
3
→ aZ
3
; A
2
→ aZ
3
A
1
, A
1
→ aZ
3
A
1
A
3
, Z
3
→ aZ
3
A
1
A
3
A
3
A
2
Z
3
,
A
2
→ b; A
1
→ bA
3
; Z
3
→ bA
3
A
3
A
2
Z
3
,
Z
3
→ bA
3
A
2
A
1
A
3
A
3
A
2
,
Z
3
→ bA
3
A
2
Z
3
A
1
A
3
A
3
A
2
,
Z
3
→ aA
1
A
3
A
3
A
2
,
Z
3
→ aZ
3
A
1
A
3
A
3
A
2
,
Z
3
→ bA
3
A
3
A
2
.

Страницы