Паскаль: мова та метамова

Паскаль: мова та метамова

ПАСКАЛЬ: МОВА ТА МЕТАМОВА.

Дитина вчиться розмовляти до того, як вивчить формальні правила граматики, але правила вчасні, коли вона досягає повноліття.

Д.Кнут.

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

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

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

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

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

Правила, за якими виразам мови зіставляється зміст, утворюють семантичну систему мови. Розуміти мову — значить уміти зіставити виразу його зміст. Можна сказати, що комп" ютер «розуміє» мову Паскаль за допомогою «перекладача» — програми-транслятора (утім, translator і є англійське «перекладач»).

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

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

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

У кожній мові є своя система понять. Наприклад, будь-який конкретний оператор є представником загального поняття «оператор», будь-яке ім" я — представником поняття «ім» я" тощо. Представники понять, тобто конкретні оператори або імена — це вирази деякої структури (синтаксису). Наприклад, усі імена — це послідовності букв і цифр, що починаються з букви, цілі сталі - послідовності цифр, а кожний оператор присвоювання складається з імені, знака «:=» і виразу. Остання фраза по суті містить три правила: вони описують синтаксис представників понять «ім» я", «стала», «оператор присвоювання» і називаються синтаксичними.

Дамо синтаксичним правилам чіткішу форму. Позначимо поняття словами в <�кутових дужках>. Це позначення розглядається як неподільне і називається нетермінальним символом, або нетерміналом, наприклад, <�оператор> або <�ім" я>. Символи й лексеми мови будемо брати в «апострофи» або виділяти жирним шрифтом, наприклад, program або «:=». Вони також розглядаються як неподільні і називаються термінальними символами, або терміналами.

Відзначимо, що «термінальний» означає «остаточний», тобто термінали — це і є «остаточні» символи мови. «Нетермінальний», тобто «неостаточний», символ не є символом мови. Він є позначенням представників якогось поняття, а їх структура повинна бути описана синтаксичними правилами. Наприклад, вигляд терміналів «+», «:=» або program зафіксовано в мові Паскаль, а структуру представників понять <�оператор присвоювання> або <�ім" я> треба описати.

Послідовність, складена з терміналів і нетерміналів, називається метавиразом, наприклад, <�ім" я> «:=» <�вираз>. Елементи метавиразу, тобто нермінальні й нетермінальні символи, для наочності іноді будемо відокремлювати пропусками. Порожню послідовність позначимо кутовими дужками <>.

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

<�оператор присвоювання> має структуру <�ім" я> «:=» <�вираз>.

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

<�оператор присвоювання> := <�ім" я> «:=» <�вираз>.

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

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

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

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

Синтаксичні правила, записані у вигляді <�поняття> := <�метавираз>, називаються формами Бекуса-Наура, за прізвищами тих, хто їх придумав. Форми Бекуса-Наура скорочено називаються БНФ. Поняття, записане в БНФ ліворуч від «:=», називається її лівою частиною, а метавираз праворуч — правою. Знак «:=» не є символом мови й називається метасимволом.

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

<�оператор присвоювання> := <�ім" я> «:=» <�вираз>

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

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

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

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

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

Приклад 1. Розглянемо мову, виразами в якій є речення, що складаються з підмета й присудка. Підмет, крім того, може мати означення (а може і не мати). Цим означенням може бути одне зі слів — злющий або великий, підметом — комар або слон, присудком — дзижчить або тупотить. Побудуємо сукупність БНФ, що задають синтаксис речень.

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

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

<�означення> := великий | злющий.

<�підмет> := комар | слон.

<�присудок> := дзижчить | тупотить.

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

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

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

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

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

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

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

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

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

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

<�означення> <�підмет> тупотить,.

злющий <�підмет> тупотить,.

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

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

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

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

У прикладі 10.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. Виразом є ціла стала, а також:

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

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

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

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

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

:= | «(««)» | |.

| «(««)» .

:= <�Ц>{<�Ц>}.

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

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

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

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

Відповідно термінальні символи «(«та else мають вигляд.

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

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

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

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

<�оператор> { «,» <�оператор>},.

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

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

.