Засоби подання правил граматики

Для опису правил граматики (формалізації синтаксису інших мов) використовуються так звані метамови (“надмови”).

Основними метамовами (формами представлення) для опису КВ-граматик є

- нотація Бекуса–Наура (БНФ),

- розширені БНФ (РБНФ),

- синтаксичні діаграми Вірта.

Нотація Бекуса–Наура. Є найбільш уживаною натепер метамовою для опису синтаксису мов програмування. Ідея цієї метамови полягає в структуруванні понять вихідної мови програмування і визначення більш складних понять через більш прості.

Термінальний словник даної метамови містить чотири символи (метасимволи):

< – відкриваюча кутова дужка

> – закриваюча кутова дужка

| – знак альтернативи (союз “або”)

::= – “ дорівнює за визначенням” або “тобто”

Правила граматики в даній метамові (БНФ-конструкція) задаються у вигляді метаформул, дуже схожих на математичні вирази:

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

Лівою частиною такого виразу є нетермінальний символ, що визначається. У правій частині міститься комбінація символів термінального і нетермінального словників тієї мови, для якої визначається правило граматики.

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

У метамові БНФ прийняті певні угоди. Зокрема, побудова БНФ-конструкцій відповідає наступним правилам:

• Конкатенація. Запис

<метавираз1>::= <метавираз2> <метавираз3> …

означає, що <метавираз1> являє собою послідовний запис (конкатенацію) інших понять.

• Вибір. Запис

<метавираз1>::= <метавираз2> | <метавираз3> | …

означає вибір, а саме, що <метавираз1> збігається з одним із інших понять.

Для прикладу розглянемо правило, яке визначає БНФ-конструкцію < ідентифікатор >:

<ідентифікатор>::= <літера> | <ідентифікатор> <літера> |<ідентифікатор> <цифра>

<літера>::= А|В|С|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z| a|b|c|d| e|f| g|

h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z.

<цифра>::= 0|1|2|3|4|5|6|7|8|9.

Правила можна задавати і нарізно, наприклад,

<ідентифікатор>::= <літера>.

<ідентифікатор>::= <ідентифікатор> <літера>.

<ідентифікатор>::= <ідентифікатор> <цифра>.

Важливою властивістю БНФ є те, що за допомогою цієї форми можна задавати рекурсивні визначення. У даному прикладі конструкція < ідентифікатор > в альтернативних визначеннях задається за допомогою самої себе і таким чином дозволяє класифікувати як ідентифікатор ланцюжок довільної довжини, що складається з літер і цифр, але починається обов'язково з літери.

У наступному прикладі (конструкція <рядок>) також використовується рекурсивне визначення:

<рядок>::= '<послідовність символів>'.

<послідовність символів>::= <символ>ú <послідовність символів> <символ>.

<символ>:: = <основний символ> ú.

Відповідно до зазначених БНФ-конструкцій, рядок являє собою послідовність символів, укладену в одинарні лапки (апострофи). Особливістю останнього правила є розташований в його кінці знак "або" (|). Це означає, що в даній конструкції допустима відсутність будь-яких символів взагалі. Так формалізується визначення порожнього рядка [2].

Розглянуті вище в прикладах нетермінальні конструкції мов програмування по суті є лексемами, до яких, зазвичай, відносять спеціальні символи, ідентифікатори, рядки, тощо.

Розширені БНФ. Нотація БНФ дозволяє описувати будь-який синтаксис мови, однак її застосування є достатньо ємним. Зокрема, в БНФ відсутня конструкція повторення. Це приводить до того, що будь-яке повторення доводиться визначати шляхом введення додаткових проміжних нетерміналів і рекурсивних правил, через що визначення стає надмірно великим за об'ємом і малозрозумілим.

РБНФ відрізняється від БНФ наявністю більш «ємних» конструкцій, які дозволяють при тій же виразності спростити і скоротити обсяг опису, а саме:

• Умовне входження (" [ " і " ] "). Синтаксична конструкція, укладена в квадратні дужки "[" і "]", може бути відсутньою. Так правило виду A = [B] означає, що нетермінал A або є порожнім, або складається з нетермінала B.
• Повторення (" { " і " } " або " {/ " і " /} "). Частина визначення, укладена у фігурні дужки "{" і "}", може бути повторена довільне число раз (у тому числі жодного разу). Поєднання фігурних дужок і косої риски "{/" і "/}" використовується для позначення повторення один і більше разів. Наприклад, правило вигляду A = {B} означає, що нетермінал A — або порожній, або є конкатенацією будь-якого числа нетерміналів B (B, BB, BBB і т.ін.). Якщо потрібно, щоб нетермінал A був або B, або довільне число B, але не міг бути порожнім, використовується запис виду A = B{B}.

§ Групування (" ( " і " ) "). Круглі дужки "(" і ")" використовуються обмеження альтернативних конструкцій шляхом групування складних БНФ-конструкцій усередині простих. Наприклад, правило A = (B|C)(D|E) означає, що нетермінал A складається з двох нетерміналів, першим з яких є або B, або C; другим - або D, або E. Тобто A може бути одним із ланцюжків BD, BE, CD, CE.

Окрім того, у РБНФ спрощений синтаксис запису правил: символ визначення «::=» замінений на «=» і скасовано використання кутових дужок для виділення нетерміналів. В результаті зникла можливість називати нетермінали багатослівними ідентифікаторами, зате запис став коротшим.

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

Наприклад, поняття < ідентифікатор > може бути представлене наступним чином:

ідентифікатор = літера {літера | цифра}.

літера = "A"|"B"|"C"|"D"|"E"|"F"|"G"|"H"|"I"|"J"|"K"|"L"|"M"|"N"|"O"|"P"|"Q"|"R"|

"S"|"T"|"U"|"V"|"W"|"X"|"Y"|"Z"|"a"|"b"|"c"|"d"|"e"|"f"|"g"|"h"|"i"|"j"|"k"|

"l"|"m"|"n"|"O"|"p"|"q"|"r"|"s"|"t"|"u"|"v"|"w"|"x"|"y"|"z".

цифра = "0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9".

Існують різні розширені форми БНФ-нотації, які незначно відрізняються одна від одної. Їх різноманітність найчастіше пояснюється бажанням розробників мов програмування по-своєму описати створювану мову. Прикладами таких широко відомих метамов можна віднести: метамову PL / I, метамову Вірта, яка використовується при описі Модуль-2, метамову Керніган-Рітчі, що описує Сі.

Головна перевага РБНФ перед БНФ — можливість описувати прості повторювані конструкції невизначеної довжини (списки, рядки, послідовності і т.ін.) без рекурсивних правил. Опис повторень в РБНФ виявляється одночасно і коротше, і зручніше для сприйняття людиною. Але платою за переваги РБНФ перед БНФ є більша складність автоматичної інтерпретації РБНФ-описів.

Синтаксичні діаграми Вірта. Окрім текстових способів опису синтаксису мов широко використовуються і графічні метамови, серед яких найбільшу популярність здобула мова діаграм Вірта, вперше застосована для опису мови Паскаль.

Метасимволи у цій мові замінені графічними позначеннями:

- термінал

, - нетермінал

- з’єднувальні лінії, що забезпечують зв’язок між термінальними і нетермінальними символами

- вхідна дуга з назвою поняття

 

Кожен графічний елемент, що відповідає терміналу або нетерміналу, має по одному входу і виходу, які, зазвичай, малюються на протилежних сторонах.

Кожному правилу відповідає своя синтаксична діаграма, окремим елементом якої може бути символ алфавіту (термінал) або поняття мови (нетермінал), з'єднані за допомогою дуг, що вказують порядок слідування елементів. Альтернативи в правилах задаються розгалуженням дуг (аналог метасимвола “|” в БНФ), а ітерації - їх злиттям. Якщо є зациклена лінія (петля), що торкається основної лінії, то це аналог рекурсивної частини виразу БНФ; якщо є кілька петель (поряд або одна над іншою), то їх аналоги в БНФ будуть розділяться метасимволом “|”. Повинна бути одна вхідна дуга (розміщується, зазвичай, ліворуч і зверху), що задає початок правила і позначається ім'ям поняття, що визначається, і одна вихідна, що задає його кінець (зазвичай, розміщується праворуч і знизу).

Приклад опису ідентифікатора з використанням діаграм Вірта представлений на рис 1.

 

Рис. 1. Приклади діаграм Вірта

Зазвичай, стрілки на дугах діаграм не ставляться, а напрями зв'язків відслідковуються рухом від початкової дуги відповідно до плавних вигинів проміжних дуг і розгалужень. Таким же чином визначаються входи і виходи терміналів і нетерміналів. Спеціальних стандартів на діаграми Вірта немає, тому графічні позначення можуть змінюватися залежно від засобів малювання. Можна, наприклад, використовувати псевдографіку або просто текстові символи, зв'язки зі стрілками. Однак такий вид правил менш зручний для сприйняття і тому застосовується вкрай рідко.

Діаграми Вірта дозволяють задавати альтернативи, рекурсії, ітерації і по виразності еквівалентні РБНФ. Але графічне відображення правил більш наочно. Крім цього допускається довільне проведення дуг, що зменшує кількість елементів в правилі за рахунок його неструктурованості.