Зауваження

Алгоритм приведення граматики

Визначення

Метод

Алгоритм видалення марних символів

Визначення

Метод

Алгоритм видалення недосяжного символу

Визначення

Символ називається недосяжним в граматиці G=(VT, VN, P, S), якщо він не з‘являється в жодній сентенціальній формі цієї граматики.

Вхід: КС – граматика G=(VT, VN, P, S)

Вихід: КС – граматика , що не містить недосяжних символів, для якої .

1. V₀={S}; i=1.

2. в та .

3. Якщо , то , і переходимо до кроку 2, інакше складається з правил множини Р, що містять тільки символи з V_i; .

Символ називається марним в граматиці G=(VT, VN, P, S), якщо множина є порожньою.

Вхід: КС – граматика G=(VT, VN, P, S)

Вихід: КС – граматика , що не містить марних символів, для якої .

Рекурсивно будуємо множини N₀, N₁…

1. , i=1.

2. та .

3. Якщо , то і=і+1, і переходимо до кроку 2, інакше складається з правил множини Р, що містять лише символи з .

КС-граматика G називається приведеною, якщо в ній немає недосяжних та марних символів.

1. Знаходяться та видаляються усі марні нетермінали.

2. Знаходяться та видаляються всі недосяжні символи.

Видалення символів супроводжується видаленням правил висновку, що містять ці символи.

Якщо у цьому алгоритмі переставити кроки 1 та 2, то не завжди результатом буде приведена граматика.

Для опису синтаксису мов програмування намагаються використовувати однозначні, приведені КВ-граматики.