WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Мова та метамова - Реферат

Мова та метамова - Реферат

нетерміналів незалежно від того, чи виводиться сама ця послідовність із 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 із виразом у дужках.
Ці неформальні, але однозначні правила легко перекладаються на мову БНФ. Нехай позначає вираз (англійське Expression), - сталу (Constant), - знак бінарної (двомісної) операції (Binary Operation Sign), - знак унарної (одномісної) операції (Unary Operation Sign), - ім'я функції (Function Name). Тоді
::= | '('')' | |
| '('')'
::= {}
(уточнення інших нетерміналів залишається читачеві, див. підр. 2.2 ). Р
4. Синтаксичні діаграми
Мова форм Бекуса-Наура - не єдина метамова для описання структури конструкцій мов програмування. Досить поширеною є також метамова синтаксичних діаграм.
В основі цієї метамови також лежать нетермінальні й термінальні символи. Але тут вони записуються у прямокутниках та колах (овалах) відповідно. Наприклад, нетермінали та позначаються так:
Відповідно термінальні символи '(' та else мають вигляд
Порядок символів у метавиразах задається стрілками, наприклад:
Альтернативні метавирази задаються розгалуженням стрілок. Наприклад, якщо E1, E2 - метавирази, то E1 | E2 має такий вигляд:
Можливість присутності або відсутності якоїсь частини виразу задається аналогічно, тільки одна з альтернатив порожня. Наприклад, структура операторів розгалуження задається так:
Фігурним дужкам {E}, які задають повторення, відповідає повернення стрілки на початок діаграми, відповідної E. Наприклад, структура непорожньої послідовності операторів задається метавиразом
{ ';' },
якому відповідає діаграма
Нарешті, поняття, вказане у БНФ ліворуч від знака "::=" нетерміналом, наприклад, A, записується також ліворуч від діаграми:
Loading...

 
 

Цікаве