- •М. С. Нікітченко теорія програмування Частина 1
- •1. Формалізація простої мови програмування
- •1.1. Неформальний опис простої мови програмування
- •1.2. Формальний опис синтаксису мови sipl
- •1.3. Формальний опис семантики мови sipl
- •1.3.2. Функції
- •1.3.3. Композиції
- •1.3.4. Програмні алгебри
- •1.3.5. Визначення семантичних термів
- •1.3.6. Побудова семантичного терму програми
- •1.3.7. Обчислення значень семантичних термів
- •1.3.8. Загальна схема формалізації мови sipl
- •1.4. Властивості програмної алгебри
- •2. Розвиток основних понять програмування
- •2.1. Аналіз словникових визначень поняття програми
- •2.2. Розвиток поняття програми з гносеологічної точки зору
- •2.3. Розвиток основних понять програмування
- •2.3.1 Початкова тріада понять програмування
- •2.3.2. Тріада прагматичності програм
- •2.3.3. Тріада основних понять програмування
- •2.3.4. Пентада основних понять програмування
- •2.4. Розвиток основних програмних понять
- •2.4.1. Тріада основних програмних понять
- •Малюнок 2.7. Програма як діалектичне заперечення проблеми
- •2.4.2. Пентада основних програмних понять
- •2.5. Сутнісні та семіотичні аспекти програм
- •2.6. Програми і мови
- •2.7. Пентада програмних понять процесного типу
- •3. Формалізація програмних понять
- •3.1. Теоретико-функціональна формалізація
- •3.2. Класи функцій
- •3.3. Програмні системи
- •3.4. Рівні конкретизації програмних систем
- •4. Синтактика: формальні мови та граматики
- •4.1. Розвиток понять формальної мови та породжуючої граматики
- •4.2. Визначення основних понять формальних мов
- •4.3. Операції над формальними мовами
- •4.4. Породжуючі граматики
- •4.5. Приклад породжуючої граматики та її властивості
- •4.6. Ієрархія граматик Хомського
- •4.7. Автоматні формалізми сприйняття мов
- •4.7.1. Машини Тьюрінга
- •4.7.2. Еквівалентність машин Тьюрінга та породжуючих граматик
- •4.7.3. Лінійно-обмежені автомати
- •4.7.4. Магазинні автомати
- •4.7.5. Скінченні автомати
- •4.8. Методи подання синтаксису мов програмування
- •4.8.1. Нормальні форми Бекуса–Наура
- •4.8.2. Модифіковані нормальні форми Бекуса–Наура
- •4.8.3. Синтаксичні діаграми
- •4.9. Властивості контекстно-вільних граматик
- •4.9.1. Видалення несуттєвих символів
- •4.9.2. Видалення -правил
- •4.9.3. Нормальна форма Хомського
- •4.9.4. Нормальна форма Грейбах
- •4.9.5. Рекурсивні нетермінали
- •4.10. Властивості контекстно-вільних мов
- •4.11. Операції над формальними мовами
- •4.12. Дерева виводу
- •4.13. Однозначні та неоднозначні граматики
- •4.14. Розв’язні та нерозв’язні проблеми кв-граматик та мов
- •4.15. Рівняння в алгебрах формальних мов
- •5. Теорія рекурсії (теорія найменшої нерухомої точки)
- •5.1. Рекурсивні визначення та рекурсивні рівняння
- •5.2. Частково впорядковані множини, границі ланцюгів та -області
- •5.3. Неперервні відображення
- •5.4. Теореми про нерухомі точки
- •5.5. Конструювання похідних -областей
- •5.6 Властивості оператора найменшої нерухомої точки
- •5.7. Застосування теорії ннт
- •5.7.1. Уточнення синтаксису мов програмування
- •5.7.2. Семантика мов програмування
- •5.7.3. Рекурсивні розширення мови sipl
4.8. Методи подання синтаксису мов програмування
Граматики типу 2 (контекстно-вільні граматики) відіграють велику роль у формалізації мов програмування. Справа в тому, що вони задають чітке подання деякого синтаксичного поняття як структури, що складається з певних частин. Ті частини, у свою чергу, мають частини і так далі. Тобто контекстно-вільні граматики подають ієрархічну організацію синтаксичного поняття. Це відповідає і композиційній структурі програм. Саме тому вивченню цього класу граматик буде приділено більшу увагу. Щоб продемонструвати зв’язок з мовами програмування більш чітко, розглянемо методи подання синтаксису мов програмування. Найбільш відомим методом є нормальні форми Бекуса–Наура (БНФ). Цей формалізм (метамова) широко використовується як під час подання синтаксису мов програмування, так і під час вивченні природних мов.
4.8.1. Нормальні форми Бекуса–Наура
Ці форми були запропоновані Дж. Бекусом та П. Науром для опису синтаксису мови програмування АЛГОЛ-60. Основним призначенням форм Бекуса та Наура було подання у компактному вигляді строго формальних правил написання основних конструкцій мов програмування.
Приблизно в той самий час Ноам Хомський (1959) ввів аналогічну форму – контекстно-вільну граматику – для визначення синтаксису природної мови.
БНФ складається зі скінченної множини правил, які визначають формальну мову (зокрема, синтаксис мов програмування).
Одним із класів об’єктів, що використовуються в БНФ, є символи описуваної мови. Другим класом об’єктів БНФ виступають мета змінні (нетермінальні символи), значеннями яких є ланцюжки основних символів. Для опису синтаксису мов програмування використовують велику кількість нетермінальних символів, тому для наочності їх подають як комбінації слів природної мови, що поміщені в кутові дужки. Ліву частину правил відділяють від правої частини знаком ::=, крім того, правила з однаковою лівою частиною записуються як одне правило, при цьому праві частини (альтернативи) розділяються вертикальною рискою |.
Приклад 4.16. Синтаксис операторів мови SIPL задається наступною БНФ:
<оператор> ::=
|
<змінна>:=<вираз> | <оператор> ; <оператор>| if <умова> then <оператор> else <оператор> | while <умова> do <оператор> | begin <оператор> end | skip |
За кожною БНФ легко побудувати контекстно-вільну граматику, співставляючи правилу БНФ виду A::=1 | 2 | … n сукупність правил граматики A→1, A→2, … A→n.
4.8.2. Модифіковані нормальні форми Бекуса–Наура
Для отримання більш наочних та компактних описів синтаксису застосовують модифіковані БНФ. Найчастіше передбачається введення спеціальних позначень для ітерації та альтернативи.
Наприклад, список якихось елементів задається БНФ
<список>::=<елемент><список>|
У модифікованій БНФ можна записати
<список>::={<елемент>}*
Така форма передбачає введення операції, яка називається ітерацією і позначається парою фігурних дужок із зірочкою.
Якщо певна частина синтаксичної конструкції може бути пропущена, то в модифікованих БНФ її виділяють квадратними дужками. Наприклад, замість правила БНФ
<оператор> ::=
if <умова> then <оператор> else <оператор> | if <умова> then <оператор>
можна вжити наступне правило модифікованої БНФ:
<оператор> ::= if <умова> then <оператор> [ else <оператор>].
Зрозуміло, що для модифікованих БНФ вживати дужки « { », « } », « [ » та « ] », а також « * » у якості символів мови не слід, тому що вони виступають як метасимволи формалізму модифікованих БНФ. За необхідності вживання цих дужок і зірочки для них використовують спеціальні позначення.