Визначення формальної мови і граматики

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

Формальну мову можна задати як послідовність слів. Слово – це послідовність символів. Тоді навіть програму можна вважати просто словом.

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

Термінальні – це символи, які використовуються в мові, а проміжні або нетермінальні – це символи, які використовуються для створення слів мови. Створюються слова за граматичними правилами. Застосування правила полягає в заміні в перетворюваному рядку якоїсь послідовності символів, що співпадає з лівою або правою частиною правила.

Компілятор, отримавши на вхід програму, робить зворотну роботу. Він згортає за граматичними правилами від правої до лівої частини початкові символи.

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

Якщо задано алфавіт А, то А^* - це множина всіх ланцюжків, які можна побудувати з алфавіту А. $ - порожній рядок (рядок, що не містить жодної букви) також входить в А. Для позначення всіх ланцюжків алфавіту А, що не містять порожнього використовується А⁺.

Формальною граматикою Г називається сукупність таких об’єктів:

 

Г={V_T,V_N,<I>,R},

 

Де V_T – термінальний алфавіт (словник). З букв цього алфавіту будуються ланцюжки, які породжуються граматикою.

V_N – нетермінальний (допоміжний) алфавіт. Його букви використовуються при побудові ланцюжків, вони можуть входити в проміжні ланцюжки, але не можуть входити в результат побудови.

<I> - початковий символ.

R – множина правил виведення.

Множина кінцевих ланцюжків термінального алфавіту V_T граматики Г, виведених з початкового символу <I> називають мовою, яка породжена граматикою Г і позначається L(Г).

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

Типи формальних граматик

Виділяють 4 типи формальних граматик. Ці граматики визначаються шляхом накладання обмежень на правила граматики.

Граматика типу 0 – граматика загального вигляду, немає обмежень на правила породження.

Граматика типу 1 – контекстно залежна.

Правило: χ₁<A>χ₂→ χ₁ωχ₂.

Ланцюжки χ₁ і χ₂ залишаються незмінними при застосуванні правил, тому їх називають контекстом, а граматику – контекстно залежною.

Граматика типу 2 – контекстно вільна.

Правило: <A>→α, де .

Ці правила слідують із правил граматики типу 1 за умови χ₁ = χ₂ = $.

Граматика типу 3 – автоматна.

Правила виведення: <A>→a або <A>→a<B> або <A>→<B>a, де

 

.

 

Способи задання схем граматик

Схема граматики містить правила виведення, які визначають синтаксис мови або всі ланцюжки породженої мови. Для задання правил використовують різні форми опису:

символічна

форма Бекуса-Наура (ФБН)

ітераційна

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

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