Класифікація формальних граматик та мов

Для віднесення граматики до того або іншого типу необхідна відповідність всіх її правил (продукцій) деяким схемам. Згідно Хомського, формальні граматики поділяються на чотири типи:

§ Тип 0 — необмежені. Вони не мають обмежень на вид правил. У цьому випадку для граматики G = (T, N, P, S), V=TÈN всі правила мають вид:

,

де α — будь-яка послідовність символів, що містить хоча б один нетермінал, а β — будь-яка послідовність символів алфавіту.

Практичного застосування в силу своєї складності такі граматики не мають.

§ Тип 1 — контекстно-залежні (КЗ). Правила підстановок, що застосовуються до послідовності символів, залежать від їх контексту. Тобто, для граматики G = (T, N, P, S), V=TÈN всі правила мають вид:

αAβ→αγβ, де α, βÎV^*, γÎV⁺, AÎN.

Послідовності символів α і β є контекстом правила. Символ A замінюється рядком γ, якщо знаходиться в контексті α, β.

§ Тип 2 — контекстно-вільні (КВ). Правила підстановок застосовуються до послідовності символів (до окремих символів) незалежно від тих символів, які їх оточують (від контексту), і при виконанні підстановок цей контекст залишається без змін. У цьому випадку для граматики G = (T, N, P, S), V=TÈN всі правила мають вид:

A→β, де AÎN, βÎV+.

Така граматика допускає появу в лівій частині правила тільки нетерминального символа. При цьому β - непусте слово словника граматики.

§ Тип 3 — регулярні граматики (автоматні). Є контекстно-вільними, але з обмеженими можливостями. Це граматики, в яких правила мають вид

A→ γ або A→γB, де A, B ÎN, γÎV+.

Самі прості із формальних граматик. Застосовуються для опису найпростіших конструкцій: ідентифікаторів, констант, тощо.

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

В залежності від типу граматики, на основі якої генерується задана мова, формальні мови поділяють на відповідні категорії: від типу 0 до типу 3. Мови тим більш обмежені, чим глибше знаходяться в ієрархії Хомського.

Простіші мови, з одного боку, простіше піддаються комп'ютерній обробці, а з іншого — їм бракує виразності. Наприклад, для пошуку деяких шаблонів у тексті використовують регулярні вирази, які відповідають граматикам Хомського типу 3. Їхньої виразності досить, аби шукати різноманітні фрагменти тексту, але їх недостатньо, для, наприклад, описання мов програмування. Для цього використовують граматики типу 2 (КВ-граматику).

Загалом формальні мови будуються за наступною схемою:

• Спочатку вибирається алфавіт із символів якого будуть будуватися всі вирази мови. Символами алфавіту формальної мови можуть бути букви алфавітів природних мов, дужки, спеціальні знаки, тощо.
• Потім описується синтаксис мови, тобто правила побудови осмислених виразів. Для кожної формальної мови сукупність цих правил має бути строго визначена і модифікація будь-якого з них приводить найчастіше до появи нового різновиду (діалекту) цієї мови.

§ Далі з символів алфавіту, за описаними правилами, складаються слова і вирази. Осмислені вирази отримуються у формальній мові лише якщо дотримані всі визначені в ній правила продукції.

Для формальної мови характерна однозначність визначення її словника, чіткі правила побудови виразів і їх тлумачення, що забезпечує несуперечливе, точне і компактне відображення властивостей і відношень предметної області (об'єктів, що моделюються).

Важливість формальних граматик в інформатиці порівняна з важливістю арифметики в математиці, логіки у філософії і т.ін. На принципах формальної граматики проектуються і створюються нові мови програмування, пишуться програми для перевірки орфографії і стилю, програмуються "мовні" інтерфейси, створюються програми для корекції помилок і "оптимізації" виконання програм.

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