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

Реферат на тему:

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

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

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

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

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

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

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

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

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

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

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

Дамо синтаксичним правилам чіткішу форму. Позначимо поняття словами в <кутових дужках>. Це позначення розглядається як неподільне і називається нетермінальнимсимволом, або нетермінал$ом, наприклад, <оператор> або <ім’я>. Символи й лексеми мови будемо брати в ‘апострофи’ або виділяти жирним шрифтом, наприклад, program або ‘:=’. Вони також розглядаються як неподільні і називаються термінальнимисимволами, або терміналами.

Відзначимо, що «термінальний» означає «остаточний», тобто термінали – це і є$ «остаточні» символи мови. «Нетермінальний», тобто «неостаточний», символ не є символом мови. Він є позначенням представників якогось поняття, а їх структура п$овинна бути описана синтаксичними правилами. Наприклад, вигляд терміналів ‘+’, ‘:=’ або program зафіксовано в мові Паскаль, а структуру представників понять <оператор присвоювання> або <ім’я> треба описати.

Послідовність, складена з терміналів і нетерміналів, називається метавиразом$, наприклад, <ім’я> ‘:=’ <вираз>. Елементи метавиразу, тобто нермінальні й нетермінальні символи, для наочності іноді будемо відокремлювати пропусками. Порожню послідовність позначимо кутовими дужками <>.

Перепишемо фразу «оператор присвоювання складається з імені, знака «:=» і виразу» із новими позначеннями так:

<оператор присвоювання> маєструктуру <ім’я> ‘:=’ <вираз>.

Замість слів «має структуру» поставимо знак «::=» і одержимо щось схоже на формулу:

&l$t;оператор присвоювання> ::= <ім’я> ‘:=’ <вираз>.

Взагалі, усяку фразу вигляду

<поняття> має структуру <метавираз>

можна переписати в такому вигляді:

<поняття> ::= <метавираз>.

Синтаксичні правила, записані у вигляді <понят$тя> ::= <метавираз>, називаються формамиБекуса-Наура, за прізвищами тих, хто їх придумав. Форми Бекуса-Наура скорочено називаються БНФ. Поняття, записане в БНФ ліворуч від «::=», називається її лівоючастиною,$ а метавираз праворуч – правою. Знак «::=» не є символом мови й називається метасимволом.

Сама по собі БНФ

<оператор присвоювання> ::= <ім’я> ‘:=’ <вираз>

задає лише загаль$ну структуру кожного з представників поняття «оператор присвоювання», але не їх конкретний вигляд. Для цього треба описати структуру представників понять <ім’я> і <вираз>. Пригадаємо: «ім’я – це послідовність букв і цифр, що починається з букви». У цій фразі виникають одразу два нові понятт$я – <буква> і <послідовність букв і цифр>. Перепишемо її у вигляді БНФ

<ім’я>::=<буква><послідовність букв і цифр>.

На цьому поки що зупинимося. Очевидно, для описання синтаксису останніх двох понять потрібні будуть свої БНФ, можливо, з новими поняттями. У всякому разі, зараз ми припустимо, що

синтаксис виразів мови задається деякою сукупністю БНФ, або синтаксичних правил.

А тепер почнемо уточнювати, яким саме чином суку$пність БНФ задає синтаксис виразів мови.

Приклад 1. Розглянемо мову, виразами$ в якій є речення, що складаються з підмета й присудка. Підмет, крім того, може мати означення (а може і не мати). Цим означенням може бути одне зі слів – злющий або великий, підметом – комар або слон, присудком – дзижчить або тупотить. Побудуємо сукупність БНФ, що задають синтаксис речень.

Спочатку введемо додаткові позначення. Якщо структура представників якогось поняття задається кількома БНФ, то об’єднаємо їх, записавши альтернативні праві частини в однім правилі$ й відокремивши символом «|». Цей символ позначає слово «або»; він також є метасимволом.

З цими позначеннями очевидні такі БНФ:

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

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

<присудок> ::= дзижчить | тупотить

Підмет у реченні може бути як із означенням, так і без нього. Введемо поняття &$lt;група підмета> і БНФ

<група підмета> ::= <означення> <підмет> | <підмет>

Тоді струк$тура речення задається такою БНФ:

<речення> ::= <група підмета> <присудок>-

Серед понять мови виділяється головне; воно позначається спеціальним початковимнетерміналом. Очевидно, що в нашій мові, наприклад, головним поняттям є речення, а в мові Паскаль – програма.

Означимо тепер такі поняття, як послідовністьтер$міналів, вивідназпочатковогонетермінала, і формальнамова, задана сукупністю БНФ.

$

Якщо замінити початковий нетермінал (позначимо його 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 <умова&g$t; 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, B$C, C1CAAB0 тощо. Означимо сукупність БНФ, що задає їх синтаксис.

Розглядаючи понятт$я «ідентифікатор», можна ввести поняття «послідовність букв і цифр, можливо, порожня». Позначимо ці два поняття відповідно нетерміналами <Ід> і <ПБЦ>. Введемо також поняття «буква» й «цифра» (нетермінали <Б> і <Ц>). Послідовність букв і цифр або порожня, або починається буквою або цифрою, за якою записано послідовність $букв і цифр. Іншими словами,

<Ід> ::= <Б><ПБЦ>

<Б> ::= ‘A’ | ‘B’ | ‘C’

<Ц> ::= ‘0’ | ‘1’

<ПБЦ> ::= <> | (<Б> | <Ц>) <ПБЦ>.

Узагальнимо букви й цифри поняттям «символ», додавши правило <символ> ::= <Б> | <Ц>. Тоді <ПБЦ> можна задати двома правилами:

<ПБЦ> ::= <&gt$; | <символ> <ПБЦ>.

За допомогою цих правил із нетермінала <ПБЦ> виводяться всі можливі послідовності символів:

<>, <символ>, <символ><символ>, … ,

і тільки вони. Позначимо множину послідовностей, складених із <символ>, метавиразом {<символ>} із новими метасимволами «{«, «}». Вважатимемо, що всі послідовності символ$ів вивідні з цього метавиразу. Отже, правило

<ПБЦ> ::= {<символ>}

за нашим означенням є еквівалентним правилам

<ПБЦ> ::= &lt$;> | <символ> <ПБЦ>. —

Взагалі, якщо X – довільний метавираз, то метавираз {X} позначає всі послідовності (у тому числі порожню) виразів, вивідних із X.

Дужки {} називаються ітераційними. З їх використанням поняття ідентифікатора з останнього прикладу можна задати так:

<Ід> ::=<Б> { <Б> | <Ц> }

<Б> ::= ‘A’ | ‘B’ | ‘C’

<Ц> ::= ‘0’ | ‘1’

або навіть так:

<Ід&gt$; ::=( ‘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>’)’ | <E><BinOp><E> | <UnOp><E>

| <FN>'(‘<E>’)’

<C> ::= <Ц>{<Ц>}

(уточнення інших нетерміналів залишається читачеві, див. підр. 2.2 ). —

4. Синтаксичні діаграми

Мова форм Бекуса-Наура – не єдина метамова для описання структури конструкцій мов програмування. Досить поширеною є також метамова синтаксичних діаграм.

В основі цієї мет$амови також лежать нетермінальні й термінальні символи. Але тут вони записуються у прямокутниках та колах (овалах) відповідно. Наприклад, нетермінали <A> та <оператор> позначаються так:

Відповідно термінальні символи ‘(‘ та else мають вигляд

Порядок символів у метавиразах задається стрілками, наприклад:

Альтернативні ме$тавирази задаються розгалуженням стрілок. Наприклад, якщо E1, E2 – метавирази, то E1 | E2 має такий вигляд:

Можливість присутності або відсутності$ якоїсь частини виразу задається аналогічно, тільки одна з альтернатив порожня. Наприклад, структура операторів розгалуження задається так:

Фігурним дужкам {E}, які $задають повторення, відповідає повернення стрілки на початок діаграми, відповідної E. Наприклад, структура непорожньої послідовності операторів задається метавиразом

<оператор> { ‘;’ <оператор>},

якому відповідає діаграма

Нарешті, поняття, вказане у БНФ ліворуч від знака «::=» нетерміналом, наприклад, A, записується також ліворуч від діаграми:

Post Comment