Програми і мови

Поняття програми тісно пов'язане з поняттям мови. Дескрипції можуть трактуватися як речення мови, функції – як значення речень. Тому способи подання програм можуть розглядатися як певні мови, які називають мовами програмування. Для дослідження таких

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

програмування≫, ми фактично будемо більше говорити про мови програм, ніж про процеси програмування.

10. Синтактика: формальні мови та граматики.

Мови програмування є штучними мовами, спеціально створеними для запису програм. На відміну від природних мов, які є багатоаспектними, неоднозначними, відкритими, відносно швидко змінюються, штучні мови значно бідніші, від них вимагають фіксованості смислу та однозначності.

Синтаксичний аспект є одним з основних аспектів програм. За визначенням, він пов’язаний з формами подання програм в абстракції від інших їх аспектів.

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

Наведені твердження сформулюємо як принцип абстрагування та єдності синтаксичного аспекту з іншими аспектами програм.

Уточнення синтаксичного аспекту штучних мов здійснюється на основі поняття формальної мови. Як уже говорилось, це абстрактне поняття, що відображає перші (синтаксичні) характеристики мови. Тому термін «формальний» тлумачиться не тільки як «точно заданий», але і як «абстрактний».

Хоча синтаксичний аспект пов'язаний з багатьма аспектами програм, найтісніший зв'язок є з семантичним аспектом. Зупинимось на цьому зв’язку детальніше. Синтаксичний та семантичний аспекти є подальшою конкретизацією категорій форми та змісту. Тому вивчаючи синтаксис (теорію формальних мов), ми все ж не повинні забувати, що він є похідним від семантичного аспекту, і саме ця обставина і визначає методи експлікації (уточнення) та напрями дослідження синтаксису. Щоб обгрутувати вторинність синтаксичного аспекту, треба розглянути зовнішні аспекти програм, і в першу чергу аспект адекватності програми проблемі. Зрозуміло, що в проблемі нас цікавить не стільки її форма, як її зміст. Це фактично означає, що семантика буде провідним аспектом, а синтаксис – похідним від семантики.

11. Визначення основних понять формальних мов. Операції над формальними мовами.

Визначення 4.1 Алфавітом називають скінчену непорожню множину символів (літер). Позначатимемо алфавіт знаком Σ. Приклад 4.1 Найчастіше використовуються наступні алфавіти: 1. Σ = {0, 1} – бінарний чи двійковий алфавіт; 2. Σ = {a, b … z} – множина літер англійського алфавіту. Визначення 4.2 Ланцюжком, чи інколи словом, реченням, рядком, в алфавіті Σ називають скінченну послідовність символів з Σ. Приклад 4.2 Послідовність 01101 – це ланцюжок в бінарному алфавіті Σ = {0, 1}. Ланцюжок 111 також є ланцюжком в цьому алфавіті. Визначення 4.3 Порожній ланцюжок – це ланцюжок, який не містить жодного символу. Цей ланцюжок позначається ε. Його можна розглядати як ланцюжок у довільному алфавіті. Визначення 4.4 Довжина слова (послідовності) w позначається |w|; якщо Σ ′ ⊆ Σ, то довжина послідовності, утвореної з w видаленням тих символів, що не належать Σ ′, позначається |w|Σ ′;

якщо a ∈ Σ, то |w|a означає |w|{a} і задає кількість входжень символу a в w.

Приклад 4.3 Для ланцюжка abcbacaacccb маємо: |abcbacaacccb| = 12, |abcbacaacccb|{a, c}= 9, |abcbacaacccb|c=5. Визначення 4.5 Якщо w та u – ланцюжки в алфавіті Σ, то ланцюжок wu (результат дописування слова u в кінець слова w) називається конкатенацією (катенацією, зчепленням) слів w та u. Іноді конкатенацію слів позначають w⋅ u. Визначення 4.6 Якщо w – ланцюжок в алфавіті Σ, то ланцюжок 14243 n раз w⋅ w⋅... ⋅ w називається n-ю степенню w і позначається w n. За визначенням, w 0=ε. Приклад 4.4 a3=aaa, a2b3c=aabbbc, (abcbacaacccb)2= abcbacaacccbabcbacaacccb. Визначення 4.7 Множина всіх ланцюжків в алфавіті Σ позначається Σ * і називається вільною напівгрупою, породженою Σ. Множина всіх непорожніх ланцюжків позначається Σ +. Термін ≪ вільна напівгрупа≫ веде своє походження з алгебри.

Напівгрупою називається множина з асоціативною бінарною операцією. Якщо така множина має одиничний елемент, то її називають моноїдом. Напівгрупа вільна, якщо ніяких інших співвідношень (крім асоціативності) немає. В теорії формальних мов часто вважають, що напівгрупа має одиничний елемент. Множину Σ * можна розглядати як вільну напівгрупу з одиницею. Конкатенація є асоціативною операцією, а порожній ланцюжок ε є одиницію, тому що для довільного ланцюжка w маємо w⋅ ε = ε ⋅ w= w. Такий розгляд множини ланцюжків Σ * дозволяє перейти до більш багатої структури напівгрупи та використати алгебраїчні властивості для дослідження цієї множини. Іншою обставиною є те, що подаючи множину послідовностей у вигляді напігрупи, ми ототожнюємо символ з послідовністю довжини 1, що складається з цього символу. Тому замість двохосновної моделі (алфавіт та множина послідовностей), основа – множина ланцюжків. Це спрощує дослідження. Визначення 4.8 Ланцюжок t є підланцюжком ланцюжка w, якщо w=utv для деяких ланцюжків u та v. Нарешті, введемо поняття формальної мови. Визначення 4.9 Якщо L ⊆ Σ *, то L називається формальною мовою (або просто мовою) над алфавітом Σ (в алфавіті Σ). Приклад 4.6 Множина ланцюжків {anbncn | n≥ 0} = {ε, abc, a2b2c2, a3b3c3, …} є формальною мовою над алфавітом {a, b, c}. Зауважимо, якщо L є мовою над Σ, то можна стверджувати, що L – це мова над будь-яким алфавітом Σ ′, що містить Σ. Іншими словами, є певна консервативність поняття мови до розширення алфавіту. Крім того, є монотонність множини мов відносно розширення алфавіту, бо це веде до збільшення множини мов. Операції над формальними мовами Операції над формальними мовами розподіляються на два класи. Перший клас операцій відповідає над-абстрактній моделі мов, в якій вони мають інтенсіонал множини. Тому всі теоретико- множинні операції можна застосовувати для мов. В першу чергу, це операції об’єднання ∪, перетину ∪ та різниці \. Вважаємо, що мови – аргументи цих операцій – задані над одним і тим самим алфавітом. Якщо це не так, то будуємо новий алфавіт, який є об’єднанням алфавітів мов-аргументів. Тоді всі мови-аргументи будуть мовами

над одним алфавітом. Якщо мова L є мовою в алфавіті Σ, то мова Σ *–L називається доповненням мови L відносно алфавіту Σ. Коли з контексту ясно, про який алфавіт йде мова, говорять просто, що мова Σ *–L є доповненням мови L і позначається L. Приклад 4.7 Нехай L1={anbncm| n, m ≥ 0}, L2={anbmcm| n, m ≥ 0}. Тоді L1∩ L2={ anbncn| n≥ 0}, L1\L2={ anbncm| m≠ n, n, m ≥ 0}. Другий клас операцій над формальними мовами відповідає абстрактній моделі мов, коли їх елементи тлумачаться як послідовності символів. Серед цих операцій в першу чергу відзначимо операцію добутку (конкатенації) мов, яка є похідною від операції конкатенації ланцюжків. Для позначення цієї операції використовуємо той самий символ операції конкатенації.__

12. Породжуючі граматики. Ієрархія граматик Хомського

Як відзначалось на початку розділу, породжуючі граматики можуть розглядатися як конкретизації транзиційних систем або дедуктивних систем. Для таких систем головним є відношення переходів. В граматиках відношення переходу (виведення) задається за допомогою правил граматики (продукцій), які мають вигляд α → β, де α та β – ланцюжки в певному алфавіті Σ. Таке правило дозволяє перетворити ланцюжок γ 1 в ланцюжок γ 2 (γ 1, γ 2 ∈ Σ *) тоді і тільки тоді, коли γ 1 = δ 1 α δ 2, γ 2 = δ 1 β δ 2 для деяких ланцюжків δ 1 і δ 2, що належать Σ *. Змістовно, це правило дозволяє замінити підланцюжок γ 1, який співпадає з лівою частиною правила, на праву його частину, отримуючи ланцюжок γ 2. Нехай P – множина продукцій. Тоді кожна продукція з P може розглядатися як правило виводу на Σ *. Сама послідовність правил, використаних в процесі породження деякого ланцюжка, є його виводом. Визначена таким способом граматика представляє собою формальну систему. ідомими прикладами формальних систем слугують логічні числення (числення висловлювань, числення предикатів), які детально вивчаються у відповідних розділах математичної логіки. Низку формальних систем для програм буде наведено в цьому посібнику. Наведені міркування приводять до наступного визначення. Визначення 4.14 Породжуючою граматикою (граматикою типу 0) називається четвірка G =(N, T, P, S), де N і T – скінчені алфавіти, N ∩ T =O, P ⊂ (N U T) * N (N U T) *Ч(N U T)*, P скінчена і S ∈ N. Тут • N – нетермінальний алфавіт (допоміжний алфавіт), його елементи називаються нетермінальними символами, нетерміналами, змінними, • T – термінальний алфавіт (основний алфавіт), його елементи називаються термінальними символами або терміналами, • S - початковий символ (аксіома). • P – множина продукцій. Продукцію (α, β)∈ P інколи називають правилом підстановки, правилом виводу, або просто правилом і записують у вигляді α → β. Ієрархія граматик Хомського Дослідження будь-якого класу предметів, як правило, починається з їх класифікації. Це методологічне зауваження стосується і граматик. Однією з перших була ласифікація, запропонована Н. Хомським. Суть цієї класифікації полягає в поступових обмеженнях, що накладаються на праві та ліві частини продукцій. Визначені Хомським чотири типи граматик виявились інваріантними відносно різних уточнень породжуючих граматик. Крім того, цим типам граматик природнім чином відповідають типи автоматів, що розпізнають (сприймають) формальні мови.

13. Дані. Функції. Композиції. Програмні алгебри. Визначення семантичних термів. Побудова семантичного терму програми

1.3. 1 Дані.

Базові типи даних – множини цілих чисел, бульових значень та змінних (імен):

• Int={..., -2, -1, 0, 1, 2,... }

• Bool={true, false}

• Var={M, N, … }

Похідні типи – множина станів змінних (наборів іменованих значень, наборів змінних з їх значеннями):

• State=Var → Int

Операції на множині Int. Символам +, –, ∗ відповідають операції add, sub, mult (додавання, віднімання, множення). Це бінарні операції типу Int2 → Int.

Операції на множині Bool. Символам ∨, відповідають операції or, neg. Це бінарна операція типу Bool2 → Bool (диз’юнкція) та унарна операція типу Bool → Bool (заперечення).

В мові також є операції змішаного типу. Символам операцій порівняння =, > відповідають операції eq, gr. Це бінарні операції типу Int2 → Bool.

Крім того, введемо

• параметричну функцію-константу арифметичного типу n: State→ Int, таку що n (st)=n (n∈ Int),

• тотожну функцію id: State→ State, таку, що id(st)=st.

Отримали багатоосновну алгебру даних мови SIPL A_Int_Bool_State =< Int, Bool, State;

add, sub, mult, or, neg, eq, gr, ⇒ x, x⇒, n, id, ∇ >,