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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 записати метавиразом | Означення змінних у Паскаль-програмі складається з довільного числа списків змінних, за якими після двокрапки записано ім'я типу та ';'. Списків з іменами типів може взагалі не бути. Будь-якому зі списків може передувати слово var (перед першим воно обов'язкове). Це слово відокремлюється від імені хоча б одним пропуском. Якщо обмежитися типами integer та real, то синтаксис означення змінних можна задати РБНФ

::= [ 'var ' ':'

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать