Реферат на тему:
Мова та метамова
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, або сумою чи різницею цих сталих і змінних. Головним тут, очевидно, є поняття <оператор присвоювання>: