Зубенко, Омельчук - Програмування. Поглиблений курс

Розділ ІІ. ЕЛЕМЕНТИ ІНФОРМАТИКИ

19.Знайти обернений і додатковий двобайтний двійковий код від'ємних чисел: а) –25; б) –102; в) -1334; г) -34000.

20.У системі з основою p =36 цифрами є 0, 1,…,9 і великі ла- тинські літери A, B,…., Z. Знайти десяткове значення чисел

а) 10 p ; б) ZZZZ p ; в) ABC001 p .

21.Знайти двійкові подання десяткових дробів (перші 12

цифр): а) 0.9999; б) 0.12; в) 3.14.

22.Скласти за допомогою калькулятора таблицю множення

15×15 для шістнадцяткових чисел. За допомогою цієї таб- лиці знайти добутки 25×125 та АААА×F1.

23.Що таке переповнення? Навести приклади.

24.Що таке зникнення порядку? Навести приклади.

25.Розв'язати систему лінійних рівнянь у машинній арифме- тиці із чотирма цифрами в мантисі; те саме – за допомогою калькулятора. Результати порівняти:

26.Що таке кодова таблиця символів?

27.Що таке ASCII-таблиця та її національні варіанти?

28.Яка структура НМ?

29.Яка загальна структура машинної команди НМ?

30.Пояснити дію арифметичних команд НМ. Навести приклади.

31.Пояснити дію команд порівняння. Навести приклади.

32.Пояснити дію команд збереження регістрів. Навести при- клади.

33.Пояснити дію команд завантаження регістрів. Навести приклади.

34.Пояснити дію команд пересилання адрес. Навести приклади.

35.Пояснити дію команд керування пристроями введення- виведення. Навести відповідні приклади.

36.У чому полягає смисл команд перетворення?

37.Пояснити дію команд перетворення. Навести приклади.

38.У чому полягає смисл команд переходу?

39.Пояснити дію команд переходу. Навести приклади.

40.Обчислити й вивести значення a3 , де а зберігається в ко- мірці з адресою 1000. У випадку переповнення вивести '*'. Вказівка. Скористатися СБС, яка подає схему розв'язку за-

дачі для значення a2 :.

181

ПРОГРАМУВАННЯ

Заповнення вихідного поля пробілами

_

(Х) →(2003), (2004)

LIT

OUT

HLT

41.Написати вірусну програму з кількістю команд менше п'яти.

42.Відстань Хаммінга між бітовими векторами визначається кількістю позицій, в яких вони відрізняються. Знайти цю відстань: a) між регістрами $A $X; б) між довільними поля- ми, адреси яких містяться в регістрах $R2 та $R3.

43.Реалізувати операцію MUL за допомогою алгоритму швид- кого множення за допомогою команди ADD.

44.Реалізувати операції DIV і взяття залишку MOD за допомо- гою команди SUB.

45.Реалізувати операцію POW швидкого піднесення до степеня за допомогою команди MUL.

182

Розділ ІІ. ЕЛЕМЕНТИ ІНФОРМАТИКИ

2.4. Мови програмування

¾Дескриптивні системи

¾Мови програмування

¾Класифiкацiя мов програмування

Ключові слова: дескриптивна система, синтаксис, семантика та прагматика ДС, символ, ідеограма, вербальна мова, лексема, словник мови, речення, метамова, денотат, термін, предметна константа, дескриптивний термін, кодова таблиця, кодові таблиці ASCII, Unicode, UCS-2 та UCS-4, широка літера, денотаційна й операційна семантика, базові, стандартні й функціональні типи,

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

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

2.4.1. ДЕСКРИПТИВНІ СИСТЕМИ

Ми розглядатимемо ДС лише у зв'язку з описом інформаційних систем. Дескриптивні системи – це різновид знакових систем, призначених для опису елементів інформаційних систем і роботи з ними. Кожна ДС визначає певну фіксовану сукупність об'єктів, які мають своє ім'я, значення та смисл. Іменами є знаки – матеріальні елементи, що сприймаються на чуттєвому або фізичному рівні й зображують у комунікативних процесах значення й певні властивості та відношення між інформаційними об'єктами.

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

183

ПРОГРАМУВАННЯ

Семіотика20 виділяє як визначальні три складові знакових систем: синтаксис (описує будову знаків), семантику (описує значення об'єктів і самі об'єкти) і прагматику (описує смисл об'єктів). Розглянемо ці складові окремо.

Синтаксис. Кожна ДС використовує певну фіксовану сукупність знаків. У семіотиці виділяють кілька різновидів знаків, серед яких особлива роль належить знакам-символам, які фізично не пов'язані зі своїми значеннями. Значення та смисл символів установлюються за узгодженням.

Ми вже мали справу зі знаками-символами, коли розглядали конс- танти, змінні й терми у ПЧП. Знакові системи зі знаками-символами називаються символьними. Прикладами символьних систем є системи сигналів і знаків дорожнього руху, абетка Морзе, нотна грамота, еле- ктричні схеми, природні мови, мова жестів глухонімих тощо. Дескри- птологічні знакові системи теж належать до символьних.

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

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

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

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

ними (від лат. verbalis – cловесний).

Кожна словесна ДС має свій фіксований алфавіт літер Σ = {a1 ,...,an }, який є обов'язково лінійно впорядкованим. Серед усіх

20 Наука про знакові системи.

184

Розділ ІІ. ЕЛЕМЕНТИ ІНФОРМАТИКИ

слів над алфавітом Σ зазвичай тільки частина є правильними й вико- ристовуються як символи. Решта – беззмістовні. Усі слова мови поді- ляються на слова-лексеми й слова-речення. Лексеми об'єднуються в речення за допомогою спеціальних літер-роздільників – деякі з них позначають кінець речення. Самі роздільники теж можуть належати до лексем (символи операцій +, - тощо). Таким чином, лексема речен- ня – це або префікс, що передує першому в ньому роздільнику, або суфікс, розташований між роздільниками, який не містить усередині інших роздільників. Кожна мова має свій набір літер-роздільників (пробіл, кома, крапка, тире, дужки тощо) і лексем (словник мови). За допомогою спеціальних синтаксичних правил із лексем будуються правильні речення мови. Речення може трактуватися також як певне слово у збільшеному алфавіті – алфавіті лексем, тобто це слово, побу- доване зі знаків вищого рівня. Саме така ситуація має місце в мовах програмування – транслятор працює вже на рівні лексем.

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

Приклад 2.20. Зробимо лексичний аналіз речення:

Маша їла кашу, а м'яч поцілив у ворота.

Лексемами в ньому є слова: <Маша>, <їла>, <кашу>, <а>, <м'яч>, <поцілив>, <у>, <ворота>. Роздільниками є пробіл (7 входжень), кома (1 входження) і крапка (1 входження) ■

Семантика. Семантичні правила надають деяким символьним іменам їхні значення (денотати). Імена зі значеннями називаються термінами. Таким чином, термін – це символ, з яким пов'язане конк- ретне значення або сукупність значень.

Серед термінів виділяють:

а) терми – терміни, що подають реальний чи абстрактний об'єкт (з математичними термами ми вже зустрічалися в підрозд. 1.1.1);

б) предикатні вирази – терміни, що позначають (виділяють) об'єкти серед інших об'єктів за допомогою їхніх особливих властивостей;

в) предметно-функціональні вирази – терміни, що позначають дії,

процеси, функції, операції тощо.

У прикл. 2.20 термами є іменники <Маша>, <кашу>, <м'яч> та <во- рота>, прикметник <футбольний> – предикатний вираз, а дієслова <їла> та <поцілив> – предметно-функціональні вирази.

Сам процес іменування може здійснюватись у два способи: 1) шляхом прямого зіставлення й закріплення за іменем його постій- ного конкретного денотата; 2) опосередковано – шляхом опису дено-

185

ПРОГРАМУВАННЯ

тата як носія певних ознак і властивостей у вигляді дескрипцій. Тер- міни, що отримали значення в перший спосіб, називаються предмет- ними константами. Це назви конкретних предметів, явищ, дій тощо. Решта термінів називаються дескриптивними.21 В описі їхніх значень обов'язково беруть участь інші терміни, наприклад: "2 +7" ("2" та "7" – предметні константи, " + " – символ операції), "перша ЕОМ у контине-

нтальній Європі", "число, яке задовольняє рівняння x2 − 2x + 2 = 0 ", "студент факультету кібернетики". Остання дескрипція вказує не на конкретну особу, а на сукупність осіб, які є студентами факультету кібернетики, а передостання показує, що термін може мати смисл, але сукупність його можливих значень порожня.

Прагматика. Є визначальним елементом ДС, оскільки саме вона формує мету інформаційних процесів. Прагматика задає як загаль- ний смисл об'єктів у співвідношенні з іншими об'єктами, так і їхній смисл у кожному конкретному знаковому процесі. Смисл засвоюється в процесі розуміння й застосування об'єкта, роботи з ним. Він також може брати участь у визначенні значень об'єктів. Першим звернув на це увагу німецький математик Г. Фреге. У сучасній літературі співвід- ношення між іменем, його денотатом і смислом часто зображують у вигляді схеми, що дістала назву "трикутник віднесення":

Смисл

Вершини трикутника зображують три аспекти об'єкта: ім'я, денотат і смисл, взаємовідносини між якими забезпечуються процесом спілку- вання. При цьому смисл є посередником між іменем і денотатом, спосо- бом, яким ім'я позначає денотат. Прямі стрілки вказують на реальні відношення між елементами трикутника, а хвиляста (між іменем і дено- татом) – на те, що це відношення виникло опосередковано завдяки сми- слу, як у наведених вище прикладах: "перша ЕОМ у континентальній

Європі", "число, яке задовольняє рівняння x2 − 2x +1 = 0 " або в описі змінної "int i". Значенням першої дескрипції є ЕОМ МЕСМ. Друга де- скрипція визначає об'єкт, який є розв'язком відповідного квадратного рівняння. Остання дескрипція задає числовий об'єкт з іменем i , зна-

21 Звідси й назва "дескриптивні системи".

186

Розділ ІІ. ЕЛЕМЕНТИ ІНФОРМАТИКИ

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

2.4.2. МОВИ ПРОГРАМУВАННЯ

Розглянемо загальну структуру мов програмування, більшість із яких є вербальними. Ми вже зазначали, що великий вплив на створення мов програмування мало ПЧП. Одне із центральних понять мов про- грамування – вираз (арифметичний, логічний) – визначається у вигляді математичного терму, конструкції, прямо запозиченої у ПЧП23.

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

Для опису конструкцій мов програмування в інформатиці застосо- вується цілий арсенал метазасобів: від природних мов до штучних, таких, як ПЧП, мов специфікації функцій і алгоритмів, структурних блок-схем і схем програм, БНФ, КС-граматик, синтаксичних діаграм, різних класів автоматів тощо.

Синтаксис мов програмування. Як вербальна ДС, кожна мова про-

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

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

ється багато зусиль для стандартизації алфавітів мов програмування. Необхідно узгодити різні не тільки формально, а й за походженням і природою численні алфавіти національних мов. Один із підходів для розв'язання цієї проблеми запропоновано розробниками Універсаль- ного символьного набору багатооктетних кодів (Universal MultipleOctet Code Character Set (UCS-4)) у стандарті ISO/IES 1064. Цього на-

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

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

23Семантика виразів мов програмування дещо відрізняється від математичної. Це пов'язано з динамічним характером процесів іменування даних.

24У літературі інколи невдало, на наш погляд, ототожнюють терміни "символ" і "літера". Літера стає символом, тільки коли їй надається певне значення або смисл.

187

ПРОГРАМУВАННЯ

Існує двобайтний варіант цього набору – UCS-2, що містить усі літери набору UCS-4 (включаючи 20000 ієрогліфів Китаю, Японії та Кореї), у яких два старших байти нульові. Первісно відомий набір символів Unicode, який запровадила організація Unicode Consortium (www.unicode.org), був двобайтним і узгодженим з набором UCS-2. Третя версія цього стандарту – Unicode-3.0 – повністю відповідає стандарту

ISO/IES 1064. Усі стандарти – UCS-4, UCS-2 та Unicode – узгоджені зі стандартом ASCII. Це означає, що 16-бітні коди, старші байти яких до- рівнюють 0, є 9-бітним розширенням відповідних літер набору ASCII.

Літери, коди яких за розміром більші від восьмибітних, називають- ся широкими. У сучасних версіях мов програмування передбачається використання в символьних і літеральних константах та ідентифіка- торах широких літер із наборів UCS-2 і UCS-4.

Як приклад кодової таблиці наведемо верхню частину таблиці кодів Windows-1251, що містить літери українського, російського, білорусько- го й деяких інших національних алфавітів. Числа під літерами подають 16-ковий код символу в коді UCS-2. Нижня частина цієї таблиці (з ко- дами від 0 до 127) відповідає стандартному семибітному коду ASCII.

Кодова таблиця Windows-1251 (верхня частина)

З літер будуються лексеми мови, з яких, у свою чергу, утворюються всі інші синтаксичні конструкції, у тому числі й головні – програми. Лексика мов програмування виділяє п'ять класів лексем: ідентифіка- тори, ключові слова, константи, операції й роздільники. Вони деталь- но розглядаються в підрозд. 3.1.2 на прикладі мови С.

188

Розділ ІІ. ЕЛЕМЕНТИ ІНФОРМАТИКИ

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

Семантика мов програмування. Кожна мова програмування описує певну фіксовану сукупність даних і програм. За принципом функціональності кожній програмі відповідає певний X −Y - оператор, що пов'язує вхідні дані й результати. Цей оператор є дено- татом програми (денотаційна семантика програми). Програма має й операційну семантику – алгоритм (машинну програму), що описує пошук результатів запиту на машинному рівні.

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

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

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

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

тори-описи й оператори-декларації. Оператори опису й декларації на-

189

ПРОГРАМУВАННЯ

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

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

ІЛП = Вирази + Первинні оператори + Композиції

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

Вежа типів = Базові типи + Конструктори + ІЛП

Прагматика мов програмування. Програми створюються для то-

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

2.4.3. КЛАСИФIКАЦIЯ МОВ ПРОГРАМУВАННЯ

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

190