Паскаль. Прикладне програмне забезпечення


Мова та метамова

1. Мова: вирази та їх семантика

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

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

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

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

Правила, за якими виразам мови зіставляється зміст, утворюють Семантичну Систему мови. Розуміти мову – значить уміти зіставити виразу його зміст. Можна сказати, що комп'ютер розуміє мову Паскаль за допомогою перекладача – програмитранслятора утім, translator і є англійське перекладач.

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

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

2. Метамова БНФ

У кожній мові є своя Система Понять. Наприклад, будьякий конкретний оператор є представником загального поняття оператор, будьяке ім'я – представником поняття ім'я тощо. Представники понять, тобто конкретні оператори або імена – це вирази деякої структури синтаксису. Наприклад, усі імена – це послідовності букв і цифр, що починаються з букви, цілі сталі – послідовності цифр, а кожний оператор присвоювання складається з імені, знака:= і виразу. Остання фраза по суті містить три правила: вони описують синтаксис представників понять ім'я, стала, оператор присвоювання і називаються Синтаксичними.

Дамо синтаксичним правилам чіткішу форму. Позначимо поняття словами в кутових дужках. Це позначення розглядається як неподільне і називається Нетермінальним Символом, або Нетерміналом, наприклад, оператор або ім'я. Символи й лексеми мови будемо брати в 'апострофи' або виділяти Жирним шрифтом, наприклад, Program або ':='. Вони також розглядаються як неподільні і називаються Термінальними Символами, або Терміналами.

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

Послідовність, складена з терміналів і нетерміналів, називається Метавиразом, наприклад, ім'я ':=' вираз. Елементи метавиразу, тобто нермінальні й нетермінальні символи, для наочності іноді будемо відокремлювати пропусками. Порожню послідовність позначимо кутовими дужками.

Перепишемо фразу оператор присвоювання складається з імені, знака:= і виразу із новими позначеннями так:

оператор присвоювання Має Структуру ім'я ':=' вираз.

Замість слів Має структуру поставимо знак::= і одержимо щось схоже на формулу:

оператор присвоювання::= ім'я ':=' вираз.

Взагалі, усяку фразу вигляду

поняття Має структуру метавираз

Можна переписати в такому вигляді:

поняття::= метавираз.

Синтаксичні правила, записані у вигляді поняття::= метавираз, називаються Формами БекусаНаура, за прізвищами тих, хто їх придумав. Форми БекусаНаура скорочено називаються БНФ. Поняття, записане в БНФ ліворуч від::=, називається її Лівою Частиною, а метавираз праворуч – Правою. Знак::= не є символом мови й називається Метасимволом.

Сама по собі БНФ

оператор присвоювання::= ім'я ':=' вираз

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

ім'я::=буквапослідовність букв і цифр.

На цьому поки що зупинимося. Очевидно, для описання синтаксису останніх двох понять потрібні будуть свої БНФ, можливо, з новими поняттями. У всякому разі, зараз ми припустимо, що

Синтаксис виразів мови задається деякою сукупністю БНФ, або синтаксичних правил.

А тепер почнемо уточнювати, яким саме чином сукупність БНФ задає синтаксис виразів мови.

Приклад 1. Розглянемо мову, виразами в якій є речення, що складаються з підмета й присудка. Підмет, крім того, може мати означення а може і не мати. Цим означенням може бути одне зі слів – Злющий або Великий, підметом – Комар або Слон, присудком – Дзижчить або Тупотить. Побудуємо сукупність БНФ, що задають синтаксис речень.

Спочатку введемо додаткові позначення. Якщо структура представників якогось поняття задається кількома БНФ, то об'єднаємо їх, записавши альтернативні праві частини в однім правилі й відокремивши символом |. Цей символ позначає слово або; він також є метасимволом.

З цими позначеннями очевидні такі БНФ:

означення::= Великий | Злющий

підмет::= Комар | Слон

присудок::= Дзижчить | Тупотить

Підмет у реченні може бути як із означенням, так і без нього. Введемо поняття група підмета і БНФ

група підмета::= означення підмет | підмет

Тоді структура речення задається такою БНФ:

речення::= група підмета присудок

Серед понять мови виділяється Головне; воно позначається спеціальним Початковим Нетерміналом. Очевидно, що в нашій мові, наприклад, головним поняттям є Речення, а в мові Паскаль – Програма.

Означимо тепер такі поняття, як Послідовність Терміналів, Вивідна З Початкового Нетермінала, і Формальна Мова, задана сукупністю БНФ.

Якщо замінити початковий нетермінал позначимо його S на праву частину правила, у якому S ліворуч, то одержимо послідовність символів терміналів і нетерміналів, що називається Вивідною З S. У прикладі 10.1 такою є

група підмета присудок

Якщо у вивідної з S послідовності замінити якийсь нетермінал на відповідну йому праву частину, то одержимо послідовність, що теж називається вивідною з S, тощо. Наприклад,

означення підметприсудок,

означення підмет Тупотить,

Злющий підмет Тупотить,

Злющий комар тупотить

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

Вивідні з S послідовності, що складаються лише з терміналів, називаються Вивідними Виразами. Саме вони є представниками головного поняття мови. Наприклад, послідовність Злющий комар тупотить є вивідним виразом і представником головного поняття – речення.

Нарешті, Формальна Мова, задана сукупністю БНФ – це множина вивідних виразів.

У прикладі 1 формальна мова утворена всіма можливими реченнями. Зауважимо, що всього їх 12: 8 із означеннями і 4 без них.

Крім поняття виводимості з початкового нетермінала, використовується також поняття виводимості з довільної послідовності терміналів і нетерміналів незалежно від того, чи виводиться сама ця послідовність із S, чи ні. Так, із присудок у прикладі 10.1 виводяться Дзижчить і Тупотить, незважаючи на те, що сам по собі присудок із початкового нетермінала не виводиться.

Будемо вважати також, що будьяка з альтернатив метавиразу виводиться з нього. Наприклад, із метавиразу

група підмета::= означення підмет | підмет

Виводяться і означення підмет, і підмет.

Приклад 2. Розглянемо оператори присвоювання змінним, іменами яких можуть бути лише x, y, z, а вирази у правій частині можуть бути або сталими 1 і 2, або іменами x, y, z, або сумою чи різницею цих сталих і змінних. Головним тут, очевидно, є поняття оператор присвоювання:

оператор присвоювання::= ім'я ':=' вираз

Вираз складається зі сталих і імен. Узагальнимо їх поняттям первинне, і запишемо БНФ виразів і первинних:

вираз::= первинне | первинне '+' первинне |

первинне '' первинне

первинне::= стала | ім'я

БНФ сталих і імен очевидні:

стала::= '1' | '2'

ім'я::= 'x' | 'y' | 'z'

Записана сукупність БНФ задає синтаксис операторів присвоювання, а також виразів, сталих і імен. Крім того, задано множини конкретних імен, сталих, виразів і операторів присвоювання.

Підіб'ємо підсумок. БНФ – це вираз у алфавіті, що складається з терміналів, нетерміналів і спеціальних метасимволів. БНФ мають цілком визначений синтаксис нетермінал, потім знак '::=' і метавираз. Їхньою семантикою є задання структури і множин представників понять, позначених нетерміналами. Таким чином, ми маємо Мову БНФ. Вона призначена для описання інших мов і називається Метамовою.

Існують різні метамови; деякі з них задаються строго й точно засобами логіки і математики і тому називаються Формальними. Мова БНФ, описана тут неформально, насправді є окремим випадком формальної метамови – Мови Формальних Граматик.

Мова БНФ була створена спеціально для описання синтаксису виразів мов програмування. З цією метою її використовуємо й ми.

3. Розширені БНФ

Доповнимо мову БНФ кількома зручними конструкціями. Тут нам знадобиться ще одне поняття – еквівалентність БНФ. Дві сукупності БНФ називаються Еквівалентними, якщо задають ту саму формальну мову.

Для запису еквівалентних БНФ у більш короткому і наочному вигляді алфавіт метасимволів розширюється символами,, [, ], {, }. Метавирази з такими символами називаються Розширеними, а БНФ – Розширеними БНФ, або скорочено РБНФ. Розглянемо побудову РБНФ.

Нехай букви X, Y, Z, , T позначають довільні метавирази можливо, порожні, N – нетермінал.

Заміною кількох правил вигляду

N::= X Z Y

N::= X T Y

У деякій сукупності БНФ на правило вигляду

N::= X Z | | T Y

Утворюється сукупність БНФ, еквівалентна початковій. Метасимволи та тут просто відокремлюють частину метавиразу з альтернативами Z, , T від інших частин. Наприклад, правила

вираз::= первинне '+' первинне |

первинне '' первинне

Можна замінити на правило

вираз::= первинне '+' | '' первинне

Заміною двох правил вигляду

N::= X Z Y

N::= X Y

На правило N::= X [ Z ] Y також утворюється еквівалентна БНФ. Наприклад, замість правил

вираз::= первинне | первинне '+'| '' первинне

Можна вжити правило

вираз::= первинне [ '+'| '' первинне ]

Або замість правил

операторирозгалуження::=

If умова Then оператор Else оператор |

If умова Then оператор

– правило

операторирозгалуження::=

If умова Then оператор [ Else оператор ]

Іноді буває зручно позбутися якогось поняття, замінивши його нетермінал відповідним метавиразом, наприклад, замість нетермінала первинне з прикладу 10.2 записати метавиразом стала | ім'я або навіть '1' | '2' | 'x' | 'y' | 'z'. Таким чином, сукупність БНФ із прикладу 10.2 еквівалентна сукупності

оператор присвоювання::=

ім'я ':=' '1' | '2' | ім'я [ '+'| '' '1' | '2' | ім'я ]

ім'я::= 'x' | 'y' | 'z'

Зміст метасимволів {, } означимо за допомогою такого прикладу.

Приклад 3. Ім'я, або ідентифікатор, у мовах програмування – це послідовність букв і цифр, що починається з букви. Нехай буквами є лише A, B, C, цифрами – 0 і 1. Ідентифікаторами в цьому алфавіті є, наприклад, A, B1, BC, C1CAAB0 тощо. Означимо сукупність БНФ, що задає їх синтаксис.

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

Ід::= БПБЦ

Б::= 'A' | 'B' | 'C'

Ц::= '0' | '1'

ПБЦ::= | Б | Ц ПБЦ.

Узагальнимо букви й цифри поняттям символ, додавши правило символ::= Б | Ц. Тоді ПБЦ можна задати двома правилами:

ПБЦ::= | символ ПБЦ.

За допомогою цих правил із нетермінала ПБЦ виводяться всі можливі послідовності символів:

, символ, символсимвол, ,

І тільки вони. Позначимо множину послідовностей, складених із символ, метавиразом {символ} із новими метасимволами {, }. Вважатимемо, що всі послідовності символів вивідні з цього метавиразу. Отже, правило

ПБЦ::= {символ}

За нашим означенням є еквівалентним правилам

ПБЦ::= | символ ПБЦ.

Взагалі, якщо X – довільний метавираз, то Метавираз {X} позначає всі послідовності у тому числі порожню виразів, вивідних із X.

Дужки {} називаються Ітераційними. З їх використанням поняття ідентифікатора з останнього прикладу можна задати так:

Ід::=Б { Б | Ц }

Б::= 'A' | 'B' | 'C'

Ц::= '0' | '1'

Або навіть так:

Ід::= 'A' | 'B' | 'C' { 'A' | 'B' | 'C' | '0' | '1' }.

Приклад 4. У мовах програмування широко використовується поняття список імен, розділених комами. Структуру таких списків можна задати РБНФ

список імен::= ім'я{','ім'я}.

Означення змінних у Паскальпрограмі складається з довільного числа списків змінних, за якими після двокрапки записано ім'я типу та ';'. Списків з іменами типів може взагалі не бути. Будьякому зі списків може передувати слово Var перед першим воно обов'язкове. Це слово відокремлюється від імені хоча б одним пропуском. Якщо обмежитися типами integer та real, то синтаксис означення змінних можна задати РБНФ

означення змінних::= [ 'var 'список імен ':' ім'я типу ';'

{ [ 'var ']список імен':'ім'я типу';' }

]

ім'я типу::= 'integer' | 'boolean'

Оператори мови Паскаль, на відміну від означень, не закінчуються роздільником ';', і синтаксис непорожньої послідовності операторів задається РБНФ

послід. операторів::= оператор {';' оператор}

Приклад 5. Розглянемо вирази з цілими сталими, в яких можуть бути виклики одномісної функції odd. Виразом є ціла стала, а також:

1. вираз у дужках,

2. два вирази й знак бінарної операції між ними,

3. вираз із знаком унарної операції на початку,

4. виклик функції odd із виразом у дужках.

Ці неформальні, але однозначні правила легко перекладаються на мову БНФ. Нехай E позначає вираз англійське Expression, C – сталу Constant, BinOp – знак бінарної двомісної операції Binary Operation Sign, UnOp – знак унарної одномісної операції Unary Operation Sign, FN – ім'я функції Function Name. Тоді

E::= C | ''E'' | EBinOpE | UnOpE

| FN''E''

C::= Ц{Ц}

уточнення інших нетерміналів залишається читачеві, див. підр. 2.2.

4. Синтаксичні діаграми

Мова форм БекусаНаура – не єдина метамова для описання структури конструкцій мов програмування. Досить поширеною є також метамова Синтаксичних діаграм.

В основі цієї метамови також лежать нетермінальні й термінальні символи. Але тут вони записуються у прямокутниках та колах овалах відповідно. Наприклад, нетермінали A та оператор позначаються так:

Відповідно термінальні символи '' та Else мають вигляд

Порядок символів у метавиразах задається стрілками, наприклад:

Альтернативні метавирази задаються розгалуженням стрілок. Наприклад, якщо E1, E2 – метавирази, то E1 | E2 має такий вигляд:

Можливість присутності або відсутності якоїсь частини виразу задається аналогічно, тільки одна з альтернатив порожня. Наприклад, структура операторів розгалуження задається так:

Фігурним дужкам { E}, які задають повторення, відповідає повернення стрілки на початок діаграми, відповідної E. Наприклад, структура непорожньої послідовності операторів задається метавиразом

оператор { ';' оператор},

Якому відповідає діаграма

Нарешті, поняття, вказане у БНФ ліворуч від знака::= нетерміналом, наприклад, A, записується також ліворуч від діаграми: