.

Мова: вирази та їх семантика (реферат)

Язык: украинский
Формат: реферат
Тип документа: Word Doc
2 2386
Скачать документ

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

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

Д.Кнут

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, записується також ліворуч від діаграми:

Нашли опечатку? Выделите и нажмите CTRL+Enter

Похожие документы
Обсуждение

Оставить комментарий

avatar
  Подписаться  
Уведомление о
Заказать реферат!
UkrReferat.com. Всі права захищені. 2000-2020