Сторінка
2

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

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

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

<присудок> ::= дзижчить | тупотить Підмет у реченні може бути як із означенням, так і без нього. Введемо поняття <група підмета> і БНФ <група підмета> ::= <означення> <підмет> | <підмет> Тоді структура речення задається такою БНФ: <речення> ::= <група підмета> <присудок> Серед понять мови виділяється головне; воно позначається спеціальним початковим нетерміналом. Очевидно, що в нашій мові, наприклад, головним поняттям є речення, а в мові Паскаль – програма. Означимо тепер такі поняття, як послідовність терміналів, вивідна з початкового нетермінала, і формальна мова, задана сукупністю БНФ. Якщо замінити початковий нетермінал (позначимо його 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 також утворюється еквівалентна БНФ. Наприклад, замість правил <вираз> ::= <первинне> | <первинне> ('+'| '-') <первинне> можна вжити правило <вираз> ::= <первинне> [ ('+'| '-') <первинне> ] або замість правил