Нормальні форми Хомського та Грейбах

 

 

Теорія: …

 

+ алгоритм: як позбутися ε-правил (ε-переходів) !!! + який сенс застосування (отримаємо нескорочуючі правила, ефективний синтаксичний аналіз)

Означення: Нетермінал  КС-граматики  називається -нетерміналом, якщо .

Алгоритм.Пошук -нетерміналів:

….

…. П_n

Тоді множина  — множина -нетерміналів.

 

 

+ алгоритм: як позбутися лівої рекурсії + сенс застосування (ефективний синтаксичний аналіз – LL(k), тоді можлива однозначна (без повернень) побудова зліва-направо = лівостороння стратегія виводу)

Запропонуємо декілька прийомів, що дають можливість при побудові граматик уникнути лівої рекурсії. Розглянемо граматику зі схемою правил , яка має ліворекурсивний нетермінал . Замінимо схему правил новою схемою з трьома правилами

.

 

 

Теорія про НФ Хомського та Грейбах:

· визначення,

· можливо, алгоритм зведення,

o для Хомського:

§ виключити непродуктивні і недосяжні нетермінали

§ позбутися ε-продукцій (стандартним алгоритмом підстановки та виключення), та ввести нову аксіому, якщо ε виводиться в граматиці

§ для всіх терміналів ввести допоміжні нетермінали, відповідні правила (A ® a, B ® b) та виконати заміни

§ всі продукції з «довшими» за 2 символи правими частинами розбиваємо на декілька (довжина – 1), вводячи допоміжні нетермінали

§ якщо в правій частині продукції залишився 1 нетермінал, виконати його «каскадні»/«ланцюжкові» заміни

§

o для Грейбах:

§ виключити непродуктивні і недосяжні нетермінали

§ позбутися ε-правил (стандартним алгоритмом підстановки та виключення), та ввести нову аксіому, якщо ε виводиться в граматиці

§ позбутись лівої рекурсії

§ підставити замість нетерміналів на 1 місці в правих частинах їх праві частини згідно правил граматики

§

· застосування (навіщо вони потрібні?) …

 

 

Завдання 2.7.

Звести наступну КВ-граматику до нормальної форми Хомського:

S ® bS | pCD

C ® aaD | CCD

D ® ε

 

Розв’язок.

1) Нетермінал S присутній в правих частинах продукцій, тому додаємо продукцію S₀®S, S₀ – нова аксіома

2) Термінал b замінюємо на B, a замінюємо на А, p – на P, тобто вводимо нові нетермінали і замінюємо входження терміналів у правила на нові, щойно введені, нетермінали.

S ® BS | PCD

C ® AAD | CCD

D ® ε

Додаємо продукції A ® a, B ® b, P ® p

3) Всі продукції з правими частинами, довжина яких (l) більша за 2, «розкладаємо» на (l–1) продукції так, щоб у правих частинах було тільки по 2 нетермінальних символи, при цьому вводимо нові допоміжні нетермінали. Так, Q ®AA, W ® PC, E ® CC – нові правила, тоді:

вводимо також правила S ® WD, C ® QD, C ® ED

виключаємо правила S ® PCD, C ® AAD , C ® CCD

{Q, W, E} Î N – нові нетермінали

Отримали:

S ® BS | WD

C ® QD | ED

Q ® AA

W ® PC

E ® CC

D ® ε

A ® a, B ® b, P ® p

4) У нас є продукція D ® ε, тому позбуваємось e-нетерміналу стандартним способом (виключення з правих частин), отримуючи:

виключається правило D ® ε,

додаються: S ® W, C ® Q, C ® E

5) Маємо продукції з одним нетерміналом у правій частині: S ® W, C ® Q, C ® E, тому проводимо відповідну «каскадну підстановку»:

S ® W, W ® PC,

C ® Q, Q ® AA,

C ® E, E ® CC, отже, отримуємо нові правила: S ® PC, C ® AA, C ® CC, а старі S ® W, C ® Q, C ® E – виключаються.

6) Оскільки в правилі S₀ ® S права частина теж закоротка, підставимо для S₀ всі альтернативи для S. В результаті отримаємо граматику у нормальній формі Хомського, еквівалентну початковій:

S₀ ® BS | WD | PC

S ® BS | WD | PC

C ® QD | ED | AA | CC

Q ® AA

W ® PC

E ® CC

A ® a, B ® b, P ® p

 

 

Завдання 2.8.

Звести наступну КВ-граматику до нормальної форми Хомського:

S ® bC | aD

C ® bCC | aS | a

D ® aDD | bS | b

P ® aD

 

Розв’язок.

1) Відкинемо недосяжні і непродуктивні нетермінали.

Ітераційно побудуємо множини досяжних:

R₀ = {S}

R₁ = {C,D,S}

R₂ = {C,D,S} = R₁ = R

та продуктивних нетерміналів:

P₀={C,D}

P₁={C,D,S,P}

P₂={C,D,S,P} = P₁=P

Тоді недосяжні нетермінали: N\R = {P}, а непродуктивних – немає: N\P = Æ

Тому правило P ® aD слід виключити з граматики і подальшого розгляду.

2) Нетермінал S присутній в правих частинах продукцій тому додаємо продукцію S₀ ® S, S₀ – нова аксіома граматики

3) Вводимо нові допоміжні нетермінали A та B, і в правилах b замінюємо на B, a замінюємо на А – отримуємо:

S ® BC | AD

C ® ACC | AS | A

D ® ADD | BS | B

Додаємо також продукції A ® a, B ® b

4) Вводимо допоміжні нетермінали для правил з довшими за 2 елементи правими частинами, а також відповідні правила для них: Q ® AC, W ® AD, C ® QC, D ® WD, виключаючи при цьому C ® ACC і D ® ADD ({Q, W} Î N)

5) Маємо продукції C ® A, A ® a, D ® B, B ® b, тому вводимо продукції C ® a, D ® b, натомість виключаємо C ® A, D ® B.

6) Отримуємо еквівалентну граматику у нормальній формі Хомського, підставивши у правило S₀ ® S всі альтернативи для S:

S₀ ® BC | AD

S ® BC | AD

C ® QC | AS | a

D ® WD | BS | b

Q ® AC

W ® AD

A ® a, B ® b

 

 

Завдання 2.9.

Звести наступну КВ-граматику до нормальної форми Хомського:

S ® aKd

K ® aKd | P | ε

P ® bPc | F | ε

 

Розв’язок.

1) Відкинемо недосяжні і непродуктивні нетермінали. F-непродуктивний.

2) Позбудемось ε–правил.

Замість K ® ε додаємо: K ® ad, S ® ad; замість P ® ε – додаємо P ® bc.

Отримаємо:

S ® aKd | ad

K ® aKd | ad | P

P ® bPc | bc

3) Замість правила K ® P (із закороткою правою частиною), враховуючи P ® bPc | bc, додамо нові правила: K ® bPc | bc

4) Вводимо допоміжні нетермінали та правила: A ® a, B ® b,D ® d,C ® c, отримуємо відповідно:

A ® a, B ® b,D ® d,C ® c

S ® AKD | AD

K ® AKD | AD | BC | BPC

P ® BPC | BC

5) Врешті, розбивши «довгі» праві частини правил шлязом введення допоміжних нетерміналів, отримаємо результуючу граматику у нормальній формі Хомського:

S ® XD | AD

K ® XD | AD | BC | YC

P ® YC | BC

A ® a, B ® b,D ® d,C ® c

X ® AK, Y ® BP

 

 

Завдання 2.10.

Звести наступну КВ-граматику до нормальної форми Хомського:

S ® aUbU | CCb | e

U ® S | C | ba

 

Розв’язок.

1) Відкинемо недосяжні і непродуктивні нетермінали: C-непродуктивний.

2) Введемо нову аксіому S₀, оскільки символ S присутній в правих частинах правил, при цьому позбудемось ε–правила S ® e (S і U є ε–нетерміналами). Отримаємо:

S₀ ® e | S

S ® aUbU | ab | abU | aUb

U ® S | ba

3) Додамо допоміжні нетермінали і правила: T_a ® a, T_b ® b, отримаємо:

S₀ ® e | S

S ® T_aUT_bU | T_aT_b | T_aUT_b | T_aT_bU

U ® S | T_bT_a

T_a ® a, T_b ® b

4) Для довгих правих частин введемо допоміжні нетермінали, щоб розбити їх на частини:

S₀ ® e | S

S ® AB | T_aT_b | AT_b | T_aB

A ® T_aU

B ® T_bU

U ® S | T_bT_a

T_a ® a, T_b ® b

 

5) Закороткі правила U ® S та S₀ ® S заміняємо всіма можливими замінами S:

S₀ ® e| AB| T_aT_b | AT_b | T_aB

S ® AB | T_aT_b | AT_b | T_aB

A ® T_aU

B ® T_bU

U ® AB | T_aT_b | AT_b | T_aB | T_bT_a

T_a ® a, T_b ® b

Таким чином отримаємо результуючу еквівалентну граматику у нормальній формі Хомського.

 

 

Завдання 2.11.

Звести наступну КВ-граматику до нормальної форми Хомського:

S ® aD | D

U ® bb | Cb

D ® e | Db | Ua

L ® UD

Розв’язок.

1) Оскільки C – непродуктивний, а L – недосяжний нетермінали, вхідна граматика еквівалентна наступній:

S ® aD | D

U ® bb

D ® e | Db | Ua

2) Оскільки граматика породжує, зокрема, порожнє слово, необхідно ввести нову аксіому S₀ та правило S₀ ® S | e.

3) Введемо допоміжні нетермінали і правила: A ® a, B ® b, отримаємо:

S₀ ® S | ԑ

S ® AD | D

U ® BB

D ® ԑ | DB | UA

A ® a, B ® b

4) Позбавляємось e-правила D ® ԑ :

S₀ ® S | ԑ

S ® AD | D | A

U ® BB

D ® DB | UA | B

A ® a, B ® b

5) Нарешті, для односимвольних правих частин робимо заміни: для S ® A і D ® B виконуємо заміни на відповідно термінали, а для S ® D – підставляємо всі альтернативи для нетермінала D:

S₀ ® ԑ | AD | DB | UA | b | a

S ® AD | DB | UA | b | a

U ® BB

D ® DB | UA | b

A ® a, B ® b

Отримаємо результуючу еквівалентну граматику у нормальній формі Хомського.

 

 

Завдання 2.12.

Звести наступну КВ-граматику до нормальної форми Грейбах:

S ® AB

A ® ε | aC

B ® Bb | ε

C ® Cc | ε

Розв’язок.

1) Легко перевірити, що всі нетермінали суттєві, тобто досяжні й продуктивні: R₀ = {S}, R₁ = {S, A, B}, R₂ = {S, A, B, C} = N; P₀ = {A, B, C} P₁ = {S, A, B, C} = N.

2) Позбудемось ε-переходів (ε-правил), для цього додамо правила, отримані шляхом підстановок ε-нетерміналів:

S ® B, S ® A, S ® ε, B ® b, C ® c, A ® a

та вилучимо ε-правила:

A ® ε, B ® ε, C ® ε

Отримаємо еквівалентну граматику:

S ® AB | A | B | ε

A ® aC | a

B ® Bb | b

C ® Cc | c

3) Позбудемось лівої рекурсії. Для цього правило

 C ® Cc | c

замінемо сукупністю еквівалентних правил (ввівши новий нетермінал D):

C ® cD, D ® cD, D ® ε

Позбудемось отриманого ε-правила D ® ε:

додамо правила C ® c, D ® c

і одержимо: C ® cD | c, D ® cD | c

 

Аналогічно для B ® Bb | b :

    B ® bF | b, F ® bF | b

    В решті отримаємо:

S ® AB | A | B | ε

A ® aC | a

B ® bF | b, F ® bF | b

C ® cD | c, D ® cD | c

4) Для всіх правил, де у правій частині перший символ – нетермінал, робимо всі можливі для нього підстановки, а саме:

S ® a, S ® aC для S ® A

S ® b, S ® bF для S ® B

S ® aB, S ® aCB для S ® AB

вилучаючи при цьому самі такі правила, тобто:

S ® A, S ® B, S ® AB

Отримаємо еквівалентну даній граматику у нормальній формі Грейбах:

S ® aB | aCB | a | aC | b | bF | ε

A ® aC | a

B ® bF | b, F ® bF | b

C ® cD | c, D ® cD | c

 

 

Завдання 2.13.

Звести наступну КВ-граматику до нормальної форми Грейбах:

S ® aAC | BA

B ® Pk | ε

A ® a | aA

C ® c | cC

Розв’язок.

1) Знайдемо продуктивні нетермінали:

P₀ = {A, B, C}

P₁ = {S, A, B, C}

P₂ = {S, A, B, C} = P₁ = P

Отже, CP = {P} – непродуктивний нетермінал, тому виключаємо з граматики правило B ® Pk

2) Позбудемось ε-правила B ® ε, для цього додамо правило S ® A.

При цьому виключаємо продукції B ® ε та S ® BA, оскільки більше не залишається продукцій з нетерміналом B у лівій частині.

Отримаємо:

S ® aAC | A

A ® a | aA

C ® c | cC

3) У правилі S ® A заміняємо перший у правій частині нетермінал на всі можливі для нього альтернативи, тобто додаємо правила S ® a, S ® aA

В решті отримаємо еквівалентну граматику у нормальній формі Грейбах:

S ® aAC | a | aA

A ® a | aA

C ® c | cC

 

 

Завдання 2.14.

Звести наступну КВ-граматику до нормальної форми Грейбах:

S ® AS | ε

A ® aS | P | b

P ® Pc | b

 

Розв’язок.

1) Всі нетермінали граматики – суттєві, тобто досяжні і продуктивні.

2) Оскільки слово ε виводиться в граматиці, вводимо окрему нову аксіому, для якої будуть лише два правила, щоб відділити вивід слова ε від усіх інших можливих виводів у граматиці: S₀ ® ε та S₀ ® S. Також позбудемось ε-переходу S ® ε шляхом підстановки у інші правила, де S є у правих частинах, отримаємо:

S₀ ® ε | S

S ® AS | A

A ® aS | P | b | a

P ® Pc | b

3) Позбудемось лівої рекурсії для нетермінала P, замінивши правила

 P ® Pc | b

сукупністю правил

P ® bP¹, P¹ ® cP¹, P¹ ® ε

Далі позбудемось отриманого ε-правила P¹ ® ε, для цього виконаємо можливі підстановки P¹ і одержимо нові правила: P ® b та P¹ ® c замість P¹ ® ε, тобто в решті решт одержимо такі нові правила:

P ® bP¹ | b

P¹ ® cP¹ | c

Отримаємо:

S₀ ® ε | S

S ® AS | A

A ® aS | P | b | a

P ® bP¹ | b

P¹ ® cP¹ | c

4) Підставляємо замість нетермінала P на першому місці правих частин правил слова, що безпосередньо вивдяться з P:

S₀ ® ε | S

S ® AS | A

A ® aS | bP¹ | b | a

P ® bP¹ | b

P¹ ® cP¹ | c

аналогічно – для нетермінала A:

S₀ ® ε | S

S ® aSS | bP¹S | bS | aS | bP¹ | b | a

A ® aS | bP¹ | b | a

P ® bP¹ | b

P¹ ® cP¹ | c

Оскільки нетермінали A та P стали в результаті перетворень недосяжними, виключимо їх з правил граматики – отримаємо граматику, еквівалентну початковій, у нормальній формі Грейбах:

S₀ ® ε | aSS | bP¹S | bS | aS | bP¹ | b | a

S ® aSS | bP¹S | bS | aS | bP¹ | b | a

P¹ ® cP¹ | c

 

 

Завдання 2.15.

Звести наступну КВ-граматику до нормальної форми Грейбах:

S ® A | bD

D ® Ԑ | aa | CD

A ® u | ε | C

K ® Bf

 

Розв’язок.

1) Знайдемо недосяжні і непродуктивні нетермінали.

R₀ = {S}

R₁ = {S, A, D}

R₂ = {S, A, D, C}

R₃ = {S, A, D, C} = R₂ = R

Отже, недосяжні нетермінали N\R = {K}, тобто нетермінал K виключаэмо з правил граматики. Щодо продуктивних нетерміналів:

P₀ = {D, A}

P₁ = {S, D, A}

P₂ = {S, D, A} = P₁ = P

Отже, непродуктивні нетермінали – N\P = {C}   , тому виключаємо нетермінал C з граматикики також, залишиться:

S ® A | bD

D ® ε | aa

A ® u | ε

2) Оскільки нетермінал A – на першій позиції в правій частині правила S ® A, замінимо його можливими підстановками: A ® u | ε, отримаємо:

S ® u | ԑ | bD

D ® ε | aa

A ® u | ε

Тепер нетермінал A став недосяжним, отже, виключаємо його з граматики і отрумуємо:

S ® u | ԑ | bD

D ® ε | aa

3) Позбудемось ε-продукцій, замінивши входження ε-нетерміналів (S та D) у всіх правилах, а також ввівши нову аксіому S₀ (для збереження можливості породження слова ε):

S₀ ® S | ԑ

S ® u | bD | b

D ® aa

Отже, отримаємо еквівалентну початуовій граматику у нормальній формі Грейбах:

S₀ ® ԑ | u | bD | b

S ® u | bD | b

D ® aa

 

 

Завдання 2.16.

Звести наступну КВ-граматику до нормальної форми Грейбах:

S ® c | aABU | cC

A ® Aa | bU | ԑ

B ® aa | Cc

U ® bA | BB | ԑ

M ® AB

 

Розв’язок.

1) Легко визначити, що C – непродуктивний, М – недосяжний нетермінали, тому виключимо їх з правил граматики:

S ® c | aABU

A ® Aa | bU | ԑ

B ® aa

U ® bA | BB | ԑ

2) Виключимо ԑ-переходи (A ® ԑ та U ® ԑ) з граматики, отримаємо:

S ® c | aABU | aBU | aAB | aB

A ® Aa | bU | b | a

B ® aa

U ® bA | BB | b

3) Позбавимось лівої рекурсії для нетермінала A:

S ® c | aABU | aBU | aAB | aB

A ® bUW | bW | aW

W ® aW | ԑ

B ® aa

U ® bA | BB | b

4) Залишилось позбутись ԑ-переходу W ® ԑ та першого входження нетерміналу B у правилі U ® BB (шляхом підстановки можливих виведень згідно продукцій граматики):

S ® c | aABU | aBU | aAB | aB

A ® bUW | bW | aW | bU | b | a

W ® aW | a

B ® aa

U ® bA | aaB | b

і ми отримали граматику у нормальній формі Грейбах, яка еквівалентна початковій.

 

 

Завдання для самостійної та контрольної роботи

 

 

……

 

---

Дата добавления: 2018-04-05; просмотров: 663; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!