Побудова семантичного терму програми

Програма мови SIPL може бути перетворена в семантичний терм (терм програмної алгебри), який задає семантику цієї програми (семантичну функцію програми), перетвореннями такого типу:

• sem_P: Prog → FS

• sem_S: Stm → FS

• sem_A: Aexp → FA

•sem_B: Bexp→ FB

Теорема 1.1. Для довільної програми мови SIPL її семантична функція задається термом алгебри A_SIPL.

14. Синтактика: формальні мови та граматики. Розвиток понять формальної мови та породжучої граматики

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

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

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

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

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

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

15. Принцип відокремлення, підпорядкування та єдності синтаксичного та семантичного аспектів. Принцип теоретико-множинного тлумачення формальної мови. Принцип тлумачення речень мови як послідовностей

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

Неважко зрозуміти, що елементи формальних мов – речення – слід розглядати як «білі скриньки», тобто їх можна розпізнавати та відрізняти одне від одного.

Обгрунтування вибору такого тлумачення надає принцип відокремлення, підпорядкованості та єдності, який стверджує вторинність синтаксису від семантики, зокрема і те, що синтаксис речення повинен допомогти у встановленні його семантики. А це можливо лише тоді, коли синтаксис є видимим, зрозумілим, прозорим («білим»). Звідси випливає, що мова є множиною (а не абстрактною сукупністю) певних елементів (речень, слів). Саме елементи множини тлумачаться як «білі скриньки». Отже мова розглядається на конкретноструктурованому рівні, який позначимо L.S (Language is a Set).

Принцип теоретико-множинного тлумачення формальної мови: на найвищому рівні абстракції синтаксичний аспект програм подається у вигляді формальної мови, яка тлумачиться як множини речень.

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

Отже, перша надабстрактна модель мови – це деяка множина L={si | i∈ I}. На цьому рівні абстракції нічого, крім теоретикомножинних понять немає, тому немає і власне теорії мов (а є теорія множин). Треба переходити на інший рівень абстракції, який має хоч би деякі специфічні характеристики мов. Цей перехід, як відомо з діалектичної логіки, є перехід від цілого до частин. Тут головне – виділити структуру, що пов’язує ціле з частинами. Щоб це зробити, треба конкретизувати структуру речень.

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

Абстрагуючись від лінгвістичних конотацій та асоціацій будемо для таких послідовностей вживати терміни «ланцюжок», «слово» або «речення». Відзначимо, що в комп’ютерній термінології часто вживається термін «слово» (word), в лінгвистичній – «речення» (sentence).

Принцип тлумачення речень мови як послідовностей: на наступному рівні абстракції речення розглядаються як послідовності літер певного алафавіту.

Друга, абстрактна модель формальної мови – це деяка підмножина L ⊆ A*, де A* – скінченні послідовності літер з алфавіту A. Це фактично є певним абстрактним поняттям формальної мови.

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

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

16. Принцип розгляду механізму породження мови як транзиційної системи. Принцип подання породжуючих систем породжуючими граматиками

Принцип розгляду механізму породження мови як транзиційної системи: надабстрактну модель породжуючої системи тлумачимо як транзиційну систему TS = (St, I, F, tr) з визначеними раніше параметрами (St, I, F, tr) та яка визначає множину породжуваних елементів мови наступною формулою L(TS) = { c | (a, c)∈ tr*, a∈ I, c∈ F}.

Зауважимо, що транзиційні системи можна використовувати і як моделі сприйняття. В цьому випадку можна застосувати формулу L(TS) = { a | (a, c)∈ tr*, a∈ I, c∈ F}.

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

Транзиційні системи є моделями абстрактних динамічних систем, але суто мовні характеристики в них відсутні. Дійсно, як видно з наведеного визначення, ця надабстрактна модель (транзиційна система) має той же рівень тлумачення елементів мови як і надабстрактна модель формальної мови. Треба тепер конкретизувати цю модель, щоб перейти до тлумачення мови як множини ланцюжків, тобто перейти на рівень абстрактної моделі мови. Будемо вважати, що система має породити мову L ⊆ A*.

Принцип подання породжуючих систем породжуючими граматиками: Абстрактну модель породжуючієї системи тлумачимо як породжуючу граматику G=(N, T, P, S) з наведеними вище параметрами, що є конкретизацією транзиційної системи TS = (St, I, F, tr) та визначає формальну мову L(G) вказаним вище чином.

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

17. Визначення основних понять формальних мов. Визначення 1-9

Визначення 4.1 Алфавітом називають скінчену непорожню множину символів (літер). Позначатимемо алфавіт знаком Σ.

Визначення 4.2 Ланцюжком, чи інколи словом, реченням, рядком, в алфавіті Σ називають скінченну послідовність символів з Σ.

Визначення 4.3 Порожній ланцюжок – це ланцюжок, який не містить жодного символу. Цей ланцюжок позначається ε. Його можна розглядати як ланцюжок у довільному алфавіті.

Визначення 4.4 Довжина слова (послідовності) w позначається |w|; якщо Σ ′ ⊆ Σ, то довжина послідовності, утвореної з w видаленням тих символів, що не належать Σ ′, позначається ; якщо a ∈ Σ, то означає |w|{a} і задає кількість входжень символу a в w.

Визначення 4.5 Якщо w та u – ланцюжки в алфавіті Σ, то ланцюжок wu (результат дописування слова u в кінець слова w) називається конкатенацією (катенацією, зчепленням) слів w та u. Іноді конкатенацію слів позначають w⋅ u.

Визначення 4.6 Якщо w – ланцюжок в алфавіті Σ, то ланцюжок називається n-ю степенню w і позначається .

За визначенням, .

18. Операції над формальними мовами. Визначення 10-13

19. Породжуючі граматики. Визначення 14-17

20.

21. Ієрархія граматик Хомського. Визначення 20-21