1 Теоретичний питання «семантика і семантичні схеми програм»

Попередня ↔ Наступна

1.1Операціонная семантика 3

1.2Денотаціонная семантика 5

1.3Аксіоматіческая семантика 8

1.4Трансляціонная семантика 9

1.5Виводи щодо методів визначення семантики 10

2 Завдання про п'ять обідають філософів 10

2.1 Постановка завдання 10

2.2 Рішення завдання 11

2.3 Лістинг процедур, які забезпечують вирішення задачі 12

3 Список використаних джерел 15

1 Теоретичний питання «Семантика і семантичні схеми програм» 3

1.1 Операційна семантіка3

1.2 Денотаціонная семантіка5

1.3 Аксіоматична семантіка8

1.4 Трансляційна семантіка9

1.5 Висновки щодо методів визначення семантікі9

2 Завдання про п'ять обідають філософах10

2.1 Постановка задачі10

2.2 Рішення задачі10

2.3 Лістинг процедур, які забезпечують вирішення задачі11

3 Список використаних істочніков15

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

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

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

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

Опис операційної семантики операторів мов програмування високого рівня вимагає створення реального або віртуального комп'ютера. Апаратне забезпечення комп'ютера є чистим інтерпретатором його машинного мови. Чистий інтерпретатор будь-якої мови програмування може бути створений за допомогою програмних засобів, які стають віртуальним комп'ютером для даної мови. Семантику мови високого рівня можна описати, використовуючи чистий інтерпретатор цієї мови. При такому підході, правда, існують дві проблеми. По-перше, складність і індивідуальні особливості апаратного забезпечення комп'ютера і операційної системи, що використовуються для запуску чистого інтерпретатора, ускладнюють розуміння процесів, що відбуваються. По-друге, виконане таким чином семантичне визначення буде доступно тільки для людей з абсолютно ідентичною конфігурацією комп'ютера.

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

Використання операційного методу для повного опису семантики мови програмування Lтребует створення двох компонентів. По-перше, для перетворення язикаLв оператори вибраної мови низького рівня потрібен транслятор. По-друге, для цієї мови низького рівня необхідна віртуальна машина, стан якої змінюється за допомогою команд, отриманих при трансляції операторів високого рівня. Саме зміни стану цієї віртуальної машини визначає зміст даного оператора.

У таблиці 1.1 представлений приклад, в якому семантику конструкції forязика З можна описати в термінах наступних простих команд.

Таблиця 1.1 - Приклад операційної семантики

Оператор мови С

goto label if var relop var goto label

Тут relop - одні з операторів відносин з набору, ident - ідентифікатор, a var - ідентифікатор або константа. Всі ці оператори прості і легкі для розуміння і реалізації.

Першим і найзначнішим використанням формальної операційної семантики було опис семантики мови PL / I. Ця абстрактна машина і правила трансляції мови PL / I були названі загальним ім'ям Vienna Definition Language (VDL) в честь міста, в якому вони були створені корпорацією IBM.

Операційна семантика є ефективною до тих пір, поки опис мови залишається простим і неформальним. На жаль, опис VDL мови PL / I настільки складно, що практичним цілям воно практично не служить.

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

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

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

Для введення в денотаціонний метод ми використовуємо дуже просту мовну конструкцію - двійкові числа. Синтаксис цих чисел можна описати наступними граматичними правилами:

<двоичное_число> → 0 | 1; | <двоичное_число> 0; | <двоичное_число> 1.

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

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

Нехай область визначення семантичних значень об'єктів являє собою множину невід'ємних десяткових цілих чисел Nat. Це саме ті об'єкти, які ми хочемо зв'язати з двійковими числами. Семантична функція Мb відображає синтаксичні об'єкти в об'єкти безлічі N відповідно до зазначених вище правилам. Сама функція Мb визначається наступним чином:

Мb ( '0') = 0, Мb ( '1') = 1; Мb (<двоичное_число> '0') = 2 × Мb (<двоичное_число>); Мb (<двоичное_число> '1') = + 2 × Мb (<двоичное_число>) + 1.

Опис значення десяткових синтаксичних літеральних констант. <десятичное_число> → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9; | <десятичное_число> (0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9).

Денотаціонние відображення для цих синтаксичних правил мають такий вигляд:

Md ( "0") = 0, Md ( '1') = 1. Md ( '9') = 9; Мd (<десятичное_число> '0') = 10 × Мd (<двоичное_число>); Мd (<десятичное_число> '1') = 10 × Мd (<десятичное_число>) + 1; ... Мd (<десятичное_число> '9') = 10 × Мd (<десятичное_число>) + 9.

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

Денотаціонную семантику програми можна визначити в термінах змін станів ідеального комп'ютера. Подібним чином визначалися операційні ceмантікі, приблизно так само визначаються і денотаціонние. Правда, для простоти вони визначаються тільки в термінах значень всіх змінних, оголошених в програмі. Операційна і денотаціонная семантики розрізняються тим, що зміни станів в операційній семантиці визначаються запрограмованими алгоритмами, а в денотаціонной семантиці вони визначаються строгими математичними функціями. Нехай стан s програми визначається наступним набором упорядкованих пар:

Кожен параметр i є ім'ям змінної, а відповідні параметри v є поточними значеннями даних змінних. Будь-який з параметрів v може мати спеціальне значення undef, яке вказує, що пов'язана з ним величина в даний момент не визначена.

Нехай VARMAP - функція двох параметрів, імені змінної і стану програми. Значення функції VARMAP (ik, s) дорівнює vk (значення, відповідне параметру ik в стані s).

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

Вирази є основою більшості мов програмування. Більш того, ми маємо справу лише з дуже простими виразами. Єдиними операторами є оператори + і ×; вираження можуть містити не більше одного оператора; єдиними операндами є скалярні змінні і цілочисельні літеральние константи; круглі дужки не використовуються; значення виразу є цілим числом. Нижче йде опис цих виразів: <выражение> → <десятичное_число> | <переменная> | <двоичное_выражение> <двоичное_выражение> → <выражение_слева> <оператор> <выражение_справа> <оператор> → + | ×

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

З одного боку, денотаціонние опису дуже складні, з іншого - вони дають чудовий метод короткого опису мови. [1, С.188-191]

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

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

Ось визначення, яке дає тлумачний словник: аксіоматична семантика - семантика мов програмування, в якій значення мовної конструкції або програми на деякій мові програмування визначається "аксіомою". Для кожного конкретного висловлювання аксіома вказує, що має бути істинним після його реалізації в контексті того, що було істинним до реалізації висловлювання. Аксіоматична семантика грає важливу роль в доведенні коректності програм.

На відміну від операційної семантики дедуктивна семантика відмовляється від того, щоб пов'язувати зміст конструкцій мов програмування з будь-яким способом проведення обчислень. Таким чином, вона абстрагується від ряду деталей обчислень, несуттєвих для розуміння сенсу програми, і дає можливість говорити про абстрактні властивості програм. Проте, дедуктивна семантика в основному орієнтована на імперативне програмування. [2]

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

У загальному випадку трансляційний підхід може використовуватися і для мов високого рівня. Як мова, на який здійснюється переказ, може бути обраний певний математичний мову (наприклад, мова -ісчісленія), деякий іншу мову програмування (наприклад, мова Алмо для мов опису алгоритмів або мову Паскаль для мови Сетл) або конкретний машинний мову. Таким чином, транслятор для мови високого рівня на конкретний машинний мова стає семантичним визначенням мови. [3]

Висновки щодо методів визначення семантики

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

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