Мова та метамова
СОДЕРЖАНИЕ: Реферат на тему: Мова та метамова 1. Мова: вирази та їх семантика У попередніх розділах було описано означення, вирази й оператори мови Паскаль. Очевидно, всі вони мають визначену структуру, абоРеферат на тему:
Мова та метамова
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 , записується також ліворуч від діаграми: