Алгоритм побудови правил граматики

1. Виписати кілька прикладів із заданої множині ланцюжків.

2. Проаналізувати структуру ланцюжків, виділяючи початок і кінець, де повторюються символи чи групи символів.

3. Ввести позначення для складних структур символів, що складаються з груп, такі позначення є нетермінальними символами граматики.

4. Побудувати правило для кожної з виділених структур, використовуючи для завдання повторюваних структур рекурсію.

5. Об'єднати всі правила.

6. Перевірити за допомогою висновку можливість одержання ланцюжків з різною структурою.

6. КОНТЕКСТНО-ВІЛЬНІ ГРАМАТИКИ Й АВТОМАТИ

5.1. Приведені граматики

З чотирьох типів граматик контекстно-вільні граматики (КВ) є найбільш важливими з погляду додатків до мов програмування і компіляції. За допомогою КВ-граматики можна визначити велику частину структури мови програмування. При побудові граматик, що задають конструкції мов програмування, часто приходиться прибігати до їх перетворення, щоб породжувана мова придбала потрібну структуру, тому спочатку розглянемо трохи досить простих, але важливих перетворень КВ-граматик. Перший вид перетворення зв'язаний з видаленням із граматики марних символів. Марні символи в граматиці можуть виявитися в наступних випадках:

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

Спочатку розглянемо алгоритм виявлення символів, з яких не можна вивести кінцеві
ланцюжки.

6.2. Визначення непродуктивних символів

Символ X ÎV_A називається непродуктивним, якщо з нього не може бути виведений кінцевий термінальний ланцюжок.

Розглядаючи правила граматики, можна зробити висновок, що якщо всі символи правої частини є продуктивними, то продуктивним є і символ, що стоїть в лівій частині. Останнє твердження дозволяє написати процедуру виявлення непродуктивних символів у наступному виді:
1. Скласти список нетерміналів, для яких знайдеться хоча б одне правило, права частина якого не містить нетерміналів.
2. Якщо знайдене таке правило, що всі нетермінали, що стоять у його правій частині вже занесені в список, то додати в список нетермінал, що стоїть в його лівій частині.
3. Якщо на кроці 2 список більше не поповнюється, то отримано список усіх продуктивних нетерміналів граматики, а всі нетермінали які не потрапили в нього є непродуктивними.