If<умова> then<оператор> else<оператор> | if<умова> then

< оператор >

можна вжити наступне правило модифікованої БНФ:

< оператор >:: = if < умова > then < оператор > [ else < оператор > ].

Зрозуміло, що для модифікованих БНФ вживати дужки “ { “,

“ } ”, “ [ “ та “ ] ”, а також “ * ” у якості символів мови не слід, тому що

вони виступають як метасимволи формалізму модифікованих БНФ.

При необхідності вживання цих дужок і зірочки для них

використовують спеціальні позначення.

27. Синтаксичні діаграми

Для поліпшення зорового сприйняття і полегшення розуміння синтаксичних описів, застосовують подання синтаксичних правил у вигляді синтаксичних діаграм. Такі діаграми мають одну вхідну і одну вихідну стрілки. Схематично їх можна зображувати таким чином (D – внутрішність діаграми):

Синтаксичні діаграми є структурованими. Це означає, що вони визначаються індуктивно: є найпростіші діаграми, а більш складні будуються за допомогою певних правил. Найпростішими є наступні діаграми:

• Порожня діаграма

• Термінальна діаграма (a – термінальний символ)

• Нетермінальна діаграма (A – нетермінальний символ)

Далі вважаємо, що побудовані наступні діаграми:

Є три правила побудови нових діаграм з наведених діаграм:

• Послідовність

• Альтернатива

• Ітерація

Діаграми можуть мати назву, яка є нетермінальним символом. Сукупність іменованих діаграм задає певну формальну мову, кожне слово якої складається з термінальних символів, які знаходяться на шляху від початкової стрілки до заключної (від вхідної до вихідної стрілки), причому нетермінальні символи замінуються на термінальні слова, які задаються діаграмою, що називається цим нетермінальним символом.

28. Властивості контекстно-вільних граматик

В цьому підрозділі розглянемо властивості контекстно-вільних граматик (КВ-граматик), зокрема їх еквівалентні перетворення та нормальні форми. Спочатку доведемо лему про еквівалентність граматик щодо бієктивного перейменування нетерміналів.

Лема 4.2 (про перейменування нетерміналів). Нехай задані граматика G=(N, T, P, S), та бієктивне відображення ρ: N→ N′ множини нетерміналів N на деяку іншу множину нетерміналів N ′ (N ′ ∩ T=∅). Тоді для граматики G ′ =(N ′, T, S ′, P ′), де P ′ – множина правил, отриманих з P заміною нетерміналів N на відповідні нетермінали з N ′, а S ′ =ρ (S), маємо: L(G)= L(G ′).

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

29. Видалення несуттєвих символів. Видалення ε – правил. Нормальна форма Хомського

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

Визначення 4.35 Назвемо КВ-граматику G=(N, T, P, S) граматикою без ε -правил (або нескорочуваною), якщо Р не містить ε - правил, тобто правил виду A → ε.

Лема 4.6 За кожною КВ-граматикою можна побудувати еквівалентну їй (з точністю до порожнього ланцюжка – ε - еквівалентну) граматику без ε -правил.

Доведення. Нехай дана КВ-граматика G=(N, T, P, S), що породжує мову L(G). Проведемо серію перетворень множини P. Якщо множина P містить правила B→ α Aβ і A→ ε для деяких A, B∈ N, α, β ∈ (N∪ T)*, то додамо правило B→ α β в P. Повторюємо цю процедуру поки множина правил не стабілізується. Далі виключимо із множини P всі правила вигляду A→ ε.

Наведений алгоритм можна уточнити за допомогою наступних індуктивних визначень.

1. P0=P

2. P i={B→ α β  є правила B→ α Aβ ∈ Р, A→ ε ∈ Pi-1} ∪ R i-1 (i=1, 2, …).

Оскільки множина правил є скінченною, а праві частини нових правил коротші, то формула для визначення Pi задає монотонне за і відображення. Тому існує k (k≥ 0), що Pk=Pk+1. Іншими словами, послідовність P0, P1, P2, … стабілізується на k-му кроці. Покладемо P′ =Pk\{A→ ε ∈ Pk}. Одержана граматика G′ =(N, T, P′, S) породжує мову L(G)\ {ε }. Дійсно, кожен вивід в граматиці G, який не породжує порожнє слово, може бути промодельований в граматиці G′, що легко доводиться індукцією по довжині виводу. Так само, можна промоделювати виводи в G′ виводами в G, використовуючи замість модифікованих правил виду B→ α β початкові правила виду B→ α Aβ з подальшим виводом порожнього ланцюжка з A▄